All ideas except the problem C belong to MikeMirzayanov. The author of C is Rox.

Special thanks to opukittpceno_hhr for the invaluable help with the round preparation!

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int calc(int a, int b, int c) {
return abs(a - b) + abs(a - c) + abs(b - c);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int a, b, c;
cin >> a >> b >> c;
int ans = calc(a, b, c);
for (int da = -1; da <= 1; ++da) {
for (int db = -1; db <= 1; ++db) {
for (int dc = -1; dc <= 1; ++dc) {
int na = a + da;
int nb = b + db;
int nc = c + dc;
ans = min(ans, calc(na, nb, nc));
}
}
}
cout << ans << endl;
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
const string MOVES = "LRUD";
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
string s;
cin >> s;
map<char, int> cnt;
for (auto c : MOVES) cnt[c] = 0;
for (auto c : s) ++cnt[c];
int v = min(cnt['U'], cnt['D']);
int h = min(cnt['L'], cnt['R']);
if (min(v, h) == 0) {
if (v == 0) {
h = min(h, 1);
cout << 2 * h << endl << string(h, 'L') + string(h, 'R') << endl;
} else {
v = min(v, 1);
cout << 2 * v << endl << string(v, 'U') + string(v, 'D') << endl;
}
} else {
string res;
res += string(h, 'L');
res += string(v, 'U');
res += string(h, 'R');
res += string(v, 'D');
cout << res.size() << endl << res << endl;
}
}
return 0;
}
```

1272C - Yet Another Broken Keyboard

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
cin >> n >> k;
string s;
cin >> s;
set<char> st;
for (int i = 0; i < k; ++i) {
char c;
cin >> c;
st.insert(c);
}
long long ans = 0;
for (int i = 0; i < n; ++i) {
int j = i;
while (j < n && st.count(s[j])) ++j;
int len = j - i;
ans += len * 1ll * (len + 1) / 2;
i = j;
}
cout << ans << endl;
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 1;
vector<int> rg(n, 1);
for (int i = n - 2; i >= 0; --i) {
if (a[i + 1] > a[i]) rg[i] = rg[i + 1] + 1;
ans = max(ans, rg[i]);
}
vector<int> lf(n, 1);
for (int i = 1; i < n; ++i) {
if (a[i - 1] < a[i]) lf[i] = lf[i - 1] + 1;
ans = max(ans, lf[i]);
}
for (int i = 0; i < n - 2; ++i) {
if (a[i] < a[i + 2]) ans = max(ans, lf[i] + rg[i + 2]);
}
cout << ans << endl;
return 0;
}
```

