## 517A — Vitaly and Strings

To solve this problem we can, for example, find string *next*, which lexicographically next to string *s* and check that string *next* is lexicographically less than string *t*. If string *next* is lexicographically smaller than string *t*, print string *next* and finish algorithm. If string *next* is equal to string *t* print *No* *such* *string*.

To find string *next*, which lexicographically next to string *s*, at first we need to find maximal suffix of string *s*, consisting from letters '*z*', change all letters '*z*' in this suffix on letters '*a*', and then letter before this suffix increase on one. I.e. if before suffix was letter, for example, '*d*', we need to change it on letter '*e*'.

Asymptotic behavior of this solution — *O*(|*s*|), where |*s*| — length of string *s*.

## 517B — Tanya and Postcard

To solve this problem at first will count array *cnt*[], where *cnt*[*c*] — how many times letter *c* found in string *t*. We will count two numbers *ans*1 and *ans*2 — how many times Tanya will shouts joyfully *YAY*! and how many times Tanya will says *WHOOPS*.

Let's iterate on string *s* and if *cnt*[*s*[*i*]] > 0, then increase *ans*1 on one and decrease *cnt*[*s*[*i*]] on one.

Then let's again iterate on string *s*. Let *c* is letter which equal to *s*[*i*],but in the opposite case for it. I. e. if *s*[*i*] = '*w*', then *c* = '*W*'. Now, if *cnt*[*c*] > 0, then increase *ans*2 on one and decrease *cnt*[*с*] on one.

Now, print two numbers — *ans*1 and *ans*2.

Asymptotic behavior of this solution — *O*(|*s*| + |*t*|), where |*s*| — length of string *s* and |*t*| — length of string *t*.

## 517C — Anya and Smartphone

To solve this problem we will store two arrays — *a*[] and *pos*[]. In array *a*[] will store current order of icons, i. e. in *a*[*i*] store number of application, icon which stay on position *i*. In array *pos*[] will store on which place in list stays icons, i. e. in *pos*[*i*] store in which position of array *a*[] stay icon of application number *i*. We will count answer in variable *ans*.

Let's iterate on applications which we need to open. Let current application has number *num*. Then to *ans* we need add (*pos*[*num*] / *k* + 1). Now, if icon of application number *num* doesn't stay on first position in list of applications, we make the following — swap *a*[*pos*[*num*]] and *a*[*pos*[*num*] - 1] and update values in array *pos*[] for indexes of two icons which numbers *a*[*pos*[*num*]] and *a*[*pos*[*num*] - 1] .

Asymptotic behavior of this solution — *O*(*n* + *m*), where *n* — number of applications, *m* — number of requests to start applications.

## 517D — Ilya and Escalator

To solve this problem let's use dynamic programming. We will store two-dimensional array *z*[][] with type *double*. In *z*[*i*][*j*] will store the likelihood that after *i* seconds *j* people are on escalator.

In dynamic will be following transitions. If *j* = *n*, i. e. all *n* people already on escalator then we make transition *z*[*i* + 1][*j*] + = *z*[*i*][*j*]. Else, or person number *j* go to escalator in *i* + 1 second, i. e. *z*[*i* + 1][*j* + 1] + = *z*[*i*][*j*] * *p*, or person number *j* stays on his place, i. e. *z*[*i* + 1][*j*] + = *z*[*i*][*j*] * (1 – *p*).

Now we need to count answer — it is sum on *j* from 0 to *n* inclusive *z*[*t*][*j*] * *j*.

Asymptotic behavior of this solution — *O*(*t* * *n*), where *t* — on which moment we must count answer, *n* — how many people stay before escalator in the beginning.

## 517E — Arthur and Questions

