omg hi!

I will add implementations soon.

**UPD**: Implementations are added

**Tutorial**

**Tutorial**

**Tutorial**

**Tutorial**

1504E - Travelling Salesman Problem

**Tutorial**

**Tutorial**

**Tutorial**

**Tutorial**

# | User | Rating |
---|---|---|

1 | tourist | 3803 |

2 | Benq | 3783 |

3 | Radewoosh | 3602 |

4 | Um_nik | 3541 |

5 | fantasy | 3526 |

6 | maroonrk | 3504 |

7 | ko_osaga | 3500 |

8 | jiangly | 3465 |

9 | orzdevinwang | 3460 |

10 | cnnfls_csy | 3427 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 178 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

6 | adamant | 163 |

8 | kostka | 161 |

9 | YouKn0wWho | 158 |

10 | antontrygubO_o | 154 |

omg hi!

I will add implementations soon.

**UPD**: Implementations are added

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

1504E - Travelling Salesman Problem

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #712 (Div. 1)

Tutorial of Codeforces Round #712 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/30/2023 20:21:30 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

omg hi!

Hey

Hey

Hello!!!

Recursion

Hi

Hi

imagine figuring that C out

Is there a proof to solution of C?

After adding brackets for positions where $$$s = 1$$$ you can observe that when you add a new pair of alternating brackets your balance will never be lower than zero after putting the first bracket and it will come back to the original balance after putting the second one.

Yes, that 'balance' thing is really nice way to approach.

But could you please explain the part where we fill first $$$\frac{k}{2}$$$ 1's with opening brackets and the rest with closing?

Imagine a 2d plane where (x,y) = (no. of unclosed open brackets in first sequence, no. of unclosed open brackets in second sequence). We can then map the 4 possible moves:

-> adding a '(' to first string when s[i]=1 => we go from x,y to x+1,y+1

-> adding a '(' to first string when s[i]=0 => we go from x,y to x+1,y-1

.. and similarly for adding ')' in both cases, we get opposite moves.

We start at origin, and our objective is to return to the origin after n moves without crossing any of the axes. If you draw it out on paper or something, it will be clear that by following the given strategy, we either stay on the x = y line or x = y + 1 line, and dont cross any of the axes, unless the string begins or ends with a 0.

Wow! This approach is really interesting. Thank You!

Your explanation is truly fantastic, I tried to rebuild it on my own, and it's super amazing!

Nice visualization. Helpful. Thanks!

Me : *trying to push monogon contribution to moon

Monogon : *making greedy problems that shove my rating into dirt

*sad cat noises

E is a good problem! I'm so close :(

Constructiveforces.

Sry，I went to the wrong place ，I come back to div3 immediately TAT

You are not alone...

Wow!! Fast editorials really helps. Thanks.

In E's solution 1 why only need to add i-> j+1? (i.e. don't need i->j+2....)

it's at least as cheap to go i->j+1->j+2 as i->j+2 because you get to subtract $$$c_{j+1}$$$. There's always a path from j+1 to j+2 because of either edge 3 or a combination of the edges from 1 and 2.

It can be proved that $$$cost(i,j+2)\ge cost(i,j+1)+cost(j+1,j+2)$$$. The following is the proof. Since $$$a_i$$$ is increasing and $$$cost(i,j+1)=a_{j+1}-a_i-c_i$$$, therefore $$$cost(i,j+2)=a_{j+2}-a_i-c_i$$$. So $$$cost(i,j+2)-cost(i,j+1)=a_{j+2}-a_{j+1}\ge \max(0,a_{j+2}-a_{j+1}-c_{j+1})=cost(j+1,j+2)$$$. Therefore, $$$cost(i,j+2)\ge cost(i,j+1)+cost(j+1,j+2)$$$, so we needn't add $$$i\ \rightarrow j+2$$$.

omg hi cyan

Can anyone proof solution of problem Div.2 D?

damn, I was correct for E. Just 10 min left to implement so couldn't implement in time. I wish I didn't cost much time at B

A. Déjà Vu

I. Deja vu

Pretest for div2B was very weak. Don't know why my O(n) solution exceeded the time limit 111887915

Your code is O(n^2) in the worst case since you are doing string z = b + z

Thanks got it!

You should probably look up what weak pretest means before commenting.

Sorry for my bad statement. But my solution passed the pretest with O(n*n) approach. And then failed the system tests.

Great problem set!!! 1-gon orz

Glad that Div2C, D, and E all passed in python3 even without pypy3!

one of the greatest contest i have ever partipicated in . thanks to the author. Waiting soon for ur next contest

If anyone wants to see how I overkilled 1C with 2 segment trees and coordinate compression and then forgot to sort wrt $$$a[]$$$ and couldn't get AC in contest : 111939130

Sorry I am stupid but can you elaborate div1C solution 2's formula

python: 111931953

C++: 111890876

