Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### fcspartakm's blog

By fcspartakm, 5 years ago, translation, ,

## 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 ans1 and ans2 — 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 ans1 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 ans2 on one and decrease cnt[с] on one.

Now, print two numbers — ans1 and ans2.

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 a1 + a2 + ... + ak and a2 + a3 + ... + ak + 1. It is correct that a1 + a2 + ... + ak < a2 + a3 + ... + ak + 1. If move from right to left all elements apart from ak + 1, all of them will reduce and will left only a1 < ak + 1. If write further all sums we will obtain that sequence disintegrate on k disjoint chains: a1 < ak + 1 < a2k + 1 < a3k + 1..., a2 < ak + 2 < a2k + 2 < a3k + 2..., ..., ak < a2k < a3k....

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 ans0 — 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 ans0 on one. Similary count number of horizontal pipes.

Let's count ans1 — 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 ans1 we need to add one, if (sumg[i][j] — sumg[i][0]) + (sumv[i][j] — sumv[0][j]) = 0.

Let's count ans2 — 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 ans2. Then rotate our matrix three times on 90 degrees and after every rotate add to ans2 count of pipes, which begin from top row and end in top or bottom row. Then we need divide ans2 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 ans1 + ans2 + ans3.

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.

• +73

 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 For example,map
 » 5 years ago, # | ← Rev. 5 →   +15 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 :)
•  » » 5 years ago, # ^ |   +8 That's Problem E actually.
•  » » 5 years ago, # ^ |   0 Had the same problem for some time.
 » 5 years ago, # |   0 Hi. Would this be the best place to highlight (potential) cheaters who ask for pretests?
 » 5 years ago, # |   0 This submission's result is WA. 10007183when 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 :)
•  » » 5 years ago, # ^ |   0 1 extra byte for the null character at the end
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 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?
•  » » » » 5 years ago, # ^ |   0 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 segfault
•  » » » » 5 years ago, # ^ |   0 What 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: printf("%p %p\n", &s, &t);
•  » » » » » 5 years ago, # ^ |   0 Wow!!! That's amazing! I don't know about that process absolutely. Thank u!!
 » 5 years ago, # |   +4 How would Anya and Smartphone be solved if everytime we launch an application, it's moved to the first page's first position?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 years ago, # ^ |   0 Please explain how will you do it using treap?
•  » » » 5 years ago, # ^ |   0 Okay. How will you do it using a segment tree?
•  » » 5 years ago, # ^ |   0 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 elements larger than 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.
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 We can use a BST.We will maintain 2 data structures: A BST keyed with "score". The lower the app's score, the lower is its position. App at position 1 has the lowest score. In this BST we will also have to maintain the app id and size of the subtree rooted at this node. A vector of BST iterators mapping app id to BST nodes as defined above. Update operation (when Anya clicks on an app): Calculate cost. This will be a function of rank of the BST node in an inorder traversal. Easy to calculate using the sizes we have stored in #1. (When traversing right, add left_size+1, when traversing left, do nothing; Refer augmented RB trees in Cormen for details). Delete BST node using the iterator from #2 and re-insert it with 1 less than the current lowest score (to ensure 1st position). Does this work?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Edit : I think what I said was wrong.
 » 5 years ago, # |   0 Awesome contest, thank you! ;)
 » 5 years ago, # |   +2 it's third time I've got wrong answer because of "long long int"
 » 5 years ago, # |   0 Could we obtain the dp of problem D also with matrix exponentiation?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » 5 years ago, # ^ |   0 what would be the transition matrix?
•  » » » » 5 years ago, # ^ |   +1 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) Matrix M(n+1,n+1), B(n+1,1), Mx, Ex; M[0][0] = 1.0; B[0][0] = 1.0; for(int i=1;i
 » 5 years ago, # |   0 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).
 » 5 years ago, # |   0 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 helphttp://codeforces.com/contest/518/submission/10008582
•  » » 5 years ago, # ^ |   +1 if(i==n) dp[i][j]+=dp[i][j-1]+dp[i-1][j-1]*(1-p); That second term should be multiplied by p, not 1-p.
•  » » » 5 years ago, # ^ |   0 Thanks buddy :) !! that was a stupid one
 » 5 years ago, # |   +3 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?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 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.
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ |   0 Ah, thank you so much. I didn't notice that.
 » 5 years ago, # |   0 Concerning problem F: Could someone explain what values are stored in sumv and sumg? I didn't understand what grid is supposed to mean in this context.
»
5 years ago, # |
0

