### isaf27's blog

By isaf27, history, 5 years ago, translation,

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.

Jury's solution: 44522356

Jury's solution: 44522430
Jury's solution: 44522470
Jury's solution: 44522488
Jury's solution: 44522506
Jury's solution: 44522527
Jury's solution: 44522542

Solution by Endagorion: 44519413 (maximal spanning tree)

Jury's solution: 44522571
• +55

| Write comment?
 » 5 years ago, # |   +22 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.codein the end it goes almost to the same solution.
•  » » 5 years ago, # ^ |   +3 Could you please elaborate why this is working?
 » 5 years ago, # |   0 Auto comment: topic has been translated by isaf27 (original revision, translated revision, compare)
 » 5 years ago, # |   +14 When editorial will be available in English
•  » » 5 years ago, # ^ |   -30 Soon
•  » » 5 years ago, # ^ |   -16 Use Google Translator
•  » » » 5 years ago, # ^ |   +15 Google translate has certain problems while displaying mathematical things.
 » 5 years ago, # |   0 Time to learn some russian I guess.
 » 5 years ago, # |   -32 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
 » 5 years ago, # |   +3 Editorial for problem D is in Rusian! I dont understand :(
•  » » 5 years ago, # ^ |   +41 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.
•  » » » 5 years ago, # ^ |   +11 arigatou!!!
 » 5 years ago, # |   0 Please post editorial in English as well.
•  » » 5 years ago, # ^ |   +3 Now editorial is available. Sorry for waiting.
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   +10 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.
 » 5 years ago, # |   0 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.
 » 5 years ago, # | ← Rev. 3 →   +2 Can anyone please explain the solution to Problem D?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 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.
 » 5 years ago, # |   0 Can anyone explain why the O(n3) solution of F run such fast ?
 » 5 years ago, # |   +4 IN D:min(pi,(pi)')why we take min??
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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<
 » 5 years ago, # |   0 please anyone explain solution of c
•  » » 5 years ago, # ^ |   0 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) = nWell 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