Hey

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.

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.

You are not alone...

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

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

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

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

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:

    sort(ve.begin(), ve.end());
    long long mx = ve[0].first + ve[0].second;
    for(int i = 1; i < n; i++) {
        ans += max(0LL, ve[i].first - mx);
        mx = max(mx, ve[i].first + ve[i].second);
    }

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

    sort(ve.begin(), ve.end());
    long long mx = ve[0].first + ve[0].second;
    for(int i = 1; i < n; i++) {
        if(ve[i].first + ve[i].second >= mx) {
            ans += max(0LL, ve[i].first - mx);
            mx = ve[i].first + ve[i].second;
        }
    }

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.

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

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)

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

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.

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

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

Proof?

This is literally the second solution in the editorial.

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

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.

OK

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

1
8
10011001

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.

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.

So many greedy problems! (I love greedy!)

maybe it's impossible

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.

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.

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)

On the test case

1

4

1011

You don't output anything.

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

You are creating array 'arr' many many times

Anyone ?

Monogon

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

https://codeforces.me/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.

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.

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 ?

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-python

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.

abaa

Try

1
abaa

Edit: Alwyn was faster :D

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?

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