A2SV Gen 4 Contest 9 Editorial
Difference between en3 and en4, changed 0 character(s)
[problem:433454A]↵

<spoiler summary="Hint 1">↵
Consider the strategy of forming teams based on the power of the players. How can this strategy be optimized to maximize the number of wins?↵
</spoiler>↵

<spoiler summary="Hint 2">↵
How can sorting help you come up with a strategy?↵
</spoiler>↵

<spoiler summary="Solution">↵
To maximize the number of wins, we can sort the candidate players in decreasing order of power and form teams by picking a player with the highest power and pairing them with the player with the lowest power. This strategy ensures that we use the highest power available while minimizing the number of players needed to form a team with a particular power.↵

We can then leverage Pak Chanek's ability to change the power of players in a team by increasing their power to the maximum available power in the team. This increases the chances of winning a match by ensuring that the team's total power is as high as possible.↵

To determine the maximum number of wins, we can iterate through the formed teams and count the number of teams that can defeat an enemy team with a specified power. This can be done by comparing the total power of the team with the power of the enemy team and checking if it is strictly greater.↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
n, d = map(int, input().split())↵
players = sorted(list(map(int, input().split())), reverse=True)↵

num_wins = 0↵
right = n - 1↵

for left in range(n):↵
    if left > right:↵
        break↵

    curr = players[left]↵

    while right > left and curr <= d:↵
        curr += players[left]↵
        right -= 1↵

    num_wins += int(curr > d)↵

print(num_wins)↵
~~~~~↵
</spoiler>↵

[problem:433454B]↵

<spoiler summary="Hint 1">↵
Simulate the program.↵
</spoiler>↵

<spoiler summary="Solution">↵
Simulate the program by simulating the recursion stack. Since we only have "add" operations and a for loop we can use ↵
simply multiply nest loop results.↵

Time Complexity &mdash; O(N)↵
Space Complexity &mdash; O(N)↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
from sys import stdin↵

n = int(stdin.readline().strip())↵
stack = [[1, 0]]↵

for _ in range(n):↵
    command = stdin.readline().strip()↵

    if command == "add":↵
        stack[-1][1] += 1↵
    elif command == "end":↵
        iterations, add = stack.pop()↵
        stack[-1][1] += iterations * add↵
    else:↵
        _, iterations = command.split()↵
        stack.append([int(iterations), 0])↵

if stack[-1][1] > (2**32 &mdash; 1):↵
    print("OVERFLOW!!!")↵
else:↵
    print(stack[-1][1])↵
~~~~~↵
</spoiler>↵

[problem:433454C]↵

<spoiler summary="Hint">↵
Try sorting.↵
</spoiler>↵

<spoiler summary="Solution">↵
After sorting we can observe that the target rectangle area should be $a_{i} \cdot a_{4n}$. Then we just need to check for each ${i}$ from 1 to n that $a_{2i-1}=a_{2i}$ and $a_{4n-2i+1}=a_{4n-2i+2}$ and $a_{2i-1}\cdot a_{4n-2i+2}=area$. If all conditions are satisfied for all i  then the answer is "YES". Otherwise, the answer is "NO".↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
from sys import stdin, stdout↵

t = int(stdin.readline().strip())↵

for _ in range(t):↵
    n = int(stdin.readline().strip())↵
    arr = list(map(int, stdin.readline().split()))↵
    arr.sort()↵

    i, j = 0, len(arr) - 1↵

    ok = True↵

    area = arr[i] * arr[j]↵

    while i < j:↵
        if arr[i] == arr[i + 1] and arr[j] == arr[j - 1] and arr[i] * arr[j] == area:↵
            i += 2↵
            j -= 2↵
        else:↵
            ok = False↵
            break↵
    ↵
    print("YES" if ok else "NO")↵
~~~~~↵
</spoiler>↵

[problem:433454D]↵

<spoiler summary="Hint">↵
Look for an optimal way to arrange the emotes.↵
</spoiler>↵

<spoiler summary="Solution">↵
The optimal way to arrange the emotes is to choose a chunk of k &mdash; 1 of the most potent emote separated by a single emote of the second most potent emote. Eg: Let's say "a" is the most potent emote and "b" is the second most potent. The best way to arrange the emotes is like: "a1, a2, a3 .... a k &mdash; 1, b, a1, .... a k &mdash; 1, b , a1..."↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
from sys import stdin, stdout↵

n, m, k = map(int, stdin.readline().split())↵
arr = list(map(int, stdin.readline().split()))↵
arr.sort(reverse=True)↵

chunk_len = k + 1↵

full = (arr[0] * k + arr[1]) * (m // chunk_len)↵
rem = m % chunk_len↵

part = arr[0] * min(rem, k)↵
rem -= min(rem, k)↵

part += arr[1] * rem↵

print(full + part)↵
~~~~~↵
</spoiler>↵

[problem:433454E]↵

<spoiler summary="Hint">↵
What happens as we increase or decrease "k" in regard to the damage done to the dragon?↵
</spoiler>↵

<spoiler summary="Solution">↵
Use binary search to look for the minimum k that deals at least h damage to the dragon.↵
</spoiler>↵

<spoiler summary="Code">↵
~~~~~↵
from sys import stdin↵

t = int(stdin.readline().strip())↵

for _ in range(t):↵
    n, h = map(int, stdin.readline().split())↵

    arr = list(map(int, stdin.readline().split()))↵

    left = 1↵
    best = right = h↵

    while left <= right:↵
        mid = (left + right) // 2↵

        curr_max = -1↵
        damage = 0↵

        for time in arr:↵
            damage += mid - max(curr_max - time, 0)↵
            curr_max = time + mid↵

        if damage >= h:↵
            best = mid↵
            right = mid - 1↵
        else:↵
            left = mid + 1↵

    print(best)↵
~~~~~↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English a2sv 2023-03-19 13:10:03 43
en4 English a2sv 2023-03-19 12:59:11 0 (published)
en3 English a2sv 2023-03-18 22:25:32 4 Tiny change: 'hould be ${a_i \cdot a_4n}$. Then' -> 'hould be $a_{i} \cdot a_{4n}$. Then'
en2 English a2sv 2023-03-18 22:24:09 3 Tiny change: '4n-2i+2}=a_{rea}$. If all ' -> '4n-2i+2}=area$. If all '
en1 English a2sv 2023-03-18 22:22:14 5470 Initial revision (saved to drafts)