fcspartakm's blog

Codeforces Round #288 (Div.2) Editorial
By fcspartakm, 10 years ago, translation, In English

508A — Pasha and Pixels

To solve this problem let's create matrix with type bool and dimensions n on m. Cell (x, y) of this matrix is true — if this cell painted in black color.

Let on move number k Pasha paints pixel in position (i, j). Then game ending on this move, if square 2 × 2 formed from black cells appears, and cell (i, j) will upper-left, upper-right, bottom-left or bottom-right of this squares. Only this squares we need to check on current move. If we haven't such squares after k moves, print 0. Asymptotic behavior of this solution — O(k), where k — number of moves.

508B — Anton and currency you all know

Because of specified number is odd (that mean that last digit of this number is odd) we need to swap last digit with some even digit. How to maximize number after this swap?

If number consists only from odd digits print  - 1.

Else, we need to find first even digit, which less than last digit if we will iterate from most significant digit. If we find such digit — swap it with last digit and we have an answer.

Else, we need to find first even digit, which more than last digit if we will iterate from less significant digit. If we find such digit — swap it with last digit and we have an answer.

Asymptotic behavior of this solution — O(n), where n — count of digits in specified number.

508C — Anya and Ghosts

This problem can be solved with help of greedy algorithm. Let's iterate on moments when ghosts will appears.

We need to use use array, in wich we will mark moments of time, in wich we lighted candles (for example, put in corresponding positions 1). Than for every new ghost will count how many candles lights in time of his visit from our array.

If ghost appears in moment of time wi, iterate on out array from wi - 1 to wi - t, where t — count of seconds, which candle burns, and count the number of ones. If this count is not less than r, continue iterating on ghosts. Else, iterate on our array from wi - 1 to wi - t, and, if in current second candle didn't lighted — make it, and put in this position in array 1. We need to do such operation, while count of ones in this section of our array will not be equals to r. If we can't do this fore some ghost, we can print  - 1.

Answer to this problem — count of ones in our array. Asymptotic behavior of this solution — O(mt), where m — count of ghosts, t — the duration of a candle's burning.

508D — Tanya and Password

At first, let's convert data from input in directed graph. Vertexes in this graph will all strings with length equals to 2 and consisting of uppercase and lowercase letters of the latin alphabet. For all 3-letters strings from input — si's, let's add edge from vertex si[0]si[1] to si[1]si[2].

Now we need to find in this graph Euler path. For this we can use Fleury's algorithm. It is worth noting, that Euler path consists, if count of vertexes, in wich in-degree and out-degree differs by one, less then 3, and in-degree and out-degree of others vertexes — even. If we can't find Euler path — print NO. Asymptotic behavior of this solution — O(m), where m — count of different 3-letters strings from input. It equals to number of edges in graphs.

508E — Arthur and Brackets

This problem can be solved with help of dynamic dynamic programming. Let's create squre matrix Z with sizes n × n, where n — count of open brackets in sequence. Main hint — if open bracket is in position l, and corresponding for her close bracket — in position r, than from position l + 1 to position r - 1 must stay a regular bracket sequence.

In array Z first parametr lf — number of open bracket, second parametr rg — number of last open bracket, which can be in a regular bracket sequence, which will exists between open bracket with number lf and corresponding for it close bracket.

Z[lf][rg] = true if it is possible to construct such sequence. Otherwise Z[lf][rg] = false.

For current lf and rg let's iterate on cnt — how many open brackets and corresponding them close brackets in a regular bracket sequence will stay between open bracket number lf and corresponding for it close bracket. If this count falls in the given interval for open bracket lf, recurcively run dynamic from two segments — (lf + 1, lf + cnt) and (lf + cnt + 1, rg).

