The equation is divided by x^k, so actually the exponents of x are from -k to +k, and when raised to 2*t, coefficients of x^i will give the number of ways in which 2*t numbers between -k to +k will add up to i.

And for Memory to win the final score should be greater than b — a, so we are interested in sum of all the coefficients whose exponents are greater than b — a.

The minimum side is a bound for velocity of increase.

Which part in particular did you failed to convince yourself that the greedy algorithm must be true?

It is interesting that, reversing the problem reduces the problem complexity to a lot than it sounds.If anyone with a greedy solution without "reversing approach" is most welcome.

Proof regarding the approach mentioned here, Lets set (x,y,z) be length at any step.

1. Initially x = b y = b z = b
2. If you notice, the every side length should be increased to min(a, (y + z - 1)). This is the maximum length any side can take. Substituting maximum value obviously minimizes the steps taken.
3. Array of lengths of triangle is always maintained in sorted order.

When I read the problem statement, This idea didn't strike me. Reversing is too powerful tool here I think.

Here is a more detailed write-up of the proof that the greedy algorithm works. As in the explanation, we start with an equilateral triangle with side length b and must get to one with side length a ≥ b.

Proof. Call a triple (x, y, z) valid if x ≤ y ≤ z and x + y > z. In other words, a triple is valid if it is sorted and corresponds to the side lengths of a non-degenerate triangle. We will say (x₁, y₁, z₁) ≤ (x₂, y₂, z₂) (with  ≤  read as "dominated by") if x₁ ≤ x₂, y₁ ≤ y₂, and z₁ ≤ z₂.

Suppose we have (x₁, y₁, z₁) ≤ (x₂, y₂, z₂) ≤ (a, a, a) with all triples valid. We show that (x₂, y₂, z₂) can reach (a, a, a) in fewer steps than (x₁, y₁, z₁) when using an optimal algorithm. To see this note that any sequence of side increases valid on the smaller triple can also be applied to the larger triple. More specifically, suppose we wish to increase x₁ → c. Then we can increase x₂ → max(c, x₂) with the modified triples (once sorted) still both valid and in the same domination order (requires a little checking). The same can be seen for modifying y₁ or z₁. Since the domination order remains respected, the increases can be repeated inductively until reaching (a, a, a).

Starting from any valid triple (x, y, z), we finally note that the side increase to (y, z, y + z - 1) gives a valid triple that dominates all other possible valid triples achievable with 1 increase. To see this first consider increases in z → c. Then c ≤ x + y - 1 and we have (x, y, c) ≤ (y, z, y + z - 1). If instead we increase y → c then we either have (x, c, z) ≤ (y, z, y + z - 1) or (x, z, c) ≤ (y, z, y + z - 1). Lastly, if we increase x → c we either have (c, y, z), (y, c, z) or (y, z, c) all of which are dominated by (y, z, y + z - 1).

Can u please clarify ur recurrence relation,especially the transition of dp(t,i) from dp(t,i-1). Thanks in advance.

ans += (dp[now][i + shift] * pr[max(0,o+shift)]) % MOD;
Can you tell me what this line means? Why we need to multiply dp[][] with pr[]?

The advantage of reversing is that it let us know the max possible value to increase. You just do something like this: a = min(x, b + c — 1).

And how can you solve the problem without reversing? My attempts have failed.

Notice that something like a = max(y, c — b + 1) didnt' work — it can't take us the best answer, you can check it out even in example x = 22, y = 3.

