isaf27's blog

Mail.Ru Cup 2018 Round 1 — Editorial
By isaf27, history, 6 years ago, translation, In English

Problems A-G have been created by isaf27. The idea of the problem A has been offered by peltorator.

The problem H has been created by cdkrot.

Tutorial is loading...

Jury's solution: 44522356

Tutorial is loading...
Jury's solution: 44522430
Tutorial is loading...
Jury's solution: 44522470
Tutorial is loading...
Jury's solution: 44522488
Tutorial is loading...
Jury's solution: 44522506
Tutorial is loading...
Jury's solution: 44522527
Tutorial is loading...
Jury's solution: 44522542

Solution by Endagorion: 44519413 (maximal spanning tree)

Tutorial is loading...
Jury's solution: 44522571
  • Vote: I like it
  • +55
  • Vote: I do not like it

Comments Comments (24)
| Write comment?
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

A bit different approach for D: lets build the answer greedily. On each moment add value, which will minimize the number of bad segments ( when current prefix is equal to some previous). lets just pick best for it.

code

in the end it goes almost to the same solution.

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

    Could you please elaborate why this is working?

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

Auto comment: topic has been translated by isaf27 (original revision, translated revision, compare)

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

When editorial will be available in English

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

Time to learn some russian I guess.

→ Reply
»
6 years ago, # |
  Vote: I like it -32 Vote: I do not like it

If you wanna know how to solve H easily using FFT, you can read my blog entry explaining a very simple FFT implementation.

FFT made easy

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

Editorial for problem D is in Rusian! I dont understand :(

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

    OK, I'll try to explain in Spanish then.

    La solución es con prefijos de xors. Suponé que vas a procesar la posición i. Tenés dos opciones, o agarrás Ai o agarrás el complemento de Ai. Fijate cuál apareció menos veces en los prefijos que ya pasaron y usá esa. Es greedy la solución. Pasa.

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

Please post editorial in English as well.

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

    Now editorial is available. Sorry for waiting.

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

Here is a linear time solution for H that doesn't pass any tests (I'm just writing it here because I think it's cool).

Consider the polynomial , where the modulo in the exponent is OK because of Fermat's little theorem. Then the degree of q(x) is at most p - 1. Say we could compute ti = q(ci2) for all i = 0, 1, ..., i - 1. Then we would be set, because then the answer is simply

There is an algorithm that does polynomial multi-point evaluation (exactly the thing stated) in time where n is the number of points and d is the degree of the polynomial. This would give a "linear" time solution, except it runs way too slowly.

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

    I actually mentioned it in my earlier comment, but I also wrote there how to solve problem in to find all values of some polynomial P(x) modulo prime number p for all numbers 1, ..., p - 1.

    And multipoint evaluation in was intentionally cut out by authors.

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

In problem H, you can also handle all three components simultaneously by applying FFT to the 491 and 499 dimension and FWT to the 2 dimension.

See my code here if necessary.

After all, problem H is such a fantastic problem that I really enjoyed it.

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

Can anyone please explain the solution to Problem D?

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

    The solution relies on two/three ideas:

    First idea:

    Xor sum idea.

    Second idea:

    comp(a) xor b = comp(a xor b)

    Third Idea:

    we can arbitrarily set the prefix_xor[i] values

    Now this leads us to the solution. For every value X in the array have an "corresponding" value of comp(X), which we can interchange by definition of the problem. We only want one of them, say, the minimum. (other methods of separating works).

    Then for each we assign roughly half of X to comp(X) so to minimize repeat occurences of X in the prefix xor sum (p[i]). Why? Because (a xor a) = 0, and thus it is a bad subarray.

    We can count the answer fast now using formula. N positions * N-1 other positions / 2 because we both consider (A -> B) and (B -> A) gives us formula cnt(cnt-1)/2 bad positions if there are cnt amount of element X in the result array.

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

Can anyone explain why the O(n3) solution of F run such fast ?

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

IN D:

min(pi,(pi)')

why we take min??

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

    We could also take max, or number with most/least one bits, or anything else that always divides numbers into two categories: the basic idea is that we don't want pi and (pi)' to both be counted, only one of them.

    In the case we take max, treat the 0 index as (1<<k)-1 instead of 0.

    My code: 44885325

    Edit:

    Of course, you don't need to even use some separating function. Instead you can count the solution twice by calculating bad sequences for x with the sum of the count of x and x'. But then you subtract twice the amount, so you need to account for overcount. (i.e divide subtracted amount by 2)

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

please anyone explain solution of c

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

    Even though I am just restating editorial, hope it helps

    Let's first ignore the whole L an R thing. Instead we can make array, let's say, g[i] where as position i there are g[i] other element greater than it. Well g[i] = L[i] + R[i].

    Now we can also observe that if (elements > x) + (element <= x) = n

    Well that means g[i] + (element <= x) = n, and thus the amount of elements less than or equal value at position i = n-g[i] = (n-L[i]-R[i]).

    Now let us say there are k elements less than or equal to than the current element (one of the k elements may be the current element itself). If L and R are valid then then you can just assign current element as k. So ans[i] = (n-L[i]-R[i]).

    If L and R are consistent by definition it will always be an answer. If the L and R is not valid, when you check this resulting array, there will be problems so we can say it is impossible

    → Reply