I was solving a problem, but I couldn't do it. So I looked at the editorial, in witch this was given:

(X + Y) / (A + B) <= MAX{X / A, Y / B}

where X, Y, A, B >= 0 and are integers.

So my question is, what is the proof to that? Sorry for the stupid question, but I couldn't find this anywhere.

How does one prepare for IOI like style contests (the same difficulty as the IOI). So what kind of tasks should I solve?

I was solving a segment tree problem in witch you are given:

Update L, R. — updates [L;R] with the value of the current operation (1, 2, ... M)

Query. — count different elements in [0; N]

N <= 10^7

M <= 4 * 10^4

I couldn't come with an aproach. I will be really happy if someone helps me with it. Thankd in advance! :)

Am I the only one who is really curious about who will be the next coordinator?

Hello guys :)

Today I tried to solve IOI 2015's first problem (Boxes with Souvenirs). I thought of dynamic programming:

dp[i] = min(dp[j] + min(l, 2 * (l - pos[j + 1]), 2 * pos[i]) ( j >= i — k and j < i)

So this algo is O(N^2) and it time limit. My question is how to reduce it to O(N).

Thanks in advance :)