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.
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.
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.
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.
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.
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 (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]) + (sumv[i][j] — sumv[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.