Hello!
Uzbekistan IOI 2024 Team Selection Test took place last month, and we have uploaded its problems to Codeforces Gym.
About the competition:
Two contests with 3 problems each
Duration 5 hours
IOI format (problems have subtasks)
Statements in English
Problems are NOT ordered by difficulty
All tasks were prepared by DilshodbekX, MDSPro, and drdilyor. Note that in the original competition, we used CMS and graders, so if we have made a mistake while exporting them to Polygon, please let us know.
We hope you enjoy the problems!
Is there any editorial of problems?
In problem 105186A - Kep.uz Arena this code 263109793 got only 22 points(1,2 subtask) but I was waiting for 42 points(1,2,3 subtasks).In 3rd subtask it says time limit exceed on test 39.But it works in ~ O(n^3) where n=(count of D's) max(n)=18.You said you could make mistake while preparing it in polygon system can it be mistake or my code not effectively?
I checked your code and it should get 22 points, not 42. I suggest you to analyze the time complexity of your code.
Oh yeah there is also a loop from 0 to s.size().Thanks!
will there be an editorial?
Can somebody write editorial for day1 A problem please.I tried to solve it whole day but I couldn't!
sorry but I haven't solved it yet either. my code only passed subtask 2 worth 8 points.
Since no official editorial has been published i can help you.
...First try to think what happens if you delete a random W, a random L or random D.
...It is easy to see that we can delete all L, so we just have an array full of D and W. Now think about when it is good to delete D and when it is good to delete W.
It is a bad idea to delete W, because in no case it will increase the answer. But it's sometimes good to delete D. I considered some possibilites. Firt we should see that if there are some D in a row either we delete all or none, beacuse if we just delete some it won't increase our answer. But if we have 2 or more D in a row it isn't good to delete all, because if we have $$$x$$$ D, we were deleting $$$x$$$ point from our answer. But in the best case we will just add 2 point to our solution. (if you dont understand this you can ask me more). So the only case that we have to discuss is if there is just one D after some W and before some W. Now the only important thing is if this will increase our solution. Think about when it will increase the answer.
The only thing that is important is if we have at least 2 W before the D and at least 1 W after the D. In this specific case if we delete the D the answer wont be changed, but if we have more than 1 W after the D the answer will be increased.
...
If you have any doubt, or I didn't explain well something, ask me.
why is it even good to delete a D or a W?
Do we need to use dp or not ?? Are you presenting some greedy solution ?
Trivial greedy. No DP needed.
can you write one for me ,please.
No, in fact I'm not subservient to you
Can someone give me a hint for the final subtask of problem C? I seem to be able to solve every subtask except for the last one.
think about dfs tree , bridges. How to convert the graph to a tree ?
consider the dfs tree of the graph If an edge in the dfs tree is not a bridge than assign its weight to $$$0$$$ And solve the problem on the new tree. $$$f(x , y) = $$$ sum of costs in the path from x to y in the dfs tree
Can you give me hints on problem B ?
In each query you can find out the position of a number relative to a set of other numbers that are ordered
How do you solve the problem when the graph is a tree? (Subtask 3)
centroid decomposition