paula's blog

By paula, history, 3 years ago,

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!

• +104

 » 3 years ago, # |   +10 Reminder: the contest starts in one hour.
 » 3 years ago, # | ← Rev. 2 →   +21 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! :)
•  » » 3 years ago, # ^ |   +24 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +10 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.
•  » » » » 3 years ago, # ^ |   +24 SpoilerTo 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.
 » 3 years ago, # |   +15 Will we be able to upsolve the problems?
•  » » 3 years ago, # ^ |   +21 You can upsolve the problem in the tasks section of the evaluator [HONI 2020/21].
 » 3 years ago, # | ← Rev. 2 →   +28 Some people asked me p3 solution so I am putting it over here as well p3...p3-handle cases where no edge of corresponding type leaves from the 2 starting nodes1.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
•  » » 3 years ago, # ^ |   +10 QuestionWhat 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?
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +23 Spoiler Root the tree with his opponent, let say player $Q$. Then lift $P$ up by $\frac{dist(P, Q) - 1}{2}$, after that search for those edges inside the subtree.
•  » » » 3 years ago, # ^ |   0 answerin that case edge (x,y) cannot draw the game
 » 3 years ago, # |   +10 how to solve Task "Po" ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +20 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.
•  » » 3 years ago, # ^ |   +15 SpoilerI 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.
 » 3 years ago, # |   +15 Really enjoyed contest, thanks a lot! By the way, how to solve E (got only 55 points)?
•  » » 3 years ago, # ^ | ← Rev. 5 →   +20 Spoiler You could solve it by segment tree and lazy propagation. Notice that we can see the answer as many pairs of "plus and minus", e.g. $-a[x_1] + +a[x_2] + ...$ and $x_i< x_{i+1}$. So, we maintain a state dp table, $dp[i][j]$ which stores the maximum temporary sum for the answer, for each node. State $dp[+][j]$ means that we has an unmatched element which is a "plus" on left handside. State $dp[-][j]$ means that we has an unmatched element which is a "minus" on lhs. State $dp[0][j]$ means that we don't have any unmatched element on lhs. Same logic can be applied with $dp[i][+]$ etc for right handside. $dp[0][0]$ of the root node will be the answer.
 » 3 years ago, # |   +36 You can solve all problems here: https://oj.uz/problems/source/541