This summer, me and 244mhq held a contest in Petrozavodsk Programming Camp. $$$1$$$ problem was provided by gepardo, and we are very thankful for that, and other problems were created by us, 244mhq and antontrygubO_o. This contest will be held as an OpenCup contest on September 19, 11:00 UTC+3.
I and 244mhq are friends for long time, since our years of participation at IMO, and it's 244mhq who introduced me to competitive programming. Therefore, we decided to call this contest GP of IMO.
Link (OpenCup login needed to participate)
I will publish the editorial here soon after the contest ends.
Good luck and have fun!
UPD1: Shame on me, I forgot to thank testers of this contest: gamegame, Geothermal, nitrousoxide.
UPD2: Editorial
UPD3: I just realized that I forgot to upload the contest to the gym and that it would be good to do so.
Here it is: 2021 Летние Петрозаводские сборы, день 3: IQ test (XXII Открытый кубок, Гран-при IMO)
How to solve problem Q(Delete Files) from Div2 ? Is it greedy or DP ?
I tried to implement various greedy algorithms, but they don't work.
Greedy method actually works. Let's iterate through each file from top to bottom. When we reach a file $$$i$$$ that does not need to be deleted, we need to delete all files less than $$$L_i$$$ that we have already visited. To do this, for each file, we would maintain the length of its filename(denote as $$$l_i$$$), and the length of the longest filename of all undeleted files after it(denote as $$$r_i$$$). Then, for each deletion, we need to make sure that the horizontal coordinates of the rectangle are in $$$[l_i,r_i]$$$. So we can sort all the files by $$$l_i$$$, and delete them greedily.
Thank you Qingyu! Nice observation ! We misled some points in our approach.
There is another greedy approach for Q.
Process in order from the shortest length. When processing, you should check how much you can delete the files before it and the files after it. It is a greedy algorithm. Intuitively it is obvious that we will delete the much as possible and also we will not delete the needed files as we delete from the shortest file and when we checking we will stop when we achieved the needed which is equal more than the length we want delete. Code: here
Problem H can be solved by implementing an $$$O(n^3*2^n)$$$ checker and randomly generating some undirected graphs.
By the way, it seems that the language of this post is set to Russian, which is not visible in Recent Action for English users.
You are right, corrected
G can be solved by calculating random things in hope that everything cancels out: https://pastebin.com/b3GNafWD
Sorry for being scratchy (We drew it during VP), here is a note.
The code calculates $$$\mathit{cnt}_{\mathit{left}}$$$ by iterating $$$BC$$$ and count $$$\mathit{cnt}_{BA = BD = CA = CD \neq BC}$$$, and calculates $$$\mathit{cnt}_{\mathit{right}}$$$ by iterating $$$AB$$$ similarly. Then we get $$$\mathit{cnt}_{\mathit{left}} - \mathit{cnt}_{\mathit{right}}$$$ as answer because lower left part and upper right part cancel out.
I think this solution is easier than Editorial.
Is there any other approach for A exempt the editorial's version ? Maybe,it is possible to construct the answer in other way.
Is there any other approach for E exempt the editorial's version ? Maybe, it is possible to find the answer with other strategy.
How to solve Div.2 O and P?
Div2 O: Let's just simply check all permutations of digits (0, 1, 2, 3, 4 , 5, 6, 7, 8 , 9) and find the permutation, when it is possible to obtain the maximum value. Code
Div2 P: Obviously we want to delete as much as possible. For this case let's observe what will be if we achieved to the panel '<' and our direction at that time is going right, so it will turn our direction to the left. If we will not have '>' we will exit from game and we will not be able to delete as much as possible. So obviously our answer will be the panels which have pairs(means that each '>' has his '<' from the right, one '>' can have 2 '<' and vice versa) and some part if there is, from where our player will run out. By some observation it will be seen that mostly center will have pairs and some parts from right or left may have panels which don't have pairs. So we will choose the maximum part (the left or right), actually we will choose the maximum count from where we will exit if such parts exists. Code
Thanks for your solution, I get it now.
You are welcome !
how to get a login for opencup?
Better to ask here [email protected]. Cordinator of your region must register you.