KAN's blog

By KAN, 11 months ago, translation, In English,
Tutorial is loading...

Author, preparation: KAN.

Tutorial is loading...

Author, preparation: _kun_.

Tutorial is loading...

Author, preparation: KAN.

Tutorial is loading...

Author, preparation: KAN.

Tutorial is loading...

Authors: MikeMirzayanov, _kun_, preparation: _kun_.

Tutorial is loading...

Author, preparation: ne0n25.

Tutorial is loading...

Author, preparation: KAN.

Tutorial is loading...

Author KAN, preparation: KAN, 300iq.

Huge thanks to _kun_ and 300iq for discussing the problems and general invaluable help in preparation!

 
 
 
 
  • Vote: I like it
  • +79
  • Vote: I do not like it

»
11 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Isn't the statement of C clear? "the other team must choose the other one on its turn", I didn't think "the other must choose immediately".

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I found that confusing too & I discovered that I was misunderstanding the problem until I read the tutorial! :(

»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

E) Haha — very funny...

»
11 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

There is a better solution for B — with O(m) time :)

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have it :) 46223705

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro can u explain how are you able to calculate no i*i % m = k for a particular val

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your code?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    of course O(m)

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    In addition to provided solution:

    Instead of looping for every pair, you can loop through one dimension (loop through i^2) and calculate a vector which stores how many values mod m are equal to the index ( for i = 1 to m: vector_i[i^i mod m] ++ ). After this, do it for the other dimension (vector_j), and then sum all the products where indices give m when summed (for i = 1 to m: sum += vector_i[i] * vector_j[m-i]). Another note, since we are working with a square, vector_i and vector_j are in fact the same, so you need just one array.

»
11 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Very fast edutorial, thanks a lot for a contest !

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    Edutorial is much better word than editorial.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why set intersection in A problem doesn’t work?

»
11 months ago, # |
  Vote: I like it +23 Vote: I do not like it

How does persistent treap solve G?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    My solution uses a persistent randomized BBST which is rebuilt whenever the depth becomes too large. I don't actually know why it works though ...

    46228890

»
11 months ago, # |
  Vote: I like it +22 Vote: I do not like it

I am dumb. Can anybody tell me in problem E how can we check for a particular length, say l, of r0 the corresponding string formed exactly matches string t in O(|s|) time.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    For each digit in s, compute the hash of the corresponding segment in t. Then compare the hashes.

    To achieve O(s) complexity you need to compute hashes in O(1). Check out the section "Fast hash calculation of substrings of given string" in String Hashing.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Do we have to pray to many hash god that collisions don't happen, that is if collisions happen could it lead to incorrect output?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        If you know a little bit theory, it's possible to prove that hashes work correctly with some reasonable probability (which depends on the number of operations and modulo)

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          At first, I used unsigned long long value for base and nothing define for mod value. as we know, in unsigned operation it works on modulo by 2^64. By this hashing approach, I got wrong answer in test 17. After this, I used a int base and 10^9 + 7 for mod. but it passes. As per I know, unsigned hashing is more secure than other where less collision is occur. If I am worng, please describe my above two process. Thanks in Advance.

          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            No, you are wrong. Hashing with 264 is pretty bad.

»
11 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Delete this

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It doesn't say that the interactive took 13. That last line is both your output and the input. The problem is you took 3 instead of 32. It even says that in the comment

»
11 months ago, # |
Rev. 11   Vote: I like it -25 Vote: I do not like it

has been removed

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

problem G, second approach is very weird. let C[i]=exit station's index when start index is i and start t is n-1. If we do i=C[i] and check visit[i]=true recursively, at some time, C[i] is already visited. Let this time = cyc[i]. I can find a simple rule of max(cyc[i]). It is updated only n=2^k , m=1 or n-1. And max(cyc[i]) is:

n=8192 : max(cyc[i])=141, n=16384 : max(cyc[i])=188, n=32768 : max(cyc[i])=342, n=65536 : max(cyc[i])=475.

Although start t!=n-1 and just repeat (go next station use following algorithm ,t--) n times, we can gain similar value. So this code can accept! (because time complexity is O(475n))