Essentially each city must have an outgoing cost of its floor. Additionally, we're going to need to pay the cost max(a) — min(a). However, if we use a sequence of cities to go from min(a) to max(a), we can use the floors to "pay" for max(a) — min(a). In other words, we only need to pay for the parts of the segment from min(a) to max(a) that aren't already paid for by the floors of the cities along the way.

I mean I can understand the dijkstra one and everything before, but I can't understand why the formula in solution 2 is true.

I think its missing the sum of c , otherwise it should be correct . the summation in the editorial is counting how much extra cost we have to pay to reach i if we can jump from any city j with j<i which is $$$(a_{i} - a_{j}) - c_{j}$$$

I didn't understand either. I think the wording is kind of confusing.

The formula is $$$max(0,a_j-a_i-c_i)$$$. There are two cases. If $$$a_j>a_i+c_i$$$ then $$$a_j+c_j$$$ must update the greatest value. Otherwise $$$max(0,a_j-a_i-c_i)=0$$$ and it won't contribute to the answer.

I think we actually need a detailed analysis to justify the formula. Maybe I am just not that good for having the intuition, though.

Here is the analysis, consider constructing the path from a1:

Lemma 1. Consider without max(0,), it is always beneficial for us to break one step into two steps.

proof: two step cost is a[3]-a[2]-c[2] + a[2]-a[1]-c[1], one step cost is a[3]-a[1]-c[1], since c[2]>0 the two step cost is better.

Now add max(0,) back, so sometimes breaking steps are useless (but never worse).

Lemma 2. To reach the i-th block, the one step with minimum cost is from j with max a[j]+c[j] before.

proof: I am not considering the steps before j but only this step, this should be trivial.

Now let's call this maximum a[j]+c[j] "premax". (prefix max)

Lemma 3. If we reach some i such that a[i]>premax, than a[i]+c[i] becomes new premax in the next iteration. Let's call such i "breakpoint". Also note that when reaching a breakpoint, the cost>0 so max(0,) is useless and thus we can apply Lemma 1 later.

proof: Because c[i]>0. So a[i]+c[i]>a[i]>premax.

Combine these all, we would obtain the strategy. Strategy:

Suppose we are standing at some certain block, then we can keep going right and update premax with zero cost until we reach a breakpoint. Then because of Lemma 1 we should make a step to the breakpoint, and because of Lemma 2 we should go from the premax we've found. Because of Lemma 3, paths like this won't happen: i -> j -> i -> k (where a[i]+c[i] is the premax for both j and k) since j would be the premax for k. So we won't need to step on a premax twice, which allows us to reconstruct a Hamiltonian Cycle later. Thallium54 Although not rigorous, hope this helps.

Lemma 1 is important. Thanks for the explanation.

I think this is the reasoning behind the formula: we want to get from $$$a_1$$$ to $$$a_n$$$ in a number of steps, with the minimum cost. If these steps are $$$s_1, s_2, ... s_k$$$, with $$$s_1 < s_2 < ... < s_k$$$ ($$$s_1 = 1$$$ and $$$s_k = n$$$), then the path will be $$$a_{s_1}, a_{s_2}, a_{s_3}, ..., a_{s_k}$$$. So the $$$a_i$$$ not included in the step series will be the nodes on the path from $$$a_n$$$ to $$$a_1$$$.

In the summation, I found it a bit easier to do it backwards (from $$$n$$$ to $$$1$$$, the final answer will remain the same): so, firstly, we want to see from which node $$$a_j$$$ we get the best cost from $$$a_j$$$ to $$$a_n$$$ and, as the editorial shows, it's the $$$j$$$ with the maximum $$$\max(a_j+c_j)$$$. So this $$$j$$$ will be the the step $$$s_{k-1}$$$. Then, when we have $$$i = j$$$, we update the $$$j$$$ index for the next best $$$\max(a_j+c_j)$$$ and this new $$$j$$$ will be $$$s_{k-2}$$$.

We repeat this process until we reach $$$i = 1$$$, when we know for certain that we have calculated the whole step series (because then we just get that $$$s_1 = 1$$$, which we already knew). So basically we construct the path from $$$a_1$$$ to $$$a_n$$$ edge by edge, the only difference between my explanation and the editorial being the order in which we construct the step series. The $$$i$$$ indexes for which we have $$$a_i-\max_{j<i}(a_j+c_j) \leq{0}$$$ will belong to the path from $$$a_n$$$ to $$$a_1$$$.

All the proofs above are extremely cool and clear up the whole idea. Colin's stream has also a similar proof. I got it from there. Folks can see there too if they are still unsure.

I guess I'll also put my proof here, since I've been thinking about it for a while.

The problem is the following: you are given a weighted directed graph with $$$n$$$ vertices (numbered from $$$1$$$ to $$$n$$$). The $$$i$$$th vertex has outgoing edges to all vertices $$$j < i$$$ with weight $$$0$$$, and outgoing edges to all vertices $$$j > i$$$ with weight $$$\max(0, a_j - a_i - c_i)$$$. What is the weight of the shortest path from vertex $$$1$$$ to $$$n$$$, plus $$$\sum c_i$$$?