1272E - Nearest Opposite Parity

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
vector<int> a;
vector<int> ans;
vector<vector<int>> g;
void bfs(const vector<int> &start, const vector<int> &end) {
vector<int> d(n, INF);
queue<int> q;
for (auto v : start) {
d[v] = 0;
q.push(v);
}
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto to : g[v]) {
if (d[to] == INF) {
d[to] = d[v] + 1;
q.push(to);
}
}
}
for (auto v : end) {
if (d[v] != INF) {
ans[v] = d[v];
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n;
a = vector<int>(n);
g = vector<vector<int>>(n);
vector<int> even, odd;
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (a[i] & 1) odd.push_back(i);
else even.push_back(i);
}
for (int i = 0; i < n; ++i) {
int lf = i - a[i];
int rg = i + a[i];
if (0 <= lf) g[lf].push_back(i);
if (rg < n) g[rg].push_back(i);
}
ans = vector<int>(n, -1);
bfs(odd, even);
bfs(even, odd);
for (auto it : ans) cout << it << " ";
cout << endl;
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 202;
const int INF = 1e9;
int dp[N][N][2 * N];
pair<pair<int, int>, pair<int, char>> p[N][N][2 * N];
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int bal = 0; bal < 2 * N; ++bal) {
dp[i][j][bal] = INF;
}
}
}
dp[0][0][0] = 0;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int bal = 0; bal < 2 * N; ++bal) {
if (dp[i][j][bal] == INF) continue;
int nxti = i + (i < n && s[i] == '(');
int nxtj = j + (j < m && t[j] == '(');
if (bal + 1 < 2 * N && dp[nxti][nxtj][bal + 1] > dp[i][j][bal] + 1) {
dp[nxti][nxtj][bal + 1] = dp[i][j][bal] + 1;
p[nxti][nxtj][bal + 1] = make_pair(make_pair(i, j), make_pair(bal, '('));
}
nxti = i + (i < n && s[i] == ')');
nxtj = j + (j < m && t[j] == ')');
if (bal > 0 && dp[nxti][nxtj][bal - 1] > dp[i][j][bal] + 1) {
dp[nxti][nxtj][bal - 1] = dp[i][j][bal] + 1;
p[nxti][nxtj][bal - 1] = make_pair(make_pair(i, j), make_pair(bal, ')'));
}
}
}
}
int ci = n, cj = m, cbal = 0;
for (int bal = 0; bal < 2 * N; ++bal) {
if (dp[n][m][bal] + bal < dp[n][m][cbal] + cbal) {
cbal = bal;
}
}
string res = string(cbal, ')');
while (ci > 0 || cj > 0 || cbal != 0) {
int nci = p[ci][cj][cbal].first.first;
int ncj = p[ci][cj][cbal].first.second;
int ncbal = p[ci][cj][cbal].second.first;
res += p[ci][cj][cbal].second.second;
ci = nci;
cj = ncj;
cbal = ncbal;
}
reverse(res.begin(), res.end());
cout << res << endl;
return 0;
}
```

Not hard, but still nice problems with nice solutions.

Missing a '$$$|$$$' in the tutorial of 1272A. It should be $$$|na-nb|+|na-nc|+|nb-nc|$$$. Thanks for the nice problems and a neat editorial.

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

Thank you, fixed.

How to solve

modified version of Di.e. if we can Remove at most K element. problem_linkFirstly, try to find the longest increasing subarray without removing any of the element from the array. assign the maximum to variable ans. After that find the length of the longest increasing subarray ending at position i(from 0 to i), and length of the longest decreasing subarray from ending i.e. n-1 position to position i. store the lengths in two seperate arrays dp1,dp2 respectively. Then try to delete elements one by one from i = 1 to n-2 (we won't try deleting element at i = 0 or i = n-1 because it will not increase the length if we did so). If, we delete element at position i then we check if(a[i-1] < a[i+1]) then ans = max(ans,dp1[i-1]+dp2[i+1]) which basically means we are joining the maximum increasing left subarray ending at position i-1 to the maximum increasing right subarray starting at position i+1 subarray.

EDIT: I did not read the problem carefully.He is asking for the modified version, ie, suppose if we can remove at most K elements.

Can this solution here be generalised by maintaining k+1 arrays?

Solution link Can you look and get something? alokjnvl41

During the contest I have solved this problem by exactly same method you have discussed here_mine_one.

And you know maintaining k+1 arrays sounds difficult/lengthy if K is of range 1000 or more.

Actually I am having an idea just wanted to know others opinion.....

My thought(might be wrong/modification might be needed)following with our previous method(I.e. maintain two arrays dp1 and dp2. Here dp1[i] denotes the length of longest subarray(without any deletion) ending at ith index and ith element inclusion is must, and dp2[i] denotes the length of longest subarray ending at ith index with at most k deleted element ith element inclusion is must. In previos case k was 1)Nowjust create an additional 3rd array say dp3 s.t dp3[i]= no of element deleted till now for dp2[i] result. And by this result we can construct for dp2[i+1] by looking at dp3[i] I.e. if no of deleted element at ith position is less than k then we still can delete otherwise not.I think we can do this by this method. or correct me if something else/extra needed.

I didn't get the idea of why inversing the graph works

Okay, so let us put it this way. Let's

consider the normal graphwhere you can gofroman index $$$i$$$toan index $$$j$$$. And you add an edge between $$$i$$$ and $$$j$$$ only if the values at those indices are ofsame[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 without-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 stepvalues 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$$$), andgo backto the nodes you used to reach the source (here $$$k$$$)SpoilerThink of bfs as the traversal where an edge

from$$$x$$$to$$$y$$$ means youcameto$$$x$$$from$$$y$$$.Hope this helps !!

Thank you

Or more simply put ; updation of ans[node] happens via dfs only in the back-track move of the dfs.

It looks something like :

So whatever we do ; we update answer only in the backtrack move of dfs. And if now we need to do something via BFS ( And keeping in mind that BFS is not a recursive algo ) ; its tough even to write a back-track.

Hence its better to inverse the graph first ; and then proceed with BFS for the same purpose...

This is highly informal way to explaining ; hope it helps biannaib

Since you're mentioning dfs here, I am curious as to whether it can be solved using dfs or any modification of that? ritesh1340

No I don't think that this problem can be solved via dfs ; because dfs is what I tried in the actual contest ; but I failed to receive an AC.

Then actually I was confused as to why was I going wrong. By that time the editorial was not out ; so we were discussing the problems on the announcement page.

Why I thought of dfs and how I came to know that it will not work can be found HERE. Special thanks to hellomoto

After hellomoto explained that what is the problem in the logic ; I took several other attempts trying to make something out of dfs only ; however all of them failed...

Some of those attempts I can share — My contest submission

My first attempt after realizing mistake

Attempt 2

Attempt 3

So after trying enough ; most probably ; I think it can't be solved via dfs ( Or maybe some cool person reads this and suggests some better way on dfs itself ).

So then I finally shifted to learn the concept provided in editorial ; and it gave me AC

The main issue with the DFS was that there might be back-edges in the dfs-trees ( or essentially, cycles) and hence the updates would probably be impossible.

Yes ! And thus in my remaining attempts ; when I understood what was happening ; I tried to re-run dfs on the nodes that were not relaxed ( on nodes for which ( ans[i] = inf ).

I had the intution before-hand that there can be many such nodes ; and it was highly probable that such solution could time out ( As it did on test case 12 ) ; but still it was worth a try.

$$$DFS$$$ works but will result in a TLE verdict. The problem is, in $$$DFS$$$ we may have to update each vertex more than one time (refer to $$$dp[u]$$$ in my code). This is not true in $$$BFS$$$, since its property is to expand the calculated vertices step by step, each $$$dp[u]$$$ is calculated only once and thus achieving $$$O(n)$$$ complexity.

My DFS submission got TLE on test 19

My BFS submission got AC

Yeah... an already relaxed vertex using some dfs can be relaxed more...

Hence we will return to the same node more than once...

But in BFS ; only one relaxation is enough to update dp[u] ; hence BFS ensures a strict O(n) time ; whereas time of DFS will depend on the structure of the graph ; it will pass a few graphs... but will time out !

Nice explanation. By the way, do you know similar problems where you need to invert the graph to solve it? :)

Finding strongly connected components in a directed graph :)

Thank you for such a detailed explanation. But I dare to assume there is a mistake: "And you add an edge between i and j only

if the values at those indices are of opposite parity, right, else you could simply put the answer for index i as 1 and proceed for the other indices." Should it be "if the values at those indices are ofsameparity" instead of "opposite"?Ah right, didn't realize the mistake earlier. Edge will be between indices having same parity elements. FIXED !!

1272E - Nearest Opposite Parity ->

Could you please tell where am i going wrong in this question

80077469

Thanks in advance.

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

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

In F problem in the tutorial its written that bal can have max length 200 , ok no problem but then in code why have we taken bal as 2*N shouldnt it be just N or say to be on a safe side N+5

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.

In problem A answer is just max(|A-B|+|A-C|+|B-C|-4, 0). I don't know why, but it's true.

Also problem D could be solved with dynamic programming. Let dp[i][0] be the answer for prefix i, and the element wasn't erased. dp[i][1] — the answer for prefix i, element was erased. Formula is:

1) if (a[i-2]<a[i]) dp[i][1]=max(dp[i][1],dp[i-2][0]+1); (if element i-1 was deleted).

2) if (a[i-1]<a[i]) dp[i][0]=max(dp[i][0],dp[i-1][0]+1), dp[i][1]=max(dp[i][1],dp[i-1][1]+1); (everything is good, answer is growing).

3) if (a[i-1]>=a[i]) dp[i][0]=max(dp[i][0],1LL), dp[i][1]=max(dp[i][1],1LL);

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?

Yes, but not between 0 and i inclusive, but between 0 and i-1 inclusive.

Ah, I understand the solution now, thanks.

hey,didnt expect to see you here

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, thereforesum=(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 minimizedsum=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: 66774673Wind_Yatagarasu 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 don't know how to solve it using recursive dp, because I used iterative approach, too.

My solution: https://codeforces.com/contest/1272/submission/66803356

Not the most elegant but This was my recursive solution. Pretty sure you don't need the map if you manage the function calls well enough

why in part 2) dp[i][1]=max(dp[i][1],dp[i-1][1]+1) ? If i am deleting i-1th element then i will not delete any previous one

it should be same as anser for previous one not erased so dp[i][1]=max(dp[i][1],dp[i-1][0]);

Help me out.I am getting wa in test 4

I am not able to understand problem F's solution i know dp will be used but still Can somebody please give a well comented solution describing each step , why its done please

Vovuh please reply to this as well

༼ つ ◕_◕ ༽つ

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

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

Thanks a lot (∩_∩)

What is

`S = 228`

in your code? And why 228? Also, there are mentions of using BFS in DP, and of backtracking also. Could anyone explain what they are referring to here?Constant

`S`

is actually shorthand for`Size`

and refers to general size of arrays in solution. So, it is used as three dimensions of $$$dp$$$ array. Constant`SL`

stands for`SizeLarge`

and represents amount of waves in BFS-like algorithm.Why exactly $$$228$$$ and what is it? I don't think that this number is somewhat specific. I've used this just as a number that is not much greater than $$$max(|S|, |T|)$$$. Just added some reserved elements to make sure that I can use some prefix of $$$\{n, n+1, n+2, \dots\}$$$ indexes if some of them are needed. Why not usual (at least for me usual) $$$200+5$$$? That was chosen at very early stages of solution, when I wasn't sure in all the details. For some non-important reason I've chosen to have more additional elements than usual and $$$228$$$ was the first number that come to my mind. Just as $$$SL = 10 \cdot S$$$ is much greater than actually needed: $$$3 \cdot S$$$ or even $$$2 \cdot S$$$ would've been enough. Overall solution turned out to be memory-hungry, so these extra limits put it dangerously close to MLE (480+ MB, but it is easy to optimize if needed).

Short story of 228, not related to programming at allArticle 228 of the Criminal Code of the Russian Federation. Illegal acquisition, storage, transportation, manufacture, processing of narcotic drugs, psychotropic substances or their analogues, as well as illegal purchase, storage, transportation of plants containing narcotic drugs or psychotropic substances, or their parts containing narcotic drugs or psychotropic substances.

So, it is more or less associated with drugs or similar illegal substances in Russia.

BFS part of the solution is loop that starts in line $$$102$$$:

It passes layer by layer forming next layers, where each layer contains all DP states that have result equal to

`len`

.Backtracking part comes right after BFS part, starting at line $$$148$$$. It starts from position $$$dp_{n,m,0}$$$. And uses backtracking information of $$$dp$$$ states:

These are used to put one bracket into answer and move to previous state that allows to put one

`last`

character to the answer and move further backwards.Hope it helps.

In the tutorial for problem D, the explanations for array

landrseem to be swapped.lirecords the max length of increasing sequenceendingatiandrirecords the max length of increasing sequencestartingati. This way the explanations would be coherent with the code.Otherwise, the final update can be changed into

li+1 + ri-1Yes, the code and explanation differ. The remove at ith index part needs to be swapped.

Can we do E with DFS? I tried solving it but getting wrong answer 66719636. My approach:-

`Suppose dp[i][odd/even] represents the distance of odd/even bit from the ith element.`

Do dfs and update the result.

But the problem is with the case when there is loop, like A->B->A. First I go from A to B. Then since I have already visited A, then I try to update my results for B. But since I have not got the final answer for A(as it is still in the stack), my answer for B will be wrong.

Can anyone help me how can I overcome this problem??

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

My CF predictor was showing +10..But after the hacking in my rank decrease -10... :( Can anyone tell me what is the problem...Is CF predictor is wrong??

My solution over problem 'A' was a bit different. I think it will be proved that the amount we are trying to minimize is being lowered only '4' units for each query and we only need to output max (0 , |a-b| + |b-c| + |a-c| — 4) p.s:This solution passed the test data :)

I solved it the same way although it took me some time to find it. Thats why I think the best solutions is bruteforce.

can someone explain a DP approach to problem D. PLZZ

I had a slightly different approach for question D. I had first calculated the array

`dp[n]`

where`dp[i]`

holds the longest increasing subarray ending at i. The next thing I did was to find all the endpoints of the blocks of increasing subarrays. One can prove that the answer to the question is the max of the following two cases: 1. The maximum value in`dp`

. 2. The maximum value of`dp[endpts[i]]+dp[endpts[i+1]]-1`

. There are two possibilities in this case,removing the last element of the current block and joining the current block with the next, or doing the same by removing the first element of the next block. Of course we must run the check that the pair of elements crossing the two resultant blocks after removal of an element are still strictly increasing. Submission for reference: Submission #66717570.its a nice solution , but i dont think we can call it dp.

An alternative solution for D, using DP, is as follows : Store two arrays

`subs`

and`subs_rem`

, indexed with 0. Here`subs[i]`

denotes the length of longest subarray ending at ith index, and`subs_rem[i]`

denotes the length of longest subarray ending at ith index with a deleted element, whose index <= i-1.`subs[0] = 1; subs_rem[0] = 0;`

Also, subs[i] can be calculated easily using dp. For subs_rem[i] do the following: Knowing subs[i], we know the index j from which the longest subsequence ending at i begins.

Giving some thought, we realise that the only two elements which can be deleted and the length of sequence would grow, is either jth element or (j-1)th element.

Two cases arise:

Suppose j-1 and j-2 are both indexes of the array(j-2 >= 0), this means that

`a[j] <= a[j-1]`

, where`a`

array is 0 indexed, if`a[j] > a[j-2]`

then we could remove the`a[j-1]`

and then`val1 = subs[i]+subs[j-2];`

, since we have already deleted`a[j-1]`

element no other element can be deleted.Again suppose j-1 and j+1 are both indexes of the array(j+1 <= i and j-1 >= 0), this means again that

`a[j] <= a[j-1]`

, if`a[j-1] < a[j+1]`

then we could remove the`a[j]`

element and then`val2 = subs[i]-1+subs[j-1];`

, since we have already deleted`a[j]`

element no other element can be deleted.Now,

`subs_rem[i] = max(val1,val2,1);`

1 because we could simply delete the`a[i-1]`

element. The final answer is the max of all values of subs array and subs_rem array.My implementation here : 66725589

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

good work

66806946 for D is incorrect, and it's giving me some funny errors (I understand my WA error, but not the uninitiaized value usage on the line 32) Can anyone explain what's going on?

Declaring arrays outside main function gets rid of the error 66809101

Ah, thank you so much!

In the writer's solution of F, he/she restores the answer string by the memo when he/she calculated DP table. can I restore the answer string only by its recurrence's transition? For example, dp[i][j] = min(dp[i — 1][j] + x, dp[i][j — 1] + y) is the target. Only using its recurrence's transition means that finding the before situation of dp[i][j] is by checking both dp[i — 1][j] + x == dp[i][j] and dp[i][j — 1] + y == dp[i][j], and decides the correct before situation(satisfied the either equals). If both of them are OK, I can choose any of them. In this way to restore, can I accept problem F?

Can anyone explain problem E??

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

Thanks, got it!

Can someone please tell me the issue with my code for PROBLEM C . I used a similar logic but implementation is a bit different from the editorial. Submission : 66825640 It gives a wrong answer for test case 12 ( n = 2*10^5 ) .

int main() {

}

i got same , 12 th test case failed

For problem A, why the answer

(|A-B|+|A-C|+|B-C|-4, 0)is true? How come the solution is this? I dont understand how it's deduced?Is it possible to solve problem E using DP (DP is not there in the problem tags) ?

I guess the tutorial for problem D has a mistake. Where it's said "The array l can be calculated in order from right to left ". I think array l should be calculated from left to right and array r vice versa.

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.

can you explain answer to Problem D?

Can anyone explain the working of D.

Problem F is very good in the sense that this was the first time i calculated dp using bfs.

I am getting wrong answer in test case 4 in problem D Here is my code, What am i doing wrong?

include<bits/stdc++.h> typedef long long int ll; typedef unsigned long long int ull; define fast ios_base::sync_with_stdio(false);cin.tie(NULL); using namespace std; int main() { fast; // your code goes here ll n; cin>>n; vector v(n); for(ll i=0;i<n;i++) { cin>>v[i]; } vector dp(n,0); dp[n-1]=1; if(v[n-2]<v[n-1]) dp[n-2]=2; else dp[n-2]=1; ll maxi=max(dp[n-1],dp[n-2]); for(ll i=n-3;i>=0;i--) { dp[i]=(v[i+1]>v[i])?dp[i+1]+1:1; dp[i]=max(dp[i],(v[i+2]>v[i])?dp[i+2]+1:dp[i]); maxi=max(maxi,dp[i]); } cout<<maxi; return 0; }

In problem D, I have traversed the list and found out the length of the subsequence by removing at most 1 element and at end of the subsequence, started to search for another subsequence from the element which i removed in the previous iteration. Here is the code https://ideone.com/xL5oax. Can someone please help me understand the fault in my logic?

In c problem, the time complexity is O(n*k) right???

In the

problem C — Yet Another Broken KeyboardThe solution is

correct but memory limit keeps exceeding. I don't think it should.My Submission

The problem is in this part: // Generate substrings for(int i=0; i<n; i++){ for(int j=1; j<=n-i;j++){ subs.PB(s.substr(i,j)); } }

According to the task, n can be as large as 2*10^5. The total number of substrings is n*(n+1)/2. Thus, you need to generate about 10^10 of substrings. Even if one substring takes 1 byte of memory, you need 10^10 bytes which is about 10 gigabytes.

Thanks for the answer. I solved the question using the approach mentioned in the tutorials. But I didn't knew the reason behind my submission exceeding memory limit.

Thanks for explaining.Can anyone provde solution for problem D with dp? :)

You can check mine. 81844897

or81848247 Solved it usingtwo pointerand basic implementationNeed dp idea for Problem C.

Thanks for a definitive editorial!

Minor problem E note: I was confused by a variable name in bfs function:

`for (auto to : g[v])`

. Shouldn't it be`from`

instead of`to`

? Since we are dealing with the inverse graph here. So mentally you would read it as`iterate over vertices _from_ which we can go to vertex v`

75963478 ///////////////////////////////////////////////////////////////////// import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException {

} ////////////////////////////////////////////////// Problem — D Can someone tell me why the above code for java doesent work I got wrong ans for test 4 but for all simple cases it works

For C, wouldn't it be a lot simpler to just have a streak variable and add the streak to count each step? Then you don't have to do any extra math. I solved it like this:

Dp solution of D ( recursive ) submission

Can someone explain, why we can not apply recursion in problem E. I have tried applying it but got wrong ans at testcase 2. I am not able to understand what is happening. If someone can give a shorter testcase which proves my submission is wrong. That would be really helpful. Thanks Here is my submission:- https://codeforces.com/contest/1272/submission/82418760

i am not able to find the bug in my code please help me problem E https://codeforces.com/contest/1272/submission/84568253 getting wrone answer on test case 2

I am not understanding this part of the editorial of problem C. Can anyone please help me to understand this:

If we are staying at the position i and its value is zero, just skip it. Otherwise, let's find the leftmost position j such that j>i and the j-th value is zero. Then we have to add to the answer the value (j−i)⋅(j−i+1)2 and set i:=j.

Can E be solved with DP? https://codeforces.com/contest/1272/submission/88624220 Can't figure out what is wrong, even if there is a cyclic dependency (idx i depends on idx A and A depends on i), I think this should work