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

I have it :) 46223705

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.

Edutorial is much better word than editorial.

it should and it does :) 46211365

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

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.

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

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.

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.

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.

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

Let the difficulties of the problems be d₁, d₂, ..., d_k in increasing order. We have factors of 1 / .9, 1 / .9², 1 / .9³, ..., 1 / .9^k and want to pair each d_i to a factor then add them up. You should put the highest d_i with the lowest 1 / .9ⁱ because you want to minimize its contribution to the total sum. Similarly, you should put the lowest d_i with the highest 1 / .9ⁱ because you want the small difficulty problems to count the most. So the smallest possible sum is d₁ / .9^k + d₂ / .9^k - 1 + ... + d_k / .9.

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.

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.

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