### KAN's blog

By KAN, 15 months ago, translation, ,

The analysis is being updated.

Thanks Arpa for the proofs!

•
• +77
•

 » 15 months ago, # |   +12 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.com/contest/827/submission/28488942
•  » » 15 months ago, # ^ |   0 http://codeforces.com/contest/827/submission/28492511 It runs faster even than some fft solutions.
•  » » » 15 months ago, # ^ | ← Rev. 3 →   +22 Please test this case string(499999, 'V') + 'K' It seems that your solution can't give result in several minutes
•  » » » » 15 months ago, # ^ |   +29 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.
•  » » » 15 months ago, # ^ |   +3 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)
•  » » 15 months ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » 15 months ago, # ^ |   0 thanks. I did the test in my machine.For a long time no results.This test data should be added
 » 15 months ago, # |   0 827D — Лучший вес для ребра -- you forgot to translate problem name.
 » 15 months ago, # | ← Rev. 2 →   +1 I still couldn't quite understand the analysis for div2E, can someone explain it to me plz?
 » 15 months ago, # |   0 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 in this problem.
•  » » 15 months ago, # ^ |   0 Sort spend O(nlogn) time => it is (1000000 * 20) / 100000000 = 0.2 sec.
•  » » 15 months ago, # ^ |   0 Sorting 106 ints (or chars) is usually fast enough in C++.
•  » » » 15 months ago, # ^ |   0 Got it, big thanks!
 » 15 months ago, # |   +11 How to use centroid decomposition in hint 3 part of div1D?
 » 15 months ago, # |   0 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?
•  » » 15 months ago, # ^ | ← Rev. 2 →   +5 Maybe modulo operation"%" is very slow...
 » 15 months ago, # |   +1 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
•  » » 15 months ago, # ^ |   0 use vector> instead of vector> In pair 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
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 Thanks, MLE got eliminated and now i amngetting TLE on test 8. What i maybe doing wrong? Submission: 28528640
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 use vec[v[i].second]] instead of tobe you can check the reason : http://www.cplusplus.com/reference/string/string/operator=/
•  » » » » » 15 months ago, # ^ |   0 Thanks!!! now it got AC. But i am still not getting how just storing the string in a variable can affect performance.
•  » » » » » » 15 months ago, # ^ |   0 You can check the complexity of assignment operator in string
 » 15 months ago, # | ← Rev. 2 →   0 problem name: 828C - String Reconstructionverdict: Memory Limit Exceededmy submission: 28526470Any suggestion please?
•  » » 15 months ago, # ^ |   +1 See discussion above.
 » 15 months ago, # |   +1 Used the concept of dsu in div2C , code 28475861
•  » » 15 months ago, # ^ |   +1 Can you explain your idea a bit more?
•  » » » 15 months ago, # ^ |   +4 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...
 » 15 months ago, # |   +1 someone please help me visualize how the BITs are actually built in div2E/div1C
 » 15 months ago, # | ← Rev. 2 →   0 In 827A,"sort all given string by their positions" I wonder how to do itand if we scanf all of the information it will scanf at most 10^5*10^6 figures,won't it TLE?
•  » » 15 months ago, # ^ | ← Rev. 2 →   +8 It is guaranteed that... the sum of all ki doesn't exceed 106. There can be at most 106 values to scanf.
•  » » » 15 months ago, # ^ |   0 I didn't see clearly...sorry..
 » 15 months ago, # |   0 MLE in 827A — String Reconstruction.here is my solution, please help.
•  » » 15 months ago, # ^ |   +2 consider the case when |s|=10^6 and k=10^6 ...
•  » » » 15 months ago, # ^ |   0 thanks, it worked :DAC
 » 15 months ago, # |   0 Where is the proof of 827B? Why is it not published yet?
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 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.
 » 15 months ago, # |   +16 In Div 1 D. For the MST edges part, what is the solution using centroid decomposition ?
•  » » 15 months ago, # ^ | ← Rev. 5 →   0 Solution using centroid decomposition 28779873Idea 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.
 » 15 months ago, # |   0 Hi all,Thank you for the comments on the problems. However, regarding problem 827C DNA Evolution, I do not understand the english of the second paragraph. Can someone please clarify for me the second paragraph? I would like to get a clearer idea about the presented solution. Cheers,
 » 15 months ago, # | ← Rev. 2 →   0 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
•  » » 15 months ago, # ^ |   0 actually it's possible to use S = 2520. it takes more time but still under a second.
•  » » 12 months ago, # ^ |   0 can you please explain your approach a little more !
•  » » 12 months ago, # ^ |   0 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.
 » 15 months ago, # |   0 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?
 » 14 months ago, # |   0 Can anyone elaborate the proof (or give in more simpler terms) of High Load?