If for both segments we can construct regular bracket sequences, appropriate to data-in from input, put in Z[lf][rg] value true. To restore answer, we must move from segment (lf, rg) in segments (lf + 1, lf + cnt) and (lf + cnt + 1, rg), if for both this segments we can construct regular bracket sequences and recursively restore asnwer. If Z[0][n - 1] equals to false, print IMPOSSIBLE. Asymptotic behavior of this solution — O(n3).

UPD This problem can be solved with help of griddy algorithm. Asymptotic behavior of this solution — O(n). Here is example of such solution, participant matrix.

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

Comments Comments (58)
| Write comment?
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Fast editorial.

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

give me -

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

could you please upload solutions?

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

    Hello new user.

    You can find others solutions in site. Go to Dashboard then click on x???? numbers right side of problems name.

    On the opened page , click on numbers in first column(#) and read the answer , but be careful just read the Accepted submits :)

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can't divide and conquer be applied to problem E?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D has less accepts of E. D is harder than of E OR because of hard->easy solvers ?!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Well E is pretty easy, just a simple DP (it's not completely obvious what the DP should exactly do, but the rough idea of DPing by current opening bracket and the distance to its closing one is there quite clearly). On the other hand, the algorithm needed for D can be hard to code even if you know what to do.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it -17 Vote: I do not like it

      On the other hand, the algorithm needed for D can be hard to code even if you know what to do.

      You are talking about dfs, right?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        Considering you failed systests, are you saying you can't code a DFS?

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

          Having silly bugs is ok for me.

          You seem to be pretty hateful. I was not pointing at me or you personally. After your words about difficulty level of this problem I just wanted to ensure that you are talking about the same solution as I had.

          Relax ;)

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            It's hard to make silly bugs in "just a DFS".

            Hate seems to be a pretty common retort these days. There are cases when I read a problem and think "ok, this is easy to do", then start coding, but with some "oh wait, I can't just do this" moments, a lot of silly mistakes and it still fails in the end. When I look back at the result, I usually think that maybe it wasn't so simple after all. I was just pointing this out as a similar case.

            Constructing Eulerian circuits is a well-known problem, but IMO falls into this category.

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

              It's hard to make silly bugs in "just a DFS".

              Ok, compare my failed and accepted solutions.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                Okay, I just did. What I saw: twice "obviously not just a DFS". (which doesn't mean that it doesn't use DFS, but that it uses a lot of other stuff)

                It's definitely something that can be hard to code, which is what I was initially saying, and it's more complicated than the DP (+ reconstruction) needed in E. Thanks for confirming my point :D

                → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why you didn't increase constraints for C?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    With these constrains some can confuse the problem with a dp problem, that was my first impression when I read the problem and constrains (I guess).

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

    if the constraints for problem C are increased, i think we can do it using segment trees. am i right?

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

      Yeah, I was talking about increasing up to about 105 not to 103.

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

        Can you explain solution or share code with segment tree ? thanx

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

          Count the number of candles lit from time w-t to w-1 using the segment tree/bit O(log n). If this is less than r, then count how many candles can you light up in the range w-t to w-1, and if you don't have enough time to light up these candles, output -1, else add the number of candles you light up to the total and perform an update on the segment tree/bit O(log n)

          Hence asymptotic complexity will be O(n.log n). By the way, will we have to perform updates with lazy propagation?

          → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

can anyone explain the solution for problem E more clearly.....

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Speaking of C, we should output -1 only if r > t, am I right? And if so, looks like if we need to light k new candles for next ghost, we will always have at least k consecutive free seconds right before this ghost. Can't prove this, but got AC with solution based on this assumptions.

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

    Your assumption is really amazing...!!! :)

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

    You are close, I think :) Don't know if it's enough to stand out for the proof, but at least gives intuition why does it work. If t < r it's -1. When you try to lighten up r candles the first lightened up are starting to burn out and you cannot keep up. Otherwise, in the worst case, when t == r, we can always start lightning candles way before first ghost appears and keep lightning candle every second. That way at least r candles are always up. Having that in mind, you can start thinking of better approach if you have longer lasting candles. And that better approach is greedy solution described in editorial.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a question. I was trying to solve D, but got TLE as my verdict. I suppose it was because I used a map to assign each substring a value. As I was looking through the accepted solutions, I saw that a few used, what appeared to be, a function to assign each substring of length two a value. However, they did not use the same constants. example

