Round #835/1760 (Div. 4)

Updated: 2023-03-23
2 min read


Contest date: 2022-11-21

A. Medium Number


def solve():
    ar = inpl()
    return ar[1]

def run():
    for _ in range(inpi()):

if __name__ == "__main__":
    CODE_DEBUG = 0
    if os.environ.get("CODE_DEBUG") or CODE_DEBUG:
        sys.stdin = open("./input.txt", "r")
        start_time = time.time()
        print("\n--- %s seconds ---\n" % (time.time() - start_time))

B. Atilla’s Favorite Problem

Minimum size of alphabet is the ordinal number of a letter in the string.

  1. Go through each letter and find the max letter’s code with built-in function [ord](


def solve():
    n = inp()
    s = inp()

    last_i = 0
    for i in s:
        last_i = max(last_i, ord(i) - 97 + 1) # for letter 'a' unicode code is 97

    return last_i

Explanation from Codeforces:

To solve the problem we need to find the character with the highest alphabetical order in our string, since Atilla will need at least that alphabet size and won’t need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $𝑂(𝑛)$.

C. Advantage

  1. Need to know the strongest participant.
  2. Compare current with strongest.
  3. If current participant is the strongest, then compare it with the second strongest.


  1. Find two strongest.
  2. Loop and calculate diff.
def solve():
    n = inp()
    ar = inpl()

    result = ar[:]

    strongest, strongest2 = ar[-1], ar[-1]
    if len(ar) > 1:
        strongest2 = ar[-2]
    for i, x in enumerate(result):
        if x == strongest:
            result[i] = x - strongest2
            result[i] = x - strongest

    return list_to_string_list(result)

Explanation from Codeforces:

Make a copy of the array 𝑠: call it 𝑡. Sort 𝑡 in non-decreasing order, so that 𝑡1 is the maximum strength and $𝑡_2$ — the second maximum strength.

Then for everyone but the best person, they should compare with the best person who has strength $𝑡_1$. So for all $𝑖$ such that $𝑠_𝑖 ≠ 𝑡_1$, we should output $𝑠_𝑖−𝑡_1$. Otherwise, output $𝑠_𝑖−𝑡_2$ — the second highest strength, which is the next best person.

D. Challenging Valleys


E. Binary Inversions


F. Quests

Slow Solution:

G. SlavicG’s Favorite Problem