At first let's take two sums *a*_{1} + *a*_{2} + ... + *a*_{k} and *a*_{2} + *a*_{3} + ... + *a*_{k + 1}. It is correct that *a*_{1} + *a*_{2} + ... + *a*_{k} < *a*_{2} + *a*_{3} + ... + *a*_{k + 1}. If move from right to left all elements apart from *a*_{k + 1}, all of them will reduce and will left only *a*_{1} < *a*_{k + 1}. If write further all sums we will obtain that sequence disintegrate on *k* disjoint chains: *a*_{1} < *a*_{k + 1} < *a*_{2k + 1} < *a*_{3k + 1}..., *a*_{2} < *a*_{k + 2} < *a*_{2k + 2} < *a*_{3k + 2}..., ..., *a*_{k} < *a*_{2k} < *a*_{3k}....

We will solve the problem for every chain separately. Let's iterate on first chain and find all pair of indexes *i*, *j* (*i* < *j*), that *a*[*i*] and *a*[*j*] are numbers (not questions) in given sequence, and for all *k* from *i* + 1 to *j* - 1 in *a*[*k*] stay questions. All this questions we need to change on numbers so does not violate the terms of the increase and minimize sum of absolute values of this numbers.

Between indexes *i* and *j* stay *j* - *i* - 1 questions, we can change them on *a*[*j*] - *a*[*i*] - 1 numbers. If *j* - *i* - 1 > *a*[*j*] - *a*[*i*] - 1, then we need to print *Incorrect* *sequence* and finish algorithm. Else we need to change all this questions to numbers in greedy way.

Here we have several cases. Will review one case when *a*[*i*] > = 0 and *a*[*j*] > = 0. Let current chain (3, ?, ?, ?, 9), *i* = 1, *j* = 5. We need to change questions on numbers in the following way — (3, 4, 5, 6, 9). In other cases (when *a*[*i*] < = 0, *a*[*j*] < = 0 and when *a*[*i*] < = 0, *a*[*j*] > = 0) we need to use greedy similary to first so does not violate the terms of the increase and minimize sum of absolute values of this numbers.

Asymptotic behavior of this solution — *O*(*n*), where *n* — count of elements in given sequence.

## 517F — Pasha and Pipe

At first let's count two two-dimensional arrays of prefix sums *sumv*[][] and *sumg*[][]. In *sumv*[*i*][*j*] store how many grids are in column *j* beginning from row 1 to row *i*. In *sumg*[*i*][*j*] store how many grid are in row *i* beginning from column 1 to column *j*.

Let's count *ans*0 — how many pipes without bending we can pave. Count how many vertical pipes — we can pave. Iterate on *j* from 2 to *m* — 1 and, if *sumg*[*n*][*j*] — *sumg*[*n*][0] = 0 (i. e. in this column zero grids), increase *ans*0 on one. Similary count number of horizontal pipes.

Let's count *ans*1 — how many pipes with 1 bending we can pave. We need to brute cell, in which will bending. There are four cases. Let's consider first case, others we can count similary. This case — pipe begin in left column, go to current cell in brute and then go to top row. If brute cell in row *i* and column *j* then to *ans*1 we need to add one, if (*sumg*[*i*][*j*] — *sumg*[*i*][0]) + (*sumv*[*i*][*j*] — *sumv*[0][*j*]) = 0.

Let's count *ans*2 — how many pipes with 2 bendings we can pave. Let's count how many tunes begin from top row and end in top or bottom row and add this number to *ans*2. Then rotate our matrix three times on 90 degrees and after every rotate add to *ans*2 count of pipes, which begin from top row and end in top or bottom row. Then we need divide *ans*2 to 2, because every pipe will count twice.

How we can count to current matrix how many pipes begin from top row and end in top or bottom row? Let's count four two-dimension arrays *lf*[][], *rg*[][], *sumUp*[][], *sumDown*[][]. If *i* — number of row, *j* — number of column of current cell, then in position (*i*, *lf*[*i*][*j*]) in matrix are nearest from left grid for cell (*i*, *j*), and in position (*i*, *rg*[*i*][*j*]) in matrix are nearest from right grid for cell (*i*, *j*). *sumUp*[*i*][*j*] — how many columns without grids are in submatrix from (1, 1) to (*i*, *j*) of given matrix. *sumDown*[*i*][*j*] — how many columns without grids are in submatrix from (*i*, 1) to (*n*, *j*) of given matrix. Then let's brute cell in which will be the first bending of pipe (pipe goes from top row and in this cell turned to left or to right), check, that in column *j* above this cell 0 grids, with help of arrays *lf* and *rg* find out as far as pipe can go to left or to right and with help of arrays *sumUp* and *sumDown* carefully update answer.

