Hello Codeforces, I hope you enjoyed the round!
Just some notes about the problems:
In problem A, the picture and example notes should complete your understanding for the problem if the statement itself is not clear.
Solutions that check the lights of each part separately should have failed on pretests. My bad.
Problem C was assigned as B at the beginning, but moved to C lest it is harder than B difficulty. However, I think problem B is still easier than problem C (check the solution below).
I thought problem D is easier than problem E. Once, conditions are well-understood and related to each other and the problem is modeled correctly, then its implementation is easy.
The points I have just described is my own opinion in the problems. Of course, you might have a different point of view. However, I would like you to keep in mind that I did my best to make statements clear and pretests strong.
Thanks for your understanding!
For pedestrian crossing i (1 ≤ i ≤ 4), lanes li, si, ri, si + 2, li + 1, ri - 1 are the only lanes that can cross it. So, we have to check that either pi = 0 or all mentioned lanes are 0.
Complexity: O(1)
Implementation
When Sagheer reaches a floor for the first time, he will be standing at either left or right stairs. If he is standing at the left stairs, then he will go to the rightmost room with lights on. If he is standing at the right stairs, then he will go to the leftmost room with lights on. Next, he will either take the left stairs or the right stairs to go to the next floor. We will brute force on the choice of the stairs at each floor. Note that Sagheer doesn’t have to go to the last floor, so he will go to the highest floor that has a room with lights on.
Complexity: O(n·2n)
Implementation
If Sagheer can buy k items, then he can also buy less than k items because they will be within his budget. If he can’t buy k items, then can’t also buy more than k items because they will exceed his budget. So, we can apply binary search to find the best value for k. For each value k, we will compute the new prices, sort them and pick the minimum k prices to find the best minimum cost for k items.
Complexity:
Implementation
Let’s go through scenario requests one by one. For request a b, if toy b is free, then child a can take it. Otherwise, child a will wait until the last child c who requested toy b finishes playing. Since, no child can wait for two toys at the same time, each child depends on at most one other child. So we can put an edge from the a to c. Thus, we can model the scenario as a forest (set of rooted trees) as each node has at most one outgoing edge (to its parent).
For query x y, if toy y is free, then child x can take it and no child will cry. Otherwise, toy y is held by another child. Lets denote z to be the last child who requested toy y. So x now depends on z. If z is in the subtree of x, then all children in the subtree of x will cry. Otherwise, no child will cry. We can check that a node is in the subtree of another node using euler walk (tin and tout) with preprocessing in O(n) and query time O(1)
Complexity: O(k + n + q)
Implementation
In the standard nim game, we xor the values of all piles, and if the xor value is 0, then the first player loses. Otherwise, he has a winning strategy. One variant of the nim game has an extra move that allows players to add positive number of stones to a single pile (given some conditions to make the game finite). The solution for this variant is similar to the standard nim game because this extra move will be used by the winning player, and whenever the losing player does it, the winning player can cancel it by throwing away these added stones.
This problem can be modeled as the mentioned variant. Lets color leaf nodes with blue. The parent of a blue node is red and the parent of a red node is blue (that’s why all paths from root to leaves must have the same parity). Blue nodes are our piles while red nodes allow discarding apples or increasing piles.
If the xor value of blue nodes s = 0, then Soliman loses on the initial tree. To keep this state after the swap, Sagheer can:
If the xor value of blue nodes s ≠ 0, then Sagheer loses on the initial tree. To flip this state after the swap, Sagheer must swap a blue node u with a red node v such that
Complexity: O(n + maxA) where maxA is the maximum value for apples in a single node.
Implementation
You can read more about games from this link