Блог пользователя ArguteOnAir

Автор ArguteOnAir, 6 лет назад, По-английски

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
Разбор задач Codeforces Round 482 (Div. 2)
  • Проголосовать: нравится
  • +37
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Actually,

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    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)

»
6 лет назад, # |
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]

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    GOT IT :D

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    [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

»
6 лет назад, # |
  Проголосовать: нравится 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).

»
6 лет назад, # |
  Проголосовать: нравится 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:

  • »
    »
    6 лет назад, # ^ |
    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 -> aaaBb

    aaaBb -> aaaab

    aaaab -> aaaaa

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
        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?

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 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!

»
6 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Here is the same approach, but using only DFS.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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

»
6 лет назад, # |
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.

»
6 лет назад, # |
  Проголосовать: нравится +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 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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
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).

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

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

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

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
      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.

»
6 лет назад, # |
  Проголосовать: нравится 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!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +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.

»
6 лет назад, # |
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]

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
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!!

»
6 лет назад, # |
  Проголосовать: нравится 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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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)
      
»
6 лет назад, # |
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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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 :)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Problem E is 101 or 010 an alternatives path?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

UPD: the author has fixed it

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

2 abcabcabcabcabcabcabcabcabcabcabcabc aaaabbbbccccaaaabbbbccccaaaabbbbcccc ababababababababababababcccccccccccc

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

http://codeforces.com/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 лет назад, # |
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

»
6 лет назад, # |
  Проголосовать: нравится 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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.com/contest/979/submission/48867508

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Nice contest. The contest should have been more irritating,then it would have been more fun Even after seeing the editorial, it is disgusting as hell

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope you make 100 more contests. I am sure the codeforces participants will grow exponentially