This problem is equivalent to the original problem, because any path from vertex $$$1$$$ to $$$n$$$ in this problem can be turned into a tour in the original problem with the same cost: simply follow the same cities along the shortest path from $$$1$$$ to $$$n$$$, and then visit all unvisited cities (plus city $$$1$$$ to complete the tour), in decreasing order. Furthermore, the weight of the shortest path from vertex $$$1$$$ to $$$n$$$ is a lower bound for the answer in the original problem, since some path from city $$$1$$$ to $$$n$$$ must exist in the tour.

To find the weight of the shortest path from $$$1$$$ to $$$n$$$ in the new problem, define $$$dp[i] := \max(0, a_i - \max\limits_{j < i}(a_j + c_j))$$$ for $$$1 < i \leq n$$$ (same expression as in the editorial) and $$$dp[i] := 0$$$ for $$$i = 1$$$. Let's prove that the weight of the shortest path from $$$1$$$ to $$$n$$$ is equal to $$$\sum\limits_{i = 1}^{n} dp[i]$$$ using induction from $$$1$$$ to $$$n$$$.

Our inductive hypothesis is the following: suppose we're at step $$$k$$$; then for all $$$1 \leq j \leq k$$$, the weight of the shortest path from vertex $$$1$$$ to $$$j$$$ in the subgraph containing the first $$$j$$$ vertices is equal to $$$\sum\limits_{i = 1}^{j} dp[i]$$$.

This is true for $$$k = 1$$$, because the weight of the shortest path from vertex $$$1$$$ to $$$1$$$ in the subgraph containing one lonely vertex is $$$dp[1] = 0$$$.

Now suppose we're at step $$$1 < k < n$$$ and that the inductive hypothesis is true for $$$k$$$; let's show that the inductive hypothesis is true for $$$k + 1$$$. There must exist some last directed edge $$$(u \rightarrow k + 1)$$$ in some shortest path from $$$1$$$ to $$$k + 1$$$.

Firstly, let's show that all previous shortest paths don't change by adding vertex $$$k + 1$$$ to the subgraph. Suppose that there exists some $$$1 \leq j \leq k$$$ such that the shortest path from $$$1$$$ to $$$j$$$ decreases by adding this new vertex. Then one such new path must be a concatenation of some shortest path from $$$1$$$ to $$$u$$$ (in the subgraph containing the first $$$k$$$ vertices), plus the edge $$$(u \rightarrow k + 1)$$$, and then the edge $$$(k + 1 \rightarrow j)$$$. If $$$j \leq u$$$, then the previously computed shortest path from $$$1$$$ to $$$j$$$ must have been at least as good, since prefixes of $$$dp$$$ are monotonically increasing. If $$$j > u$$$, then the concatenation of the shortest path from $$$1$$$ to $$$u$$$, plus the edge $$$(u \rightarrow j)$$$, is at least as good, because the weight of the edge $$$(u \rightarrow j)$$$ is less than or equal to the weight of the edge $$$(u \rightarrow k + 1)$$$. Either way, there is a contradiction.

Now let's show that the weight of the shortest path from $$$1$$$ to $$$k + 1$$$ in the subgraph containing the first $$$k + 1$$$ vertices is equal to $$$\sum\limits_{i = 1}^{k + 1} dp[i]$$$.

Welp, my tablet pen clicked outside of the comment box, so I lost a bunch of work... Just gonna give up here... In short, the idea is the following: let $$$j$$$ be the greatest index such that $$$dp[j] > 0$$$, or $$$j := 1$$$ if no such index exists. Then it must be true that $$$u \geq j$$$. Since all prefixes past $$$j$$$ are the same, it doesn't matter from which one we transition from. So we can just choose the index $$$j \leq i \leq k$$$ with the maximum $$$a_i + c_i$$$ value, and transition from that. Turns out, the maximum $$$a_i + c_i$$$ value in general (for $$$i < k + 1$$$) must lie in that range.

After reading the explanations here, I was able to understand a bit more about the formal-"why does it work", but I still had not intuitive-"why does is work". After sleeping and thinking and trying, what finally helped me understand it, in the editorial we have this implementation:

I didn't get how this works, and why this works. I made another implementation for myself.

It is pretty much the same... I added an if-statement and removed the

`max(mx, ...)`

from calculating`mx`

. But it changes one thing, which helped me understand this. The summation to`sum`

is more explicit. We only add something, if we can improve our`mx`

. This means we check each city from the ugliest city to the most beautiful one and always enter a city if we can improve our`mx`

. The algorithm is 100% greedy now.It's also the same as in the editorial.

`ve[i].first - mx > 0`

implies`ve[i].first + ve[i]second > mx`

. So we also only add when we can improve`mx`

.I have no prove why this works, but this helped me on the "intuition"-part, why it should work.

You can see my comment for the proof. I agree that my explanation makes the solution not intuitive.

