ArguteOnAir's blog

By ArguteOnAir, 7 years ago, In English

Hi Codeforces!

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

979A - Pizza, Pizza, Pizza!!!

Solution
Code

979B - Treasure Hunt

Solution
Code

979C - Kuro and Walking Route

Solution
Code

979D - Kuro and GCD and XOR and SUM

Solution
Code

979E - Kuro and Topological Parity

Solution
Code
  • Vote: I like it
  • +37
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Actually,

Maybe this can simply the dp in E even more...

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    That is a really nice catch! That is a new thing I learned right from my own contest!

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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)

»
7 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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]

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

"holds and only holds if" should probably be "holds if and only if"

»
7 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

[sorry for asking but i didn't understand the editorial so i did ask a stupid question]

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    aaaaa -> aaaab -> aaaac -> aaaaa

»
7 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

4

aaaabcd

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 -> aaaaaaa

Since third one has max beauty I think he must win :(

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    GOT IT :D

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    [ignore,answered above] made the same mistake.

    1. aaaabcd -> aaaaacd -> aaaaaad -> aaaaaac -> aaaaaaa
    2. aaaabcd -> aaaaacd -> aaaaaad -> aaaaaac -> aaaaaaa
    3. aaaaaaa -> aaaaaab -> aaaaaaa -> aaaaaab -> aaaaaaa

    so it stands as a draw

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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 -> aaaBb

    aaaBb -> aaaab

    aaaab -> aaaaa

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Tks, at first I thought I could only change twice to make it be back, which leads me to wrong algorithm :(

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Sorry for that. Got my mistake. It's like aaaaa -> baaaa -> caaaa -> aaaaa

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C TLE. Is this 38236023 not O(n)? Poor python coder!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's n^2. See the lines path = path + [vs] and if v not in path.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks for explaining your approach. This pretty much is what I did as well

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is the same approach, but using only DFS.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
7 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 sx and go to the set's beginning. In other words, I loop through elements in array divisible by k, non greater than sx, 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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    a ^ b <= a + b, that's another nice property of xor. I'll make sure to remember it. Thanks!

»
7 years ago, # |
Rev. 6   Vote: I like it +5 Vote: I do not like it

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).

»
7 years ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

Задача D. Официальное решение выполняется 20х раз медленнее чем самое быстрое решение!!!

http://codeforces.net/contest/979/submission/38236267 46 мс.

http://codeforces.net/contest/979/submission/38249326 904 мс.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't understand what you wrote, but that 46ms solution looks like brute force with a break to stop checking.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem D is really hard for java to get rid of TLE, I failed and turned to C++.

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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]

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved D using square rooted N tries.
How did N tries passed without 'Memory Limit Exceeded'?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use new or malloc and pointers to build tries rather than array?

»
7 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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!!

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe you should use long long?Since the range is greater than int.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is no limit to value of integers in python3. So, there is no concept of long or long long in python3.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Maybe you lose too much of a precision when dividing in float numbers? Try using integer division (//).

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks awoo 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)
      
»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please tell me why am I getting wrong output here (test case 5) in problem C ? http://codeforces.net/contest/979/submission/38264299

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E seems to be a very tough problem to me. How to come up with such recursive structures, any insight/ ideas from anyone?

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem E is 101 or 010 an alternatives path?

»
7 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Is there a 2eb in the longest equation in solution for E?

UPD: the author has fixed it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

2 abcabcabcabcabcabcabcabcabcabcabcabc aaaabbbbccccaaaabbbbccccaaaabbbbcccc ababababababababababababcccccccccccc

Can someone tell me, what will be the beauty of each of the ribbons?

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, can any one tell me why this solution for problem C is wrong ?

http://codeforces.net/contest/979/submission/38786238

I'm coloring three types of nodes

nodes in sub_tree of X color 1 nodes in sub_tree of Y color 2

and other nodes will be in color 3

the answer will be n*(n-1) — (nodes of X * nodes of Y)

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

all we care is the parity of ob and ow , so we can dp it in mod 2

and if we know the parity of ob and ow , we can determine how to transmit

the complexity is O(n)

see my code for details http://codeforces.net/contest/979/submission/48867508