milind0110's blog

ICPC Kanpur Regionals 2021 Solution Discussion
By milind0110, history, 2 years ago, In English

Hello everyone!

As the Kanpur Regionals have already concluded I tried upsolving the problems in the mirror contest. I managed to do half of the problems but am unable to approach the problems Sumful Triplets, Pocket-less Billiards, Lit 'em Up!, Sequence. As there is no official editorial available yet and there is no access to the official submissions so if someone who has solved these problems might share their solution ideas that would be great.

Mirror Contest Link

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

Comments Comments (22)
| Write comment?
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

  • Revolution

  • Strange Knight

Were great! I enjoyed solving them!

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

yeah, I too in same state solved 5 except above mentioned. Please share if you get approach for them. Did you got approach for Baloons please share if possible.

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

    We know $$$total$$$ $$$balloons$$$ $$$left = n * m - total$$$ $$$balloons$$$ $$$popped$$$. For $$$total$$$ $$$balloons$$$ $$$popped$$$ we can just take the $$$sum$$$ $$$of$$$ $$$lengths$$$ of the $$$ranges$$$. Now need to remove only the $$$intersections$$$ between the ranges. Let $$$left$$$ $$$right$$$ $$$up$$$ $$$down$$$ be starting coordinates for the $$$arrows$$$ going in the respective directions.

    For $$$left$$$ and $$$right$$$ we only need to consider the $$$rightmost$$$ and $$$leftmost$$$ for $$$each$$$ $$$row$$$ respectively, similarly for $$$up$$$ and $$$down$$$ the $$$downmost$$$ and $$$upmost$$$ for $$$each$$$ $$$column$$$. Next we add those values of ranges. Now we need to remove $$$intersections$$$ between the $$$left$$$ and $$$right$$$ which will happen only if the $$$coordinate_y$$$ of $$$left <= coordinate_y$$$ of $$$right$$$. We will now remove both these ranges and consider only a single range of $$$right$$$ having $$$coordinate_y = 1$$$. Similarly, we can do for $$$up$$$ and $$$down$$$.

    Lastly, we need to remove $$$intersections$$$ between $$$right$$$ and $$$up, down$$$ and $$$left$$$ and $$$up,down$$$. We can keep the $$$coordinate-xy$$$ of all the remaining ranges starting points and $$$sort$$$ it based on $$$coordinate_y$$$. Now for $$$left$$$ we start by going through the coordinates and store the $$$up$$$ and $$$down$$$ coordinates which have $$$coordinates_y <= current_y$$$. Now the only $$$up$$$ and $$$down$$$ ranges which will intersect are those which $$$coordinates_x <= current_x$$$ and $$$coordinates_x >= currrent_x$$$ respectively. Similarly, we could do it for $$$right$$$ by going in $$$reverse order$$$.

    All the above operations could be performed using $$$map$$$ and $$$ordered set$$$.

    Code

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

      To remove common intersection of all four directions using ordered set is awesome,thanks

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain the approach used for revolution problem ??? Thank you

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

For Pocket-less billiards :

In the x-direction, the ball will alternately hit the left and right wall, similarly in the y-direction. Now, split the problem for x-direction and y-direction and solve them separately.

Let's assume that the ball hits vertical walls a times and horizontal walls (n-a) times. Then using some odd-even conditions on variables a and (n-a), we can find a formula for the total distance traveled by the ball.

Derive distance formula in terms of a which will be quadratic, and then using derivative we can find the most optimal value of a which minimizes the total distance traveled by the ball.

You can find the code here : https://pastebin.com/y7TpSYfB

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

For Sumful Triplets, I used the following observations:
1. If we can remove as many odd numbers as possible, then the remaining sequence will be 2,4,6,8... which is the same as 2*[1,2,3,4,...]. So we can perform the steps again, for a smaller n.
2. If we choose A = n/2-1, B= n/2, and keep decrementing A by 2 and incrementing B by 1, we will get a sequence of consecutive A+B. Note that to remove odd values, A should be odd.
3. Sometimes while choosing A for a given n, the (n/2-1) might not be odd. So we need to adjust it accordingly.
4. If we store unvisited values in a list, the list might have some unwanted values. For example, [2,4,6,8,...50,100]. In such a case, we can omit 100.

This is the code I came up with during the contest. Hacks and suggestions welcome.

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

Solution for Sumful Triplets (i really liked this problem, others who solved do tell your construction).

Spoiler
code
→ Reply
»
2 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it
RSVP Code
Tidy and Measured Code
Revolution code Failed System Test
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone knows how to solve D. Sequences?

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

Will the editorial be released on codedrills? Also, can anyone share their approach for problem D, sequences?

→ Reply