B was so hard for me:( i'm solve it after 1 hour.

How many hours do you code per day bro? Your graph is scary

Those who solved div2C,how do you guys think of that solution?

This was my approach during the contest.

The first and last char should be 1 because if it is 0 at any of these positions then the string can't be complete {i.e they will look like (...( and (...) }. For the answer to exist, the count of 1 and 0 should be even (self explanatory) and the prefix sum in both the string should be >=0 at any index, if we give +1 for character being '1' and -1 for being '0' and total sum should be 0. (just like we do in checking balanced parenthesis).

For finding the strings: For index with val = 1, put '(' for half the times and ')' for other half. {Eg- If the string is 11100111, then both the strings will be initialized by (((00))) } For index with val = 0, start with ( and alter for rest of the indices for the 1st string and for obtaining the 2nd string, start with ) and then alter. {Eg — If the string is 1001000011, then x = 1()1()()11, y = 1)(1)()(11 and one can be substituted by the above method }

If you carefully observe, this procedure basically leads to prefix sum >= 0 at every index.

uh.. I am not satisfied with the solution.. probably because I couldn't come up with a convincing proof..

To add on that I thought that perhaps the editorial would have some mention of proof (up to the part of even number of zeroes it is fine)

but it seems the construction just works in favour over any other possible construction you can manage to do..

So you can do some drawing on paper and see that you want to keep the stuff as close to 0 otherwise the bracket sequences will diverge and I guess that's closest to what can be called a proof.

(What hasn't been mentioned though that the prefix sum criteria is usually followed with this construction i.e prefix sum >= 0 except for 1 — 2 cases, the only thing which needs to be taken care of is to get a final sum of 0 and this construction works in favour of it)

While I figured out the first two observations mentioned in C's editorial, how do I arrive at the idea to populate the first k/2 1's with '(' and the last k/2 1's with ')' and then alternate the 0-positions?

Does anyone have any advice on what I need to think about or ask myself, to reach this idea?

Since the string must always end with a '1' and start with a '1', all '0's will be sandwiched by '1's, so it would look like ((( ()()() ))) and ((( )()()( ))). The net number of '('s is simply carried forward by the ()()() or )()()(. hope this tells you something new...

I see, so the idea that the 0's in the input string will have zero long-term effect on the running sum if they're alternating, allows me to handle the 1's separately and then just fill in the 0's with alternate brackets.

Had I thought of input strings like 110011 or 1111000011 then this may have struck me, but I got confused with imagining inputs which had alternating 1s and 0s.

Anyway, thanks!

is there a proof for Div2C?

Proof

Standard parenthesis validity checker: counter++ for '(', counter-- for ')'. The sequence is valid is counter is always non-negative and hits zero at the end.

Now, let's assume the string starts with '('. Counter = 1.

Every time string A[i] = B[i], we have either a counter++ or counter-- at both places.

So, it's safe to do the counter++ for the first half and the other for the second.

For A[i] != B[i], every 2 0s, can reset counter to 0 in both the strings. If the number of 0s is odd, there's an unsymmetrical counter residue that cannot be cleared by the equality case (as the equal case adds the same number to both A and B).

From these observations, there needs to be even number of 1s and 0s.

First half of 1s should be open, 2nd half of 1s closed.

Odd-even flip of paranthesis order for 0s.

Is it just me who lost problem D because the pretests didn't have the n=2 case?? I'm deeply saddened by this and it has affected my confidence. Was this a conspiracy against negligent coders like me?? (sobs profusely.)

Forgot to thank the creators for this amazing contest. The problems were really fun and they kept me at the edge of my seat!

The very first pretest was n = 2 though...

oh sorry, but i failed the 16th test case which had n=2, i must now proceed to quit codeforces, thanks for pointing out. bye. i will now delete all my comments

I was just an '=' away from getting AC on B. Oh Man! This is such a drag.

I don't understand why my n^4 solution passed in Div 2 D, here is link https://codeforces.com/contest/1504/submission/111924524

$$$n$$$ is only $$$100$$$ and constant factor is pretty low and time limit is $$$3$$$ secs.

IMO only the ones that solved C will understand its editorial.

(A + B) VIDEO EDITORIAL : https://www.youtube.com/watch?v=2DBLj6IOJJc

nice

Alternative solution for 1504E - Travelling Salesman Problem

Basic observation is similar. Cost for $$$i→j$$$ is $$$c_i + max(0, a_j - (a_i + c_i))$$$. There is another thing to look for. We can start from any city instead of city $$$1$$$ and still get same answer as our path is a cycle. That's how, we can just sort the cities based on $$$a_i$$$. Now, starting from the lowest $$$a_i$$$ city, we can go one by one and we can do transition from most optimal city to current city based on $$$(a_j + c_j)$$$ values.

Code — 111946687

Proof?

This is literally the second solution in the editorial.

My bad, didn't understand what he meant at the 2nd solution, it looks like implementation is exactly same. Now I just noticed that sorting was mentioned in the very beginning.

I couldn't understand either. Can you elaborate your solution?

I am not entirely sure if this proof is correct, but this is how I convinced myself of this solution. Sort array a. So we have a1<=a2<=a3....<=an

We start at a1. We want to greedily spend as little as possible. That is it would be locally preferable to have a 0 cost on going to the next city. Consider the set S of all cities having ai <= a1+c1. Obviously, S would be of the form {City 2, City 3...., City k} for some k.(City i has value (ai,ci). a is increasing after all:/).

Now, simply go to city 2, There are two cases a2+c2 < a1+c1. In this case, having a1 in the front is better than having a2, since from a1 we can go to more cities free of cost. So we try rearranging the visiting pattern. We start from a2. Visit a1 free of cost since a2+c2>a1. Now, we have a1+c1 again at the front and we can visit other cities in S free of cost. In the other case, a2+c2 > a1+c1, in this case, don't change the ordering since a2+b2 in front would allow us to potentially visit even more vertices free of cost than those contained in S.

This can be expanded to arbitrary lengths by induction. Say that you have observed {City 1, City 2, City 3,...., City k-1} and found a permutation such that the city with the maximum value of (ai+ci) observed so far (call it j) is in front. We prove that there exists an optimal ordering with this property. By Induction Hypothesis, assume this works for k-1. Then, The order of visit so far will then be {'Some other cities in some optimal order', City j} and this is the most optimal of all orderings possible with the available cities. Now the next city k can have 3 possibilities.

Case 1: a_k > a_j + c_j In this case, there is no way to get 0 costs using any of the previously visited cities. Using aj+cj which is the maximum observed so far is the best choice in minimizing the current cost(a_k — (a_i+c_i)) for any i<k. In this case, the optimal order of visiting is {'Same order as before', City j, City k} and a_k + ck has the maximum value among all {a_i+c_i} observed so far! So the Induction Hypothesis holds here! We have expended minimum extra cost to add City k to what was already an optimal visiting order.

Case 2: a_k <= a_j + c_j and a_k+c_k > a_j + c_j. Again keep the order as {'Same order as before',City j,City k}. This involves 0 cost and the front element (k) has the maximum { ai+ci } value observed so far. We have expended 0 extra cost here!.

Case 3: a_k <= a_j + c_j and a_k+c_k <= a_j + c_j. This time we would like City j to be on the front and at the same time expend 0 extra costs for visiting City k. The solution is to simply visit City k first. The resulting order will be {City k,'Nothing changes in between', City j}.

Proceeding this way, this strategy optimises the local value every step of the way and hence would give us the globally optimal solution.

Please correct me if I am wrong.

Can anyone provide a logical chain of Div2C? I understand how the answer is constructed but I am confused about how we come up with the idea from scratch and know its correctness.

https://codeforces.com/blog/entry/89319#comment-777575

Can anyone help with the TLE error for div2B My solution

This code is O(n^2).This line is actually c!=s1.length() O(n) in nature followed by for loop. U should use simulation starting from rightmost unmatching bit and using flips as a variable.

Thanks it worked :)

traveling sales man problem is NP hard so how it's possible to solve problem DIV2 E or DIV 1 C for given constraints ?

OK

Thanks very useful response .

YES

The problem given wasn't actually traveling salesman. It was a variation which could be solved much faster when you make some observations.

Is there a way I could look at test case 60 and like that for a pretest. It is shown for the first few testcases like till 30 approx. . I wanted to know if I could download or view the complete test case file or at least the first test case where I made mistake . Is it possible ?

very thanks for help, that was what I needed . How can one find it?

I generated random string with length 8 and compare your solution verdict and mine (AC solution) verdict

Great. Thankyou for help again sevlll777.

omg hi !

The solution described for C Div. 2 would give identical strings in case the input has only 1's. Is that the expected behavior or those should be different?

Did you mean deterministically single answer for a fixed length?

If so, yes, although there can be other valid answers.

The strings being identical is the expected behavior.

All 1s indicate that all positions are equal, which implies equal strings.

To decompose an array into two decreasing subsequences, there is a standard greedy approach.Can you share it please?

https://www.google.com/amp/s/www.geeksforgeeks.org/minimum-number-of-increasing-subsequences/amp/

(just swap the terms increasing and decreasing)

Essentially you build some sequences as you process the elements. Always add an element to the end of the first possible subsequence.

Can you please explain what's Wrong with my Code in D: 111943902

It seems that when you output b, i, j, the coordinates (i, j) are out of bounds.

Greedyforces

So many greedy problems! (I love greedy!)

How to solve 2F/1C for dp

maybe it's impossible

YESorNOforces

Although I always lose rating in your contests, I really like your problems :)

