Although the problem is pretty simple, it was a bit hard to understand what was asked.

for tc in range(int(input())):
    n, m = map(int, input().split())
    sl: list[int] = []
    for nc in range(n):
        sl.append(len(input()))
    ans: int = 0
    tmp: int = 0
    for length in sl:
        if tmp + length > m:
            break
        tmp += length
        ans += 1
    print(ans)

It seems there isn’t an editorial on the internet yet, so I’m not confident if my approach is optimal or does not have any corner cases.

First, to be able to make all the elements equal, the sum of all elements must be divisible by the number of elements.

Second, when we look at the leftmost (or the rightmost) element, it can be updated only from one direction. The same goes for i = 1 (0-index) or i = n - 2.

Now, i = 2 (0-index) must be updated from the right side not to break i = 0. Recursively (?), i = 4, 6, … must be updated from the right side to meet the condition.

In my approach, I make ends meet from the left side and see if all elements can be the average of the input.

def can_flatten(n: int, a: list[int]) -> bool:
    if sum(a) % n != 0:
        return False

    eq_val: int = sum(a) // n
    for i in range(n - 2):
        a[i + 2] += a[i] - eq_val

    return a[-1] == a[-2] == eq_val


for _ in range(int(input())):
    n: int = int(input())
    a: list[int] = list(map(int, input().split()))

    ans: bool = can_flatten(n, a)
    if ans:
        print("YES")
    else:
        print("NO")

2050C. Uninteresting Number - 1100

So, we cannot square a digit >= 4 because its square exceeds 10. On the other hand, a square of 1 is 1, so performing the operation on a digit with 1 has no effect.

2 ** 2 = 4 -> doubling a digit with 2 increases the sum of (digit mod 9) by 2 mod 9.

3 ** 2 = 9 -> doubling a digit with 3 increases the sum of (digit mod 9) by 6 mod 9.

Applying the operation to double 3 for two digits -> increase (6 + 6) mod 9 = 3 mod 9

Applying the operation to double 3 for three digits -> increase (6 * 3) mod 9 = 0 mod 9

Applying the operation to double 3 for four digits -> increase 6 mod 9 (same as performing only one operation on 3)

As we can see, it’s not meaningful to perform the operation on 3 more than four times since it just repeats the same result that appeared before. <=> The maximum number of the operations for 3 we need to consider is 3.

So, for digits with 2, the maximum number of the given operations that is meaningful and we must consider is 8.

def can_obtain(mod9, cnt2, cnt3) -> bool:
    cnt2 = min(cnt2, 8)
    cnt3 = min(cnt3, 2)

    for i in range(cnt2 + 1):
        sum2 = 2 * i
        for j in range(cnt3 + 1):
            sum3 = 6 * j
            if (mod9 + sum2 + sum3) % 9 == 0:
                return True
    return False


for _ in range(int(input())):
    n: str = input()
    mod9: int = 0
    cnt2: int = 0
    cnt3: int = 0
    for c in n:
        mod9 = (mod9 + int(c)) % 9
        if c == "3":
            cnt3 += 1
        if c == "2":
            cnt2 += 1

    ans: bool = can_obtain(mod9, cnt2, cnt3)
    if ans:
        print("YES")
    else:
        print("NO")

2050D. Digital string maximization - 1200

My approach still doesn’t quite make sense to me, but I’ll write it down for reference.

The i = 4 (0-index) element can be moved one index to the left with one decrement.

In the same way, the i = 4 element can be moved two indexes to the left with two decrement, by applying the operation mentioned above twice.

s[i] = max(
  [
    s[i], s[i + 1] - 1, s[i + 2], - 2, s[i + 3] - 3, s[i + 4] - 4,
    s[i + 5] - 5, s[i + 6] - 6, s[i + 7] - 7, s[i + 8] - 8,
    # s[i + 9] - 9 <= 0, so i + 9, i + 10, ... won't be the options
  ]
)

To make the lexicographically maximum string, we start from the leftmost index to the right, and pick the maximum value for each index.

for _ in range(int(input())):
    s: list[int] = list(map(int, list(input())))
    for i in range(len(s) - 1):
        max_i: int = i
        max_val: int = s[i]
        for j in range(1, 9):
            if i + j >= len(s):
                continue
            if s[i + j] - j > max_val:
                max_i = i + j
                max_val = s[i + j] - j
        for j in range(max_i, i, -1):
            s[j] = s[j - 1]
        s[i] = max_val

    print("".join([str(x) for x in s]))

Takeaways from Codeforces Round 991

What the solutions to the C problem and the D problem have in common is that they both rely on leveraging hidden (?) conditions to reduce time complexity. A naive brute-force implementation would have a time complexity of O(n^2). However, for the D problem, we only need to check eight adjacent elements for each position, which simplifies the time complexity to O(8n) = O(n). The same principle applies to the C problem.

This type of optimization comes up frequently. For instance, if we know the input consists only of lowercase alphabets, we can either prepare a fixed-length array as a counter or iterate over 26 loops. Both approaches maintain constant time complexity and avoid unnecessary overhead.

Taco Bell 30 g Egg Rice 20 g Gummies 0 g Protein shake 90 g Boba 0 g McDonald’s 20 g

20241207 ◎

2050A. Line Breaks - 800

2050B. Transfusion - 900

2050C. Uninteresting Number - 1100

2050D. Digital string maximization - 1200

Takeaways from Codeforces Round 991