Unlimited_Time's blog

By Unlimited_Time, 6 months ago, In English,

84A - Toy Army

The strict proof seems to be a little complicated as far as I consider, however an intuitive understanding suggests that the answer is n + n / 2, and it is accpeted...

84B - Magical Array

We must find out all the intervals that consist of the same integers. For an interval with P integers, the number of reasonable subsequences is . Thus, we can adopt two pointers to find out all the target intervals, and calculate the answer.

84C - Biathlon

As it has been guaranteed that no two circles intersect with each other, the given point can only fall into at most one particular circle (one special case is that two circles touch each other at the given point). Thus, we first sort the circles in an increasing order of their X-coordinates, and find out two circles between which the give point falls (check the X-coordinate of the given point as well, and a special case is that the given point falls at one of two ends of all the circles), which can be achieved by using binary search.

Then, the final step is to check which circle it falls inside, or completely outside all the circles.

84D - Doctor

The basic idea is still binary search. We use a[n] to denote the given array. We use binary search to find out the maximum T so that . Moreover, we compute K - S as the remainder. Then, any a[i] that is not larger than T should be firstly eliminated. Next we enumerate the first K - S survived a[j] in the natural order while decreasing them by one, and eliminate those a[i] ≤ T again. Finally, we start from the current position and output the survived indices one by one, by shifting to the right in a circular manner.

84E - Track

I spent about three hours modifying the algorithm to avoid the time limit....The most impressive modification I used is scaling the constant from 1 to . This is the first time that I realized what an important role that a constant can play.

The general idea is to generate all the feasible patterns of maps and find out the one with the minimum distance and order. For instance, if letter 'a' and 'b' can be used, then we will obtain a map where we can move to positions of 'a' and 'b' while the other ones can not be used. With this equivalent map, we can implement BFS from the starting position until the terminating position is reached. During this process, we update the distance and also the minimum order if necessary.

As k can take values up to 4, we may have to check as many as C264 patterns for the worst case. It turns out that this will lead to TLE. Therefore, we have to further reduce the complexity. Instead of beginning from the starting position, we can begin from every one of the four positions that can be reached from the starting position. Each time we select one position, we have determined one letter that must be used and thus the number of feasible patterns is reduced to C253, which is supposed to satisfy the time limit as I consider.

However, I made a mistake that the number of generated patterns is in fact A253 rather than C253. As these two values only differ by a constant of , I did not realize (or believe) that such a constant matters so much. After I correct the mistake, it passed... What a fascinating problem!!

  • Vote: I like it  
  • -1
  • Vote: I do not like it