It's good when your eye doesn't put extra symbols while reading. It would be really helpful when debugging. :))

Thank you, fixed.

Okay, so let us put it this way. Let's consider the normal graph where you can go from an index $$$i$$$ to an index $$$j$$$. And you add an edge between $$$i$$$ and $$$j$$$ only if the values at those indices are of same [CORRECTED] parity, right, else you could simply put the answer for index $$$i$$$ as 1 and proceed for the other indices. Now we have a graph with out-going edges (from $$$i$$$ to $$$j$$$ means an out-going edge). It is clear that answer for index $$$i$$$ will be one more that the answer for index $$$j$$$, as $$$i$$$ and $$$j$$$ house the same parity elements, and you can go from $$$i$$$ to $$$j$$$ (if you can also go from $$$j$$$ to $$$i$$$ that's a different scene, not considering it here).

For answer to exist for indices $$$j$$$ and $$$i$$$, there should be a path from $$$j$$$ to some index (maybe through a series of other same parity elements) with the opposite parity as $$$a[i]$$$, (this has to hold for a possible solution, i.e. two opposite parity reachable in one step values of array should exist). Say that index is $$$k$$$ and it came after traversing a path from $$$i$$$ to $$$j$$$ to some series of other indices of same parity as $$$a[i]$$$. This index $$$k$$$ goes to the queue as it is the source for all the elements coming to it.

So, if you build the normal graph, that is add edge to k, not from k, during bfs, you won't go anywhere from $$$k$$$ (atleast not towards the indices $$$i$$$, $$$j$$$ and others on path from them to $$$k$$$). Hence building the normal graph fails to give a solution. (One may think of using DFS with the normal graph, but DFS doesn't guarantee a shortest path, and dealing with cycles will become very terrible)

Thus building the inverted graph ensures that you start from a source (here $$$k$$$), and go back to the nodes you used to reach the source (here $$$k$$$)

Hope this helps !!

Yet another pattern of reasoning for this might be the following one: We do not know what the shortest distances from, e.g. even-to-odd nodes are (we are asked to find them), but we know for sure that the shortest distances from odd nodes to odd nodes are all 0s.

Based on that we traverse the graph backwards to get the final answers for even nodes. Repeat the same for odd-to-even nodes. Took me a while to understand this.

It can be $$$N$$$, I just wrote the solution earlier than editorial and didn't notice that I used $$$2N$$$ instead of $$$N$$$ in the code.

Do you mean dp[i][1] is the maximum length of subarray of the prefix until index i, after an element between 0 and i inclusive has been deleted?

For problem a, let's assume that a <= b <= c, so |A-B|+|A-C|+|B-C| is equal to 2 * |A-C|.

so we just need to consider the value of |A-C|.

If |A-C| <= 2 then you can always move point a, b, c to a same point, temp answer is 0.

If |A-C| >= 3 then the minimun temp answer is |A-C|-2.

temp answer times 2 is the answer.

It is because |A-B|+|B-C|+|C-A| represent twice the length of the line joining the three points on number line. You can think of this problem as trying to shorten the length of the line. Since you can move the endpoints at most 1 unit towards each other, you can at at most shorten the length by 2 units. Now, since the answer asks for twice of length of the new line segment, the answer is basically oldLength — 4, which is equal to |A-B| + |B-C| + |C-A| — 4. But we are missing one case, when the length is less than or equal to 2, we can simply reduce the line to a single point. So the answer simply becomes max(2 * oldLength — 4, 0).

In problem A, assume a<=b<=c, the pairwise sum=(|b-a|+|c-b|+|c-a|). Now since a<=b<=c, we can open the absolute/mod signs, therefore sum=(b-a+c-b+c-a)=2*(c-a). Now we have to minimize 2*(c-a), so we increase a by 1 and decrease c by 1, therefore minimized sum=2*((c-1)-(a+1))=2*(c-a-2). Now we have to handle 2 cases, when (c-a)=1 and c=b=a, in both the case answer will be 0. My submisiion: 66774673

Wind_Eagle i solved it using iterative approach . But How to solve using recursive dp ?? i've been getting stuck while thinking how many state i've to assume in recursive approach .. Please help . It would be the best if you provide a code of recursive approach . Thanks .

I can try explaining,