Does this technique have a name? If so, can somebody supply me a problem or two with which I can practice?

Thanks. :]

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

    I'm not sure whether it has a particular name, but hashing comes to mind. (Each string of length 2 is translated to an integer, which is close to what hashing does.)

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am learning to write formal proof for the algorithms, I am lost on how to start proof for the greedy algorithm of 508E - Arthur and Brackets. I know how it works, but how to prove it formally. Any helps on this?

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

    I can write proof, but I don't know English very well)) I submited greedy algorithm on contest.
    http://mirror.codeforces.com/contest/508/submission/9586845

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

      I understand the algorithm. What about proof of correctness ?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Here's an attempt at the proof of correctness.

        Typically, whenever we see a problem with greedy and we want to prove that it is correct, we do some sort of "exchange" argument (i.e. given a valid/optimal configuration, we can always swap some things so it looks like what our greedy will do).

        Suppose we have some valid solution that did not close parenthesis as soon as possible.

        For instance, let's look at a simple example

        3
2 5
1 4
1 4

        One valid solution is ((())), while a greedy would give us (())()

        Let position i be the first position in which the valid solution could close a parenthesis, but didn't. In our example above, the first position in which this happens is at position 3.

        Now, let k be the index of the opening parenthesis of the closing parenthesis at position i that we could have closed (in our example, this would be the second parenthesis). We will make a swap in our valid solution to make it one step closer to what the greedy would have done. Let j be the position in our valid solution of the k'th opening parenthesis.

        Back to our example, we have this scenario:

            j
    v
((()))
 ^^ 
 ki

        Now, we're ready to make a swap. It is perhaps best described with a picture as follows:

            j
  --v
((()))

turns into

  j 
  v--
