### Short information

Sorry for another delayed editorial, I know I promised that it will come out sooner the previous time, but I wasn't feeling well today, so the work was slower than usual.

**About problem F:**

I am once again sorry for the inconveniences caused by tight ML in this problem. It was not the intended behavior since we relied too much on the main solution and didn't assume most of the solutions using DFS will fail. In this editorial I attach the code of the main solution that we expected from the beginning, it uses ~75MB of memory.

I guess, Div. 3 Rounds are not only for participants to learn but also can serve as educational for authors as well. I'll try not to repeat the same mistakes the next time :) Thanks to everyone for participating and hope to see you again!

### The editorial

Idea: doreshnikov, MikeMirzayanov

**Tutorial**

**Solution**

```
t = int(input())
for _ in range(t):
k, s = input(), input()
res = 0
for i in range(1, len(s)):
res += abs(k.index(s[i]) - k.index(s[i - 1]))
print(res)
```

Idea: doreshnikov

**Tutorial**

**Solution**

```
t = int(input())
maps = [
lambda x: 0,
lambda x: x,
lambda x: -1,
lambda x: -x - 1
]
for _ in range(t):
x0, n = map(int, input().split())
d = maps[n % 4](n)
print(x0 - d if x0 % 2 == 0 else x0 + d)
```

Idea: doreshnikov

**Tutorial**

**Solution**

```
t = int(input())
for _ in range(t):
n = int(input())
a = sorted(list(map(int, input().split())))
res = a[0]
for i in range(n - 1):
res = max(res, a[i + 1] - a[i])
print(res)
```

Idea: MikeMirzayanov

**Tutorial**

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
string c;
cin >> c;
vector<int> l, r;
forn(i, n)
(c[i] == 'B' ? l : r).push_back(a[i]);
sort(l.begin(), l.end());
sort(r.begin(), r.end(), greater<int>());
bool ok = true;
forn(i, l.size())
if (l[i] < i + 1)
ok = false;
forn(i, r.size())
if (r[i] > n - i)
ok = false;
cout << (ok ? "YES" : "NO") << '\n';
}
}
```

Idea: MikeMirzayanov

**Tutorial**

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
string s;
cin >> s;
int bx = 0, by = 0;
int min_bx = 0, max_bx = 0, min_by = 0, max_by = 0;
for (char c: s) {
if (c == 'L') min_by = min(min_by, --by);
else if (c == 'R') max_by = max(max_by, ++by);
else if (c == 'U') min_bx = min(min_bx, --bx);
else max_bx = max(max_bx, ++bx);
if (max_bx - min_bx >= n) {
if (bx == min_bx) min_bx++;
break;
}
if (max_by - min_by >= m) {
if (by == min_by) min_by++;
break;
}
}
cout << 1 - min_bx << ' ' << 1 - min_by << '\n';
}
}
```

Idea: doreshnikov

**Tutorial**

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<string> dir(n);
for (int i = 0; i < n; i++)
cin >> dir[i];
vector<vi> res(n, vi(m, 0));
int opt = 0, optr = 0, optc = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
if (res[r][c] > 0)
continue;
int nr = r, nc = c;
int depth = 0;
vector<pii> path;
auto ok = [&n, &m](int row, int col) {
return row > -1 && row < n && col > -1 && col < m;
};
do {
res[nr][nc] = --depth;
path.emplace_back(nr, nc);
if (dir[nr][nc] == 'L')
nc--;
else if (dir[nr][nc] == 'R')
nc++;
else if (dir[nr][nc] == 'U')
nr--;
else
nr++;
} while (ok(nr, nc) && res[nr][nc] == 0);
int start = 1;
if (ok(nr, nc)) {
if (res[nr][nc] < 0) {
int cycle = res[nr][nc] - depth + 1;
for (int i = 0; i < cycle; i++) {
auto p = path.back();
path.pop_back();
res[p.first][p.second] = cycle;
}
}
start = res[nr][nc] + 1;
}
while (!path.empty()) {
auto p = path.back();
path.pop_back();
res[p.first][p.second] = start++;
}
if (res[r][c] > opt) {
opt = res[r][c];
optr = r;
optc = c;
}
}
}
cout << optr + 1 << ' ' << optc + 1 << ' ' << opt << '\n';
}
}
```

1607G - Banquet Preparations 1

Idea: doreshnikov

**Tutorial**

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<pii> dishes(n);
ll balance = 0;
ll max_a = 0, max_b = 0;
ll total_eat = static_cast<long long>(n) * m;
for (int i = 0; i < n; i++) {
cin >> dishes[i].first >> dishes[i].second;
balance += dishes[i].first - dishes[i].second;
max_a += min(m, dishes[i].first);
max_b += min(m, dishes[i].second);
}
ll max_delta = 2 * max_a - total_eat, min_delta = total_eat - 2 * max_b;
ll min_a = total_eat - max_b;
ll eat_a;
if (balance < 0) {
eat_a = min_a;
if (balance - min_delta >= 0)
eat_a = min(max_a, (total_eat + balance + 1) / 2);
} else {
eat_a = max_a;
if (balance - max_delta <= 0)
eat_a = min(max_a, (total_eat + balance + 1) / 2);
}
ll ans = abs(balance - 2 * eat_a + total_eat);
cout << ans << '\n';
ll rest_a = eat_a - min_a;
for (int i = 0; i < n; i++) {
ll cur_a = 0;
if (dishes[i].second < m)
cur_a += m - dishes[i].second;
ll add = min(rest_a, min(m - cur_a, dishes[i].first - cur_a));
cur_a += add;
rest_a -= add;
cout << cur_a << ' ' << m - cur_a << '\n';
}
}
}
```

