Hi everyone!
The fifth round of COCI will be held tomorrow, February 13th at 14:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.
The round was prepared by bukefala, jklepec, mkisic, dpaleka and me.
Feel free to discuss the problems in the comment section after the contest ends.
Hope to see you tomorrow!
Reminder: the contest starts in one hour.
Can the task "Planine" be represented using line segments? My idea, was to find the leftmost point Li that can light valley i and the rightmost point Ri that can light valley i. This can be done using similar triangles by simple math. Then we have pairs [Li, Ri] for each valley and we sort them by Li increasing. Finally we find the least number of points such that each point belongs to at least one of the [Li, Ri] segments.
This solution, however, fails one of the 30 point tests and one of the 60 point tests (possibly because I compare doubles wrongly).
Other then that, a really nice contest — I enjoyed solving other problems very much! The last problem kept me entertained for quite some time, tho I managed to come up only with the 15 point DP solution.
Lastly, it felt like a balanced problemset, at least to me. Thanks to the authors again! :)
That is how I solved it. However, you need to keep in mind that the points Li, Ri aren't necessarily determined by the slope of the edges of the valley. There might be a different peak that is so tall that it further restricts the range. This can't happen for the 20 point test case because the peaks are all at the same height.
Oh, now that makes sense. Thanks for the explanation!
UPD: Just one question. In that case how do you determine the range of point i efficiently? I can think of an N^2 solution, but not the N or N log N one.
To determine Li: work left-to-right and maintain a convex hull of peaks. You can then binary search that hull to find the peak which most blocks the line of sight. For Ri, do the same but working right-to-left.
Will we be able to upsolve the problems?
You can upsolve the problem in the tasks section of the evaluator [HONI 2020/21].
Some people asked me p3 solution so I am putting it over here as well
...
p3-handle cases where no edge of corresponding type leaves from the 2 starting nodes
1.if dist with between nodes%2==0 then player1 wins or draw
2.if dist with between nodes%2==1 then player 2 wins or draw
now you need to check whether there is winning condition or draw
wlog assume dist%2==0
second case has same solution
there must exist an edge such that player 2 can reach the nodes on that edge before player 1 and
its impossible for player 1 to ever reach that nodes on that edge
code-https://ideone.com/AiAFpL
What happens if the player $$$P$$$ who tries to draw can reach the edge $$$(x, y)$$$ (and the other player can't reach those nodes), but there is a node $$$z$$$ that $$$P$$$ has to visit to reach $$$x$$$ and can be visited earlier by the other player?
in that case edge (x,y) cannot draw the game
how to solve Task "Po" ?
Observe that for every sequence of contiguous elements ai, ai + 1, ai + 2, ..., ai + k it is optimal to increase them by ai if none of them are lower than ai. Now having that on our mind, it is easy to implement an algorithm that solves it.
For every element of the array you should keep the index of its closest (on the right) element which is lower than it. This is a standard problem that can be solved in O(N) using stack.
Next, you should keep difference arrays, e. g. diff[i] = a[i] — a[i — 1]. This helps us because we can reconstruct every element a[i] as a[i — 1] + diff[i].
Now that you've got these two you traverse elements from left to right and represent current element of array as ar[i — 1] + diff[i]. In case it is greater than zero, than increase answer by 1 and increase diff[next_greater[i]] by current element's value (as we didn't decrease elements on its right by current value). Otherwise we just continue iterating over the array.
I worked left-to-right and kept a stack of values that can be seen again without requiring another enhancement (sorted increasing). If the current value is less than the top-of-stack, pop the stack and check again. If it's equal, do nothing; if it's greater, you need a new enhancement (and can push the stack).
I don't have a formal proof that it works; it intuitively seemed right so I just submitted it.
Really enjoyed contest, thanks a lot! By the way, how to solve E (got only 55 points)?
You can solve all problems here: https://oj.uz/problems/source/541
Good quality round! I enjoyed the problem set.
My score was 285 — 17th place, Scores: 50 70 110 0 55
I wanted to share my approaches to some of the problems constructively,
Here are some of my solutions, guided with constructive hints.
Solve "Task 2 — All colors are magenta" first.
Some guiding questions:
what happens if the distance between them is 2?
what happens if the first and second players start at neighbor cells?
what happens if the distance between them is k?
Observation:
The parity of the distance between the two players at player x's turn is invariant. (i.e, every time it's the player's turn again, the parity of the distance to the other player stays the same).
Proof:
Each move changes the distance by an offset of 1.
A draw is impossible in this subtask.
"Task 2 — All colors are magenta" Solution:
Claim 1: If the distance between the two players is 2, the first player wins
Proof: We shall observe the winning strategy. Root the tree at the first player's initial cell. when the first player's turn, he should go to the child such that the subtree of which contains the other player's node. Note that this process must terminate. (Convince yourself that this always works!).
Claim 2: If they start at neighboring cells, the second player wins.
Proof: Either the first player cant move (then he loses) or he makes a move that changes the distance to be 2. then, root the tree at the second player's initial starting cell and use the exact same strategy as in Claim 1.
Final solution: If the distance is odd, the second player wins. Otherwise, the first player wins.
Proof: Convince yourself that this works by using our invariant from Hint 2 and apply the strategy used in Claims 1 & 2 to the winning player. you can't escape forever this way!
Now, we shall move to solve the full problem. this time we have blue & red edges, that only one of the players can go through.
If the first player is surrounded only by edges he can't go through that he loses. Otherwise, if the second player has the same issue he loses. From now on we will call this Case 0 and we shall ignore this case in all further observations.
How does the logic of subtask 2 apply here? can the winning player we found by applying subtask 2 lose? (Except case 0)
Claim:
Except Case 0, either the winning player we find by applying subtask 2's algorithm (ignoring edge colors) wins, or there is a draw. i.e he can't lose
Proof:
Let's suppose he can lose, then that contradicts the logic of subtask 2 because the only difference is that we have more restrictive edges. if he was the determined winner then it means that on his turn the parity of the distance is always even, and given that it's not case 0, he can always move to some other node in his component.
So the task of the "losing player" is to obtain a draw, he should look for some "shelter"...
Let's root the tree at the player which is determined to win by subtask 2's algorithm (ignoring edge colors)'s initial node.
The "losing player" needs to reach some component such that:
he will able to get there before the winning player could block him from getting there
he has space to move
the winning player is unable to reach the root of that component.
How would you check if he can do that?
Again, ignoring case 0, handle it separately.
let u be the "winning player", and v be the "losing player" (based on subtask 2 ignoring edge colors)
Root the tree at u.
With a dfs scan, store in a set all of the nodes that u can reach. Let this set be called W. In that same dfs scan calculate the depth of each node & the parent of each node.
With a dfs scan, store in a set all of the nodes that v can reach with the additional condition that the distance from v to the node (maintain with the dfs recursion) is less than the depth of the node (or equal to incase the losing player is the first player). Let this set be called L.
the condition checked in the second dfs scan formulates the "nodes you can reach before the other player will block them" idea.
Claim: A draw is achievable by the "losing player" if and only if there exists a node x such that:
x is in L
p[x] is in L.
p[x] is not in W.
this claim formulates the "shelter" idea.
Convince yourself that this claim is true.
if there is such x go there with the "losing player", he will always be able to move and the "winning player" can't reach him.
if there isn't such x it means no matter where the "losing player" goes the "winning player" will be able to trap him in a place such that he can't move.
So by using a heap / std::set or any other structure that allows us to insert and search numbers quickly, we can check the draw condition in O(N log N) and we are done :)
TODO Tomorrow morning as it's midnight :(
Let me know if you have any comments or feedback on the provided editorials, lior5654.
Loool I got mentioned here cuz you signed your name I think.
Hope you are doing well, Lior.
You again :p
Yeah in the first revision I accidentaly mentioned you instead of myseld
Is it just on my side or have the spoiler tags broken? All of a sudden all of the text escaped the hint blocks and everything is shown, weird issue :(
I worked hard on this editorial, sad to see codeforces ruined the style...
What happened to the hints for Problem 5: Sjeckanje? Really needed a hint for that one :(