Let's forget about bracket sequences and just construct a string $$$A$$$ that is a supersequence of these two strings $$$S$$$ and $$$T$$$ ($$$A$$$ contains both $$$S$$$ and $$$T$$$ as a subsequence). This problem can be solved with following DP: compute shortest supersequence for all possible pairs of prefixes $$$S'$$$ and $$$T'$$$. Instead of storing explicit strings we store lengths of matched prefixes and length of resulting sequence. Let $$$dp_{i,j}$$$ be minimum possible length of supersequence for prefix $$$S'$$$ with length $$$i$$$ and prefix $$$T$$$ with length $$$j$$$. For empty prefixes empty string matches both $$$dp_{0,0} = 0$$$. Suppose we have have calculated $$$dp_{i,j}$$$, now we can append new character $$$c$$$ to the end of this string, length of the string will be increased by $$$1$$$, and size of matched prefixes also can be increased by $$$1$$$, it depends whether new character is equal to first unmatched character in strings: $$$i$$$ will increase if $$$S_i = c$$$ and $$$j$$$ will increase if $$$T_j = c$$$. This works in $$$\mathcal{O}(|S| \cdot |T|)$$$.

Now coming to the fact that we have bracket sequences instead of arbitrary strings. Bracket sequences have a concept of balance, I will call it depth. This is actually amount of opened but not yet closed brackets (difference of opened and closed brackets). For some bracket sequence to be correct, balance of any prefix must be non-negative (we cannot put more closing brackets than opening) and must be $$$0$$$ at the end (each opening bracket must have a pair of closing one). Sequence properties as a prefixes only depend on it's depth. So we can add one more parameter to our DP, let $$$dp_{i,j,d}$$$ be length of shortest correct supersequence for prefix $$$S'$$$ with length $$$i$$$ and prefix $$$T$$$ with length $$$j$$$ with depth equal to $$$d$$$.

So we actually need to store this information about prefixes and be able to continue any prefix with either opening bracket or closing bracket (if it is possible). Generally we say that empty string has depth $$$0$$$ and matches empty prefixes: $$$dp_{0,0,0} = 0$$$. All other states are not calculated yet. Then we can extend all states with ( and ) possibly getting to new states and updating these states. About order of calculations: each extension increases length of sequence by $$$1$$$, and as we are seeking for minimum there is no point trying to update some states that already have a lower value than current state. So we can do this process in BFS-style. Firstly use $$$0$$$-result state to find all states that can have result of $$$1$$$. Then use all $$$1$$$-result states to get all possible $$$2-$$$result states, etc. Depth parameter $$$d$$$ can be safely capped at $$$max(|S|, |T|) = 200$$$, if we just concatenate sequences we can get sequence with depth $$$|S| + |T|$$$, but when both strings have large amount of opening (or closing) brackets they will be matched simultaneously.

Answer will be stored in $$$dp_{n,m,0}$$$. Minimum-length supersequence that has zero bracket depth and completely matches both sequences $$$S$$$ and $$$T$$$.

Also we need to actually restore the answer: for each state we can save last character and another DP state that was preceding for current state (last state that was successfully extended to current one), then restore string one character at a time: add last character to the answer and move to previous state until you get to $$$dp_{0,0,0}$$$.

So we get $$$\mathcal{O}(|S| \cdot |T| \cdot \max(|S|, |T|))$$$

Here is my solution 66725721 . All the logics of state extension is incapsulated into state struct.

Firstly, it prepares all the DP states to have not-reached-yet status and $$$dp_{0,0,0}$$$ to be the starting point and the only state with $$$0$$$ result. Then it starts the process, at step $$$k$$$ of the process all states with result equal $$$k$$$ are extended forming list of states that are $$$(k+1)$$$-result states and putting them into next list. When all states are processed target state $$$dp_{n,m,0}$$$ must be reached. We can start recovering answer starting at the end and moving to a previous state character by character.

Hope it helps.

I don't think we can do this easily by DFS

And I missed the second case during the contest and hence messed up :(

Declaring arrays outside main function gets rid of the error 66809101

To find the minimum number of moves of opposite parity. We construct a graph(g) in the following manner.

g[i] is a vector containing all indexes which reaches to position i in one move only. Now we traverse the graph(for odd and even values separately).

For instance, traversing with odd values.

First push all the nodes in a queue. Now while traversing the graph if any even value node is encountered. Then the number of moves required = number of moves required by the parent + 1 and then push it into the queue. In this process all the even nodes with moves required 1 is encountered first, then 2,3,4.....

Same is done for the even value nodes.

For better understanding refer to my solution. link

No, it is correct. Think once again. Unless, you see the elements on the right side of the index i, you can't compute l[i] that is why you compute l[i] by traversing the array from the right to the left.