1607H - Banquet Preparations 2

Idea: MikeMirzayanov

**Tutorial**

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
struct seg {
int a, b, m;
int index;
};
int n, ans;
vector<seg> segments;
map<int, vector<seg>> diags;
void erase(multiset<pair<pair<int,int>, int>>& lr, int l, int r, int index) {
pair<pair<int,int>,int> plr = make_pair(make_pair(l, r), index);
auto i = lr.find(plr);
assert(i != lr.end());
lr.erase(i);
}
void erase(multiset<pair<pair<int,int>, int>>& lr, multiset<pair<pair<int,int>, int>>& rl, int l, int r, int index) {
erase(lr, l, r, index);
erase(rl, r, l, index);
}
map<int, pair<int,int>> dd;
void setup_dd(int index, int value) {
assert(dd.count(index) == 0);
int x = segments[index].a - value;
int y = segments[index].m - x;
assert(segments[index].a - x >= 0);
assert(segments[index].b - y >= 0);
assert(x + y == segments[index].m);
dd[index] = make_pair(x, y);
}
int solve(vector<seg> s) {
int n = s.size();
multiset<pair<pair<int,int>, int>> lr;
multiset<pair<pair<int,int>, int>> rl;
forn(i, n) {
int min_d = max(s[i].m - s[i].b, 0);
int max_d = min(s[i].a, s[i].m);
lr.insert(make_pair(make_pair(s[i].a - max_d, s[i].a - min_d), s[i].index));
rl.insert(make_pair(make_pair(s[i].a - min_d, s[i].a - max_d), s[i].index));
}
int result = 0;
while (!rl.empty()) {
result++;
auto min_r_iterator = rl.begin();
int r = min_r_iterator->first.first;
int l = min_r_iterator->first.second;
int index = min_r_iterator->second;
erase(lr, rl, l, r, index);
setup_dd(index, r);
while (!lr.empty()) {
auto min_l_iterator = lr.begin();
int ll = min_l_iterator->first.first;
int rr = min_l_iterator->first.second;
int ii = min_l_iterator->second;
if (ll <= r) {
erase(lr, rl, ll, rr, ii);
setup_dd(ii, r);
} else
break;
}
}
return result;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
cin >> n;
diags.clear();
dd.clear();
segments = vector<seg>(n);
forn(i, n) {
seg s;
s.index = i;
cin >> s.a >> s.b >> s.m;
diags[s.a + s.b - s.m].push_back(s);
segments[i] = s;
}
int sum = 0;
for (auto p: diags)
sum += solve(p.second);
cout << sum << '\n';
forn(i, n)
cout << dd[i].first << " " << dd[i].second << '\n';
}
}
```

Thanks for an amazing round !

Correct me if I'm wrong but I believe there's a typo in the editorial to problem B. It says "coordinate −1 is even, jumping right to 2 leads to 2", when jumping right 2 from -1 should be 1 (2-1 = 1).

The 2nd and 3rd statements should have been like this:

2.coordinate −1 is

odd, jumping right to 2 leads to13.coordinate 1 is

odd, jumping right to 3 leads to 4Sorry, that's a typo, fixed

Thank you for fastn't editorial.

I finally know why so many people I know can't solve problem F.

But I get TLE because I forgot to push a tag XD.

doreshnikov Can you explain the following line in the editorial with an example for problem : Robot on the Board 1?

Since the robot breaks as soon as goes outside the field, if any command causes it to break, it either leads to its total shift relative to (r, c) of exactly c to the left or exactly m — c + 1 to the right, or, similarly, of exactly r up or exactly n — r + 1 down.

If there's a moment in time when the robot moves to the left exactly

`c`

times more than to the right, it will fall off the left edge of the board. And the similar statements for each other direction.MikeMirzayanov I wonder how did you come up with problems like 1607D - Blue-Red Permutation What i mean is how do start thinking while framing a problem (sorry if question is too broad).

can anyone share accepted java solution for problem C. mine is https://codeforces.com/contest/1607/submission/134305901 giving TLE

Try to shuffle the array before sorting.

How to sort arrays in Java and avoid TLE

it worked....thanks [user:m1_k3][user:UpAndDown]

For the case n=10 and x0=10 in problem B, where x0 is the starting point and n is total number of steps, how the output is 11? From what I understood from the problem statement, I was getting 15.

10-1+2-3+4...+10 -> 15

The correct sequence is 10-1+2+3-4-5+6...

Oh..got it what I was mistaking. Thanks for clarifying.

Question D was really interesting

Why in problem F the solution with dfs gives MLE?

Don't you see the reason in the post?Authors didn't suppose that participants will use DFS for solving this problem...

No, I saw. I'm just wondering why the solution crashes and how I can optimize my dfs

I'm kinda scared answering to such questions since my comments on the topic tend to get highly disliked (though, maybe, it's deserved in some way, I feel some people are just still unhappy with my existence) xD

There are some solutions using dfs that passed. I can't guarantee that for your particular solution it will work, but you can try

One of the testers' solutions used tail recursion, so maybe it was optimized by the compiler, but I'm not that familiar with the fact whether g++ can do such optimizations and if they are used by Cf's compilers.

Sorry if I missed something, maybe someone else can help you a bit more. Good luck!

I guess that's because the maximum recursion stack size is about 2e5, while in problem F there could be 4e6 recursive calls of dfs.

Maximum stack size is not 2e5 -_-. Stop confusing people. Dfs with 4e6 size can pass.

So what was the problem then?

The problem is that your recursion takes up space. So if you have dfs with depth 4e6, it will take extra MBs.

For example if your arrays and vectors use 80 megabytes. This dfs of size 4e6 will add extra 180 MBs. And total will be 80+180=260 which will get MLE. But if you optimize your dfs. Then it can use less memory.

How to calculate the "180 MB", thank you a lot.

there is no accurate way to do so. But it depends on the depth and number of variables that you initialize inside of it.

Using iterative DFS instead of recursive DFS using stacks(or deque) bypasses the recursion stack limit problem: My Solution

I think the tutorial of problem C has a mistake:

The Words in the tutorialIndeed, if we look at $$$a_0=[1,4,7,12,13]$$$, it will undergo changes as follows: $$$[\color{blue}1,4,6,12,15]→[\color{blue}3,5,11,14]→[\color{blue}2,8,11]→[\color{blue}6,9]→[\color{blue}3]$$$.

I think $$$a_0$$$ should be [1,4,6,12,15].

can anyone explain problem E

There is also an O(n) approach to problem D. I solved it without sorting the array. Link to my submission.

I think my code is correct. And the sample is passed too. But WA. Help me!

I am getting WA on problem G on the codeforces compiler, but have copied the exact test cases into my compiler and confirmed I'm getting a different (the right) answer on my local machine. https://codeforces.com/contest/1607/submission/134616768 Can anyone help me figure out what's wrong?

I have a problem in the problem C that is minimum extraction. Is it mandatory that after the subtraction the new element in the first positon of the array be the smallest? It can be a negetive element at first and then after the subtraction can be a positive element greater than rest of the elements of the array. Does in that case also this logic holds?

Used Binary Search for E:Solution

What's the invariant you used ?

And why does your O(NlogN) solution passes and mine(has same TC) doesn't ?

My submission : E-TLE

If you carefully analyze my code you will see my code is doing less operations as compared to your code .

1) No extra vector is created

2) i am trying to calculate x and y coordinated in only 1 binary search .

Even your code is under the limit n*log(n) but there are too many operations .

I have just used simple binary search. Approach:

set left and right limit of the coordinates for both x and y then do binary search ...check for the number of commands executed using those coordinates . Check whether x coordinates exceeded the limit or the y then according to that update the x and y . if whole string is covered ...then that's your ans (simple break)

what does "max[->]" mean in editorial of problem E

jj