Anyone please help me in C , Here is my submission 1504C

I have taken two characters from string at a time and created two brackets array according to them

(if first two chars are 10)

10 -

ch1+=()

ch2+=((

11 —

ch1+=()

ch2+=()

01 —

ch1+=()

ch2+=))

This is done iteratively and at last i checked both brackets array for balance using stack then accordingly printed "YES" or "NO"

I am not able to figure out why it is failing in test case 2 only .

Consider the following case: 10010101

Now as per your algo: a = ()()()() b = (()))))) And so you will print "NO". But it is possible to find valid bracket sequences and they are as follows: a = (()(())) b = ()(())()

Hope this helps.

111968151

For problem A, Insert 'a' into the symmetrical position of the first letter that is not equal to 'a', why it is wrong ?

You should insert it into the position n-i, not n-i-1. For example, on the test case bab you output baab instead of baba.

Thanks for reminding!

I misunderstood the usage of insert

https://codeforces.com/contest/1504/submission/111914872 my code runs well if i use Sytsem.out.println. But when i append my ans on bufferWriter it does not show the String with extra 'a' in codeforces ide but when running on my eclipse ide it gives correct output. Why is it so?

That isn't the only difference between your codes. You also changed i<n/2 (which causes the wrong answer) to i<=j(which is correct)

