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.
Revolution
Strange Knight
Were great! I enjoyed solving them!
Can you please explain the approach used for revolution problem ??? Thanks
I solved it using dp, you may check out my submission.
If any query is there then you may ask!
I was trying to solve it using dp , but unable to implement. I appreciate the code , but I'm unable to understand the dp state. Can you elaborate it a bit ??
$$$dp(i, j)$$$ defines the minimum cost to reach the cell $$$(i, j)$$$.
Can it be done by finding the shortest weight path : from any element on the bottom & left -> any element from top and right?
Yep, the main intuition was Dijkstra, that I used to solve this problem.
https://codeforces.net/contest/1749/problem/E
A similar problem you may like.
can you please share the solution of strange knight
Okay here you go :)
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.
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
To remove common intersection of all four directions using ordered set is awesome,thanks
Can you please explain the approach used for revolution problem ??? Thank you
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
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.
Solution for Sumful Triplets (i really liked this problem, others who solved do tell your construction).
first get rid of odd numbers as much as we can.
$$$ example: $$$
(15,1) => removal of 14
(13,3) => removal of 10
(11,5) => removal of 6
(9,7) => removal of 2
what's left 4 8 12 16
and upon dividing by 4 it will be again 1 2 3 4
i think you can now see the obvious recursion
we need to make sure there are even count of odd numbers while performing the removal otherwise we will not get a good pattern like 4,8,12,16
If there is odd count of odd numbers remove the last odd number
Anyone knows how to solve D. Sequences?
You can check the following discussion for the solution. Link
Will the editorial be released on codedrills? Also, can anyone share their approach for problem D, sequences?
You can check the following discussion for the solution.Link