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

Автор KAN, 12 месяцев назад, ,

Разбор дополняется.

•
• +77
•
•   KAN
•   12 месяцев назад
•   51

 » 12 месяцев назад, # |   +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
•  » » 12 месяцев назад, # ^ |   0 http://codeforces.com/contest/827/submission/28492511 It runs faster even than some fft solutions.
•  » » » 12 месяцев назад, # ^ | ← Rev. 3 →   +22 Please test this case string(499999, 'V') + 'K' It seems that your solution can't give result in several minutes
•  » » » » 12 месяцев назад, # ^ |   +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.
•  » » » 12 месяцев назад, # ^ |   +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)
•  » » 12 месяцев назад, # ^ | ← 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.
•  » » » 12 месяцев назад, # ^ |   0 thanks. I did the test in my machine.For a long time no results.This test data should be added
 » 12 месяцев назад, # |   0 827D — Лучший вес для ребра -- you forgot to translate problem name.
 » 12 месяцев назад, # |   0 can someone explain non-HLD and non-centroid decomposition strategy for solving Hint-3 of Div1-D
 » 12 месяцев назад, # | ← Rev. 2 →   +1 I still couldn't quite understand the analysis for div2E, can someone explain it to me plz?
 » 12 месяцев назад, # |   0 827C — when you will tranaslate it?
 » 12 месяцев назад, # |   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.
•  » » 12 месяцев назад, # ^ |   0 Sort spend O(nlogn) time => it is (1000000 * 20) / 100000000 = 0.2 sec.
•  » » 12 месяцев назад, # ^ |   0 Sorting 106 ints (or chars) is usually fast enough in C++.
•  » » » 12 месяцев назад, # ^ |   0 Got it, big thanks!
 » 12 месяцев назад, # |   +11 How to use centroid decomposition in hint 3 part of div1D?
 » 12 месяцев назад, # |   +3 TL задачи С div.2 на последнем тесте на C# (104 тест) :( Дискриминация медленных языков? :)
•  » » 12 месяцев назад, # ^ |   0 тоже самое для питона :( правда чуть пораньше — 53 и 58 тест
 » 12 месяцев назад, # |   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?
•  » » 12 месяцев назад, # ^ | ← Rev. 2 →   +5 Maybe modulo operation"%" is very slow...
 » 12 месяцев назад, # |   +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
•  » » 12 месяцев назад, # ^ |   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
•  » » » 12 месяцев назад, # ^ | ← Rev. 2 →   0 Thanks, MLE got eliminated and now i amngetting TLE on test 8. What i maybe doing wrong? Submission: 28528640
•  » » » » 12 месяцев назад, # ^ | ← Rev. 2 →   0 use vec[v[i].second]] instead of tobe you can check the reason : http://www.cplusplus.com/reference/string/string/operator=/
•  » » » » » 12 месяцев назад, # ^ |   0 Thanks!!! now it got AC. But i am still not getting how just storing the string in a variable can affect performance.
•  » » » » » » 12 месяцев назад, # ^ |   0 You can check the complexity of assignment operator in string
 » 12 месяцев назад, # | ← Rev. 2 →   0 problem name: 828C - String Reconstructionverdict: Memory Limit Exceededmy submission: 28526470Any suggestion please?
•  » » 12 месяцев назад, # ^ |   +1 See discussion above.
 » 12 месяцев назад, # |   +1 Used the concept of dsu in div2C , code 28475861
•  » » 12 месяцев назад, # ^ |   +1 Can you explain your idea a bit more?
•  » » » 12 месяцев назад, # ^ |   +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...
 » 12 месяцев назад, # |   +1 someone please help me visualize how the BITs are actually built in div2E/div1C
 » 12 месяцев назад, # | ← 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?
•  » » 12 месяцев назад, # ^ | ← 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.
•  » » » 12 месяцев назад, # ^ |   0 I didn't see clearly...sorry..
 » 12 месяцев назад, # |   0 MLE in 827A — String Reconstruction.here is my solution, please help.
•  » » 12 месяцев назад, # ^ |   +2 consider the case when |s|=10^6 and k=10^6 ...
•  » » » 12 месяцев назад, # ^ |   0 thanks, it worked :DAC
 » 12 месяцев назад, # |   0 Where is the proof of 827B? Why is it not published yet?
 » 12 месяцев назад, # |   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.
•  » » 12 месяцев назад, # ^ | ← 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.
 » 12 месяцев назад, # |   0 In Div 1 D. For the MST edges part, what is the solution using centroid decomposition ?
 » 12 месяцев назад, # |   +16 In Div 1 D. For the MST edges part, what is the solution using centroid decomposition ?
•  » » 12 месяцев назад, # ^ | ← 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.
 » 12 месяцев назад, # |   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,
 » 12 месяцев назад, # | ← 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
•  » » 12 месяцев назад, # ^ |   0 actually it's possible to use S = 2520. it takes more time but still under a second.
•  » » 10 месяцев назад, # ^ |   0 can you please explain your approach a little more !
•  » » 9 месяцев назад, # ^ |   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.
 » 12 месяцев назад, # |   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?
 » 11 месяцев назад, # |   0 Can anyone elaborate the proof (or give in more simpler terms) of High Load?