### _iloveNQ_'s blog

By _iloveNQ_, 10 months ago, ,

Hi Codeforces!

This is the editorial of Codeforces Round #482 (Div. 2). I hope you guys enjoy it.

979A - Пицца, пицца, пицца!!!

Solution
Code

979B - Охота за сокровищами

Solution
Code

979C - Куро и прогулочный маршрут

Solution
Code

979D - Куро, НОД, побитовое исключающее ИЛИ, сумма и все-все-все

Solution
Code

979E - Куро и Топологическая четность

Solution
Code

•
• +37
•

 » 10 months ago, # |   +31 Actually, Maybe this can simply the dp in E even more...
•  » » 10 months ago, # ^ |   +16 That is a really nice catch! That is a new thing I learned right from my own contest!
•  » » 10 months ago, # ^ | ← Rev. 2 →   +3 There's a catch -- this formula fails for n = 0. So one needs to be slightly careful there. But otherwise, I believe the dp becomes even simpler.Edit: In response to Illidan's comment below, our dp state becomes dp [i][ob>0][ow>0] -- as in the boolean values ob>0 and ow>0, so I think we are down to O(n) states. (If I'm not hallucinating)
•  » » » 9 months ago, # ^ |   0 Actually there are some O(n) solutions and I've written one.and there are many O(n) solutions better than mine. XD
 » 10 months ago, # | ← Rev. 2 →   +10 E: all states that matters are oddblack and oddwhite, because even number doesn't change parity. This leads to n3 solution dp[i][ob][ow]
 » 10 months ago, # |   +13 "holds and only holds if" should probably be "holds if and only if"
 » 10 months ago, # | ← Rev. 6 →   0 [sorry for asking but i didn't understand the editorial so i did ask a stupid question]
•  » » 10 months ago, # ^ |   +2 aaaaa -> aaaab -> aaaac -> aaaaa
 » 10 months ago, # | ← Rev. 2 →   +1 4aaaabcd aaaabcd aaaaaaa Can someone explain why the answer for this case is "draw"?Since there are four turns first and second one will make the string as aaaaaaa after 3 turns and for the last turn let us assume it is aaaaaab.The third one will do the following : aaaaaaa-> aaaaaab -> aaaaaaa -> aaaaaab -> aaaaaaaSince third one has max beauty I think he must win :(
•  » » 10 months ago, # ^ |   +4 First one: aaaabcd > aaaabce > aaaaace > aaaaaae > aaaaaaa. Second one: same as first one. Third one: aaaaaaa > aaaaaab > aaaaaaa > aaaaaab > aaaaaaa.So the answer is Draw.
•  » » 10 months ago, # ^ |   0 GOT IT :D
•  » » 10 months ago, # ^ | ← Rev. 2 →   +1 [ignore,answered above] made the same mistake. aaaabcd -> aaaaacd -> aaaaaad -> aaaaaac -> aaaaaaa aaaabcd -> aaaaacd -> aaaaaad -> aaaaaac -> aaaaaaa aaaaaaa -> aaaaaab -> aaaaaaa -> aaaaaab -> aaaaaaa so it stands as a draw
 » 10 months ago, # |   0 I ran C in nlogn by rooting the tree at x and then doing LCA queries for all nodes and node y. If the lca of some node i and y was x, that takes out however many nodes are in the subtree of y (including y).
 » 10 months ago, # |   0 Can someone give a better explanation for B in the case n is odd? I though that if we had length L for each string and each letter frequency of F[i], then we could say that min(L, F[x] + n) is our "answer" for a letter x, but for the case in which n = L - F[x] + 1, then we would set all the letters of the string to x, with 1 turn left, so this turn will change anyone of the already equal letters, leading to a beauty of L - 1, but in the case n > L - F[x] + 1, one can use what's left to make a cycle for a letter, since its possible.Tell me what's wrong with this idea, please? D:
•  » » 10 months ago, # ^ | ← Rev. 2 →   +7 If you have a string aaabb and N = 3, you can first change one of the b's to a random other letter, and then change them to a's.aaabb -> aaaBbaaaBb -> aaaabaaaab -> aaaaa
•  » » » 10 months ago, # ^ |   +1 Thanks, I noticed my error. I didn't think about making an uncomplete cycle starting with a different letter than the one I want to set. :D
•  » » » 10 months ago, # ^ |   0 Tks, at first I thought I could only change twice to make it be back, which leads me to wrong algorithm :(
•  » » » » 10 months ago, # ^ | ← Rev. 2 →   0 What if string is aaaaa and n=3. In this case you will get 4 at most. But solution says 5. Can anyone explain this?
•  » » » » » 10 months ago, # ^ |   +1 Sorry for that. Got my mistake. It's like aaaaa -> baaaa -> caaaa -> aaaaa
 » 10 months ago, # |   0 Problem C TLE. Is this 38236023 not O(n)? Poor python coder!
