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

The problem H has been created by _kun_.

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: 44522542Solution by Endagorion: 44519413 (maximal spanning tree)

Tutorial is loading...

Jury's solution: 44522571
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.

Could you please elaborate why this is working?

Auto comment: topic has been translated by isaf27 (original revision, translated revision, compare)When editorial will be available in English

Soon

Use Google Translator

Google translate has certain problems while displaying mathematical things.

Time to learn some russian I guess.

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

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

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ásA_{ i}o agarrás el complemento deA_{ i}. Fijate cuál apareció menos veces en los prefijos que ya pasaron y usá esa. Es greedy la solución. Pasa.arigatou!!!

Please post editorial in English as well.

Now editorial is available. Sorry for waiting.

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 mostp- 1. Say we could computet_{ i}=q(c^{ i 2}) for alli= 0, 1, ...,i- 1. Then we would be set, because then the answer is simplyThere is an algorithm that does polynomial multi-point evaluation (exactly the thing stated) in time where

nis the number of points anddis the degree of the polynomial. This would give a "linear" time solution, except it runs way too slowly.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 numberpfor all numbers 1, ...,p- 1.And multipoint evaluation in was intentionally cut out by authors.

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.

In C. Candies Distribution,Since a[i] is no. of Candies a ith Child will get,how is a[i] going to be (n-l[i]-r[i]) because (n-l[i]-r[i]) is the no. of Children who got less Candies than ith Child or equal Candies to ith Child Candies??

thanks for english edition

Can anyone please explain the solution to Problem D?

The solution relies on two/three ideas:

First idea:

Xor sum idea.So basically we can observe a xor a = 0. This is because every digit is the same, and thus each position becomes 0. And that a xor 0 = a. We can use this to get range xors in O(1). For example: (xor of a[1..R]) xor (xor of a[1..L-1]) = xor of a[L..R] because elements from 1 to L-1 get cancelled out.

Second idea:

comp(a) xor b = comp(a xor b)And let us define comp(x) as flip the first k bits of x and return it. Well then comp(x) = x xor (2^k)-1, because 2^k-1 stores all 1 which will flip each bit. And by definition of xor (add each digit and mod 2), it is commutative and thus it don't matter when you xor by (2^k)-1.

Third Idea:

we can arbitrarily set the prefix_xor[i] valuesLet us define p[i] = a[1] xor a[2] ... xor a[i]. So by definition of problem we can always set the array a[i] to comp(a[i]). But by our previous definition of comp(x), we can see it something like comp(a) xor b xor c = comp(a xor b xor c). So xor'ing position i will affect p[i+1], p[i+2] and so on. But if you xor position i+1 it will cancel the effect. Therefore we can arbitraily set p[i] to comp(p[i]) by doing xor on a[i] and then again on a[i+1].

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.

Can anyone explain why the

O(n^{3}) solution of F run such fast ?IN D:

min(pi,(pi)')

why we take min??

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)

thanks for reply

please anyone explain solution of c

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