scipianus's blog

By scipianus, 6 years ago, In English

474A - Keyboard

This is an implementation problem, therefore most of the solution fit in the time limit. We can even save the keyboard in 3 strings and make a brute force search for each character to find its position and then print the left/right neighbour.

474B - Worms

There are two solutions:

  1. We can make partial sums (sumi = a1 + a2 + ... + ai) and then make a binary search for each query qi to find the result j with the properties sumj - 1 < qi and sumj ≥ qi. This solution has the complexity O(n + m·log(n))

  2. We can precalculate the index of the pile for each worm and then answer for each query in O(1). This solution has the complexity O(n + m)

474C - Captain Marmot

For each 4 points we want to see if we can rotate them with 90 degrees such that we obtain a square. We can make a backtracking where we rotate each point 0, 1, 2 or 3 times and verify the figure obtained. If it's a square we update the minimal solution. Since we can rotate each point 0, 1, 2 or 3 times, for each regiment we have 44 configurations to check. So the final complexity is about O(n).

474D - Flowers

We can notate each string as a binary string, instead of red and white flowers. A string of this type is good only if every maximal contigous subsequence of "0" has the length divisible by k. We can make dynamic programming this way : nri = the number of good strings of length i. If the i-th character is "1" then we can have any character before and if the i-th character is "0" we must have another k - 1 "0" characters before, so nri = nri - 1 + nri - k for i ≥ k and nri = 1 for i < k. Then we compute the partial sums (sumi = nr1 + nr2 + ... + nri) and for each query the result will be sumb - suma - 1. This solution has the complexity O(maxVal + t), where maxVal is the maximum value of bi.

474E - Pillars

We have to find a substring i1, i2, ..., ik such that abs(hij - hij + 1) ≥ D for 1 ≤ j < k. Let's suppose that the values in h are smaller. We can make dynamic programming this way : besti = the maximal length of such a substring ending in the i-th position, besti = max(bestj) + 1 with j < i and hj ≥ D + hi or hj ≤ hi - D. So we can easily search this maximum in a data structure, such as an segment tree or Fenwick tree. But those data structure must have the size of O(maxH) which can be 109. For our constraints we mantain the idea described above, but instead of going at some specific position in the data structure based on a value, we would normalize the values in h and binary search the new index where we should go for an update or a query in the data structure. Therefore, the data structure will have the size O(n). The complexity of this solution is O(n·log(n)).

474F - Ant colony

For each subsequence [L, R] we must find how many queens we have. A value is "queen" only if is the GCD of (sL, sL + 1, ..., sR). Also, we must notice that the GCD of (sL, sL + 1, ..., sR) can be only the minimum value from (sL, sL + 1, ..., sR). So for each query we search in a data structure (a segment tree or a RMQ) the minimum value and the GCD of (sL, sL + 1, ..., sR) and if these two values are equal then we output the answer R - L + 1 - nrValues, where nrValues is the number of values in the subsequence equal to the GCD and the minimum value. The complexity of this solution is O(n·log(nlog(valMax) + t·log(nlog(valMax)), where valMax is the maximum value of si.

Read more »

  • Vote: I like it
  • +27
  • Vote: I do not like it

By scipianus, 6 years ago, In English

Hello, Codeforces! On 6th October at 19:30 MSK the Codeforces Round #271 (Div. 2) will take place. Div1 participants can take part out of competition, as usual.

I am Ciprian Olariu (scipianus) from Romania and this is my first round on Codeforces. It is more special as it is held right after I became red on Codeforces. I would like to thank Maxim Akhmedov (Zlobober) and Gerald Agapov (Gerald) for helping me to prepare this round, Delinur for translating the statements and also MikeMirzayanov for Codeforces and Polygon platform.

In this round the main characters will be Mole and Marmot, two good friends, and you will help them in their activites.

Please note that this round will have an experimental duration of 2.5 hours and 6 problems. The scoring will be 500-1000-1500-2000-3000-3000.

I hope you will enjoy the round. Good luck and have fun :)

UPD : To avoid overlapping Topcoder SRM #635 and Bayan 2015 Contest Warm Up, we decided to move round to Monday 19:30 MSK

UPD 2 : The editorial was published here

UPD 3 : Round has finished. Thanks for participating. Congratulations to the winners:






Read more »

  • Vote: I like it
  • +240
  • Vote: I do not like it