1820

A_Yura_s_New_Name

Explanation

Yura wants to change his name to a string consisting of "" and "^" characters.

However, he wants every character to be part of at least one "^^" or "^^" smiley face, and these smiley faces should be consecutive in the name.

Task is to find the minimum number of characters to insert into the name to meet Yura's criteria.

Logic

Iterate through the input string and keep track of the number of '_' characters in between '^' characters.

Based on this count, determine how many characters need to be added to satisfy Yura's criteria.

def solve():
    s = input()
    res = 0

    if len(s) == 1:
        res = 1 if s[0] == "^" else 2
    else:
        if s[0] == "_":
            res += 1

        gap = 0
        for c in s:
            if c == "_":
                gap += 1
            else:
                res += max(0, gap - 1)
                gap = 0

        res += max(0, gap - 1)

        if s[-1] == "_":
            res += 1

    print(res)


for _ in range(int(input())):
    solve()

B_JoJo_s_Incredible_Adventures

Explanation

This problem involves a binary string, and with that string, you construct a square mesa (table). The first row of the mesa contains the original string.

The subsequent rows contain a cyclic shift of the string by one to the right.

Need to find the rectangle within this mesa that consists only of ones ('1') and has the largest area.

The challenge is to find this rectangle's maximum possible area. If there are no rectangles consisting of ones, the answer should be 0.

Logic

The logic to solve this problem revolves around finding the longest contiguous sequence of '1's in the input string (including its cyclic shifts) and using this sequence to calculate the maximum area.

This area is calculated as the product of the half-length of this sequence (rounded up and down respectively).

For edge cases where all characters are '1's, the maximum area would be the square of the length of the string.

import math


def solve():
    s = input()
    n = len(s)

    if "0" not in s:  # If string contains only '1's
        print(n * n)
        return

    s += s  # for cyclic shift handling
    max_group = 0
    curr_group = 0

    for c in s:
        if c == "1":
            curr_group += 1
            max_group = max(max_group, curr_group)
        else:
            curr_group = 0

    max_group += 1
    max_area = math.ceil(max_group / 2) * (max_group // 2)
    print(max_area)


for _ in range(int(input())):
    solve()

C_Constructive_Problem

Explanation

The key to solving this problem is understanding how the MEX is calculated and how the operation changes the array.

The MEX of the array is the smallest non-negative integer that doesn't exist in the array.

If we assign a certain non-negative integer value to all elements within a subsegment of the array, we are essentially adding more of that integer to the array.

This could potentially increase the MEX of the array by exactly one if we choose the right subsegment and the right integer value.

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    b = sorted(a)
    mex = 0

    for i in b:
        if i == mex:
            mex += 1
        elif i > mex:
            break

    if mex == n:
        print("No")
        return

    L = n
    R = -1

    if mex + 1 not in a:
        print("Yes")
        return

    for i in range(n):
        if a[i] == mex + 1:
            L = min(L, i)
            R = max(R, i)

    b = a[:L] + [mex] + a[R + 1 :]
    b.sort()
    mex2 = 0

    for i in b:
        if i == mex2:
            mex2 += 1
        elif i > mex:
            break

    print("Yes" if mex2 == mex + 1 else "No")


for _ in range(int(input())):
    solve()