Now print number *ans*1 + *ans*2 + *ans*3.

Asymptotic behavior of this solution — *O*(*n* * *m* * *const*), where *n* — hoew many rows in given matrix, *m* — how many columns in given matrix, *const* takes different values depending on the implementation, in solution from editorial *const* = 10.

On D, I thought of state f(n, t, p): expected number if n people are on elevator, t seconds have passed, and accumulated probability is p. Being p a floating point, how can I store such thing?

For example,

map<state, state_answer>

For problem E, my program kept failing the fifth testcase, which is this one:

5 1 1000000000 ? ? ? ?

The jury solution was: 1000000000 1000000001 1000000002 1000000003 1000000004, but my program gave an "Incorrect sequence", since none of the numbers were in range [-1e9, 1e9]. Apparently this restriction only applied to the given numbers? Please, be a bit more clear about this next time, I assumed the entire sequence was supposed to be in that range..

EDIT: Yep, changing all my 1e9's to 1e11 made it pass. A bit frustrating, to be honest.

EDIT: And yes, problem E, not D :)

That's Problem E actually.

Had the same problem for some time.

Hi. Would this be the best place to highlight (potential) cheaters who ask for pretests?

This submission's result is WA. 10007183

when I change from char s[200000],char t[200000] to s[200001], t[200001], 10007601 The result is accepted.

I don't know why my first submission is wrong.

Input string's max length is 200000 and my array's max length is 200000 too. When I test with max length's string, the result is 0 200000 or 200000 0. Please help me :)

1 extra byte for the null character at the end

To elaborate, scanf writes the entire scanned string plus a terminating null character. If the buffer isn't large enough to handle this (as in your WA), then it's undefined behavior.

What happens in practice depends on how memory is laid out. I tested with a global char s[8], t[8] and two 8-char strings, and the C++ compilers put t directly before s in memory. t's null terminator was written to s[0], making s an empty string and giving you the 0 0 output. (The C compiler put s before t, effectively appending t to s.)

Point being, when dealing with character buffers, make sure to account for the null terminator. Or use a safer method such as std::cin >> std::string.

Thank u about your answer! from now on, I will use array with enough index :(

But, I have another question about this.

I read your answer and tested with a global char s[7], t[7] and two 7-char strings like you.

I expected WA in test 3. because test 3 input's length is 7. (the test 3 input is abacaba / AbaCaBA) 10008773 But, test 3 is accepted in test 3, and WA in test 6(test 6 input's length is 26).

Than, what happen?

Insufficient array bounds causes buffer overflow and may cause undefined behavior depending on how the memory is allocated. strlen reads the string till it hits a null char

`'\0'`

, which in case of of an overflow cannot be predicted. It can either find it just after the actual string or after reading a lot of garbage and might even give a segfaultWhat happens in cases like these depends on the memory alignment of the buffers. It looks like GCC and MS C++ align char[] to 4 bytes in this environment, whereas g++ aligns to 1. So in test 3 the buffers are actually 8 bytes apart so there's room for the null terminator, but in test 26 one buffer overruns the other.

See for yourself:

Wow!!! That's amazing! I don't know about that process absolutely. Thank u!!

How would Anya and Smartphone be solved if everytime we launch an application, it's moved to the first page's first position?

I see obvious solutions like segment tree or treap. Segment tree solution is not too hard so I think this will be the best solution. Can explain further if you wish.

Edit: ok, I don't have any idea how to solve it with treap now. My bad.

Please explain how will you do it using treap?

Okay. How will you do it using a segment tree?

What I thought was maintain a supreme counter. Assign 1 to n to a[n-1], a[n-2] that is in

reverse order. Now on opening an application query the no of elementslargerthan current value for that application, which shall give number of gestures and update the current value with supreme and increment supreme. My approach uses BIT so it is easier I think than Segment Trees and Treap. I would love to hear how to do this with treap.We can use a BST.

