1802A - Likes
Idea: Aleks5d, Preparation: vaaven
Let's show a construction that maximizes the number of likes. We need to first leave all the likes that we can put, and only then delete them.
To minimize the number of likes, we need to delete the like (if we can) immediately after we post it.
The code below implements these constructs.
#include "bits/stdc++.h"
using namespace std;
void solve() {
int n;
cin >> n;
int likes = 0, dislikes = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > 0) likes++;
else dislikes++;
}
for (int i = 1; i <= n; ++i) {
if (i <= likes) cout << i << ' ';
else cout << likes * 2 - i << ' ';
}
cout << '\n';
for (int i = 1; i <= n; ++i) {
if (i <= dislikes * 2) cout << i % 2 << ' ';
else cout << (i - dislikes * 2) << ' ';
}
cout << '\n';
}
signed main() {
int t = 1;
cin >> t;
for (int i = 1; i <= t; ++i) {
solve();
}
return 0;
}
1802B - Settlement of Guinea Pigs
Idea and preparation: Aleks5d
Todo
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int known = 0, unknown = 0;
int need = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
if (x == 1) ++unknown;
else {
known += unknown;
unknown = 0;
}
need = max(need, unknown + (known ? known / 2 + 1 : 0));
}
cout << need << endl;
}
signed main() {
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}
1801A - The Very Beautiful Blanket
Idea and preparation: 4qqqq
The maximum number of different numbers we can type is always $$$n\cdot m$$$. Let's show how you can build an example for any $$$n$$$ and $$$m$$$.
Note that if we were able to construct a correct matrix, then any of its submatrix is also a correct matrix of a smaller size. Therefore, let's build a correct matrix for some $$$N$$$ and $$$M$$$, and as an answer we will output the upper left corner of this matrix of the desired size.
Take $$$N = M = 2^8$$$ and construct the matrix using the following algorithm. Let's break it into blocks of size $$$2 \times 2$$$. Let's number the blocks from left to right and from top to bottom in order, starting from zero. The $i$th block will have the form
$$$4i + 0$$$ $$$4i + 1$$$
$$$4i + 2$$$ $$$4i + 3$$$
With this construction, the bitwise exclusive OR any submatrix of size $$$2\times 2$$$ will be zero. You can verify this as follows. Let's look at the upper left corner of $$$(i,\,j)$$$ of an arbitrary submatrix of size $$$2\times 2$$$. There are 4 cases:
- both coordinates are even;
- $$$i$$$ is even, $$$j$$$ is odd;
- $$$i$$$ odd, $$$j$$$ even;
- both coordinates are odd.
Immediately note that $$$i, \, j < 200 < 2^8$$$
Consider the most unpleasant case — the last one. The remaining cases are treated in a similar way. In this case, the submatrix will have the form:
$$$4i + 3$$$ $$$4(i + 1) + 2$$$
$$$4(i + 2^8) + 1$$$ $$$4(i + 2^8 + 1) + 0$$$
Note that the second part of each term is less than 4, and the first part of each term is greater than or equal to 4. Therefore, they can be considered independently.
$$$3 \oplus 2 \oplus 1 \oplus 0$$$ $$$=$$$ $$$0$$$.
If $$$i$$$$$$=$$$$$$1$$$, then
$$$4i \oplus 4(i + 1)$$$ $$$=$$$ $$$12$$$,
$$$4(1 + 2^8) \oplus 4(2 + 2^8)$$$ $$$=$$$ $$$12$$$.
If $$$i\neq 1$$$, then
$$$4i \oplus 4(i + 1)$$$ $$$=$$$ $$$4$$$
$$$4(i + 2^8) \oplus 4(i + 2^8 + 1)$$$$$$=$$$$$$4$$$ (for $$$i=0$$$, you can check with your hands, for $$$1 < i <2^8$$$ $$$4(i+ 2^8)$$$ will be reduced and $$$4$$$ will remain from the second term).
$$$4 \oplus 4 \oplus 0$$$ $$$=$$$ $$$0$$$. Thus, in the selected submatrix, the bitwise exclusive OR is zero.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int SZ = 256;
int v[SZ][SZ];
void Solve(){
int n, m;
cin >> n >> m;
cout << n * m << '\n';
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cout << v[i][j] << " \n"[j + 1 == m];
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
{
int now = 0;
int n = 256;
int m = 256;
for(int i = 0; i < n; i += 2)
for(int j = 0; j < m; j += 2){
v[i][j] = now;
v[i][j + 1] = now + 1;
v[i + 1][j] = now + 2;
v[i + 1][j + 1] = now + 3;
now += 4;
}
}
int num_test = 1;
cin >> num_test;
for(int i = 1; i <= num_test; i++){
Solve();
}
}
1801B - Buying gifts
Idea: Tikhon228, Preparation: DishonoredRighteous
To begin with, let's sort all departments in descending order $$$b_i$$$ (and if ~--- is equal, in ascending order $$$a_i$$$). Now let's go through the $$$i$$$ department, in which the most expensive gift for the second girlfriend will be bought. Note that in all departments with numbers $$$j < i$$$, Sasha must buy a gift for the first girlfriend, otherwise the gift $$$i$$$ will not have the maximum value among the gifts bought for the second girlfriend. Therefore, we will immediately find the value of $$$m = \max \limits_{j < i} a_j$$$. Thus, we can already get the answer $$$\lvert m - b_i\rvert$$$.
In all departments with numbers $$$j > i$$$, for which $$$a_j \le m$$$, Sasha can buy a gift for any of her friends, and this will not affect the answer in any way. Now consider all departments with numbers $$$j > i$$$ for which $$$a_j > m$$$. If you buy a gift for your first girlfriend in some of these departments, the value of $$$m$$$ will increase, which means the answer may improve. Therefore, let's iterate through all these departments and update the response with the value $$$\lvert a_j - b_i\rvert$$$.
Time $$$O(n^2)$$$.
Let's optimize this solution. To begin with, instead of calculating the value of $$$m$$$ anew at each iteration, we will maintain its value in some variable. Then, when moving from department $$$i - 1$$$ to department $$$i$$$, we will update the value of $$$m$$$ as follows: $$$m:= \max(m, a_i)$$$.
It remains to learn how to quickly find the optimal department number $$$j$$$, such that $$$j > i$$$, $$$a_j > m$$$, as well as $$$\lvert a_j - b_i\rvert$$$ is minimal. Let's choose on the suffix of the array the minimum $$$a_j$$$, such that $$$a_j\ge b_i$$$, and also the maximum $$$a_j$$$, such that $$$a_j \le b_i$$$. You can notice that the optimal $$$a_j$$$ is one of the two selected numbers (you also need to remember to check the condition $$$a_j > m$$$). Therefore, it is enough to update the answer only with the help of them.
You can search for these two elements using the \texttt{set} data structure. We will support in the set all $$$a_j$$$ located on the suffix. Then you can find the necessary two elements for $$$O(\log n)$$$. When moving from department $$$i - 1$$$ to department $$$i$$$, you need to remove the value $$$a_{i - 1}$$$ from the data structure.
Time $$$O(n\log n)$$$
#include <bits/stdc++.h>
using namespace std;
template<typename T>
bool smin(T& a, const T& b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool smax(T& a, const T& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int INF = 0x3f3f3f3f;
const int N = 500100;
std::pair<int, int> a[N];
void run() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d", &a[i].first, &a[i].second);
}
sort(a, a + n, [&](const pair<int, int>& p1,
const pair<int, int>& p2) {
return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);
});
multiset<int> setik;
for (int i = 0; i < n; ++i) {
setik.insert(a[i].first);
}
int mx = -INF;
int ans = INF;
for (int i = 1; i < n; ++i) {
smin(ans, abs(a[i].first - a[0].second));
}
for (int i = 0; i < n; ++i) {
setik.erase(setik.find(a[i].first));
if (i == 0) {
mx = a[i].first;
continue;
}
smin(ans, abs(mx - a[i].second));
auto it = setik.lower_bound(a[i].second);
if (it != setik.end() && *it >= mx) {
smin(ans, abs(*it - a[i].second));
}
if (it != setik.begin() && *std::prev(it) >= mx) {
smin(ans, abs(*prev(it) - a[i].second));
}
smax(mx, a[i].first);
}
printf("%d\n", ans);
}
int main(void) {
int t;
scanf("%d", &t);
while (t--) {
run();
}
return 0;
}
1801C - Music Festival
Idea: vaaven, Preparation: ViktorSM
Let's introduce the concept of a compressed album for an album, which is obtained from the original one by removing all elements except those that are the first maxima on their corresponding prefixes.
For example:
For the album $$$[\textbf{1}, \textbf{4}, 4, 3, \textbf{6}, 5, 6]$$$ the album will be compressed $$$[1, 4, 6]$$$.
Now we note that the solution of the original problem is reduced to solving the same problem, but on compressed albums. Indeed, the answer to them will not be different, because if some element increased the impression on ordinary albums, then it will increase if you compress albums and vice versa. Next, it will be assumed that all albums have been compressed beforehand.
Let's introduce $$$dp_c$$$ — the maximum impression that can be obtained if there were no albums such that they have elements larger than $$$c$$$. Then, $$$dp_c$$$ is equal to $$$dp_{c-1}$$$, or you can add another element or two if $$$c$$$ is the maximum element for some album. Then for all compressed albums, it can be recalculated through the value of $$$dp$$$ at the point before the first element of the album, or through $$$c - 1$$$. Thus, for recalculation, it is enough to know for each $$$c$$$ which albums ended in this index, as well as for each album its first element. Solution for $$$O(K)$$$
Let's now solve the complete problem. For each value of $$$c$$$, let's remember the indexes of albums that contain an element equal to $$$c$$$. We go in order of increasing $$$c$$$, we maintain for each album the value of $$$dp_i$$$ — the maximum impression that can be obtained if there were no elements of large $$$c$$$ and Masha listened to the last $$$i$$$ album. Suppose for the next $$$c$$$ there is an album $$$i$$$, that there is a song with the coolness of $$$c$$$ in it. Then $$$dp_i$$$ should be taken as the maximum of $$$dp_i + 1$$$ and the values for all $$$dp_j + 1$$$, such that the maximum element in the $$$j$$$th album is less than the maximum element of $$$i$$$th, since she could listen to this track, either next in this album, or after listening to some other album completely. Note that you can store the value of $$$mx$$$ — maximum for all albums for which the maximum value in them is less than $$$c$$$ and recalculate it when moving to $$$c + 1$$$, storing those albums that have ended, then you will get a solution for $$$O(K + C)$$$.
#include "bits/stdc++.h"
#include <algorithm>
#include <locale>
#include <random>
#include <unordered_map>
#include <vector>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef long long ll;
typedef long double db;
typedef unsigned long long ull;
vector<int> shrink(vector<int> &a) {
vector<int> a1;
int n = a.size();
int mx = 0;
for (int i = 0; i < n; ++i) {
if (a[i] > mx) {
a1.emplace_back(a[i]);
mx = a[i];
}
}
return a1;
}
void solve() {
int n;
cin >> n;
vector<vector<int>> a(n);
int k;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
a[i].resize(k);
for (auto &j : a[i]) {
cin >> j;
}
}
vector<vector<int>> a1(n);
for (int i = 0; i < n; ++i) {
a1[i] = shrink(a[i]);
}
map<int, vector<int>> b;
for (int i = 0; i < n; ++i) {
for (auto &j : a1[i]) {
b[j].emplace_back(i);
}
}
vector<int> dp(n);
int closed = 0;
for (auto &it : b) {
int c = it.first;
int newclosed = 0;
for (auto &i : it.second) {
if (c == a1[i].back()) {
dp[i] = max(dp[i] + 1, closed + 1);
newclosed = max(newclosed, dp[i]);
continue;
}
if (c == a1[i].front()) {
dp[i] = closed + 1;
continue;
}
dp[i] = max(dp[i] + 1, closed + 1);
}
closed = max(closed, newclosed);
}
cout << *max_element(all(dp));
}
signed main() {
int t = 0;
cin >> t;
while (t --> 0) {
solve();
cout << '\n';
}
return 0;
}
1801D - The way home
Idea: Tikhon228, Preparation: Ormlis
Note that the show can be done "postponed". As soon as we don't have enough money to walk along the edge, we can do several shows in advance among the peaks that we have already passed, so as to earn the maximum amount of money.
For the general case, you can write $$$dp[v][best] = (\textit{min show}, \textit{max money})$$$, where $$$v$$$ is the number of the vertex where we are, and $$$best$$$ is the vertex with max. $$$w_i$$$, which we have already passed through. It can be shown that it is optimal to minimize the number of shows first, and then maximize the amount of money. This dynamics can be recalculated using Dijkstra's algorithm. Asymptotics of $$$O(mn\log n)$$$
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define ar array
#define vec vector
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pair<int, int>>;
const ll INF = 2e18;
const int maxN = 3e5 + 10;
struct PathParams {
ll num_show;
int money;
};
bool operator==(const PathParams &a, const PathParams &b) {
return tie(a.num_show, a.money) == tie(b.num_show, b.money);
}
bool operator!=(const PathParams &a, const PathParams &b) {
return !(a == b);
}
struct State {
PathParams params;
int v;
int best;
};
bool operator<(const PathParams &a, const PathParams &b) {
if (a.num_show != b.num_show) return a.num_show < b.num_show;
return a.money > b.money;
}
bool operator<(const State &a, const State &b) {
return tie(a.params, a.v, a.best) < tie(b.params, b.v, b.best);
}
bool operator>(const State &a, const State &b) {
return !(a < b);
}
void solve() {
int n, m, p, group;
cin >> n >> m >> p;
vector dp(n, vector<PathParams>(n, {INF, 0}));
vector<vpi> g(n);
vi w(n);
rep(i, n) cin >> w[i];
rep(i, m) {
int a, b, s;
cin >> a >> b >> s;
a--;
b--;
g[a].emplace_back(b, s);
}
dp[0][0] = {0, p};
priority_queue<State, vector<State>, greater<>> pq;
pq.push({.params = {.num_show=0, .money=p}, .v = 0, .best=0});
while (!pq.empty()) {
auto current = pq.top();
pq.pop();
int v = current.v;
int best = current.best;
if (dp[v][best] != current.params) continue;
for (auto &[u, s]: g[v]) {
auto state2 = current;
PathParams &path = state2.params;
if (path.money < s) {
ll need = (s - path.money + w[best] - 1) / w[best];
path.num_show += need;
path.money += need * w[best];
assert(path.money < s + w[best]);
}
path.money -= s;
state2.v = u;
if (w[u] > w[state2.best]) state2.best = u;
if (path < dp[u][state2.best]) {
dp[u][state2.best] = path;
pq.push(state2);
}
}
}
ll ans = INF;
rep(i, n) {
ans = min(ans, dp[n - 1][i].num_show);
}
cout << (ans == INF ? -1 : ans) << '\n';
}
signed main() {
int t = 1;
cin >> t;
rep(_, t) {
solve();
}
return 0;
}
1801E - Gasoline prices
Idea and preparation: Kirill22
To begin with, let's understand what is required of us. A tree is given, in each vertex of which the price range for this vertex is recorded. A query is a pair of paths of equal length, the prices at the $$$i$$$-th vertices along these paths should be equal for all $$$i$$$. We need to find the number of ways to place prices at the vertices for each prefix of restrictions
Let's start with a slow solution of the problem. We will store the connectivity components (in each vertex prices should be equal). For each of them, we store an acceptable price range. The answer will be the product of the lengths of the ranges over all components. We will go along the paths and combine 2 vertices into one component using DSU. It is clear that to speed up this solution, it is necessary to search faster for the moments when two vertices are combined into one component.
First, let's analyze the long solution. Let's make a heavy-light decomposition, with which we will hash the paths in the tree, taking the root number of its components as a symbol for the vertex. Now, with the help of bin search, we will look for the first moment when the hashes on the path prefixes differ, that is, two vertices are combined into one component. With the help of transfusions, we will update the roots of their components for vertices and the tree of segments for hld. We will get $$$n$$$ unions, we will find each one for $$$O(log^2(n))$$$ using hld. There will also be $$$O(n\cdot log(n))$$$ updates in the segment tree due to overflows. For each request there will be $$$O(log^2(n))$$$ from hld. The final asymptotic $$$O((n+q)\cdot log^2(n))$$$
Now let's give a beautiful solution to this problem. Let's start with bamboo.
Replace the equality of prices on a pair of paths with two pairs of paths with lengths equal to the maximum power of two, less than the length of the original path (as in sparse table). Now the path lengths of all constraints have become powers of two. We will iterate over the powers of two in descending order $$$2^k$$$, for each path of length $$$2^k$$$ we will get a vertex in the graph, we will also get a vertex for each such path in reverse order. Now the constraints define edges in such a graph. Let's spend them, select the spanning tree. For each edge from the backbone, we divide the constraints into 2 constraints with path lengths half as long and continue the process. On a layer with lengths 1, we will get the spanning tree we need, which will be responsible for the first moments when some pairs of vertices were combined into components. Note that no more than $$$2n$$$ edges will be added down from each layer, as well as no more than $$$2q$$$ edges from queries. That is, each layer will work for $$$O((n + q)\cdot\alpha(n))$$$, where $$$\alpha(n)$$$ is the average operating time in DSU, the inverse of the Ackerman function. We got the solution in $$$O((n + q) \cdot\alpha(n)\cdot log(n))$$$
For a complete solution on the tree, first we divide a pair of paths into three pairs of corresponding vertical paths (take from the 4 end vertices of these paths the pair of vertices closest to the lca on its path, then we pair this path with a vertical path (part of another path), now we get one vertical path and an arbitrary path in the tree, let's split the second path by lca and the first by the corresponding lengths). Next, we will proceed similarly to bamboo, only the place of the vertex responsible for the segment, we will get the vertex responsible for the binary ascent in the tree to a height equal to the power of two.
#include "bits/stdc++.h"
using namespace std;
const int mod = (int) 1e9 + 7;
int inv(int x) {
int res = 1, n = mod - 2;
while (n) {
if (n & 1) {
res = res * 1ll * x % mod;
}
x = x * 1ll * x % mod;
n /= 2;
}
return res;
}
const int N = (int) 2e5 + 22, K = 18;
vector<int> g[N];
pair<int, int> a[N];
int n, q, ans = 1;
int h[N], up[N][K], lg[N];
vector<array<int, 3>> graph[K]; // lower vertex1, lower vertex2, time, vertex with direction
vector<array<int, 3>> gr[N];
vector<array<int, 3>> edges;
struct dsu {
vector<int> p, sz;
void build(int n) {
p.resize(n);
sz.resize(n);
for (int i = 0; i < n; i++) {
p[i] = i;
sz[i] = 1;
}
}
int get(int v) {
return (v == p[v] ? v : p[v] = get(p[v]));
}
bool merge(int v, int u) {
v = get(v), u = get(u);
if (v != u) {
if (sz[v] > sz[u]) {
swap(v, u);
}
p[v] = u;
sz[u] += sz[v];
return true;
}
return false;
}
} G, dsu[K];
void dfs(int v, int pr, int d) {
h[v] = d;
up[v][0] = pr;
for (int j = 1; j < K; j++) {
up[v][j] = up[up[v][j - 1]][j - 1];
}
for (auto u : g[v]) {
dfs(u, v, d + 1);
}
}
int la(int v, int x) {
for (int j = 0; j < K; j++) {
if (x >> j & 1) {
v = up[v][j];
}
}
return v;
}
int lca(int v, int u) {
if (h[v] > h[u]) {
swap(v, u);
}
u = la(u, h[u] - h[v]);
if (v == u) {
return v;
}
for (int j = K - 1; j >= 0; j--) {
if (up[v][j] != up[u][j]) {
v = up[v][j], u = up[u][j];
}
}
return up[v][0];
}
int id(int v) {
return (v > 0 ? v : -v + n);
}
int sgn(int v) {
return (v > 0 ? 1 : -1);
}
void add_edge(int j, int v, int u, int t) {
if (dsu[j].merge(id(v), id(u))) {
if (j > 0) {
if (sgn(v) == sgn(u)) {
add_edge(j - 1, v, u, t);
add_edge(j - 1, sgn(v) * up[abs(v)][j - 1], sgn(u) * up[abs(u)][j - 1], t);
} else {
if (sgn(v) == -1) {
swap(v, u);
}
add_edge(j - 1, v, sgn(u) * up[abs(u)][j - 1], t);
add_edge(j - 1, sgn(v) * up[abs(v)][j - 1], u, t);
}
} else {
edges.push_back({abs(v), abs(u), t});
}
}
}
void add(int v, int u, int x, int y, int t, int type1, int type2) {
if (h[v] < h[u]) {
swap(v, u);
}
if (h[x] < h[y]) {
swap(x, y);
}
assert(h[v] - h[u] == h[x] - h[y]);
int g = lg[h[v] - h[u]];
if (type1 == type2) {
add_edge(g, type1 * v, type2 * x, t);
add_edge(g, type1 * la(v, h[v] - h[u] - (1 << g) + 1), type2 * la(x, h[x] - h[y] - (1 << g) + 1), t);
} else {
add_edge(g, type1 * v, type2 * la(x, h[x] - h[y] - (1 << g) + 1), t);
add_edge(g, type1 * la(v, h[v] - h[u] - (1 << g) + 1), type2 * x, t);
}
}
void merge(int v, int u) {
v = G.get(v), u = G.get(u);
if (v != u) {
G.merge(v, u);
if (G.sz[v] > G.sz[u]) {
swap(v, u);
}
if (a[v].first <= a[v].second) {
ans = ans * 1ll * inv(a[v].second - a[v].first + 1) % mod;
}
if (a[u].first <= a[u].second) {
ans = ans * 1ll * inv(a[u].second - a[u].first + 1) % mod;
}
a[u].first = max(a[u].first, a[v].first);
a[u].second = min(a[u].second, a[v].second);
if (a[u].first > a[u].second) {
ans = 0;
} else {
ans = ans * 1ll * (a[u].second - a[u].first + 1) % mod;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int j = 2; j < N; j++) {
lg[j] = lg[j / 2] + 1;
}
cin >> n;
for (int i = 2; i <= n; i++) {
int v;
cin >> v;
g[v].push_back(i);
}
for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
ans = ans * 1ll * (a[i].second - a[i].first + 1) % mod;
}
dfs(1, 1, 0);
cin >> q;
for (int j = 0; j < K; j++) {
dsu[j].build(2 * n + 1);
}
for (int i = 0; i < q; i++) {
int v, u, x, y;
cin >> v >> u >> x >> y;
int w = lca(v, u);
int z = lca(x, y);
if (h[v] - h[w] > h[x] - h[z]) {
swap(v, x);
swap(u, y);
swap(w, z);
}
if (v != w) {
int d = h[v] - h[w];
int v2 = la(v, d - 1);
int x2 = la(x, d - 1);
add(v, v2, x, x2, i, 1, 1);
v = up[v2][0];
x = up[x2][0];
}
if (x != z) {
int d = h[x] - h[z];
int v2 = la(u, (h[u] - h[v]) - d);
int x2 = la(x, d - 1);
add(v, up[v2][0], x, x2, i, -1, 1);
v = v2;
x = up[x2][0];
}
add(v, u, x, y, i, (h[v] > h[u] ? 1 : -1), (h[x] > h[y] ? 1 : -1));
}
G.build(n + 1);
int j = 0;
for (int i = 0; i < q; i++) {
while (j < (int) edges.size() && edges[j][2] == i) {
merge(edges[j][0], edges[j][1]);
j++;
}
cout << ans << '\n';
}
}
1801F - Another n-dimensional chocolate bar
Idea and preparation: Tikhon228
For $$$A$$$ we denote the maximum value of $$$a_i$$$
To begin with, let's solve the problem for $$$O(n\cdot k\cdot f(k, A))$$$ using dynamic programming.
Let's put $$$dp[i][j]$$$— the maximum possible volume of the smallest piece, if by the first $$$i$$$ measurements we divided the chocolate into $$$j$$$ parts. If we have divided into more than $$$k$$$ parts, we will also put the result in $$$dp[i][k]$$$. In terms of calculation, we need to decide how many hours to divide the chocolate bar along the next dimension. Let's look at several ways to do this.
It is possible for $$$O(k)$$$ to sort out the state to which we are moving, and from this calculate how many parts you need to divide the chocolate bar along the next dimension. — We get $$$O(n\cdot k^2)$$$
It is possible for $$$O(A)$$$ to sort out how many parts we divide the chocolate bar along the next dimension.
Being in the state of $$$dp[i][j]$$$, you can iterate over $$$b_i$$$ — into how many parts to divide the chocolate until $$$j\cdot b_i\le k$$$. It can be shown that such a solution will work for $$$O(n\cdot k\cdot\ln{k})$$$
The key idea
suppose we need to divide a chocolate bar into $$$10$$$ parts, and along the first measurements we have already divided it into $$$5$$$ parts, or $$$6$$$ parts, or $$$7, 8$$$ or $$$9$$$ parts. All these states are not distinguishable for us, because in all these cases we need to divide the chocolate bar into at least $$$2$$$ parts. It remains to understand how many such <> states there are and learn how to store them. There are several approaches for this, let's analyze one of them:
we are interested in all the values of $$$\lceil\frac{k}{i}\rceil$$$ for $$$i = 1, 2, \ldots k$$$— this is how many parts the chocolate bar may still need to be divided into. Among them, only $$$O(\sqrt{k})$$$different, since either $$$i\le\sqrt{k}$$$, or the value of $$$\lceil\frac{k}{i}\rceil\le\sqrt{k}$$$ itself. If we make all these numbers states, and recalculate, iterating over the state to which to go, we get $$$O(n\cdot\sqrt{k} \cdot\sqrt{k}) = O(n\cdot k)$$$— this is still not enough to solve the hollow problem.
Last observation
If we are in the state of $$$dp[i][remain]$$$ where $$$remain = \lceil\frac{k}{i}\rceil$$$ for some $$$i$$$, we will apply the same idea to it. From it, we are interested in transitions to the states $$$\lceil \frac{remain}{j} \rceil$$$ for $$$j = 1, 2, \ldots remain$$$. What kind of asymptotics will be obtained if we iterate over only interesting transitions?
$$$n \cdot (\sum\limits_{r=1}^{\sqrt{k}}{ 2 \cdot \sqrt{r} + 2 \cdot \sqrt{\lceil \frac{k}{r} \rceil}})$$$
- it can be shown that this is $$$O(n\cdot k^{3/4})$$$— which solves the problem
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200;
int a[MAXN];
const int MAXK = 1e7 + 100, MAXH = 1e4;
int hsh[MAXK];
int rev[MAXH];
double dp[MAXN][MAXH];
vector<array<int, 2>> go[MAXH];
main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int id = 0;
for (int c = 1;; ++id) {
rev[id] = (k + c - 1) / c;
hsh[(k + c - 1) / c] = id;
int t = (k + c - 1) / c - 1;
if (t == 0) break;
c = (k + t - 1) / t;
}
++id;
dp[0][hsh[k]] = k;
for (int i = 0; i < id; ++i) {
int k = rev[i];
for (int c = 1;;) {
go[i].push_back({c, hsh[(k + c - 1) / c]});
int t = (k + c - 1) / c - 1;
if (t == 0) break;
c = (k + t - 1) / t;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < id; ++j) {
double val = dp[i][j];
if (val == 0) continue;
for (auto elem : go[j]) {
int c = elem[0], k1 = elem[1];
if (c > a[i]) break;
int cur = a[i] / c;
dp[i + 1][k1] = max(dp[i + 1][k1], val * cur / a[i]);
}
}
}
cout << fixed << setprecision(20);
cout << dp[n][hsh[1]] << '\n';
return 0;
}
1801G - A task for substrings
Idea and preparation: grphil
Let's use the Aho-Korasik structure to store strings from $$$S$$$. Let's build compressed suffix links on it. This way it is a little more optimal to find all the lines from $$$S$$$ ending in this position $$$t$$$.
Denote by $$$pref[i]$$$ the number of substrings of $$$S$$$ in the prefix $$$t$$$ of length $$$i$$$.
Denote by $$$suf[i]$$$ the number of substrings of $$$S$$$ in the suffix $$$t$$$ starting from the position $$$i$$$.
Note that $$$pref[r] + suf[l] - priv[|T|]$$$ is equal to the number of substrings of the string for $$$t$$$ from $$$S$$$ on the segment $$$[l, p]$$$ minus the number of substrings of $$$t$$$ from $$$S$$$ that begin before $$$l$$$ and end later than $$$r$$$.
For each query, we will find a substring $$$t$$$ that matches $$$s_i$$$, which covers the string $$$t[l, r]$$$ and ends as close as possible to $$$r$$$. If there is no such thing, then the answer can be calculated using the previous formula. Otherwise, $$$t[l, r]$$$ is invested in $$$s_i[l', r']$$$. At the same time, there are no substrings of $$$S$$$ in the string $$$s_i$$$ that begin before $$$l'$$$ and end later than $$$r'$$$. To get the answer, we apply the previous formula with the string $$$s_i$$$ and the sub-section $$$[l', r']$$$.
Asymptotics: $$$O(S+ t +m \log m)$$$
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
struct node {
int nx[26];
int p;
int pp;
int len;
int id;
int cnt;
bool term;
node() : p(-1), pp(-1), len(0), id(-1), term(false), cnt(0) {
for (int i = 0; i < 26; i++) {
nx[i] = -1;
}
}
};
vector<node> g;
vector<string> s[2];
string t[2];
vector<vector<long long>> c[2], pid[2];
vector<long long> tc[2];
int add(int a, char c) {
c -= 'a';
if (g[a].nx[c] == -1) {
g[a].nx[c] = g.size();
g.emplace_back();
g.back().len = g[a].len + 1;
}
return g[a].nx[c];
}
void build_aho(int a) {
vector<pair<int, int>> q;
for (int i = 0; i < 26; i++) {
if (g[a].nx[i] == -1) {
g[a].nx[i] = a;
} else {
q.emplace_back(a, i);
}
}
int qb = 0;
while (qb < q.size()) {
int b = q[qb].x;
int i = q[qb].y;
qb++;
int v = g[b].nx[i];
int c = g[b].p;
if (g[v].term) { // bug in c != -1
g[v].cnt = 1;
}
if (c == -1) {
g[v].p = a;
g[b].pp = -1;
} else {
g[v].p = g[c].nx[i];
if (g[v].term) {
g[v].pp = v;
} else {
g[v].pp = g[g[v].p].pp;
}
g[v].cnt += g[g[v].p].cnt;
}
for (int i = 0; i < 26; i++) {
if (g[v].nx[i] == -1) {
g[v].nx[i] = g[g[v].p].nx[i];
} else {
q.emplace_back(v, i);
}
}
}
}
vector<vector<pair<int, int>>> ts;
vector<int> qlen;
priority_queue<pair<int, int>> h;
vector<long long> ans;
long long get_ans(int rdst, int len, vector<long long>& a, vector<long long>& b, bool substr) {
int l = a.size() - 1 - rdst;
int r = l + len;
long long cnt = a[r] + b[a.size() - 1 - l] - a.back();
if (substr && l == 0 && r == a.size() - 1) {
cnt++;
}
return cnt;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
g.emplace_back(); g.emplace_back();
s[0].resize(n); s[1].resize(n);
c[0].resize(n); c[1].resize(n);
pid[0].resize(n); pid[1].resize(n);
ans.resize(m);
cin >> t[0];
t[1] = t[0];
reverse(t[1].begin(), t[1].end());
ts.resize(t[0].size());
for (int i = 0; i < n; i++) {
cin >> s[0][i];
}
sort(s[0].begin(), s[0].end(), \
[](const string& a, const string& b) { return a.size() < b.size(); });
for (int i = 0; i < n; i++) {
s[1][i] = s[0][i];
reverse(s[1][i].begin(), s[1][i].end());
for (int e = 0; e < 2; e++) {
int a = e;
for (auto j : s[e][i]) {
a = add(a, j);
}
g[a].term = true;
g[a].id = i;
}
}
build_aho(0); build_aho(1);
for (int e = 0; e < 2; e++) {
tc[e].resize(t[0].size() + 1);
int a = e;
for (int i = 0; i < t[0].size(); i++) {
a = g[a].nx[t[e][i] - 'a'];
tc[e][i + 1] = tc[e][i] + g[a].cnt;
}
for (int i = 0; i < n; i++) {;
c[e][i].resize(s[0][i].size() + 1);
pid[e][i].resize(s[0][i].size() + 1, -1);
int a = e;
for (int j = 0; j < s[e][i].size(); j++) {
a = g[a].nx[s[e][i][j] - 'a'];
c[e][i][j + 1] = c[e][i][j] + g[a].cnt;
if (g[a].term) { // bug always
pid[e][i][j + 1] = g[a].id;
}
}
for (int j = (int)s[e][i].size() - 1; j >= 0; j--) { // bug forget
if (pid[e][i][j] == -1) {
pid[e][i][j] = pid[e][i][j + 1];
}
}
c[e][i].back()--; // bug forget string itself
}
}
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--;
ts[b - 1].emplace_back(a, i);
qlen.emplace_back(b - a);
}
int a = 0;
for (int i = 0; i < t[0].size(); i++) {
// cout << i << ' ' << t[0][i] << '\n';
for (auto j : ts[i]) {
h.emplace(j);
}
a = g[a].nx[t[0][i] - 'a'];
if (g[a].pp != -1) { // bug ignore
int id = g[g[a].pp].id;
int bg = i + 1 - (int)s[0][id].size();
while (h.size() > 0 && h.top().x >= bg) {
int rdst = i - h.top().x + 1;
int nid = pid[1][id][rdst]; // bug forget
// cout << h.top().x << ' ' << h.top().y << ' ' << rdst << ' ' << nid << '\n';
ans[h.top().y] = get_ans(rdst, qlen[h.top().y],
c[0][nid], c[1][nid], true);
h.pop();
}
}
}
while (h.size() > 0) {
// cout << h.top().x << ' ' << h.top().y << '\n';
ans[h.top().y] = get_ans(t[0].size() - h.top().x, qlen[h.top().y], tc[0], tc[1], false);
h.pop();
}
for (auto i : ans) {
cout << i << ' ';
}
cout << '\n';
}
Testcases aside, I thought this was generally a really cool round (or at least all the problems I tried).
same
What does SNM mean in tutorial of d1E?
It's DSU, fixed now
It can be shown that it is optimal to minimize the number of shows first, and then maximize the amount of money.
Can anyone share a proof of this statement? it seems intuitive but i failed to prove it:c
If there are fewer shows, they can do another show to get more money
It can be seen that for all paths with end vertex $$$v$$$ and best vertex $$$t$$$, the number of shows is $$$0$$$ and/or the amount of money $$$< w_t$$$. So comparing any two possible paths with the same $$$v, t$$$, you can always do more shows on the path with fewer shows to get at least $$$w_t$$$ rubles, which would be more money than the other path.
Never thought 69 would hurt so much
This round is a little difficult, but the tasks are really interesting. I love div 2C.
div1E smart solution is great!
Can I solve solve Div1 B with ternary search? If so, why my solution 197805657 did'nt work for this? Can someone help me?
alternate construction for beautiful blanket: for each row, simply use consecutive integers. denote the smallest power of 2 greater than m as 2^j. then let the first element in each row i be i*2^j, and the rest of the elements be simply the consecutive integers after i*2^j. this construction satisfies the conditions in the problem. examples:
Thanks ! Your solution is easier to prove its accuracy.
can any one say whats wrong with this solution for div2.c
Check the xor value of 3,6,13,16 (not zero)
为什么没有中文版?
Why is there no Chinese version?
I think it is necessary,too.
I'm sure this is inadvertant, but in problem 1801A, after submitting any wrong solution, the pattern is literally visible in jury's answer xD.
Can somebody explain solution to Div 1. C? I can't understand what the editorial says.
This is how I solved the problem. It's a bit long but I tried to make it as comprehensive as possible -
the first thing we notice is no matter which track we start from in a particular song, the ending track will always remain the same and this position is the last track in the song such that it is strictly greater than all tracks before it. Let's denote this track's value as $$$X[i]$$$.
We notice that if we place a song $$$j$$$ with larger $$$X[j]$$$ before a song $$$i$$$ all tracks in song $$$i$$$ become redundant since you can't continue any of them.
So it's best if we sort the songs by the value of $$$X[i]$$$ in non decreasing order. But the issue is when we reach a case like -
$$$n$$$ = 3
first song — 1 2 3
second song — 5
third song — 4 5 6
here we could place the third song after the first song to get a higher value.
From now on we shall consider all songs as sorted by $$$X[i]$$$. So we do dp, where $$$dp[i]$$$ stores the max coolness in the prefix of length $$$i$$$.
We also notice that the values of $$$dp[i]$$$ are non decreasing since we can always just continue off of the values of $$$dp[i-1]$$$.
Now, let us denote $$$val[i][j]$$$ as the max that we can extend the $$$jth$$$ track in song i, for example the following song would have values —
song = 4 1 3 6 2 8
$$$val[i]$$$ = 3 -1 -1 2 -1 1
I denote -1 for some $$$val[i][j]$$$ because they are not the max value in the prefix and they never add to the coolness.
To compute $$$dp[i]$$$, we go through all tracks of song $$$i$$$ and binary search to find the first $$$X[k]$$$ that is strictly less than $$$a[i][j]$$$ (where $$$a[i][j]$$$ denotes the value of track $$$j$$$ in song $$$i$$$) and $$$val[i][j] \neq -1$$$, then we choose the max value of $$$dp[k]+val[i][j]$$$ over all valid tracks $$$j$$$.
The final answer is $$$dp[n]$$$. Here is my submission
Thank you bro, great explanation!
I did pretty much the same thing that you did. I am somehow getting the wrong answer. Here is my submission link submission. I am having a hard time debugging. Could you please help
What's the correctness issue with using Dijkstra's directly using the same cost function as the editorial mentions, and using the shortest path found to n-1, rather than maintaining the dp state for NxN [v][best] pairs?
It might be optimal to 'stop by' a different node for higher money from performances, before continuing on to the end.
The solution for 1801A can be simpler: just let M(i,j)=i*256+j.
I appreciate the fast editorial, however it has been quite a while and the solution for B has not been posted yet. Aleks5d please post the solution! It would help newbies like me out :)
Let U be a guinea pig whose gender is not yet known.
If $$$x=1$$$, let $$$U:=U+1$$$.
If $$$x=2$$$, let $$$K$$$ be the number of guinea pigs whose gender is known.
In the state of $$$U$$$, it must always be in a cage. For $$$K$$$, $$$⌈K/2⌉$$$ cages are needed.
This is because in the worst case, the gender must be determined in order male, female, male, etc., and eventually $$$⌈K/2⌉$$$ cages are needed.
However, since cages are not lost once they are bought, the maximum value of the answer is updated as follows.
ans = max(ans, k + ceil(t/2))
C,
Actually, We can always make all part as zero with this.
Div-1 E doesn't really require HLD, we can simply use two fenwick trees to find hash of a path in $$$O(\log{n})$$$ similarly to how we query path sum in trees.
Each path $$$u \rightarrow v$$$ can be divided into two subpaths $$$u \rightarrow lca(u, v)$$$ and $$$lca(u, v) \rightarrow v$$$.
We can now build two fenwick trees upon euler tour of the tree, one to find the hash of upward vertical path $$$u \rightarrow lca(u, v)$$$ and one to find the hash of downward vertical path $$$lca(u, v) \rightarrow v$$$.
($$$par_u$$$ is the parent of $$$u$$$ in dsu, $$$H$$$ is height of the tree, and $$$P$$$ is the number we chose for exponents in hash)
To find hash of upward vertical path $$$a \rightarrow b$$$, simply query range $$$[ExitTime_a, ExitTime_b]$$$ in the first fenwick tree. To find hash of downward vertical path $$$a \rightarrow b$$$, simply query range $$$[EntryTime_a, EntryTime_b]$$$ in the second fenwick. (Exponents can ofc be easily adjusted in $$$O(1)$$$ with $$$O(n\log{MOD})$$$ precomputation.)
Implementation: link
Can someone please explain Problem C- Music Festival solution? I did not understand the tutorial at all. vaaven
how does one get the logic of div2a (beautiful blanket) during contest?
Div 1D. Can we use the topological sort instead of dijkstra?
270590828 — My wa6 solution.
Div 1D, Can someone please help me with my submission? I have tried debugging for a few hours but I can't get it.
I suspect it is something to do with priority_queue ordering, WA6. Thanks.
Edit: solved