I think in the editorial of Problem E, it should be mentioned that it is always optimal to go from i to j+1 instead of j+2,j+3,j+4 etc....

111918468 Problem C, what's wrong with my answer? Input: 4 1111 Output: YES ()() ()() Checker: wrong answer a[i] = b[i] <=> s[i] = 1 broken at i = 1 Thank's for help)

On the test case

1

4

1011

You don't output anything.

People after submitting C : Well prob was easy , i can go to D now. . . . test-case 64 : You ain't going anywhere.

Could someone please explain why in the last part of the tutorial of Div1D "there is a unique way to decompose each segment"?

Took me a while, but I think I figured it out. Suppose that we're trying to find a decomposition for some segment $$$[a, b]$$$ ($$$1 \leq a \leq b \leq n$$$). Let's maintain two subsequences $$$s_1$$$ and $$$s_2$$$, initially empty at the start of the segment. Without loss of generality, let's immediately add $$$f(a)$$$ to the end of $$$s_1$$$. Now let's greedily choose placements for all characters in the range $$$[a + 1, b - 1]$$$ (yes, this is intentional).

Firstly, let's define $$$s(i) = \max\limits_{j > i} f(j)$$$ for $$$0 \leq i < n$$$ and $$$-1$$$ for $$$i = n$$$. Similarly, let's define $$$p(i) = \min\limits_{j \leq i} f(j)$$$.

Suppose that we're currently choosing a placement for index $$$i$$$. Now, there's 2 cases: either $$$f(i) > s(i)$$$, or $$$f(i) < s(i)$$$.

In the first case, since there's no divider between $$$i$$$ and $$$i + 1$$$, it must be true that $$$p(i) < s(i)$$$. Furthermore, $$$f(i) \neq p(i)$$$, since $$$f(i) > s(i)$$$ and $$$p(i) < s(i)$$$. Therefore, $$$p(i - 1) = p(i) < s(i)$$$. The key observation here is that $$$p(i - 1)$$$ must be equal to some $$$f(j)$$$ for $$$a \leq j < i$$$ (since either this segment was the first one, or there was a divider before this segment), and therefore must also be the value at the end of either $$$s_1$$$ or $$$s_2$$$. Since $$$f(i) > p(i - 1)$$$, it must be added to whichever subsequence doesn't end with $$$p(i - 1)$$$.

In the second case, it must be true that $$$s(i - 1) = s(i)$$$. Since there's no divider between $$$i - 1$$$ and $$$i$$$, it must be true that $$$p(i - 1) < s(i - 1) = s(i)$$$. Once again, $$$p(i - 1)$$$ must be at the end of either $$$s_1$$$ or $$$s_2$$$. This time, we must add $$$f(i)$$$ to whichever subsequence has $$$p(i - 1)$$$ at the end of it, since otherwise we would have both subsequences ending in something less than $$$s(i)$$$, which is impossible.

What's left is determining in which subsequence $$$f(b)$$$ should go (if $$$b = a$$$, then we're done). Suppose that $$$f(b) < s(b)$$$. Then $$$s(b - 1) = s(b)$$$. Since there's no divider between $$$b - 1$$$ and $$$b$$$, $$$p(b - 1) < s(b - 1) = s(b)$$$. However, this is a contradiction, since this implies $$$p(b) \leq p(b - 1) < s(b)$$$, which shouldn't be the case if either there is a divider between $$$b$$$ and $$$b + 1$$$, or $$$b = n$$$. Therefore, $$$f(b) > s(b)$$$. It follows that $$$p(b - 1) < s(b - 1) = f(b)$$$. Once again, since $$$p(b - 1)$$$ is at the end of either $$$s_1$$$ or $$$s_2$$$, $$$f(b)$$$ must be placed at the end of the other subsequence.

In all cases, the choice of adding to the end of either $$$s_1$$$ or $$$s_2$$$ is deterministic. Note that if we began by adding $$$f(a)$$$ to the end of $$$s_2$$$ instead of $$$s_1$$$, all decisions would have been swapped due to symmetry, hence the only choice we have to make is which subsequence is which.

lmk if I made any mistakes, I'm too tired to proofread :D

How to solve D1D with 2-sat?

Can anyone help me why my O(n) solutions: 112036570 and 111956392 both give TLE?

