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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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
Tutorial is loading...
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 to 1
3.coordinate 1 is odd, jumping right to 3 leads to 4
Sorry, 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
ctimes more than to the right, it will fall off the left edge of the board. And the similar statements for each other direction.can anyone share accepted java solution for problem C. mine is https://codeforces.net/contest/1607/submission/134305901 giving TLE
Try to shuffle the array before sorting.
How to sort arrays in Java and avoid TLE
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...
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:
Indeed, 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].
what does "max[->]" mean in editorial of problem E
jj
problem H can also be thought of as segments on an X, Y graph. In this case the X coordinate is the amount of A left and the Y coordinate can be thought of as the amount of B left. Drawing this out one can observe that all such segments have slope -1 and thus only segments with the same y intercept can intersect with each other. It turns out this y intercept corresponds to the total amount of left over food across both A and B which is A + B — M. We can solve such a problem for each one of these intercepts separately and see that by rotating these lines to a slope of 0 we essentially have a problem where there are segments that may or may not overlap and we want to choose the minimum amount of points such that all segments are covered by these points. This is a well known greedy problem. Notice that we can just sort segment endpoints by the total amount of A left as when rotating this line to have slope 0, the order of these endpoints will not change if they are sorted by the X coordinate for these points.
Hi, could someone figure out why my submission for Problem F is TLEing? A runtime analysis of this shows that it should only be O(mn) — the size of the board, which theoretically should pass. Thanks a lot!
For F question(Robot on the Board 2), I submitted this code but it is giving wrong answer on test 2 — test case 223. Can anyone help me out with the mistake?
Checker comment is: wrong answer number of steps in the output is 6 but in fact it's 7 (test case 223)