•  » » 10 months ago, # ^ |   0 It's n^2. See the lines path = path + [vs] and if v not in path.
•  » » » 10 months ago, # ^ |   0 Alright those operations on path are questionable, so I redid the find_path to be totally like my DFS for counting the subtree size: 38269505 Still TLE though!
 » 10 months ago, # |   +3 I have solved C in O(n) also but in another way, first find the shortest path from x to y (simple BFS), lets say the shortest path is x > a > b > y, then we remove the edge (x, a) and start DFS from x to count how many nodes behind x (including x itself), define it as xCnt, then do the same thing with y, remove the edge (y, b) and start DFS from y to count how many nodes behind y (including y itself), define it as yCnt.Finally the solution is n * (n - 1) - xCnt * yCnt.To remove the edges quickly we can set nodes a and b visited before start the DFS.
•  » » 10 months ago, # ^ |   +1 Thanks for explaining your approach. This pretty much is what I did as well
•  » » 10 months ago, # ^ |   0 This is a good approach.I too have done in this way.
•  » » 10 months ago, # ^ |   0 Here is the same approach, but using only DFS.
•  » » 6 months ago, # ^ |   0 I did something completely different (rooting the tree at y, counting subtree size of x, rooting at x, counting subtree size of y) and I got the same formula. Interesting
 » 10 months ago, # | ← Rev. 2 →   +8 In problem D, there is no need to bother for Trie. You can pick a Set and do binary search on it by holding a binary-form-prefix of desired xor(which is already found in set) on each iteration.
 » 10 months ago, # |   +6 I got accepted on D with a kinda weird solution, O(n**2), I believe.Basically for each number [1...1e5] I have its divisors in a vector (this can be calculated in O(n log n)).As a primary data structure I have a vector (of size 1e5) of sets.Now, for each type-1 query x I loop through its divisors d (from that vector) and add x to set with index d (so that I know which numbers in array satisfy condition k | x).For each type-2 query on the other hand, I run an upper_bound on k-th set with s — x and go to the set's beginning. In other words, I loop through elements in array divisible by k, non greater than s — x, this is obviously O(n) for a type-2 query and with this implementation I got TLE. What made this solution accepted was an additional condition "if currently checked multiply of k plus x is less than current-best" then I stopped checking lesser candidates.Why is this correct? One may prove that a ^ b <= a + b, so if v + x < current-best then we are not able to find better solution, so we can stop searching for it. I am afraid though that this solution is only (in a worst case scenario) two times faster than the original one. But surprisingly it is accepted.For a reference you may see my submission 38240724. I know it is not a very clean code.
•  » » 10 months ago, # ^ |   0 a ^ b <= a + b, that's another nice property of xor. I'll make sure to remember it. Thanks!
 » 10 months ago, # | ← Rev. 6 →   +5 If I undestood all correctly, complexity of D in editorial should be O(MAXlog(MAX)2 + qlog(MAX)), because each second query is calculated in log MAX, and for the first queries we are using estimation that number of pairs (x, y), such that x | y is MAX + MAX / 2 + MAX / 3 + ... + MAX / MAX = O(MAX ln MAX). Because individual first query can be added in tries. Beatiful idea, btw.However, my solution, that doesn't check, if we added the same number earlier, and for which this estimation can't be apply and we can make it each time look at all tries (I used std::set instead of trie) passed all tests too (may be weak tests?).Also, this problem can be solved by using std::set instead of trie and using lower_bound for each bit calculation. Then second part of complexity would be qlog(MAX)2 (code example, same link as above).
 » 10 months ago, # | ← Rev. 2 →   -16 Задача D. Официальное решение выполняется 20х раз медленнее чем самое быстрое решение!!!
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 I don't understand what you wrote, but that 46ms solution looks like brute force with a break to stop checking.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 It seems like a brute force searches all number that can be divided by k and only breaks when found v - x  >  i  +  x, which means for all j < i , ( means XOR) because and So it seems that the data q = 100000 and t = 2 k = 1 x = 1 s = 100000 with no number added can make this program search O(q2) times.
 » 10 months ago, # |   0 I"m having trouble figuring out how many nodes we have in the trie. I created one trie using an array with the 105 tries as children of the "root". I tried multiple values for the size of the array (number of nodes), but none of them worked. In the end, I chose a large value that fit in memory (2·107) and it passed. How do you determine how many nodes there are in the worst case? Thanks!