You are creating array 'arr' many many times

I moved the declaration above my while loop here: 112037826 and it still gives me TLE.

I'm not sure but seems that

`scanf(" %s", &arr);`

is`O(n)`

not`O(the size of the string)`

so try to use`string arr`

instead of`char arr[300001];`

You can only create char arrays in C for strings.

Use C++

That doesn't solve my question and I've seen passed attempts in C that use scanf.

Ok I'm really sorry I don't know C

112208235

I changed

`scanf(" %s", &arr)`

to`scanf("%s", &arr)`

and got AC. I have also ever faced similiar bug, but I don't understand the cause as well. Maybe somebody else might be able to explain.My approach for Problem div2C: Let us consider balance of a string as the difference of opening and closing brackets. So in order for the string to be perfectly balanced, the balance of the string should never be < 0 in any iteration and should be 0 at the end of all iteration.

bal1=balance of 1st string bal2=balance of 2nd string

the main approach here is that we want our balance to be as close to 0 as possible.

Notice that '1' always increases or decreases the balance of both string by 1 and '0' decreases the balance of one string and increases the balance of the other one.

Therefore we would greedily increase or decrease the balance of both the string so that their balance remains closer to 0.

There is also an edge case where bal1=1 and bal2=1 and the current position in string has '1' in it. in this case we have to check the next character of the string.

Why we have to check the edge case?

As because greedy solution will decrease both the balance by 1 and if the next character is '0' then balance of one of the string would become negative.

My solution:112041165

In Div1 D : "We can independently choose how to decompose each segment into two subsequences" Can anyone tell me how to decompose a single segment ?

Anyone ?

Monogon

You can decompose a single segment using the greedy algorithm mentioned here.

https://codeforces.com/blog/entry/89319?#comment-777475

This gives you two sequences, and you just have to choose which one to call the first subsequence. Choose the one that requires the fewest flips.

Thank you! I got it

