KAN's blog

Codeforces Round #423 Analysis
By KAN, 7 years ago, translation, In English

The analysis is being updated.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Thanks Arpa for the proofs!

Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +77
  • Vote: I do not like it

Comments Comments (43)
| Write comment?
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I used binary search to pass div1.E (have been accepted). but later, I found it was probably wrong. Can someone provide me with a data or prove it is right? thanks！ code goes here: http://codeforces.net/contest/827/submission/28488942

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

    http://codeforces.net/contest/827/submission/28492511 It runs faster even than some fft solutions.

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

      Please test this case

      string(499999, 'V') + 'K'

      It seems that your solution can't give result in several minutes

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

        Oh, I feel really sorry about it. During preparation of this task I did many tests to check correctness of solutions' answers, but when I did tests against slow solutions I invented only O(cntV·cntK) solution. The comment below shows, that it's possible to fail this solution using random test with good distribution of letters, but I was too stupid and didn't thought that tests with this distribution can be bad for some solutions.

        Now I looked through all accepted during contest solutions, most of then uses FFT or NTT and only 2 or 3 looked incorrect for me, so I hope it didn't affected participants too much. Anyway, it was my big mistake and I apologize for it.

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

      It is even more bruteforce than you think, because:

      It should be

      for(int j = i; j <= n; j += i) can[j] = true, vis[j] = 1;

      instead of vis[j]=0 (which does nothing)

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it 
    n = 500000;
s[0] = 'V';
for (int i = 1; i < n; ++i) s[i] = i % 10 ? '?' : 'K';

    And result is TL with more than 10s execution time.

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

      thanks. I did the test in my machine.For a long time no results.This test data should be added

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

827D — Лучший вес для ребра -- you forgot to translate problem name.

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

I still couldn't quite understand the analysis for div2E, can someone explain it to me plz?

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

In div2 C, can I sort an array with 10^6 elements? I thought that I could sort only arrays with ~10^5 size in order to pass TL. I mean array <startPos, string_id> in this problem.

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to use centroid decomposition in hint 3 part of div1D?

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

For problem div1D, after TLE with NTT(Fast Number-Theoretic Transform), I have a question:

Why NTT is slower than FFT? FFT uses Complex Number, so it's clear that you need at least twice times than integer in each calculation.

But the result is quite different than what I thought, FTT get Accepted easily, and NTT can't get answer during 3000 ms.

So I can't help to wondering, is that because I wrote something wrong, or NTT is really slower than FFT?

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

828C - String Reconstruction I did the same as is given in the tutorial.
I am getting MEMORY LIMIT EXCEEDED on test 8.
It would really be of great help if anybody can help me.
Thanks!!!
Code: 28528063

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

    use vector<pair<int,int>> instead of vector<pair<int,string>> In pair<in,int> first is the start index of string and second is the string and store strings in vector

    Also, don't do string tobe=v[i].second; it may give TLE

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

problem name: 828C - String Reconstruction

verdict: Memory Limit Exceeded

my submission: 28526470

Any suggestion please?

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

Used the concept of dsu in div2C , code 28475861

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

    Can you explain your idea a bit more?

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

      sure,

      but first you must understand my initial thought process, here is the code 28455243 , what i am trying to do in this code (which got TLE) is that i m simply going to the next position that is empty but i m not doing it efficiently, for example suppose you have the value dddd 1 1 then the vis array(which holds the next position that is not filled) will be [4,3,2,1] which simply tells how much forward we have to move in order to get to the next unfilled position but then you have the value dddd 2 2 3 then again the array is filled like the following(note that we will first jump to the position 4) [4,3,2,1,1,1,1] now observe for large value (like in test case 8) we can get 1,1,1,1.... for a long period and each time a new string is entered we have to move many positions one at a time hence complexity increases many folds.....So i thought how can i reduce the complexity to O(n) therefore i thought of the array as a segment and whenever i fill a sub-segment, i now update the array such that i move to the next unfilled sub-segment as compared to earlier in which i moved one by one in the worst case and just like in dsu the find operation is O(1) , here also i have used the similar concept of path compression and we can jump to the next segment in O(1) time and fill the value of result array with the currentpos(P) — given position of the string(pos) so as to get the exact value at that unfilled spot and if the next unfilled spot is out of bounds, i simply ignore it..I hope now u can understand the concept and my code, the only thing remains is that how is this correct?? if u think carefully then this is easy as if a position is filled we dont need to fill it again as the data is not contradictory...so we access each unfilled position only once and we dont need to access the whole string ti only the specific characters of it.. and there are at most 1e6 given position and hence O(n) complexity.. there fore path compression came to my rescue...

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