•  » » 10 months ago, # ^ |   +5 First, let's calculate maximum count of operations "add number to trie". If we add all numbers from 1 to 105 operations count will be equal to the count of different pairs (x, y), such that x | y and y ≤ 105. This count is equal to ⌊105⌋ + ⌊105 / 2⌋ + ⌊105 / 3⌋ + ... + ⌊105 / 105⌋ (count of pairs (1, y), (2, y), (3, y), ... (105, y) respectivly). This expression is smaller than 105·(1 / 1 + 1 / 2 + 1 / 3 + ... + 1 / 105), which is almost equal to 105·ln 105 (see harmonic serie). Or you can just calculate this expression on PC.And each operation "add number to trie" creates no more than 17 new nodes (17 binary digits). So overall it can be estimated as 105·ln 105·17 ≈ 2·107.
 » 10 months ago, # |   +3 Problem D is really hard for java to get rid of TLE, I failed and turned to C++.
 » 10 months ago, # |   +8 I would like to present an alternative solution to D. Note that, for those , there are at most vi candidates, so we can enumerate all these candidates. This can be easily done by using a hashtable. When ki is small, the main problem is that there are too many candidates, a brute-force enumeration will get TLE. We may use some data structures, such as BIT, for each small k, to maintain the occurrence of multiples of k, and use binary search to find the solution. This can be done in (a good implementation may take only I think, but is enough here). This does essentially the same thing as Trie (which I didn't come up with during the contest), but they are different tools.
 » 10 months ago, # | ← Rev. 2 →   0 I have solved C in O(n) in another way. First dfs from X, recording the size of each nodes' subtree and parent of each nodes in the process of dfs. Then, we find the son of X which is on the shortest path between X and Y (just the highest parent of Y which is not X, and we can find it by the recorded parents), and denote it by Z.Finally the solution is n * (n - 1) - (size[X] — size[Z]) * size[Y]
 » 10 months ago, # |   0 I solved D using square rooted N tries.How did N tries passed without 'Memory Limit Exceeded'?
•  » » 10 months ago, # ^ |   0 Use new or malloc and pointers to build tries rather than array?
 » 10 months ago, # | ← Rev. 2 →   +3 Implementation of B is really good. Just 9 lines of code and you handled all corner cases. I messed up with n=1. Learned something new today!!
 » 10 months ago, # |   0 I know . I know . It may sound very strange that someone has got an error in first question. But, i got wrong answer for it. I followed the same approach as described in tutorial . Here is the link to my code in python3.For input 822981260158260519 , adding 1 and diving by 2 results in 411490630079130240 whereas the correct answer should have been 411490630079130260. It would be great help if someone can tell me what's wrong with it. I am not able to figure it out.
