Hi everyone, here are the solutions to the contest problems.

Note that *a*[*i*] + *a*[*i* + 1] = *b*[*i*]. Use the initial condition *b*[*n*] = *a*[*n*] and we can figure out the entire array *b*.

Time Complexity: *O*(*n*)

**Code**

First, if *S* has odd length, there is no possible string because letters must come in opposite pairs. Now, let's denote the ending coordinate after following *S* as (*x*, *y*). Since *S* has even length, |*x*| has the same parity as |*y*|. Suppose they are both even. Then clearly, we can make *x* = 0 in exactly moves, and same for *y*. If instead they are both odd, then we can change exactly one x-character into a y-character. With the correct choices of these characters, now our string has |*x*| and |*y*| with even parity, thus reducing to the problem above. Therefore, the answer is (|*x*| + |*y*|) / 2.

Time Complexity: *O*(|*S*|)

**Code**

712C — Memory and De-Evolution

Let's reverse the process: start with an equilateral triangle with side length *y*, and lets get to an equilateral triangle with side length *x*. In each step, we can act greedily while obeying the triangle inequality. This will give us our desired answer.

Time Complexity: *O*(*log* *x*)

**Code**

One approach to this problem is by first implementing naive DP in *O*((*kt*)^{2}). The state for this is (*diff*, *turn*), and transitions for (*diff*, *turn*) is the sum (*diff* - 2*k*, *turn* - 1) + 2(*diff* - 2*k* + 1, *turn* - 1) + 3(*diff* - 2*k* + 2, *turn* - 1) + ... + (2*k* + 1)(*diff*, *turn* - 1) + 2*k*(*diff* + 1, *turn* - 1) + ... + *diff*( + 2*k*, *turn* - 1).

Now, if we use prefix sums of all differences in (turn-1), along with a sliding window technique across the differences, we can cut a factor of *k*, to achieve desired complexity *O*(*kt*^{2}).

However, there is a much nicer solution in *O*(*kt* *log* *kt*) using generating functions(thanks to minimario). We can compute the coefficients of , and the coefficient to *x*^{i} corresponds to the number of ways we can form the difference *i*. To compute these coefficients, we can use the binomial theorem.

Time Complexity: *O*(*kt*^{2})

**Code**

Time Complexity: *O*(*kt* *log* *kt*)

**Code**

Lets think about two segments of casinos [*i*, *j*] and [*j* + 1, *n*]. Let *L*([*a*, *b*]) denote the probability we dominate on [*a*, *b*], and let *R*([*a*, *b*]) denote the probability we start on *b* and end by moving right of *b*. Let

*l*_{1} = *L*([*i*, *j*]),

*l*_{2} = *L*([*j* + 1, *n*]),

*r*_{1} = *R*([*i*, *j*]),

*r*_{2} = *R*([*j* + 1, *n*]).

You can use a geometric series to figure out both *L*([*i*, *n*]) and *R*([*i*, *n*]) using only *l*_{1},*l*_{2},*r*_{1}, and *r*_{2}. To derive these series, think about the probability we cross over from *j* to *j* + 1 once, twice, three times, and so on. The actual formulas are,

Now we can build a segment tree on the casinos, and use the above to merge segments.

Time Complexity: *O*(*N* + *QlogN*)

**Code**

Can someone explain how to solve D using generating functions as mentioned in editorial ?

Auto comment: topic has been updated by trashfirstsearch (previous revision, new revision, compare).Could someone elaborate solution to D ? Didn't really understand it. How is the equation formed ?

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.

Can you explain the code , as far as I know we can solve the numerator as a geometric series , then the coefficients in denominator can be easily found but for the numerator I have not seen a method better than exponential in the number of brackets

Can you please explain why the in the transformation (diff, turn) = ( diff — 1 , turn — 1 ) + 2 ( diff — 2*k + 1 , turn — 1 ) + ........ Why we are multiplying by 2, 3 here?

For C, does anyone have a formal proof that greedy is okay? I had some intuition that's a very handwavy proof, but I don't have a formal proof of correctness. In general, I find that proving greedy algorithms will work is tricky.

Someone please prove this greedy algorithm!!!

The minimum side is a bound for velocity of increase.

This thought was one of the two basis of my intuition, but it's not a formal proof at all.

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.

x=by=bz=bmin(a, (y+z- 1)). This is the maximum length any side can take. Substituting maximum value obviously minimizes the steps taken.When I read the problem statement, This idea didn't strike me. Reversing is too powerful tool here I think.