the feeling of wa because of long long can only be understood by me !!! CM :(

# agli-baar-long-long in every question

 » 5 years ago, # |   0 What is the logic to solve problem E , i am not able to understand the editorial for it
 » 5 years ago, # | ← Rev. 2 →   0 Can someone explain problem D please. Especially how is the probabilities are calculated?thanks edi
•  » » 5 years ago, # ^ |   0 Let P(n, t) be the probability of having n people on the escalator after t seconds. P(0, 0) = 1 P(0, k) = (1 — p)^k, if k > 0 P(k, 0) = 0 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
•  » » » 5 years ago, # ^ |   0 But did you try solving like this? It does not work
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 5 years ago, # ^ |   0 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), otherwiseNo sum here.. Confused a bit
•  » » » » » » 5 years ago, # ^ |   0 Look closer. There's a sum there. I'm adding up the second term separately.
•  » » » » » » » 5 years ago, # ^ |   0 Oh.and this works. So awesome thanks a lot. I ll recheck my solution
 » 5 years ago, # |   0 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/10016414Any help would be appreciated
• »
»
5 years ago, # ^ |
0

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.

 » 5 years ago, # |   +1 HelloFor 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 j is required?Thanks
•  » » 5 years ago, # ^ |   +1 Because expected value is {E}[X] = x1*p1 + x2*p2 +x3*p3 ... + xt*pt http://en.wikipedia.org/wiki/Expected_value.
•  » » » 5 years ago, # ^ |   0 Thanks :-)
•  » » » » 5 years ago, # ^ |   0 Did you understand why the probabilities are being added?? thanksEdi
 » 5 years ago, # | ← Rev. 2 →   0 Yay....
 » 5 years ago, # |   0 what is wrong with my solution for problem B Code
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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 aaAAThe correct output should be 2 0. But your code output 2 2.
 » 5 years ago, # |   0 c(n, k) = c(n, k — 1)*(n — k + 1)/k k > 0 c(n, k) = c(n — 1, k)*n/(n — k) n > 0 k < n Then 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.
 » 5 years ago, # |   0 I got wrong answer for "517C — Anya and Smartphone" because I used int instead of long. http://codeforces.com/contest/518/submission/10002898How could I have recognize that I would need long, instead of int ?
•  » » 5 years ago, # ^ |   +4 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.
•  » » 5 years ago, # ^ |   0 You must think a bit. Whenever you are summing potentially big numbers, you must use long long int.
 » 5 years ago, # | ← Rev. 7 →   0 What would be the answer for problem F for this input:and why? 3 4..#......#.#
•  » » 5 years ago, # ^ |   0 source for E would crash for that test
•  » » » 5 years ago, # ^ |   0 Sorry I meant Fthanks edi
•  » » » 5 years ago, # ^ |   0 HiCan you please reply?How is the answer 3?thanks edi
•  » » 5 years ago, # ^ |   0 The answer is 6:
 » 5 years ago, # | ← Rev. 2 →   0 Can somebody explain me whats wrong with this solution for problem B: http://codeforces.com/contest/518/submission/10033494
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 That's not a solution. [link was corrected after seeing this comment]
•  » » » 5 years ago, # ^ |   0 What would be the answer for problem F for this input: and why? 3 4..#......#.#
•  » » » 5 years ago, # ^ |   0 Sorry, the link has been updated.
•  » » » » 5 years ago, # ^ |   +4 In the line: yay += y[i]; y[i] = 0; x[i] -= y[i]; You should subtract from x[i] before setting y[i] to 0.
•  » » » » » 5 years ago, # ^ |   0 Dafaq. Facepalm Anyways, Thanks a ton mate.
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 Okay, so I realized that my code would not get accepted but why is it not running even for the first test case?
•  » » » 5 years ago, # ^ |   0 Never mind, found my mistake :)
 » 5 years ago, # |   0 Could someone please elaborate in more details how the solution proposed for the problem 518D - Ilya and Escalator guarantees this part of the problem conditions:"The absolute or relative error mustn't exceed 10 ^(- 6)."Thanks in advance.Michael.
 » 5 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   0 Use printf or set up your cout
•  » » » 5 years ago, # ^ |   0 I'll try with printf but, How can I setup my own cout?
•  » » » » 5 years ago, # ^ |   0 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 :)
 » 5 years ago, # |   0 Problem CI 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 TLE10538342 AC
•  » » 5 years ago, # ^ |   +6 strlen(A) work time is O( length_of_string ) and it is called each loop
•  » » » 5 years ago, # ^ |   0 thx!
 » 5 years ago, # |   0 My code for problem 2 gets stuck at 8 here's the code: http://codeforces.com/contest/518/submission/10856849 can anybody help :(