fcspartakm's blog

By fcspartakm, 9 years ago, translation, In English

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.

  • Vote: I like it
  • +73
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
9 years ago, # |
Rev. 5   Vote: I like it +15 Vote: I do not like it

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 :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 extra byte for the null character at the end

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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);
        
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    We can use a BST.

    We will maintain 2 data structures:

    1. 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.
    2. A vector of BST iterators mapping app id to BST nodes as defined above.

    Update operation (when Anya clicks on an app):

    1. 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).
    2. 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?

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Edit : I think what I said was wrong.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome contest, thank you! ;)

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what would be the transition matrix?

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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 otherwise

        Your 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<n+1; ++i) {
        		M[i][i]   = 1-p;
        		M[i][i-1] =   p;
        	}
        	Mx  = M.pow(t);
        	Ex  = Mx*B;
        	for(int i=1; i<n+1; ++i) {
        		ans += Ex[i][0];
        	}
        
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    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.

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

agli-baar-long-long in every question

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

thanks edi

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/518/submission/10016414

Any help would be appreciated

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 j is required?

Thanks

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is wrong with my solution for problem B Code

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • 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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

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

and why?

3 4

..#.

....

.#.#

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      ..#.

      ....

      .#.#

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, the link has been updated.

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Dafaq. Facepalm Anyways, Thanks a ton mate.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use printf or set up your cout

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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