antontrygubO_o's blog

XXII OpenCup GP of IMO
By antontrygubO_o, 3 years ago, translation, In English

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

  • Vote: I like it
  • +256
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

How to solve problem Q(Delete Files) from Div2 ? Is it greedy or DP ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I tried to implement various greedy algorithms, but they don't work.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      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.

      Code
      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    There is another greedy approach for Q.

    Solution
    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +59 Vote: I do not like it

Problem H can be solved by implementing an $$$O(n^3*2^n)$$$ checker and randomly generating some undirected graphs.

Code
→ Reply
»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

G can be solved by calculating random things in hope that everything cancels out: https://pastebin.com/b3GNafWD

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Is there any other approach for A exempt the editorial's version ? Maybe,it is possible to construct the answer in other way.

→ Reply
»
3 years ago, # |
  Vote: I like it -41 Vote: I do not like it

Is there any other approach for E exempt the editorial's version ? Maybe, it is possible to find the answer with other strategy.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div.2 O and P?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to get a login for opencup?

→ Reply