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
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
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
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
#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
#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
#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
#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
#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';
}
}