(()())

        Notice that the things under the dash marks are unchanged, so this is still valid. The only distance that changes is the k'th opening parenthesis, and it decreases to a valid amount. This means that this is still a valid solution, but we've moved our valid solution to look more like our greedy's solution. We can apply this argument over and over again until we get something that looks exactly like our greedy (i.e. close parenthesis as soon as possible).

        The above shows that for any valid solution, we can make a series of swaps so that it exactly matches our greedy solution. That means that if there exists a valid solution, then our greedy solution will find a solution. The contrapositive of this statement is also true, which says that if our greedy doesn't find a solution, then there is no valid solution. So, closing parenthesis as soon as possible works.

        → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain the dynamic programming solution for E?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Yes

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Haha, very funny, I can't stop laughing -_-

      Aside, will someone please explain the dynamic programming solution for E? Just define what Z[i][j] is, I can probably figure out the recurrences :P

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it -21 Vote: I do not like it

        Yes

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +4 Vote: I do not like it

        Here in Z (I, j) I is the position of opening bracket u r currently at and j is end point of this segment.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        I would also want an explanation ofthe dynamic programming solution for E, in the editorial is poorly written in English and I am unable to understand it.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          I quite agree, the explanation for E is poorly written. hereicomewf : what exactly is "this segment" in your explanation?

          → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Let Z[i][j] be true if there is a way to satisfy the conditions using ONLY the ith to jth conditions (with j-i+1 pairs of parenthesis), and false otherwise. Our final answer is Z[0][n-1] (if you want to actually reconstruct a solution, you need to keep prev pointers, but this is not the main point of the algorithm).

    We know that i opens then closes, and let k be the number of pairs of open/close parenthesis that go in between the i-th open and close parenthesis. Then, we need L[i] <= 2k+1 <= R[i] as well as Z[i+1][i+k] and Z[i+k+1][j] (you need to define base cases and the corner cases carefully, but it's not too hard).

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for problem C is in O(w) (O(w*log(w)) while contest because of using BIT). And it's accepted. So we don't need (m*t) here?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the dynamic programming solution of problem E?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain dfs solution of problem D.

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

    Firstly, you need to construct the graph. According to the solution of the tutorial (which is really a good one), you can build the graph from the three letter strings. Say for example:

    You have a string abc. While making graph, you split this string into two parts: ab and bc. Now suppose your adjacency list is adj. All you need to do is push the right node (bc) to the list of the left node (ab) like this: adj["ab"].push_back("bc").

    Now you need to make sure that the constructed graph has an Eulerian Circuit or an Eulerian Path. For this you have to make some checking. You should check out this link if you don't know the conditions of Eulerian Circuits or Paths: Conditions for Eulerian Paths and Circuits. Remember that the graph is directed. :)

    After you have made the confirmation that your graph has an Eulerian Path or Circuit, all you need to do is run a dfs. In this case I ran dfs and made sure that all the edges from a node are visited. To save the path, I pushed them in a vector. The resultant vector will store the nodes in reverse order, so I had to reverse it.

    You can check my submission here: 9619543 I did not convert the characters and strings into integers as I thought that the time limit is quite good enough. It took 873ms which is really good compared to 2000ms :D :P

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, I am curious that, is the number of edges m too large for a recursive solution? My code gave a Runtime Error for testcase 30 on my computer. However it passed the test on codeforces' server.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem D i'm detecting if the the graph is a euler graph and then i'm finding the path using heirholzer's algorithm ... i don't know what i'm doing wrong but i'm stuck at testcase 8 ... can anyone point out my mistake ?? 9608421

→ Reply
»
10 years ago, # |
  Vote: I like it -14 Vote: I do not like it

seems that systests for problem D are weak. I dont want to point fingers but some solutions don't pass these tests:

8 ebc bcd deb cde dey eyx yxq qey xqe

8 ebc bcd deb cde dey eyx yxq xqe qey

answer for both should be YES

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Actually, notice that you have n=8 but 9 strings after that, so the input is invalid.

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

    didn't look carefully enough. some Eulerian path implementations seemed deceptively too simple )

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I know it's four weeks late but I have a little question on problem E:

Does the test case 2 2 2

Gives a (()) ?

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

    No the answer for 2 2 2 2 2 is IMPOSSIBLE, as you can see that the minimum distance of between 2nd opening and closing brackets has to be 2, and is 1 in (()). Keep in mind that the bracket that opens first, closes last. If we denote each bracket differently which is required in the question, your answer is ([)] which as you can see is not a proper sequence.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks, and sorry for typo, I meant for 2 2 2 instead but I got your point :)

      I just totally ignore the basic point: "the bracket that opens first, closes last"...

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everyone. As I know, when we need to find Euler path or Euler circuit we should keep in mind to avoid choosing 'bridge'-s, I found some forums where people solve without considering it, by stacks, for their algorithm I have test case where it fails. But I don't know how to find and update bridges in graph in such a way, that time complexity didn't make a problem for problem D. Could you help me?!

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Just modifying the 508 — B 'Anton and currency you all know' problem,
how to solve if we want to find the maximum number by swapping exactly 2 digits?
(given input number can be odd or even but number to be obtained should be
case 1 : even,
case 2: odd,
case 3 : can be odd or even) ?

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

I'm a newbee..This may be a silly question.:P..but can anyone tell me why we are checking euler path in D problem.??..also for euler path in and out degree should be equal..right.??here it is written to be <=1

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

The editorial of problem D suggests to use Fleury's algorithm but that algorithm is O(m^2),where m is the no. of edges, which is not efficient enough to solve the problem. To solve it we must use Hierholzer's algorithm to find the Euler path or circuit. This algorithm works in O(m). Here's my solution using this algorithm: 45387404

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody give a formal proof of greedy solution of problem E ?

→ Reply