But I can't prove this rule. Why max(cyc[i]) is very small? It seem weird.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    My intuition is as follows. Perhaps a more fitting term would be a mumbo-jumbo hunch.

    Renumber the stations such that 0 is the last red station and consider the last k steps, where k ≤ min(N - M, M). The process does something like this:

    for (int i = k; i > 0; --i) {
       if (s > 0) s -= i;
       else s += i;
    }
    

    Looks familiar? Yes, this is a greedy solution to 2-PARTITION. It is incorrect in the general case, but works quite well in practice if the item sizes are well behaved. In particular, it will return a value close to zero if the ratio of consecutive elements is not too large and there are enough elements. If M is not very close to either 0 or N, this will return a value close to zero, and it will cycle very fast (like in 2-3 steps when ).

    What if, on the other hand, M is very small, say M = 1? Then I would be inclined to say that the amount by which you move counter-clockwise behaves like a random variable. If you move by the same amount twice, it means that You cycled. Due to birthday paradox, this occurs once in every iterations. Your 475 looks quite close to .

    Don't be mad at me. Much smarter and more educated people than me have looked at Pollard-Rho for considerable amount of time and failed to produce anything substantially better than this bullshit.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi, I have a question, I still don't understand why you need to repeat the t-- algorithm n times. Will you help me and clarify that part a bit? Thanks.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, is it because u want to restrict the time deduction to be a multiple of n?

»
11 months ago, # |
  Vote: I like it +47 Vote: I do not like it

,>sees sqrt in solution
,>calls it sqrt decomposition

»
11 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Can you explain me please how to count the number of pairs in the problem B satisfying the condition (x^2 + y^2) mod m = 0 ?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    The n*n matrix of (x^2+y^2) mod m is periodic & can be constructed from a matrix of size at most m*m, so 1000*1000 = 10^6 iterations at most.

    It's due to the fact that for x,y <= m if (x^2+y^2) is divisible by m than ((x+m)^2+y^2) is also divisible by m because ((x+m)^2+y^2) = (x^2+y^2)+(2*m*x+m^2) = (x^2+y^2)+m*(2*x+m).

    The first part is already divisible by m and the second is clearly divisible by m & the same thing goes for y so coordinates (x+m, y) & (x, y+m) are to be counted if they are in n*n.

    Here is a picture that explains when n > m since n <= m is too easy. The total answer will be blue (n/m)^2 + green*2 + red.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F, is it possible to rigorously prove that it's always optimal to solve them from the hardest one to the easiest one? I see that it's intuitive for cases where the difficulties of the problems are spaced out enough (you only have to train once in that case).

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    This is the rearrangement inequality: https://artofproblemsolving.com/wiki/index.php?title=Rearrangement_Inequality

    Let the difficulties of the problems be d1, d2, ..., dk in increasing order. We have factors of 1 / .9, 1 / .92, 1 / .93, ..., 1 / .9k and want to pair each di to a factor then add them up. You should put the highest di with the lowest 1 / .9i because you want to minimize its contribution to the total sum. Similarly, you should put the lowest di with the highest 1 / .9i because you want the small difficulty problems to count the most. So the smallest possible sum is d1 / .9k + d2 / .9k - 1 + ... + dk / .9.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even though for fixed problems set it's optimal to solve in decreasing order, it doesn't help to find out how to fill dp x,k discussed in solution. 0 <= k <= 100 — number of tasks, 0 <= x <= 1000 — total score, total 10^5 "cells" and you need to fill them fast. also, nothing said about relationships in this dp and how to make sure that you don't pick any task twice. If you assume that "solve in same order" means that you should allow tasks one by one same as for knapsack problem, then it means that you should try to add current task for all known "solutions". This leads to for loop over n tasks, and then for loop over whole dp: 100*10^5.

    I had other idea in my mind, but for some reason it fails on third test. I think I have proof of it, maybe I'm wrong. Anyway, I just say once again: provided solution doesn't help me.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This solution: tc*(n*n*(10*n)) works. Sad. I thought there should be something harder. My tc*n*(10*n) solution doesn't work. Looks like there is counterexample.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in B question i get the loop part but not able to understand how we are counting inside loop like the expression ((n-i)/m)*((n-j)/m) can someone expalin this to me

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    if x & y satisfy the condition then xdash = x + pm and ydash = y + qm will also satisfy the condition.

    xdash <= n

    x + pm <= n

    pm <= n-x

    p <= (n-x)/m

    Same for q. Total number can be get by multiplication property of combinations.

»
11 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

For problem G, I'm so dumb that I can't understand how to compute "for each station the station you will end up after that large step" by treap or splay. Who can give me an example?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any clear solution of 1056-H with Sqrt-Decomposition Implementation.

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Does anyone know of a good resource for learning the "strong" approach to G with a persistent treap?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, same question. Someone please explain. ._.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Also to socketnaut.

      I don't know what you mean by "learning", but here is my original solution to that problem: 55510205, if that helps.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in 1056E(check transcription) how we can check a pair(r0,r1) in |s| time , according to me it should be |t|, to check whether a particular pair of length (of string '0' and of string '1') is possible or not i need to cross through string t isn't it, please tell if you have done this

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.