•  » » 10 months ago, # ^ |   0 Maybe you should use long long?Since the range is greater than int.
•  » » » 10 months ago, # ^ |   0 There is no limit to value of integers in python3. So, there is no concept of long or long long in python3.
•  » » » » 10 months ago, # ^ |   0 I use python2 and I get accepted! XD
•  » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 Haha. Yeah, i used to code in python2. Never faced this problem. Have written a descriptive comment on my findings for this problem in python3. Do have a read. http://codeforces.com/blog/entry/59462?#comment-430929
•  » » » » 10 months ago, # ^ |   0 The same code
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 Maybe you lose too much of a precision when dividing in float numbers? Try using integer division (//).
•  » » » 10 months ago, # ^ |   +1 Thanks PikMike for pointing that out. Yeah, it does lose precision when dividing in float numbers. But "how" and "why" questions made me curious to read the python3 docs in detail. I read the python3 documentation on floating point. I have tried to list down the concepts understood on floating point and division point by point in python3 after reading from various sources below: First of all, '/' is floating point division in python3 by default. So, when we use '/' for division . The numerator n in n/d is converted to floating point number. And, the floating point number are represented using scientific notation( a*10^b ) for representing very small and big float numbers. The a are significant digits and b is power of exponent. But, the scientific notation can represent only 15 significant digits( sys.float_info.dig ) for a. So, here is the catch . The float numbers having significant digits greater than 15 digits will lose some precision while represented as float numbers. Let me try to show that using an example. I will add int with float. int + float = float . So, i will try to push the limits of floating point arithmetic. >> 10**15 + 1.0 1000000000000001.0 # As significant digits are 15 . Result is correct. It doesn't lose precision >> 10**16 + 1.0 1e+16 # 10000000000000000 # As significant digits are 16 (>15). Result is incorrect . Loses precision. More examples >> 2**53 9007199254740992 >> 2**53 + 1.0 9007199254740992.0 Thus we can see that it is not safe to represent integers as float . Now, let's talk about easy way to tackle this kind of problem. '//' integer division comes to rescue. Integer division in python3 can be handled by builtin operand '//' . Also, the integers in python3 doesn't have a limit. So, this is the safe approach as compared to float or fractional, decimal module. Now coming to test case 11 for problem 979A-38 . Input: n = 822981260158260519 Now , (n+1)/2 would first convert n+1 as float But 822981260158260519 + 1 converted to float is 8.229812601582605e+17. Let's check in interpreter. >> 822981260158260519 + 1 822981260158260520 # Whereas >> 822981260158260519 + 1.0 8.229812601582605e+17 # we can see the digits '20' are lost while representing the number as float # Converting it to int >> int(8.229812601582605e+17) 822981260158260480 >> int((822981260158260519 + 1)/2) 411490630079130240 >> (822981260158260519 + 1) //2 411490630079130260 Summary: Use '//' integer division for these kind of problem. '/' may work fine with numbers having significant digits less than 16. Notes: >> import sys >> sys.float_info sys.float_info(max=1.7976931348623157e+308, max_exp=1024, max_10_exp=308, min=2.2250738585072014e-308, min_exp=-1021, min_10_exp=-307, dig=15, mant_dig=53, epsilon=2.220446049250313e-16, radix=2, rounds=1) 
 » 10 months ago, # |   0 Can someone explain what main test 79 in problem B was. Since the test case is too big, any alternate small test case with same logic?
•  » » 10 months ago, # ^ |   0 4 aaaabcd aaaabcd aaaaaaa
•  » » » 10 months ago, # ^ |   0 Got the mistake ! Thanks alot!!
 » 10 months ago, # | ← Rev. 2 →   0 Can someone please tell me why am I getting wrong output here (test case 5) in problem C ? http://codeforces.com/contest/979/submission/38264299
•  » » 10 months ago, # ^ |   0 Hi! The problem is in line t = n*(n-1), because n is an int, but the multiplication produces overflow. If you cast n to long, you'll get AC. If you want, you can check my submission :)
•  » » » 10 months ago, # ^ |   0 Yeah, silly mistake. Thanks :)
 » 10 months ago, # | ← Rev. 3 →   0 Why am I getting TLE for O(n) solution in Java? (Problem C) http://codeforces.com/contest/979/submission/38266793
 » 10 months ago, # |   0 E seems to be a very tough problem to me. How to come up with such recursive structures, any insight/ ideas from anyone?
 » 10 months ago, # |   +5 Problem E is 101 or 010 an alternatives path?
 » 10 months ago, # | ← Rev. 2 →   +2 Is there a 2eb in the longest equation in solution for E?UPD: the author has fixed it
 » 10 months ago, # |   0 2 abcabcabcabcabcabcabcabcabcabcabcabc aaaabbbbccccaaaabbbbccccaaaabbbbcccc ababababababababababababccccccccccccCan someone tell me, what will be the beauty of each of the ribbons?
 » 10 months ago, # | ← Rev. 2 →   0 Hi, can any one tell me why this solution for problem C is wrong ? http://codeforces.com/contest/979/submission/38786238I'm coloring three types of nodesnodes in sub_tree of X color 1 nodes in sub_tree of Y color 2and other nodes will be in color 3the answer will be n*(n-1) — (nodes of X * nodes of Y)
 » 10 months ago, # | ← Rev. 3 →   0 I found myself stuck in problem D on the 13 test data.It TLE 4 times there.Could anyone tell me some tips about this?submission
 » 10 months ago, # |   0 I have implemented exactly what the editorial said in Div2D, I have kept the variables also same and still getting TLE in JAVA here is my code
 » 2 months ago, # |   0 all we care is the parity of ob and ow , so we can dp it in mod 2and if we know the parity of ob and ow , we can determine how to transmitthe complexity is O(n)see my code for details http://codeforces.com/contest/979/submission/48867508