We will maintain 2 data structures:

Update operation (when Anya clicks on an app):

Does this work?

Edit : I think what I said was wrong.

Awesome contest, thank you! ;)

it's third time I've got wrong answer because of "long long int"

Could we obtain the dp of problem D also with matrix exponentiation?

Naive Matrix multiplication for (axb) x (bxc) id O(abc)

For exponentiation of (nxn) matrix to power e is O(n3 log(e))

at n = 2000, it will give TLE. For smaller values, it is solvable

what would be the transition matrix?

One way would be (n+1)x(n+1) Matrix,

`M[i][i] = (1-p)`

and`M[i][i-1]=p`

`M[i][j]=0`

otherwiseYour state vector would be

`B[i]`

the probability that there are at least i people on the elevator. (`i=0..n`

)For F, one can also use simple DP with "layers" (multiple passes). E.g. define states {STARTED, TURNED1_LEFT, TURNED1_RIGHT, TURNED1_MOVED, TURNED2, FINISHED} and pass through the whole field in all directions for each state (each state increases number of combinations on some later state).

Here's my submission (the code is messy copy-paste though I tried to reduce stuff with macros).

hey !! has anyone done the fourth problem taking state as dp[i][j] where i is the no of persons alloted till time j..i dont know what is the problem with my dp ..please help

http://codeforces.com/contest/518/submission/10008582

That second term should be multiplied by p, not 1-p.

Thanks buddy :) !! that was a stupid one

For D :

If(n>=t): Therewill be at least one person always trying to step in. So I should always multiply with (1-p) which gives an easy solution as sum of (tCi * p^i * (i-p)^(t-i) * i);

else : if n people finish then the probability should not be multiplied with 1-p and should be add directly. So let's say I repeat the above procedure for 1 to n-1. and for n I separately calculate the sum by iterating over all times from n to t and ending at that point of time to get the required answer as above. Can somebody find any mistake in this?

My AC submission during the contest uses the same logic so I don't think there's any mistake in it . Though the dp solution mentioned in the editorial is much more simpler.

Hello. I am having trouble finding the bug in my code. It appears that my solution is what is written in the editorial, but it was given the WA verdict during the contest.

Thanks for your time.

Your solution (and the editorial, as currently written) allows characters in s to be double matched. If you match in the first pass, set s[i] to a non-letter so you can't match it in the second.

Ah, thank you so much. I didn't notice that.

Concerning problem

F: Could someone explain what values are stored insumvandsumg? I didn't understand what grid is supposed to mean in this context.the feeling of wa because of long long can only be understood by me !!! CM :(

## agli-baar-long-long in every question

What is the logic to solve problem E , i am not able to understand the editorial for it

Can someone explain problem D please. Especially how is the probabilities are calculated?

thanks edi

Let P(n, t) be the probability of having n people on the escalator after t seconds.

But did you try solving like this? It does not work

Of course it works. It's the same idea of the solution posted above, just in a different notation. Here is my accepted code: http://codeforces.com/contest/518/submission/9999105

But you are using cache[n][t] += prob(n, t — 1)*(1 — p); why are you doing a sum ?

P(n, t) = P(n — 1, t — 1)*p + P(n, t — 1)*(1 — p), if n is not the total number of people P(n, t) = P(n — 1, t — 1)*p + P(n, t — 1), otherwise

No sum here.. Confused a bit

Look closer. There's a sum there. I'm adding up the second term separately.

Oh.

and this works. So awesome thanks a lot. I ll recheck my solution

Hi,

For problem B. I am having trouble with pretest 3. for following input abacaba AbaCaBA My solution run and shows as "6 1" against expected "3 4". But when I am running the same in local against the same input its correctly running as "3 4". Can someone see what exactly is issue or if they can reproduce this issue on there machines as well with my code.

http://codeforces.ru/contest/518/submission/10016414

Any help would be appreciated