Div1C/Div2E can also be solved using disjoint set union (similar to Kruskal's algorithm). My code

Can someone explain the intuition behind solution 1 of Div1 C? I don't know how to come up with that implicit graph.

The intuition is that we've reduced the problem to shortest path in a graph with $$$O(n^2)$$$ edges. We just have to think which edges are redundant (because the other edges create a better or equal cost between the same pair). If you remove enough redundant edges, you find that you only need $$$O(n)$$$ edges.

Can anyone help me in finding the mistake in Problem D Div 2? I am doing as per the editorial only. It is failing on Test Case 6. 111982213

In problem DIV2 F (flip the cards) , could someone explain the intuition behind splitting the array into segments based on condition that minimum to left of $$$i$$$ is greater than maximum of right to $$$i$$$. I didn't get why we are doing this.

What i understood is that it's necessary we need to split [f(1),f(2),f(3),...,f(n)] into 2 decreasing subsequences (where one can also be empty). If we minimize length of one of the subsequence then number of flips would be minimized . But how we splitting is helping us here ?

Monogon could you please help here why we are splitting when minimum to left of $$$i$$$ is greater than maximum of right to $$$i$$$. I understand that finding $$$2$$$ decreasing subsequence directly might not give optimal solution . So how we justify that splitting it like that will help us find the optimal solution ?

According to the editorial two subsequences will be unique if we split in that way. How to prove it ?

Suppose there is a place where the prefix min is greater than the suffix max. Then if we split here and decompose the two halves independently, they can be combined in any way, and it will still be a valid decomposition into decreasing subsequences. The fact that we can make independent choices is intuitively good, because we can now focus only on optimizing each individual choice.

We need to show that an array with no position such that prefix min > suffix max has a unique decomposition into two decreasing subsequences (up to naming the two subsequences). Consider the maximum element in the array, let's say it is in subsequence $$$1$$$. It cannot be the first position since it would violate the condition, so everything before it must be in subsequence $$$2$$$.

Now we have the unique decomposition of the prefix. Now consider the maximum element of the remaining elements. We cannot place it in subsequence $$$2$$$, or it would violate our assumption. So we are forced to place it in subsequence $$$1$$$, and all unassigned elements before it must be in subsequence $$$2$$$. Keep repeating this process until all elements are assigned to subsequences. Every decision we made was forced except for naming one of the subsequences $$$1$$$ and the other $$$2$$$, so it is the unique decomposition.

i write my solution in python, its a O(n) solution can someone tell me why i am getting this tle? https://codeforces.com/contest/1504/submission/112123685

Rule nth: Always submit string involved code in Python 3 not PyPy 3.Reason: https://stackoverflow.com/questions/37133547/time-complexity-of-string-concatenation-in-pythonIn Div1 problem F,how can I get the solution after doing operations? And how can I find the leftmost point? I found judge points by ai>0,bi>0 will get wrong. thanks :)

You should find a point with $$$a_i>0$$$, $$$b_i > 0$$$, has an incoming $$$1$$$ edge, and has an outgoing $$$1$$$ edge. With these conditions, the choice doesn't matter.

By doing operations, we represent the curve implicitly by a linked list of the points (besides the leftmost one) as they appear horizontally. Each point keeps the card ID, so in the end the solution is given precisely by the order of elements in the linked list.

And how can I do operator 3?

Should I keep the head,tail of the linked list,and the places of incoming edge and outgoing edge?

I think it is a little troublesomely to merge two linked list,or maybe I lose some properties :(

You can look at 111940018 for the list solution. (It's also solvable using treaps, relevant submission: 111939934, and both solutions use a similar interface for the curve structure).

What a crazy problem with so many details...

can someone give me the input string that failed my solution code?

My Solution

`abaa`

Try

Edit: Alwyn was faster :D

Statement in tutorial of Problem 1504F: "Also, there is a unique way to decompose each segment: the only choice is in which one we call the first subsequence". Why it is unique? Could someone give me a detailed explanation, thanks~

Alternative (messier?) solution for 1503D - Flip the Cards

Actually it turns out to be very similar to the solution in the editorial, but maybe the "path" to this solution is more intuitive.

Consider each card as a segment $$$[\min(a_i, b_i), \max(a_i, b_i)]$$$. Let's say that a segment has color $$$0$$$ if $$$a_i < b_i$$$, $$$1$$$ otherwise.

If two segments don't intersect, there is no solution. Two segments such that the biggest one contains entirely the smallest one can be colored in any way. In any other case, the two segments should have different colors.

Let's find a coloring of an interval of length $$$n$$$. Our goal is to construct a graph such that two segments connected by an edge have different colors. If there is a solution, the graph is bipartite: for every connected component, there are two possible colorings, and we have to choose the one that minimizes the number of flips. There are two cases:

There are three types of segments: inside $$$[y, x]$$$, inside $$$[1, x]$$$ but not $$$[y, x]$$$, inside $$$[y, n]$$$ but not $$$[y, x]$$$. If two segments of type $$$2$$$ are connected by an edge, they also form a cycle of length $$$3$$$ with $$$[y, n]$$$. Hence, all the pairs of segments of type $$$2$$$ (and $$$3$$$) are such that the biggest one contains entirely the smallest one. Hence, the special segments and the segments of type $$$2$$$ and $$$3$$$ make a connected component, and any of them isn't connected to a segment of type $$$1$$$. Then, the problem can be solved recursively in the interval $$$[y, x]$$$.

How to find all the connected components in $$$O(n)$$$? For each component, we can find the segments of type $$$2$$$ and $$$3$$$ in $$$O(\text{# of such segments})$$$. Let $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$ be the special segments. While there exists a segment $$$[l, r]$$$ with $$$l < l_2$$$ and $$$r < r_1$$$, replace $$$[l_1, r_1]$$$ with such $$$[l, r]$$$ with minimum $$$l$$$. Do the same for $$$[l_2, r_2]$$$, then again for $$$[l_1, r_1]$$$, etc., until no more segments can be found.

112259448

nice solution i have some ideas of another graph model of the problem but ive didnt finished it maybe you can help me with it! my idea : if we consider 2n graph nodes which the node 2i is the i-th card normally and the 2i — 1 is the reverse of the i-th card and if we put a directed edge between node v, u(v -> u) it means that the representing card of u has bigger elements on both representing sides(like card v = {1, 5}, card u = {3, 6}) in this graph we dont have directed Cx(cycle with lengh x > 2) and we dont have even directed P3(v -> u -> z) if we have, the answer is -1 because in the answer there will be two of them in same side. so the graph is some directed stars but ive couldnt do any decomposition to get the answer do you have any idea?

Directed edges don't seem to work (if I understand, they make a dag so they can't make cycles). If the edges are undirected, you can have cycles of even length and an answer $$$\neq -1$$$ (for example, $$$(1, 6) \leftrightarrow (3, 8) \leftrightarrow (2, 5) \leftrightarrow (4, 7) \leftrightarrow (1, 6)$$$). In your graph, there are edges between each pair of cards that in my solution is $$$(\text{card of type 2}, \text{card of type 3})$$$ in the same connected component. For example, in $$$(1, 6)$$$, $$$(2, 5)$$$, $$$(3, 8)$$$, $$$(4, 7)$$$, there is only one connected component, with

well the directed graph has the star property because in your example the graph is kinda like this -> a -> c, b -> c, a -> d, b -> d. idk just and idea : ))

Yes, every connected component is a complete bipartite graph. But there may be more than $$$1$$$ connected component, for example in $$$(1, 7)$$$, $$$(2, 8)$$$, $$$(3, 5)$$$, $$$(4, 6)$$$.

[user:Mihir2422]hi

For problem 2-Coloring, when you mention

What exactly does it mean? For example, for the (x, y) mentioned, are the Ox and Oy the normal mathematical Ox (left to right) and Oy (down to top)? Or are they row (top to bottom) and column (left to right) axes?

Can you give a clearer example?

Coordinates are (row, column). Here is a picture of the described situation.

Extremely elegant and fast solution for F: 123227611