For problem F. Why it's x >= y' < y?

I think it should be x <= y' < y.

the solution of e part says that if solution exists then the root node will be the center of the diameter.

can someone please give an intuitive or rigorous proof of this statement.

Beautiful F with a great idea!

Can you please explain why Test case 15 in 765C will result in -1? shouldn't it be 10?

“Obviously, now the answer for all left endpoints in range [j, i - 1) is y - x” The segment containing both Ai and Aj should has a left endpoint L <= j , And why the answer for the segments with left endpoint in range [j , i-1) also is y — x?

Hi fellows!

For problem G (didn't get to it during the contest), I would have the following approach which I believe is simpler and takes running time complexity:

1. Let t0 be the index of the first 0 in the string. Then we have k+t0 = 0 (mod N). However, for all subsequent ti > t0 (up to 40) where we have 0 in the string we must have k+ti = 0 (mod N). Substracting the first (for t0) equation we have k+ti-(k+t0) = 0 (mod N) which means ti — t0 == 0 (mod N). Notice that this does not involve k at all! Thus, for all relationtions with 0 in the string, except the first one we can just check if ti — t[i-1] is divisible by one of the primes in N. If one does not satisfy, then there is no solution.

2. For the first relation with 0 in the string, we iterate over all primes in N (n in total) and try to make k + t0 mod pi == 0 [mod pi], which means k == pi-t0 [mod pi] AND k + t0 != 0 [mod p0, mod p1, .., mod pi-1].

3. For all positions z0,z1,.. in the string where we have 1, we must have k+zj != 0 [mod p1], k+zj != 0 [mod p2] and so on. Thus we must have for each zj that k != pi-zj [mod pi].

4. This means that for each pi we have several posibilities which satisfy: all which are not pi-zj AND which are not pi-tj (for the "lower" primes determined in step 2 above) AND for the particular prime P chosen in step 2 the reminder must be -t0. Thus, we have for all primes p1, p2, .., pn, a "list" of some posibilities for the reminder of k mod pi. By the chinese reminder theorem THERE WILL BE A SINGE SOLUTION to these modulo p1*p2*..*pn = B. Thus, there will be a total of |List1|*|List2|*..*|ListN| solutions for a particular prime P chosen at step 2 modulo B. Each List_i will be reduced in size (from pi-1) by at most 2*|s| or will hold a single element, so determining the sizes of the lists is easy. The solutions for different P's (chosen at step 2) are guranteed to be distinct since the same k cannot satisfy the conditions of step 2 for two distinct P's.

5. We compute in O(n) the total number of solutions mod B by doing step 4 for each P chosen in step 2. Let this number be T.

6. Let p1*p2*..*pn = B. We know that for each solution S in [0..B] we also have as solution S+B. Thus, if we are lucky and N%B == 0, the total number of solution will be (N/B)*T.

7. If we are unlucky and N%B != 0, some of the solutions mod B will not be available for "the final step" between floor(N/T) and N. I haven't yet figured what to do in this case, but i think the approach might have some merit even up to here so I decided to share it.

What do you think about this approach? Are there any obvious flaws in it? Do you think it could be made to work?

Best, Mircea

For problem E, I don't quite understand the definition of y' (or how's the array to be segment tree be defined?), as the array is decreasing shouldn't y be the perfect candidate that's been included in [l, r]?

For problem F,"We find the first element to the left of i which is not less than x." How can I do it within the complexity of O(logn)?

Hah, I thought my approach to G had to be the wrong one, given how much time I needed to spend during the contest to get the "5 7 ..." case to perform reasonably. For comparison: http://mirror.codeforces.com/contest/765/submission/24667492

My solution has one optimization I don't see in either of KAN's or Endagorion's solutions: it checks if S is a palindrome, and in that case cuts the search space in half by treating masks as equivalent to their bit reversals. This sounds silly, but it actually deals nicely with the all-zero case, and the other cases are a factor 1.5 — 2 faster by virtue of having a forced one somewhere.

For problem F, i am still confused about the complexity. The step where we find some aj' = y' such that x ≤ y' < y and j' < j and then repeat it can end up in linear time. In the worst case, the complexity can go up to O(N * M).

Can someone explain in another way what we have to do in D? Condition is a bit difficult to understand..

Какой ответ на этот тест в G?

Все зашедшие на контесте решения, написанные без особых оптимизаций, выдают 150056. Единственное (которое как обычно зачем-то сабмитнули 4 человека) решение, которое получает ОК на новых тестах, выдает 0, что уже довольно странно. А вообще к чему это я  –  есть подозрение, что авторское решение сейчас выдает неправильный ответ на 96 тест.

What is the two-way Tree DP being talked about in the editorial of E Problem?