Codeforces Round #310 Editorial for Div2A — Div2B (for now)

Revision en1, by xuanquang1999, 2015-06-28 12:13:29

Hello everyone, this is my editorial for Round #310. I decided to write one since the author of this round didn't have time to do it. Currently, there's only Div2A and Div2B available, and I'll try to write editorial for Div1A and Div1B soon (about Div1C and Div1D, microtony has already written a nice tutorial for them (you can check out here), and Div1E is too difficult for me).

Div2A — Case of the Zeros and Ones

First, we can come up with a naive solution. While there's still some position i that 'remove-able' ((s[i] = '0' and s[i+1] = '1') or (s[i] = '1' and s[i+1] = '0')), we'll remove s[i] and s[i+1] from the string. However, in the worst case (contain all character '0' first, then character '1' or vise-versa), the complexity is O(n^2) and will surely got TLE.

We should optimize this solution by using stack. Push each character in string s to the stack, and while pushing, check if the top two element of the stack is ('0' and '1') or ('1' and '0') (or we can simply write abs(stack[top]-stack[top-1) = 1). If this happen, remove them from stack (top:=top-2). The answer is the number of character left in the stack.

Solution using Stack: 11816506

Sound a bit complicated for Div2A, right? There must be a more simple solution. We should notice that if there's still some zero and one in the string, there must be at least one position that 'remove-able'. So, we can remove one character '0' and one character '1' from the string until one type of character run out. We can come up with more simple solution with these analysis: just count the number of character '0' and '1' in the string, and the answer is abs(cnt0-cnt1).

Solution with some analysis: 11816073

Both of the solution has complexity O(n).

Div2B — Case of Fake Numbers

To solve this problem, first, we should notice that after n action, the gear will turn back to the initial state. So, if solution exist, the number of action to get it must be less than n. We can get an solution: just keep performing the action until we get the require structure (answer is 'Yes' or the number of action goes equal n (answer is 'No'). Complexity is O(n^2).

My solution: 11816203

This solution is already fast enough to get AC. But we can easily optimize it further. We can notice that we will need k = (n-a[1]) mod n move to get a[1] equal to 0, so we can just calculate a[i] after k move (whick is (a[i]-k+n) mod n, with i mod 2 = 0 and (a[i]-k+n) mod n, with i mod 2 = 1) and check if this is the required structure. Complexity is now O(n).

The better solution: 11816999

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en14 English xuanquang1999 2015-07-06 11:13:10 1 Tiny change: 'is `'Yes'` or the nu' -> 'is `'Yes'`) or the nu'
en13 English xuanquang1999 2015-06-29 09:18:46 2 Tiny change: '` = `2*(n-k)-k+1`.\n\' -> '` = `2*(n-x)-k+1`.\n\'
en12 English xuanquang1999 2015-06-29 05:47:03 8 Tiny change: 'ission:11816073]\n\nBoth ' -> 'ission:11830868]\n\nBoth '
en11 English xuanquang1999 2015-06-29 05:16:18 12 Tiny change: 'have **O(n log n + m^2)** soluti' -> 'have **O(n^2 + m log m)** soluti'
en10 English xuanquang1999 2015-06-29 05:14:06 2
en9 English xuanquang1999 2015-06-29 05:12:20 4 Tiny change: 'e now!\n\nUPD2: Div2D-Di' -> 'e now!\n\n**UPD2**: Div2D-Di'
en8 English xuanquang1999 2015-06-29 05:11:40 4
en7 English xuanquang1999 2015-06-29 05:10:21 1565
en6 English xuanquang1999 2015-06-29 03:13:30 6 Tiny change: ' 3\n2 1 2 4\n3 3 5 6\n1 7\n~~~' -> ' 3\n2 1 2 6\n3 3 4 5\n1 7\n~~~'
en5 English xuanquang1999 2015-06-28 17:50:43 60
en4 English xuanquang1999 2015-06-28 17:29:20 192
en3 English xuanquang1999 2015-06-28 16:59:44 1937 (published)
en2 English xuanquang1999 2015-06-28 16:28:56 973 (saved to drafts)
en1 English xuanquang1999 2015-06-28 12:13:29 2969 Initial revision (published)