Editorial Codeforces Round #Pi

Revision en3, by vovuh, 2015-08-05 23:06:41

567A - Lineland Mail

One can notice that the maximum cost of sending a letter from i'th city is equal to maximum of distances from i'th city to first city and from i'th city to last (max(abs(xi - x0), abs(xi - xn - 1)). On the other hand, the minimum cost of sending a letter will be the minimum of distances between neighboring cities (i - 1'th and i + 1'th cities), more formally, min(abs(xi - xi - 1), abs(xi - xi + 1). For each city, except the first and the last this formula is correct, but for them formulas are (abs(xi - xi + 1)) and (abs(xi - xi - 1)) respectively.

567B - Berland National Library

To answer the queries correct, we need to know if the person is still in the library. For that purpose we will use in array of type bool. Also we will store two variables for the answer and ''current state'' (it will store the current number of people in the library). Let's call them ans and state respectively.

Thus, if we are given query  + ai then we should increase state by one, mark that this person entered the library (in[ai] = true) and try to update the answer (ans = max(ans, state)).

Otherwise we are given  - ai query. If the person who leaves the library, was in there, we should just decrease state by one. Otherwise, if this person was not in the library (in[ai] == false) and leaves now, he entered the library before we started counting. It means we should increase the answer by one anyway. Also one should not forget that it is needed to mark that the person has left the library (in[ai] = false).

567C - Geometric Progression

Let's solve this problem for fixed middle element of progression. This means that if we fix element ai then the progression must consist of ai / k and ai·k elements. It could not be possible, for example, if ai is not divisible by k ().

For fixed middle element one could find the number of sequences by counting how many ai / k elements are placed left from fixed element and how many ai·k are placed right from it, and then multiplying this numbers. To do this, one could use two associative arrays Al and Ar, where for each key x will be stored count of occurences of x placed left (or right respectively) from current element. This could be done with map structure.

Sum of values calculated as described above will give the answer to the problem.

567D - One-Dimensional Battle Ships

Editorial to this task will be posted later.

567E - President and Roads

Editorial to this task will be posted later.

567F - Mausoleum

Editorial to this task will be posted later.

Tags codeforces, round, 314, pi

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru9 Russian vovuh 2015-08-07 21:50:47 510
en7 English vovuh 2015-08-07 21:49:28 568
en6 English vovuh 2015-08-07 21:25:27 0 (published)
en5 English vovuh 2015-08-07 21:24:48 4538 (saved to drafts)
ru8 Russian vovuh 2015-08-07 21:15:56 0 (опубликовано)
ru7 Russian vovuh 2015-08-07 21:12:48 8 Мелкая правка: 'равен $d1[u] - d2' -> 'равен $d1[t] - d1[u] - d2' (сохранено в черновиках)
en4 English vovuh 2015-08-05 23:06:55 0 (published)
en3 English vovuh 2015-08-05 23:06:41 128 (saved to drafts)
ru6 Russian vovuh 2015-08-05 23:05:46 0 (опубликовано)
ru5 Russian vovuh 2015-08-05 23:05:18 112 (сохранено в черновиках)
en2 English vovuh 2015-08-05 22:51:32 0 (published)
en1 English vovuh 2015-08-05 22:50:14 2765 Initial revision for English translation (saved to drafts)
ru4 Russian vovuh 2015-08-05 22:42:53 0 (опубликовано)
ru3 Russian vovuh 2015-08-05 22:41:12 69
ru2 Russian vovuh 2015-08-05 22:35:07 18
ru1 Russian vovuh 2015-08-05 22:30:10 9810 Первая редакция (сохранено в черновиках)