Because the the server is doing this for(int i = 0 ; i<100; i++) a[i] = 0; when you declare int a[100]. that is initializing each array value to 0 So if you add that line after cin>>t; for(int i = 0 ; i<100; i++) a[i] = 0;

## you will get the same error

Side note: Also you are doing a[s[i]-'a']++; what if s[i] == 'A' ? then s[i]-'a' = -32. which is a negative number. you should be careful with this.

Hello

For problem D "517D — Ilya and Escalator", I am not able to understand why we have to do following:

"Now we need to count answer — it is sum on j from 0 to n inclusive z[t][j] * j."

Why

multiplication with jis required?Thanks

Because expected value is {E}[X] = x1*p1 + x2*p2 +x3*p3 ... + xt*pt http://en.wikipedia.org/wiki/Expected_value.

Thanks :-)

Did you understand why the probabilities are being added?? thanks

Edi

Yay....

what is wrong with my solution for problem B Code

Your code checks all element of w twice, so it is possible that some elements are selected in the both first loop and second loop. You have to check the elements of w which are not selected in the first loop, i think. Try this case: aa aaAA

The correct output should be 2 0. But your code output 2 2.

c(n, k) = c(n, k — 1)*(n — k + 1)/k k > 0c(n, k) = c(n — 1, k)*n/(n — k) n > 0 k < nThen it seemed that there is O(t) time and O(1) space algorithm for problem D. Accepted sample code: http://codeforces.com/contest/518/submission/10018612 although this simple implementation can be hacked with data like "2000 0.999999 1999" because there is no "minimum positive value" of 1 — p or p.

I got wrong answer for "517C — Anya and Smartphone" because I used int instead of long. http://codeforces.com/contest/518/submission/10002898

How could I have recognize that I would need long, instead of int ?

Suppose n = m = 10^5, k = 1 and every time you want to open the last app. Each launch will take 10^5 gestures, so the answer will be 10^10 which does not fit in a 32-bit integer. You have to predict the worst case of your algorithm.

You must think a bit. Whenever you are summing potentially big numbers, you must use long long int.

What would be the answer for problem F for this input:

and why?

3 4

..#.

....

.#.#

source for E would crash for that test

Sorry I meant F

thanks edi

Hi

Can you please reply?

How is the answer 3?

thanks edi

The answer is 6:

Can somebody explain me whats wrong with this solution for problem B: http://codeforces.com/contest/518/submission/10033494

That's not a solution. [link was corrected after seeing this comment]

What would be the answer for problem F for this input: and why? 3 4

..#.

....

.#.#

Sorry, the link has been updated.

In the line:

You should subtract from x[i] before setting y[i] to 0.

Dafaq.

FacepalmAnyways, Thanks a ton mate.I keep getting Run Time error for my code: 10099873 to Problem E. It is running normally for local tests. Can anyone point out what is going wrong?

Okay, so I realized that my code would not get accepted but why is it not running even for the first test case?

Never mind, found my mistake :)

Could someone please elaborate in more details how the solution proposed for the problem 518D - Илья и эскалатор guarantees this part of the problem conditions:

"The absolute or relative error mustn't exceed 10 ^(- 6)."

Thanks in advance.

Michael.

For problem D, test case — 6 — I got wrong and the log reads - wrong answer 1st numbers differ — expected: '414.0744421', found: '414.0740000', error = '0.0000011'

My algo is exactly the same as given. I coded in C++ and double instead of float for all non-integers. How to get over this problem?

Use printf or set up your cout

I'll try with printf but, How can I setup my own cout?

I think

`std::cout.precision(8)`

or overriding`std::iostream::operator <<`

may work, but overriding operators is a bit complicated. Therefore try the former method :)Problem C

I write codes such like

`for (int i = 0; i < (int)strlen(A); i++) {}`

and get a 'TLE'but use

`int lenA = strlen(A); for (int i = 0; i < len; i++) {}`

get a 'AC', why?10538344 TLE

10538342 AC

strlen(A) work time is O( length_of_string ) and it is called each loop

thx!

My code for problem 2 gets stuck at 8 here's the code: http://codeforces.com/contest/518/submission/10856849 can anybody help :(