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

Автор KAN, 5 месяцев назад, По-русски,

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

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Проголосовать: нравится  
  • +77
  • Проголосовать: не нравится  
  • Отправитель   KAN
  • Дата публикации   5 месяцев назад
  • Комментарии   51

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

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

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

    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится

      Please test this case

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

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

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

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

  • »
    »
    5 месяцев назад, # ^ |
    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.

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

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

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

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

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

can someone explain non-HLD and non-centroid decomposition strategy for solving Hint-3 of Div1-D

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

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

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

827C — when you will tranaslate it?

»
5 месяцев назад, # |
  Проголосовать: нравится 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 <startPos, string_id> in this problem.

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

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

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

TL задачи С div.2 на последнем тесте на C# (104 тест) :( Дискриминация медленных языков? :)

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

    тоже самое для питона :( правда чуть пораньше — 53 и 58 тест

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

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

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

problem name: 828C - String Reconstruction

verdict: Memory Limit Exceeded

my submission: 28526470

Any suggestion please?

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

Used the concept of dsu in div2C , code 28475861

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

    Can you explain your idea a bit more?

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

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

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

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

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?

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

MLE in 827A — String Reconstruction.

here is my solution, please help.

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

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

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

  • »
    »
    5 месяцев назад, # ^ |
    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.

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

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

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

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

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

    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.

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

»
5 месяцев назад, # |
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

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

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

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

    can you please explain your approach a little more !

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

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

Can anyone elaborate the proof (or give in more simpler terms) of High Load?