A2SV Contest #29 Editorial

Revision en2, by A2SV_Group5, 2024-08-13 21:52:32

Here is the link to the contest. All problems are from Codeforces' problemset.

A. Monkeytype

Solution
Code

B. Strings again

”solution”

”code”

k_a = k_b = 0 ans = []

while a and b: if (a[-1] >= b[-1] and k_a < k) or k_b >= k: ans.append(b.pop()) k_a += 1 k_b = 0 else: ans.append(a.pop()) k_b += 1 k_a = 0

print("".join(ans))

C. Games

Solution

  • If Alice takes an even number $$$x$$$, she adds $$$x$$$ points to the global result, otherwise $$$0$$$;
  • If Bob takes an odd number $$$x$$$, he adds $$$−x$$$ points to the global result, otherwise $$$0$$$;
  • Alice wants to maximize the global result and Bob wants to minimize it.

Obviously, this game is completely equivalent to the conditional game.

Suppose now it's Alice's move. Let's look at some number $$$x$$$ in the array.

  • If this number is even, then taking it will add $$$x$$$ points, and giving it to Bob will add $$$0$$$ points.
  • If this number is odd, then taking it will add $$$0$$$ points, and giving it to Bob will add $$$−x$$$ points.

So taking the number $$$x$$$ by $$$x$$$ points is more profitable than not taking it (regardless of the parity). To maximize the result, Alice should always take the maximum number in the array.

Similar reasoning can be done for Bob. In the task, it was necessary to sort the array and simulate the game.

Code

def input(): return stdin.readline().strip()

T = int(input())

for _ in range(T): N = int(input()) a = sorted(map(int, input().split()), reverse=True)

alice = bob = 0
alice_turn = 1
for ai in a:
    if alice_turn:
        if ai%2 == 0:
            alice += ai
    else:
        if ai%2:
            bob += ai
    alice_turn ^= 1

if alice > bob:
    print("Alice")
elif bob > alice:
    print("Bob")
else:
    print("Tie")
</spoiler>


#### [D. This is war.](https://codeforces.net/gym/541681/problem/D)

<spoiler summary="Solution">
We can easily employ a Binary Search Algorithm to find a player $$$y$$$ with the minimum token that can win the game by favoring all the random decisions toward this player $$$y$$$. Then any player that has greater tokens than this player $$$y$$$ will win the game. This will reduce the time complexity to $$$O(nlogn)$$$ instead of $$$O(n^2)$$$. 
</spoiler>

<spoiler summary="Code">

for _ in range(int(input())): n = int(input()) players = list(map(int, input().split())) tokens = sorted(players)

left, right = 0, n - 1
tot_sum = sum(tokens)
init_point = right
while left <= right:
    mid = left + (right - left) // 2
    curr_sum = sum(tokens[:mid + 1])
    for i in range(mid + 1, n):
        if curr_sum < tokens[i]:
            break
        curr_sum += tokens[i]

    if curr_sum == tot_sum:
        right = mid - 1
        init_point = mid 
    else:
        left = mid + 1 

print(n - init_point)
print(*[indx + 1 for indx in range(n) if players[indx] >= tokens[init_point]])
</spoiler>


#### [E. Beef in M.A.A.D City](https://codeforces.net/gym/541681/problem/E)

<spoiler summary = "Solution">
Firstly, let's prove that the size of the answer is not greater than $$$3$$$
. Suppose that the answer equals to $$$4$$$
. Let $$$a,b,c,d$$$
 be coordinates of the points in the answer (and $$$a&lt;b&lt;c&lt;d$$$
). Let $$$dist(a,b)=2^k$$$
 and $$$dist(b,c)=2^l$$$
. Then $$$dist(a,c)=dist(a,b)+dist(b,c)=2^k+2^l=2^m$$$
 (because of the condition). It means that $$$k=l$$$
. Conditions must hold for a triple $$$b,c,d$$$
 too. Now it is easy to see that if $$$dist(a,b)=dist(b,c)=dist(c,d)=2^k$$$
 then $$$dist(a,d)=dist(a,b)∗3$$$
 that is not a power of two. So the size of the answer is not greater than $$$3$$$
.

Firstly, let's check if the answer is $$$3$$$
. Iterate over all middle elements of the answer and over all powers of two from $$$0$$$
 to $$$30$$$
 inclusively. Let $$$xi$$$
 be the middle element of the answer and $$$j$$$
 — the current power of two. Then if there are elements $$$xi−2^j$$$
 and $$$xi+2^j$$$
 in the array then the answer is $$$3$$$
.

Now check if the answer is $$$2$$$
. Do the same as in the previous solution, but now we have left point $$$xi$$$
 and right point $$$xi+2^j$$$
.

If we did not find answer of lengths $$$3$$$
 or $$$2$$$
 then print any element of the array.

The solution above have time complexity $$$O(n⋅log10**10)$$$
.

</spoiler>

<spoiler summary="Code">

from collections import Counter

def find_three(nums, dic): # Find a sequence of three numbers with differences of powers of two for num in nums: i = 1 while i <= 10 ** 10: if num + i in dic and num + 2 * i in dic: return 3, [num, num + i, num + 2 * i] i *= 2 return None

def find_two(nums, dic): # Find a sequence of two numbers with a difference of a power of two for num in nums: i = 1 while i <= 10 ** 10: if num + i in dic: return 2, [num, num + i] i *= 2 return None

def main(): n = int(input().strip()) nums = sorted(map(int, input().strip().split())) dic = Counter(nums)

# Check for sequences of 3, then 2, or return a single number
result = find_three(nums, dic) or find_two(nums, dic) or (1, [nums[0]])

length, sequence = result
print(length)
print(*sequence)

if name == "__main__": main() ```

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English A2SV_Group5 2024-08-13 21:57:44 0 (published)
en5 English A2SV_Group5 2024-08-13 21:56:34 37
en4 English A2SV_Group5 2024-08-13 21:55:41 18
en3 English A2SV_Group5 2024-08-13 21:53:58 13
en2 English A2SV_Group5 2024-08-13 21:52:32 7459
en1 English A2SV_Group5 2024-08-13 21:14:55 189 Initial revision (saved to drafts)