### milind0110's blog

By milind0110, history, 8 months ago,

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.

• +45

 » 8 months ago, # |   +11 Revolution Strange Knight Were great! I enjoyed solving them!
•  » » 3 months ago, # ^ |   0 Can you please explain the approach used for revolution problem ??? Thanks
•  » » » 3 months ago, # ^ |   0 I solved it using dp, you may check out my submission.If any query is there then you may ask!
•  » » » » 3 months ago, # ^ |   0 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 ??
•  » » » » » 3 months ago, # ^ |   0 $dp(i, j)$ defines the minimum cost to reach the cell $(i, j)$.
•  » » » » 3 months ago, # ^ |   0 Can it be done by finding the shortest weight path : from any element on the bottom & left -> any element from top and right?
•  » » » » » 3 months ago, # ^ |   0 Yep, the main intuition was Dijkstra, that I used to solve this problem.
•  » » » » » » 3 months ago, # ^ |   0 https://codeforces.com/contest/1749/problem/EA similar problem you may like.
•  » » 2 months ago, # ^ |   0 Could you please explain the approach used for strange knight?
 » 8 months ago, # | ← Rev. 2 →   +3 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.
•  » » 8 months ago, # ^ | ← Rev. 4 →   +3 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
•  » » » 8 months ago, # ^ |   0 To remove common intersection of all four directions using ordered set is awesome,thanks
•  » » » 3 months ago, # ^ |   0 Can you please explain the approach used for revolution problem ??? Thank you
 » 8 months ago, # | ← Rev. 2 →   +5 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
 » 8 months ago, # |   +5 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.
 » 8 months ago, # |   +16 Solution for Sumful Triplets (i really liked this problem, others who solved do tell your construction). Spoilerfirst get rid of odd numbers as much as we can.$example:$ $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16$(15,1) => removal of 14(13,3) => removal of 10(11,5) => removal of 6(9,7) => removal of 2what's left 4 8 12 16and upon dividing by 4 it will be again 1 2 3 4i think you can now see the obvious recursionwe 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,16If there is odd count of odd numbers remove the last odd number codefunction)> rec=[&](ll curr,vector v){ if(v.size()<3){ return; } deque vv; set s; for(ll i=0;i=0;i--){ v2[i]/=v2[0]; } rec(curr,v2); };
 » 8 months ago, # | ← Rev. 6 →   0 RSVP Codevoid chal() { ll n; cin>>n; set ans; while(n--){ string st; cin>>st; string s; cin>>s; if(s=="yes"){ ans.insert(st); ll k; cin>>k; while(k--){ cin>>st; ans.insert(st); } } } cout< aa={'a', 'e', 'i', 'o' ,'u'}; string st; cin>>st; ll ans=0; fo(i,st.length()){ if(aa.find(st[i])!=aa.end()){ ans++; }else{ ans+=2; } } cout<=0){ ans+=dek2(i-1,j,aa,dp); } if(j-1>=0){ ans+=dek2(i,j-1,aa,dp); } return dp[i][j]=min(aa[i][j],ans); } void chal() { ll n,m; cin>>n>>m; vvl aa(n,vl(m)); vvl dp(n,vl(m)); fo(i,n) fo(j,m) dp[i][j]=-1; fo(i,n){ fo(j,m){ cin>>aa[i][j]; } } cout<
 » 8 months ago, # |   0 Anyone knows how to solve D. Sequences?
•  » » 8 months ago, # ^ |   0 You can check the following discussion for the solution. Link
 » 8 months ago, # |   0 Will the editorial be released on codedrills? Also, can anyone share their approach for problem D, sequences?
•  » » 8 months ago, # ^ |   0 You can check the following discussion for the solution.Link