antontrygubO_o's blog

By antontrygubO_o, 5 weeks ago, translation, In English

This summer, me and kefaa2 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, kefaa2 and antontrygubO_o. This contest will be held as an OpenCup contest on September 19, 11:00 UTC+3.

I and kefaa2 are friends for long time, since our years of participation at IMO, and it's kefaa2 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

»
4 weeks 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 ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      4 weeks 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
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    There is another greedy approach for Q.

    Solution
»
4 weeks 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
»
4 weeks 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.

»
4 weeks 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

»
4 weeks 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.

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div.2 O and P?

  • »
    »
    4 weeks 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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to get a login for opencup?