why this(http://beepaste.ir/view/e6b2016b) doesn't work?? I simply added k to everything ... I don't get why using Inclusion-Exclusion principle :(

Really beautiful way! If anyone stumbles upon, the inclusion-exclusion here is by number of steps in which we add >2*k points.

Isn't your array a little bit to small? At most there are 2*k*t+100 points difference between the two players, I believe that is larger than 1e4.

*It is strongly advised to pick up your pen to do a little math to understand the solution better.

I will used the same terms that the editorial uses, L[a,b]= probability dominating from a to b while starting from casino a, R[a,b]= probability of starting from casino b and ending up at casino b+1 without losing at casino a. (The editorial missed out the never losing at casino a part)

From the definitions we can find out the merging formulas of L&R[a,b] and L&R[b+1,c] (a,b,c, in range of n), c does NOT NECESSARILY needs to be n.

For L[a,c], it's a GS sum of L[a,b]*L[b+1,c] (note that L[a,b] makes Memory ends at b+1) + L[a,b] * (1-L[b+1,c]) * R[a,b] + ... (If Memory fails to dominate on interval [b+1,c], then multiply R[a,b] to get him back to position b+1), from the GS sum formula you can end up with a similar formula as shown in the editorial.

For R[a,c], it's a sum of two parts. The first part is R[b+1,c], this is pretty obvious. The second part is the GS sum when Memory fails at casino b+1 but never fails at casino a. The first term of the GS is (chance of failing at casino b+1) * (chance of getting back to b+1 w/o failing at casino a) * (dominating on [b+1,c]), that is (1-R[b+1,c]) * (R[a,b]) * (L[b+1,c]). The ratio of the sequence is (chance of failing to dominate on [b+1,c] = 1 — L[b+1,c]) * (chance of getting back to b+1 w/o failing at casino a = R[a,b]). That also brings us to the formula that the editorial gives.

My implementation: http://codeforces.net/contest/712/submission/20521550

*In case if you don't know understand segment tree, go to learn it before reading this code.

1. Size of interval [ - k, k] is 2k + 1, so for each turn player has 2k + 1 "choices".
2. For t turns each player has (2k + 1)^t "choices".
3. For two players this becomes ((2k + 1)^t)² = (2k + 1)^2t "choices".

Let's solve case, when (l, r) = (1, n), and there are no modifications:

Segment tree:

I'm also not sure, why the constraint p_i ≤ p_i + 1 was given, I (probably) only used the fact that p_i ≠ 0.

Can you please elaborate more on how you join results from the various sqrt segments.

i.e How to do D(l,r) given D(l,k) and D(k+1, r)? Given the definition of dominate, I am not sure how just multiplying these two would work.

Also how did you come up with this: "Given D(l,r) are fractions represent them as 2x1 vector"..

After t turn the minimal difference will be  - 2 × t × k and the maximal will be 2 × t × k so you need 4 × t × k + 1 positions.

Also if you want to have negative indices you can do it with this trick:

# include <bits/stdc++.h>
using namespace std;
int unused[1000005];
# define a (unused + 500000)
int main(void)
{
    a[-1] = -1;
    a[0] = 0;
    a[1] = 1;
    cout << a[-1] << ' ' << a[0] << ' ' << a[1] << '\n';
    return 0;
}

I used this in my submission.20514640

What?

I guess divergence of this process is faster than convergence, that's why.

Let's look at divergence rate, (y,y,y) to (x,x,x):
Take the smallest, and set it to sum of other two-1.
1. Clearly, as long as at least one of the other two is larger than the smallest, the number is multiplies by a real factor of at least 2.0. The only case when the smallest is multiplied by a factor < 2.0 is when all three sides are equal.
We can prove that only happens when all three sides are = y. This is because when we set the smallest to sum of other two-1, we are guaranteeing that this value becomes larger than both the remaining sides(with exception of side=1, which is outside our constraints). Now, from point (1.) we know that we are effectively taking at most log(x/y) steps, as y*(2^steps) >= x.

Let's look at convergence rate, (x,x,x) to (y,y,y): In the first step, set one of the numbers = y. Then, Take the largest, and set it to absolute(difference of other two) + 1.
Therefore, in second step, we have set the largest value = x-y+1.
In third step, we have set the largest value = x-y+1-y+1 = x-2*y+2.
In fourth step, we have set the largest value = x-2*y+2-y+1 = x-3*y+3. and so on.

Thus, total number of steps = 1 + x/(y-1).

Solving for 1+x/(y-1) <= log(x/y) keeping y constant (c = y-1)

x/c <= logx — log((1+c)*2) where c>=2 (constraints)
Using z = x/c
z <= log(z) -log((1+c)*(2*c)). So, never.

Another way of checking for 1+x/(y-1) <= log(x/y)

y=3 : x/2 <= log(x/6) => never
y=4 : x/3 <= log(x/8) => never and so on.

Therefore, rate of divergence is always more than rate of convergence.

So that precision errors dont occur. Look at caze with 5e4 casinos probability (1-e-9) and 5e4 casinos probability (e-9). Precision will give you a very different answer than actual

The problem is actually more mathematical than DP-ish. Start from the value 'a'. There are 2k+1 edges going out, and so on for the further levels. This gives us binomial pyramid like structure. Simply apply formula for last level only.

In case you are asking about the formula itself, I haven't worked it out yet. There's a comment about solving with inclusion exclusion. Maybe you can check it out as well. :)

There are 2 comments above which try to prove it. here's my attempt to prove it. Have a nice day.

A walk is you can go wherever you want, including left of i and right of j. A valid walk, however, means you can't move left of i and you must walk right of j to finish the process.

To get diff-2*k, there's only one way since both players need to get -k. To get diff-2*k+1, there's two ways since players can get -k and -k+1 or -k+1 and -k, respectively, and so on. You can see it's like a dice roll probability distribution with the peak at 0.