Most recent round I participated in after a break of about 2 weeks. This is a new exercise that I’ve started to note down my thoughts and performance history in these blogs. So that I don’t repeat same mistakes more often and have some more clarity about what I go through when I’m participating and it will also double up as notes for some techniques and styles I come across while solving or upsolving that contest. Let’s start already.

Solved during contest⌗

A. Box is Pull⌗

  • Submitted in 10 minutes. Was really slow to read, lengthy problem statement.
  • Main idea was to consider x and y displacements independently.

B. Belted Rooms⌗

  • This was the main reason for bad performance in the round. I misunderstood the problem statement, at first I thought that every snake has to complete one round across all belts and come back to its position, wasted 20 minutes and then realized if one snake could do so all will be able to follow the same path. Re-read the statement, misunderstood it again. This time I thought those circles are belts and edges are the result of their orientation. After 20 minutes read the statement again and this time got it correct.

  • My solution was messy using ideas from other two misinterpretations I had earlier, there were two cases either all snakes would be able to comeback to their place after completing one circle or every snake that has a backedge will be added in the answer. SUbmitted at 80 minute mark.

  • A short and clever submission by cerebrus97

C. ABBB⌗

  • Solved it in 15 minutes.
  • I remember solving a similar problem on atcoder. So idea came naturally that in the problems where you are asked to remove all occurences of some pattern from a string and have to take care that while you remove one pattern remaining letters might concatenate to form the same pattern. General idea is to look for some dependency and limiting constraint on the pattern, by limiting constraint I mean that some character that is scarce and is part of the pattern. Limiting constraint here was ‘A’ and it depended on ‘B’ to be on its right. So I removed all valid ‘A’s and then all ‘B’s were left which you’re allowed to remove only in pairs.

Solved after contest⌗

D. Bouncing Boomerangs⌗

  • Nice constructive problem.
  • Had about 43 minutes to solve it but coded some silly approach with incomplete cases and wrong co-ordinate system. Incorrectly reasoned that 3 also needs 1 to exist while it could be linked to any other 3,2 or 1. But 2 could be only matched with a 1. So keep note of the current height you’re at, and how many 2’s seen so far are unmatched, whenever you see a 1 match it with any 2 that is unmatched and whenever see a 3 place one target at the same height in next column if it is not 0.

E. Carrots for Rabbits⌗

  • An observation that can be made easily is that if we have enough $k$ we can cut all carrots into length $1$ pieces that would be optimal and if we keep decreasing $k$ we’ll have to merge those length $1$ pieces in pairs to make one piece of length $2$. So there are going to be atmost two kinds of children of any carrot and they will differ only by $1$ in length. So we have to use one cut on any carrot which will give us highest profit of making one more cut.

F. Fruit Sequences⌗

  • Have seen two or three problems till now other two were on atcoder, which ask you to count some property over all intervals or sometimes overall subsets. One pattern I now recognize here is you have to fix some bound and calculate its contribution in all sets or intervals, then complete this sweep to get the answer. In this problem fix $r$ and get answer for every $r$ on the fly. How $f(l,r)$ changes when we increase $r$ is depicted beautifully in editorial with help of a histogram. Many participants used segment tree to propogate changes, while editorial has a simpler approach of calculating contribution of a continuous segment of 1 by updating $L$ where $L[len]$ is the largest index for a given $r$ where $f(l,r)$ is $len$.