This is more or less how my intuition went, but it's not a formal proof at all. Your statement "substituting maximum velocity obviously minimizes the steps taken", is extremely hand-wavy. You could say something similar for many kind of problems where greedy doesn't work. For instance, in the coin changing problem: https://en.wikipedia.org/wiki/Change-making_problem

it's well known that greedy isn't optimal for certain coin denominations, yet you could say "maximizing the amount you take away obviously minimizes the steps taken" which is a completely wrong statement, but in my view, quite analogous to your argument here.

Intuition should be enough here because you can just reverse all your steps and it makes pretty good sense.

Alternatively you could also write a brute force, and then just check it yourself.

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

band must get to one with side lengtha≥b.Proof.Call a triple (x,y,z) valid ifx≤y≤zandx+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_{1},y_{1},z_{1}) ≤ (x_{2},y_{2},z_{2}) (with ≤ read as "dominated by") ifx_{1}≤x_{2},y_{1}≤y_{2}, andz_{1}≤z_{2}.Suppose we have (

x_{1},y_{1},z_{1}) ≤ (x_{2},y_{2},z_{2}) ≤ (a,a,a) with all triples valid. We show that (x_{2},y_{2},z_{2}) can reach (a,a,a) in fewer steps than (x_{1},y_{1},z_{1}) 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 increasex_{1}→c. Then we can increasex_{2}→max(c,x_{2}) 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 modifyingy_{1}orz_{1}. 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 inz→c. Thenc≤x+y- 1 and we have (x,y,c) ≤ (y,z,y+z- 1). If instead we increasey→cthen we either have (x,c,z) ≤ (y,z,y+z- 1) or (x,z,c) ≤ (y,z,y+z- 1). Lastly, if we increasex→cwe either have (c,y,z), (y,c,z) or (y,z,c) all of which are dominated by (y,z,y+z- 1).Thanks. Aside from the minor issue that you didn't prove you should never decrease your edge, I think this is a complete proof.

Nonetheless, I'm a bit perplexed that so many people solved this question during the contest. I did too, but only because I kinda gave up on proving its correctness and hoped my intuition was correct... I imagine most people did what I did which kinda makes this problem bizarre in that in punishes people who are more careful than me (I believe something they should be rewarded for). I think such questions aren't good for contests as it encourages just random stabs at a solution (which you would never do in real life).

For Problem D, See my O(kt^2) implementation. Here

Main idea : dp(t,i) can be calculated easily using dp(t,i-1) and dp(t-1,i+k) and dp(t-1,i-k-1).. See , dp(t,i) and dp(t,i-1) has much in common.

here dp(t,i) means # of ways to achieve i, after t rounds.

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

Let

dp[i][j] be in how many ways you can achieve differencejiniturns.1.

dp[0][0] = 1.2..

You can easily check that

dp[i][j] =dp[i- 1][j- 2k] +dp[i- 1][j- 2k+ 1] × 2 + ... +dp[i- 1][j- 1] × 2k+dp[i- 1][j] × (2k+ 1) +dp[i- 1][j+ 1] × 2k+ ... +dp[i- 1][j+ 2k- 1] × 2 +dp[i- 1][j+ 2k].Finally to get an

O(kt^{2}) solution you can see that:which can be found with partial sums.

Here is my implementation.20514640

How did you simplify from 2nd last equation to last equation ??

Try to find

dp[i][j- 1] -dp[i][j] using the third relation.dp[i][j- 1] -dp[i][j] = - (dp[i- 1][j- 2k- 1]) × (1 - 0) - (dp[i- 1][j- 2k]) × (2 - 1) - ... - (dp[i- 1][j- 1]) × (2k- (2k- 1)) - (dp[i- 1][j]) × (2k+ 1 - 2k) + (dp[i- 1][j]) × (2k+ 1 - 2k) + ... + (dp[i- 1][j+ 2k]) × (2 - 1) + (dp[i- 1][j+ 2k+ 1]) × (1 - 0)Understood.

I tried to implement your formula but it gives me some negative intermediate result. With

`dp[i][j] = dp[i][j-1] - sigmaA + sigmaB`

, I found that there are cases where`sigmaA > sigmaB`

so`dp[i][j]`

goes negative. Is my implementation wrong 'cause`sigmaA > sigmaB`

will never happen technically or do I need special treatment for this case?http://codeforces.com/contest/712/submission/20563138

If

sigmaA<sigmaBaddsigmaA-sgmaB+MODotherwisesigmaA-sigmaB.I found the problem. it was modulo operation:

`for(int j = left; j <= right; j++){ dp[i][j] = j-1 >= 0 ? dp[i][j-1] : 0; dp[i][j] += (psum[min(MAXGAP, j + 2*k)] - (j - 1 >= 0 ? psum[j - 1] : 0)) % MOD; dp[i][j] -= (psum[max(0, j - 1)] - (j - 2*k - 2 >= 0 ? psum[j - 2*k - 2] : 0)) % MOD; dp[i][j] = dp[i][j] % MOD; }`

When I calculate

`dp[i][101]`

, it uses not`dp[i][100]`

, but`(dp[i][100] % MOD)`

. How stupid I was :(I popped that final modulo calculation out to another loop and now it gives me correct answer.

`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[]?

I can't understand this

ans += (dp[now][i + shift] * pr[max(0,o+shift)]) % MOD;Can you tell me why?In questions C without reversing the question and decreasing the side instead of increasing, we can still solve the question greedily, right?

What advantage is reversing the question giving us?

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.

D can be solved with Inclusion–exclusion principle in

`O(Kt^2)`

.we can calculate how many way to get X scores in

`O(t)`

, and all possible scores in`O(Kt^2)`

, then we can easily get the answer.see Submisson

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.

Can anyone explain O(ktlogkt ) approach for problem D?? In,particular how to get expression for pref2[i]??

i am getting runtime error on test case 15. but i am not able to see test case.can anybody help here is submission link:submission

When will be the test cases be visible. I am getting runtime error on test 15 for Div2D. The solution is a simple 0(k^2 . t) top-down dp carrying differences of score with an offset. Need some help with this. My Code Thanks in advance.

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.

Well thanks for pointing that out , now after I corrected that mistake , and also reducing the time complexity to O(KT) , the solution is giving Time limit exceeded on test case 15. Can you point out the mistake. Where am I going wrong. 20525457

Your solution does not work in O(KT).

There are O(K*T) states for each turn of the game, and a total of O(K*T*T) states for the whole game, and you're taking O(K) time to compute each state of it, so that's O((KT)^2) in total.

The editorial have mentioned two ways of optimization. Both of them fits in the time limit, feel free to use the one that you are comfortable with. The first approach is about the sliding windows technique and prefix sum, and the second approach is about divide and conquer with an observation on the binomial coefficients.

here is my submission for problem D use partial sum 20521519 . One loop I use about 4 * 2 * MAXSCORE. Total operation ~ 800000 * t (don't contain +mod or -mod) and runtime is 200ms. CF is very fast !! PS: My source code use tab 2 and when I submit it is hard to read. How can I fix it? sorry for my bad English

Can someone explain me C in more detail, please.

Can someone please elaborate on the explanation of E.

*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.com/contest/712/submission/20521550

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

Can someone explain in Problem D, How's total number of games played will be (2*k+1)^(2*t) ??

k,k] is 2k+ 1, so for each turn player has 2k+ 1 "choices".tturns each player has (2k+ 1)^{t}"choices".k+ 1)^{t})^{2}= (2k+ 1)^{2t}"choices".Can someone clearly explain how we can get the formulas in problem E?

Let's solve case, when (

l,r) = (1,n), and there are no modifications:solve system of linear equationsConsider a walk on casinos 0, 1, 2, ...,

n,n+ 1 (0 corresponds to a state "lost in casino 1",n+ 1 corresponds to "won in casinon").Denote

f_{i}= "the probability to get into casinon+ 1, if we're in casinoi",i= 0, 1, ...,n+ 1, Δ_{i}=f_{i}-f_{i - 1},i= 1, 2, ...,n+ 1, , and .We know that

f_{0}= 0,f_{n + 1}= 1, andf_{i}= (1 -p_{i})·f_{i - 1}+p_{i}·f_{i + 1}(i= 1, 2, ...,n). We need to calculatef_{1}= Δ_{1}(a.k.a. solve system of linear equations).Rewrite this equation as

f_{i}-f_{i - 1}=p_{i}·(f_{i + 1}-f_{i - 1}), rewrite using Δ to get Δ_{i}=p_{i}·(Δ_{i + 1}+ Δ_{i}), rewrite again and this becomes .Remember that Δ

_{1}+ ... + Δ_{n + 1}= (f_{1}-f_{0}) + ... + (f_{n + 1}-f_{n}) =f_{n + 1}-f_{0}= 1, so Δ_{1}(1 +u_{1}+u_{1}·u_{2}+ ... +u_{1}·u_{2}·...·u_{n}) = 1, and finally (formula forf_{1}that we were looking for)Segment tree:

segmentsGeneral case (note: in segments I store quantities different from those in authors solution)

for segment [

L,R] store valuesA_{[L, R]}= (u_{L}·u_{L + 1}·u_{L + 2}·...·u_{R}) andB_{[L, R]}= (u_{L}+u_{L}·u_{L + 1}+u_{L}·u_{L + 1}·u_{L + 2}·... +u_{L}·u_{L + 1}·...·u_{R}).Recalculate them like this:

A_{[L, R]}=A_{[L, M]}·A_{[M + 1, R]},B_{[L, R]}=B_{[L, M]}+B_{[M + 1, R]}·A_{[L: M]}.The answer for [

L,R] will be .I'm also not sure, why the constraint

p_{i}≤p_{i + 1}was given, I (probably) only used the fact thatp_{i}≠ 0.It was given becauze consider a test case of 50000 casinos with probability (1 — 1e-9) followed by 50000 casinos with probability 1e-9. Answer over whole interval should be 0.5(I think), but precision will make it 0.

How would one prove that something "bad" (imprecision due to overflows) wouldn't happen with condidion

p_{i}≤p_{i + 1}?Thanks for explanation. I couldn't get the editorial from the post :(

nicely explained thanks

For E I used sqrt decomposition with the following idea:

Let

D(l,r) denote probability to dominate on [l,r]if

l=r, thenD(l,r) =a_{r}/b_{r}else

D(l,r) =p_{l}* (D(l+ 1,r) + (1 -D(l+ 1,r)) *D(l,r))The idea is simple: if at beginning, we move to left at

l(probabilty (1 -p_{l}), we lose.So now we've moved from

ltol+ 1, and there are two cases: Either we dominate in (l+ 1,r), or we move left (thus don't dominate) and return back toD(l,r).So we can compute

D(l,r) fromD(l+ 1,r) like this transform:D(l,r) =D(l+ 1,r) / (D(l+ 1,r) - 1 + 1 /p_{l})Since

D(l,r) are fractions, represent them as a 2x1 vector denotingAnd we see that if we apply the above transform, it's just multiplying matrix by vector and getting a new vector.

Now just build a sqrt decomposition or a segment tree to quickly get matrix multiplication for segments and multiply it by

p_{r}.Submission http://codeforces.com/contest/712/submission/20531915

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"..

I treat fractions as vectors

So we have the formula

D(l,r) =D(l+ 1,r) / (D(l+ 1,r) - 1 + 1 /p_{l})Let's shortcut it as following:

D(l,r) =F_{l}(D(l+ 1,r))Here

F_{l}is a transform that takesD(l+ 1,r) as input and outputsD(l,r)D(l,r) =F_{l}(D(l+ 1,r)) =F_{l}(F_{l + 1}(D(l+ 2,r)) =F_{l}(F_{l + 1}(F_{l + 2}(D(l+ 3,r))) = ... =F_{l}(F_{l + 1}(F_{l + 2}(F_{l + 3}(...F_{r - 1}(D(r,r))))))Let's see how

F_{l}acts on fractionsAfter simlplifying we get

So we see that

F_{l}takes a fraction and transforms it into another fraction, whose coefficients are linear combination of source coefficients.This can be written like this:

Let's call this

F_{l}operator matrixM_{l}and letC(l,r) beD(l,r) represented as a 2x1 vector corresponding to its fraction. E.g. ifD(l,r) is ,C(l,r) will beC(l,r) =M_{l}*M_{l + 1}* ...M_{r - 1}*C(r,r)So all we need is to know how to quickly compute product of matrices on a segment. Use segment tree or sqrt decomposition for this.

Also this solution doesn't seem to use the knowledge that

p_{l}is non-decreasing in any way. —Oops, this is false, this is actually needed since otherwise we would lose too much precision,as described here: http://codeforces.com/blog/entry/47050?#comment-314304Have a look at these two submissions for problem D: 20533661 20534239

The first one fails on test 17, but the other gets AC. The only difference is changing the shift length and the limit. Why is this? I thought I checked whether or not the space was large enough already, and even now I'm not sure why it was a problem.

After

tturn the minimal difference will be - 2 ×t×kand the maximal will be 2 ×t×kso you need 4 ×t×k+ 1 positions.Also if you want to have negative indices you can do it with this trick:

I used this in my submission.20514640

Nice trick, by the way. I think I understand where I went wrong now. Thanks.

Probably there is solution for D which uses fact that after multiple convolution we get very close to normal distribution...

What?

Hi, for problem C, can someone explain

Why does counting down give a separate answer as compared to counting up?

Greedy Approach

Example

22 to 4

22,22,22->22,22,4->22,19,4->16,19,4->16,13,4->10,13,4->10,7,4->4,7,4->4,4,44 to 22

4,4,4->4,4,7->4,10,7->16,10,7->16,10,22->16,22,22->22,22,22why counting up gives us the solution? (proof for correctness)

I was thinking of a DP solution for it(counting down). Is it a special case, where the optimal solution of a subproblem same as the greedy solution?

Counting down means moving from 22 to 4.

Counting up means moving from 4 to 22.

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. The only case when the smallest is multiplied by a factor < 2.0 is when all three sides are equal.2.0We 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 toabsolute(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.

I guess there has to be explanation of why this greedy work,i am really curious how did people come up with this solution during the contest,i was thinking of DP all the time,trying reverse counting would never come up to my mind and if it did i am not sure if i would write it as i am unable to prove the corectness of it.

in the name of allah, most merciful

when you counting up you follow this greedy:

min side of three side = min(max amount of side that triangle has positive area, x)

where x is side that we want have it by counting up.

but when we count down we don't have main idea and we don't know what is next step.

Blank

in the name of allah, most merciful

(b1 = a1 + a2 and bn = an) is correct and (he or she) makes mistake

i think (he or she) use a instate of b because at the end there is this statement we can figure out the entire array a.

proof:

if(x != n)

{

a[x] == b[x] — b[x+1] + b[x+2] — b[x+3] + ... (-or+)* b[n];

a[x+1] == b[x+1] — b[x+2] + b[x+3] — ... (+or -)*b[n];

so a[x] + a[x+1] == b[x];

}

else

a[x] == b[x]

I just solved Problem E with two segment trees, just like the official solution. But I still don't know why the problem needs the condition that the probabilities are in non-decreasing order. Even I solved without using that condition and got AC. Is it just a fake condition?

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

oh I see. thx

Can someone explane me solution in complexity

O(ktlogkt) for fourth task in more details ?I solved task in the first complexity and that is not problem, but I can not understand how we generate polynom from the solution and why coefficient near

x^{i}is equal toDP[t][i] ?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. :)

Hi every one , for problem D I didn't hear about sliding window technique before , so i read about it and i got a shallow idea about it, but still not unerstood how we can use it here , i didn't understand anything about that, reading the editorial and the implementation .

can any one help me with details. thanks in advanse.

Can you prove the greedy approach for Div2C , during the contest I first thought of doing greedily from larger sided triangle to smaller one , obeying triangle inequality , which was incorrect. But the doing the same thing from smaller to larger passes.

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

Can someone explain to me the

problem statementof E? What is a valid walk here? We can never go left ofibut we can go right ofj? Also, why is the statement given as`Note that Memory can still walk left of the 1-st casino and right of the casino n and that always finishes the process.`

if we can never go left ofi?Please help.

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.

So, as soon as I walk right of j, is my walk over? Or can I go right of j as many times I want, but I have to return to j and then win in order to finish my walk?

Walk ends the first time you go right of j.

Thank you :)

problem D:

for input 1 1 1 2

how the ans can be 31 ?? please explain me someone :)

I found myself trapped in some kind of (seemingly) paradox in problem E.

For each position i, we can get a probability pr[i] for returning to position 1. Obviously, pr[] is non-decreasing. Now there is a problem. We have 1-pr[i] probability to go back to position 1, but pr[i] is definitely not the probability you can get to destination (it is just the probability to get to i+1). However as the procedure is infinitely repeated until getting to the destination(on either side), so outside 1-pr[i] we must reach the other end.

Where is my fault in reasoning?

Hey guys,

Can anyone please take a look at my solution to D and suggest any improvements. It gets accepted and it seems to be running quite fast but I would like to improve it :)

http://codeforces.com/contest/712/submission/20639410

Why the complexity of problem C is O(log x). I didn't get it.

Can you please explain why the in the transformation (diff, turn) = ( diff — 1 , turn — 1 ) + 2 ( diff — 2*k + 1 , turn — 1 ) + ........ Why we are multiplying by 2, 3 here?

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.

Got that. Thanks a lot.

can not understand the solution. if at current turn, both player get -k , then their new difference should not be diff+(-k-(-k))=diff+0 ??

yes, it will be but the total number of ways will be ( 2k + 1 ) like ( — k + 1 — ( — k + 1 ) )

( k — 1 — ( k — 1 ) ) and so on

I believe D can be solved using an easier version of prefix sums.Just calculate number of ways to get a particular score after t turns for a person, then final answer is just the appropriate convolution of the score combinations which can again be done with the already calculated prefix sums.

can anyone explain me in problem C why decreasing greedily wont work my solution is 84129102