Hello, Codeforces!
I would like to invite everybody to participate in a mirror of Ural Regional School Programming Contest, which will be held on Timus Online Judge this Sunday, 31th of January, 12MSK.
For onsite participants this was a standard team contest with ICPC rules. Online participants may play it alone or in a team (up-to-3 people). Even though this is a school student competition with a certain number of simple problems, it also contains some very tricky problems, so it will be interesting for a wide range of people.
The problems were invented and prepared by Gmacem, teewar, BdE and me.
I also want to thank reshke for testing.
Good luck to everyone!
5 hours! Is it closer to Div 1 or 2? Also, how many problems?
I hope the contest will be interesting for both divisions. There will be 12 problems.
https://acm.timus.ru/problem.aspx?space=1169&num=11. I think this statement is very weird. I mean: "several lampposts", shouldn't we know this number to find the k-th interesting lamppost and also it looks like we don't have any data at all about his walk, just find the k-th lamppost. Am I missing something?
I see that there are some people that agree with me(judging by upvotes), so more might have faced this issue. May one of the contest writers clarify the statement or give some explanation of a sample?
As far as I can tell, we were expected to derive speed and initial shift from samples.
Yes, I realized in the end!:) That was a big troll ngl=)))
Somewhat confusing wording in I: in real world "wind direction" is usually understood as the direction from which the wind originates, and you are using the opposite of it.
How to solve A?
Hint
How to solve J?
Consider building a solution inductively (we claim that the answer is always YES).
If $$$n = 3$$$, then there is always a cyclic order (clockwise or anticlockwise) along which the $$$a_i$$$'s are non-decreasing. Hence, using that, we can easily construct a solution for $$$n = 3$$$. Note that in this solution, no set is empty.
We can look at the assignment as assigning arrows between $$$a_i$$$ and $$$a_{i+1}$$$ (indices wrap around), where the clockwise arrows are for assigning the conversation to player 1 and anticlockwise ones for assigning the conversation to player 2. The "balance" of the configuration can be defined as the sum of $$$to - from$$$ over all arrows $$$(from, to)$$$, and it is sufficient to find a balanced assignment of arrows inductively.
Now consider how we get from $$$i-1$$$ to $$$i$$$. You need to fit $$$a_i$$$ between $$$a_1$$$ and $$$a_{i-1}$$$. To maintain the balance between the two players, you need to assign directions to arrows between $$$a_{i-1}$$$ and $$$a_i$$$, and $$$a_i$$$ and $$$a_1$$$ depending on the direction of the arrow that is currently between $$$a_{i-1}$$$ and $$$a_1$$$.
As it turns out, this can be done in a manner similar to the $$$n = 3$$$ case, and you'll be done inductively (in $$$O(n)$$$).
Add those with $$$(a_i - a_{i + 1}) < 0$$$ in one set and $$$(a_i - a_{i + 1}) > 0$$$ in other.
The sum of two sets should be the same as the net sum in a circular array will be $$$0$$$.
This won't quite work when there are indices $$$i$$$ where $$$a_i = a_{i+1}$$$. For handling those cases, it would be sufficient to assign roughly half of those to the first player and the remaining ones to the second player.
Duh, that was a super trivial case, so I left it out of my explanation.
Thanks for the explanation!
Madball, what was the intended solution for H? It was quite similar to https://codeforces.com/problemset/problem/1446/F, except that $$$k = 1$$$ in the case of this problem, but this approach gave me TLE during the contest.
Did the problems disappear from the site or I just search for them in the bad place?
how to solve L?