Codeforces Round #378 Div. 2 review

Link

A. Grasshopper And the String

  • Category: Implementation

Even this is a first problem, I get wrong answer for first time submission. It is necessary to consider a corner case at the “end of the text”.

Some other solution is inserting extra ‘A’ at the end of text so that you can handle it in the same way. (ex. latte0119’s solution)

 

B. Parade

  • Category: math

Below implementation is a little bit optimized solution for not to use memory of \(O(N)\), but use \( O(1) \). But in the contest, it is better to consider solve it as fast as possible rather than optimize too much.

 

C. Epidemic in Monstropolis

  • Category: greedy

When we compare the sequence of \( a \) and \( b \), we notice that \( b_1 \) is made of the group from \( a_1 \) to \( a_{k_1} \), \( b_2 \) is made of the group from \( a_{k_1 + 1} \) to \( a_{k_2} \), and so on. So we can just check it can be done or not with greedy algorithm.

The implementation amount is big, so it is difficult to solve it in time for me. 

D. Kostya the Sculptor

  • Category: data structures – use map, normalized representaion.

Since this problem restricts to consider only 1 or 2 parallelepipe combination, we can check all the posibility. To check 2 parallelepipe combination, it takes \( O(n^2) \) with straight-forward implementation, but by using map we can reduce the search time and it can be done in \( O(n\log (n)) \) time.

map‘s key must be comparable, so I used pair<int, int>.

 

 

Sponsored Links

Leave a Reply

Your email address will not be published.