### fcspartakm's blog

By fcspartakm, 5 years ago, translation, ,

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

• +28

 » 5 years ago, # |   +6 Fast editorial.
 » 5 years ago, # |   +13 give me -
 » 5 years ago, # |   0 could you please upload solutions?
•  » » 5 years ago, # ^ |   +4 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 :)
 » 5 years ago, # |   0 Why can't divide and conquer be applied to problem E?
 » 5 years ago, # |   0 Problem D has less accepts of E. D is harder than of E OR because of hard->easy solvers ?!
•  » » 5 years ago, # ^ |   +7 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.
•  » » » 5 years ago, # ^ | ← Rev. 4 →   -17 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?
•  » » » » 5 years ago, # ^ |   +20 Considering you failed systests, are you saying you can't code a DFS?
•  » » » » » 5 years ago, # ^ |   0 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 ;)
•  » » » » » » 5 years ago, # ^ |   +6 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.
•  » » » » » » » 5 years ago, # ^ |   0 It's hard to make silly bugs in "just a DFS".Ok, compare my failed and accepted solutions.
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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
 » 5 years ago, # |   0 Why you didn't increase constraints for C?
•  » » 5 years ago, # ^ |   +8 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).
•  » » 5 years ago, # ^ |   0 if the constraints for problem C are increased, i think we can do it using segment trees. am i right?
•  » » » 5 years ago, # ^ |   0 Yeah, I was talking about increasing up to about 105 not to 103.
•  » » » » 5 years ago, # ^ |   0 Can you explain solution or share code with segment tree ? thanx
•  » » » » » 5 years ago, # ^ |   +1 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?
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 FYI, linear updates would work just fine in such constraits. Also, just use a BIT instead of a seg tree. Less clumsy+faster :) My solution with linear updates: 14964423
 » 5 years ago, # | ← Rev. 2 →   +9 can anyone explain the solution for problem E more clearly.....
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   0 Your assumption is really amazing...!!! :)
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # | ← Rev. 2 →   0 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. :]
•  » » 5 years ago, # ^ |   0 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.)
•  » » » 5 years ago, # ^ |   0 Thank you. :]
 » 5 years ago, # | ← Rev. 2 →   0 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?
•  » » 5 years ago, # ^ |   0 I can write proof, but I don't know English very well)) I submited greedy algorithm on contest. http://codeforces.ru/contest/508/submission/9586845
•  » » » 5 years ago, # ^ |   0 I understand the algorithm. What about proof of correctness ?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
 » 5 years ago, # |   +5 Can someone explain the dynamic programming solution for E?
•  » » 5 years ago, # ^ |   -13 Yes
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 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
•  » » » » 5 years ago, # ^ |   -21 Yes
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +4 Here in Z (I, j) I is the position of opening bracket u r currently at and j is end point of this segment.
•  » » » » 5 years ago, # ^ |   +12 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.
•  » » » » » 5 years ago, # ^ |   +8 I quite agree, the explanation for E is poorly written. hereicomewf : what exactly is "this segment" in your explanation?
•  » » 5 years ago, # ^ |   +3 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).
•  » » » 5 years ago, # ^ |   0 Got it, thanks. The dp is surprisingly simple :)
•  » » » 5 years ago, # ^ |   0 Thanks for the explanation!
•  » » » » 4 years ago, # ^ |   0 sorry, can someone tell me more clear what menas " if there is a way to satisfy the conditions using ONLY the ith to jth conditions " ? is it means that we can construct valid sequences from i to j?
 » 5 years ago, # |   0 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?
 » 5 years ago, # |   0 Can anyone explain the dynamic programming solution of problem E?
 » 5 years ago, # |   0 Can someone please explain dfs solution of problem D.
•  » » 5 years ago, # ^ |   +1 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
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Great Explanation. A name actually exists for this algorithm. It's called Hierholzer’s Algorithm. You can read a good explanation along with the code here. I have solved it using the same algorithm. Here is the AC code 14998115
•  » » » 9 months ago, # ^ |   0 I have exactly same solution, But it took 577ms
 » 5 years ago, # |   0 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.
 » 5 years ago, # |   0 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
 » 5 years ago, # |   -14 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 xqe8 ebc bcd deb cde dey eyx yxq xqe qeyanswer for both should be YES
•  » » 5 years ago, # ^ |   +17 Actually, notice that you have n=8 but 9 strings after that, so the input is invalid.
•  » » 5 years ago, # ^ |   0 didn't look carefully enough. some Eulerian path implementations seemed deceptively too simple )
 » 5 years ago, # | ← Rev. 2 →   0 I know it's four weeks late but I have a little question on problem E:Does the test case 2 2 2Gives a (()) ?
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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"...
 » 5 years ago, # |   0 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?!
 » 5 years ago, # | ← Rev. 2 →   0 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 becase 1 : even,case 2: odd,case 3 : can be odd or even) ?
 » 4 years ago, # |   0 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
 » 14 months ago, # | ← Rev. 3 →   0 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
 » 7 months ago, # |   0 Can anybody give a formal proof of greedy solution of problem E ?