Codeforces Round #310 Editorial (AB Div2 + A Div1)

Revision en4, by Lord_F, 2015-06-28 15:58:49

Hello, everyone!

An editorial for our round will be posted here in some time.

Unfortunately, both AndreySergunin and I are rather busy (we are at different summer camps at the moment) so it'll take some time to write the editorial.

Sorry for the inconvenience.

556A - Case of the Zeros and Ones

If there still exist at least one 0 and at least one 1 in the string then there obviously exists either substring 01 or substring 10 (or both) and we can remove it. The order in which we remove substrings is unimportant: in any case we will make max(#zeros, #ones) such operations. Thus the answer is |#ones - #zeros|.

Time: O(n).

556B - Case of Fake Numbers

Notice that after pressing the button n times gears return to initial state. So the easiest solution is to simulate the process of pressing the button n times and if at some step the active teeth sequence is 0, 1, ... , n - 1 output "Yes" else "No". But this solution can be improved. For instance, knowing the active tooth of the first gear you can quickly determine how many times pressing the button is necessary, go to that state and check the sequence only once.

Time: O(n) or O(n2); solutions: 11822751 (O(n)) and 11822759 (O(n2))

555A - Case of Matryoshkas

Suppose we don't need to disassemble some sequence of dolls. Then no doll can be inserted into no doll from this chain. So we don't need to disassemble a sequence of dolls only if they are consecutive and start from 1. Let the length of this chain be l. Then we will need to get one doll from another n - k - l + 1 times. Now we have a sequence 1 → 2 → ... → l and all other dolls by themselves. n - l + 1 chains in total so we need to put one doll into another n - l times. 2n - k - l + 1 operations in total.

Time: O(n); solution: 11823230.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru15 Russian Lord_F 2016-01-28 12:44:35 4 Мелкая правка: 'сделаем $max(#единиц,#' -> 'сделаем $min(#единиц,#'
ru14 Russian Lord_F 2015-07-19 06:54:38 10 Мелкая правка: 'ntu.com/11788459/), исполь' -> 'ntu.com/11902227/), исполь'
en17 English Lord_F 2015-07-19 06:54:27 10 Tiny change: 'ntu.com/11788459/) that us' -> 'ntu.com/11902227/) that us'
ru13 Russian Lord_F 2015-06-29 21:07:43 2 Мелкая правка: 'елано $2n-m-2k+1$ опе' -> 'елано $2n-l-2k+1$ опе'
ru12 Russian Lord_F 2015-06-29 16:27:01 28
en16 English Lord_F 2015-06-29 16:26:01 2 Tiny change: ' $2n-k-2l+2$ operatio' -> ' $2n-k-2l+1$ operatio'
ru11 Russian Lord_F 2015-06-29 16:25:30 12005
ru10 Russian Lord_F 2015-06-29 15:41:36 35 Мелкая правка: 's shorter we procee' -> 's shorter _or current step is the first one_ we procee'
en15 English Lord_F 2015-06-29 15:40:24 35 Tiny change: 's shorter we procee' -
ru9 Russian Lord_F 2015-06-28 23:06:48 2 Мелкая правка: 'Time: $O(nl_q)$ wher' -> 'Time: $O(n+ql_q)$ wher'
en14 English Lord_F 2015-06-28 23:05:55 2 Tiny change: 'Time: $O(nl_q)$ wher' -> 'Time: $O(n+ql_q)$ wher'
ru8 Russian Lord_F 2015-06-28 19:02:24 314
en13 English Lord_F 2015-06-28 19:01:34 314
ru7 Russian Lord_F 2015-06-28 18:49:48 62
ru6 Russian Lord_F 2015-06-28 18:49:31 1514
en12 English Lord_F 2015-06-28 18:48:19 22
en11 English Lord_F 2015-06-28 18:47:44 1476
en10 English Lord_F 2015-06-28 18:05:08 1
en9 English Lord_F 2015-06-28 18:04:19 1038
ru5 Russian Lord_F 2015-06-28 18:02:54 1039
ru4 Russian Lord_F 2015-06-28 17:25:21 3 Мелкая правка: 'es. $2n-k-l+1$ operatio' -> 'es. $2n-k-2l+2$ operatio'
en8 English Lord_F 2015-06-28 17:25:01 3 Tiny change: 'es. $2n-k-l+1$ operatio' -> 'es. $2n-k-2l+2$ operatio'
en7 English Lord_F 2015-06-28 17:23:45 271
ru3 Russian Lord_F 2015-06-28 17:21:24 3567
en6 English Lord_F 2015-06-28 16:56:11 636 Tiny change: 'ogq)$ or $qlogq$; solutio' -
ru2 Russian Lord_F 2015-06-28 16:37:50 60
en5 English Lord_F 2015-06-28 16:33:48 1080
en4 English Lord_F 2015-06-28 15:58:49 657
en3 English Lord_F 2015-06-28 15:34:14 12 Tiny change: '1$ output \t{Yes} else \t{No}. But thi' -> '1$ output "Yes" else "No". But thi'
en2 English Lord_F 2015-06-28 15:27:30 1038
ru1 Russian Lord_F 2015-06-27 23:03:38 332 Первая редакция перевода на Русский
en1 English Lord_F 2015-06-27 22:57:25 327 Initial revision (published)