someone please help me visualize how the BITs are actually built in div2E/div1C

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

In 827A,"sort all given string by their positions" I wonder how to do it
and if we scanf all of the information it will scanf at most 10^5*10^6 figures,won't it TLE?

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

    It is guaranteed that... the sum of all ki doesn't exceed 106.

    There can be at most 106 values to scanf.

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

MLE in 827A — String Reconstruction.

here is my solution, please help.

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

Where is the proof of 827B? Why is it not published yet?

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

For 827B High Load: "Then the depths of all leaves are not greater than d/2." I don't think that it is true that if tree has diameter d, then all of the leaves have depth <=d/2. For counter-example take: 2 1 1 3 3 4 4 5 5 6 It's diameter is 5, while the depth of leaf 6 is 4 which is >5/2.

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

    And i don't think we need the whole thing with depths as it's pretty intuitive that when rehanging that path to root the diameter is not increasing.

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

In Div 1 D. For the MST edges part, what is the solution using centroid decomposition ?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Solution using centroid decomposition 28779873

    Idea being: Find the centroid of current tree and lets call it C. Root the current tree on centroid C and lets call it T. Find all those bad-edges E such that C is the largest centroid lying on MST-path from E.u to E.v. This can be done by checking if E is connecting two different subtrees of T.

    Consider the paths (C, E.u) and (C, E.v). Minimize the answer of all the MST edges lying on both the paths by E.w-1. (This will be like taking the minimum of prefix of some array with given value!).

    Delete C from the tree and repeat the same process for all the new trees created.

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

div1.C solvable using sqrt(n) decomposition too.. segment size must be a number S such that S % (1 .. 10) = 0 ... the minimum S is 2520 and since it's too big I calculated the answer for two segments size once for |e| = (1,2,3,4,5,6,8,9,10) where S = 360.. and once for |e| = (7) where S2 = 357.. we can choose any other two numbers such that (S % i = 0) or (S2 % i = 0) where i belongs to [1..10]. this is my implementation

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

    actually it's possible to use S = 2520. it takes more time but still under a second.

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

    can you please explain your approach a little more !

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • assume that the original string is s and the query string is e , l is the start and r is the end of the segment that we have to compare.
    • we can calculate the answer for every character i in e by simple iterate
    • sumi = (s[l+i] == e[i]) + (s[l+i+|e|] == e[i]) + (s[l+i+2|e|] == e[i]) + (s[l+i+3|e|] == e[i]) + ... + (s[l+i+j |e|] == e[i]) .. and so on where l + i + j * |e| <= r , and finally the answer is the sum of these values..
    • knowing that we have only four letters and 1 <= |e| <= 10 .. we can make things faster by calculating the partial sum in array d[n][4] .. for every i in s we store how many 'A' from i to n but instead of step one by one we need to step S by S .. like this: i, i + S, i + 2 * S, i + 3 * S... i + j * S and the same way we calculate how many 'T','G','C'.. where S is the segment size
    • then to calculate the answer for every query we have to iterate only S where (r -l+1) > S.. and (r-l+1) where (r-l+1) <= S
    • when (r-l+1) <= S we simply iterate and calculate the answer using naive approach
    • when (r-l+1) > S we iterate only S step .. we know that for every i in s we have the number of occurrences of every character in ( i , i + S, i +2 S , i +3 S, i + j * S) from i to n , so we simply iterate over every character in e and sum these values for i , i + |e| , i + 2 * |e| , i + 3 * |e| , i + j * |e| , where j * |e| < S.
    • we can notice that S must be a multiply of |e| .. and since 1 <= |e| <= 10, S could be 2520 it's a valid value because lcm(1,2,3,4,5,6,7,8,9,10) = 2520.
    • for update we need to update d values at indices i,i+ S, i + 2 S,..., i + j S, where i + j S <= n, in the worst case it takes only n/S iterate which is almost 40 iterate.
    • sorry for broken English it's not my native, and I hope that I explained my approach in a better way.
    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 1 E, "So our task reduced to finding such all possible numbers that it is representable as the sum of a number from A and a number from B., ", why is that?

→ Reply