I'm very very sorry to all Div2 participants for unclearness in statement of A, and not including notes in the statement of B, hope it didnt ruined a contest for you. Thank you all for participating, I hope you enjoyed non-empty subset of the problems! You can rate the problems of the round in the corresponding spoilers.
Hint 1
You can always bruteforce $$$X$$$ and $$$Y$$$, and check every pair of $$$(X, Y)$$$ separately, but there is a tRiCkY solution that involves zero implementation.
Hint 2
Have you ever watched a game of tennis, a game of volleyball, e.t.c?
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
cout << s.back() << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
Everything is symmetrical, so you can fix beforehand any exact two conditions you are aimed to satisfy.
Hint 2
You need to not satisfy $$$3$$$rd condition, so it doesnt really make sense to color any elements that not used in satisfying conditions $$$1$$$ and $$$2$$$ in colors $$$b_i = 2, b_i = 3$$$. And to satisfy conditions $$$1$$$ and $$$2$$$ one element is enough.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> b(n, 1);
vector<vector<int>> inds(N + 1);
for (int i = 0; i < n; i++) {
inds[a[i]].push_back(i);
}
int k = 2;
for (int x = 1; x <= N; x++) {
if ((int) inds[x].size() >= 2) {
b[inds[x][0]] = k;
k++;
if (k > 3) {
break;
}
}
}
if (k <= 3) {
cout << "-1\n";
} else {
for (int i = 0; i < n; i++) {
cout << b[i] << ' ';
}
cout << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
How to rollback one operation? Is rollback uniquely determined?
Hint 1.1
Of course it is.
Hint 2
After performing operation $$$a_x = x$$$ always becomes a last element of array.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
k = min(k, n);
int last = n - 1;
for (int _ = 0; _ < k; _++) {
if (a[last] > n) {
cout << "No\n";
return;
}
last += n - a[last];
if (last >= n) {
last -= n;
}
}
cout << "Yes\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
Lower bound for answer: $$$LIS(a)$$$
Hint 2
Upper bound for answer: $$$LIS(a)+1$$$, you can insert $$$b$$$'s in decreasing order anywhere. When you can't achieve $$$LIS(a)$$$?
Hint 3
Solve for $$$m = 1$$$
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m), c(n + m);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
cin >> b[i];
}
sort(rall(b));
merge(all(a), all(b), c.begin(), greater<int>());
for (int i = 0; i < n + m; i++) {
cout << c[i] << ' ';
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
It makes sense to try to solve case $$$m = 1$$$ first, to get general understanding of the problem, some observations will be usefull in full solution.
Hint 1.1
What size can a multiset $$$X$$$ have?
Hint 1.2
If $$$r - l > n$$$, the answer to the problem is $$$0$$$. Now we are left in the case of $$$r - l \leq n$$$. So we can iterate over all sizes from $$$l$$$ to $$$r$$$, for each of them find the minimum anti-beauty that can have a set of this size, and take the minimum of all this for the answer.
Hint 2
For bigger $$$m$$$ you need to find a fast enough way to count minimal anti-beauty with fixed size, everything else remains the same.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define all(x) x.begin(), (x).end()
using namespace std;
void solve() {
int m;
cin >> m;
vector<int> n(m), l(m), r(m);
vector<vector<int>> a(m);
vector<vector<int>> c(m);
vector<int> sumc(m);
int suml = 0, sumr = 0, sumn = 0;
for (int i = 0; i < m; i++) {
cin >> n[i] >> l[i] >> r[i];
sumn += n[i];
suml += l[i];
sumr += r[i];
a[i].resize(n[i]);
for (int j = 0; j < n[i]; j++) {
cin >> a[i][j];
}
c[i].resize(n[i]);
for (int j = 0; j < n[i]; j++) {
cin >> c[i][j];
sumc[i] += c[i][j];
}
}
if (sumr - suml > sumn) {
cout << "0\n";
return;
}
map<int, int> sumr_a;
map<int, vector<pair<int, int>>> indexes;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n[i]; j++) {
sumr_a[a[i][j]] += r[i];
indexes[a[i][j]].pb({i, j});
}
}
int ans = (int) 2e18;
for (int len = suml; len <= sumr; len++) {
int xsize = 0, must_len = 0;
xsize += sumr - sumr_a[len];
for (auto &[i, pos] : indexes[len]) {
int cnt_not_len = sumc[i] - c[i][pos];
if (cnt_not_len < l[i]) {
xsize += l[i];
must_len += l[i] - cnt_not_len;
} else {
xsize += min(cnt_not_len, r[i]);
}
}
ans = min(ans, must_len + max(0LL, len - xsize));
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hints: Natural Way
Hint 1
Solve the problem if $$$s_i = d_i$$$ for all $$$i$$$.
Hint 1.1
Simple greedy should work.
Hint 2
Solve the problem if $$$s_i = 2 \cdot d_i$$$ for all $$$i$$$.
Hint 3
Solve the problem if $$$d_i$$$ divides $$$s_i$$$ for all $$$i$$$.
Hint 4
You can treat remainder $$$(s_i \mod d_i)$$$ separately, as an individual shelf.
Hints: Believers Way
Hint -1
What is the most obvious greedy you can do?
Hint -2
What is the second most obvious greedy you can do?
Hint -3
What is the third most obvious greedy you can do?
Hint -4
It's probably correct at this point, just proof by AC!
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> s(m), d(m);
for (int i = 0; i < m; i++) {
cin >> s[i];
}
for (int i = 0; i < m; i++) {
cin >> d[i];
}
vector<int> cnt(n + 1);
for (int i = 0; i < n; i++) {
cnt[a[i]]++;
}
set<pair<int, int>> cubes;
for (int x = 1; x <= n; x++) {
if (cnt[x] == 0) continue;
cubes.insert({cnt[x], x});
}
vector<vector<int>> ans(m);
for (int i = 0; i < m; i++) {
ans[i].assign(s[i], 0);
for (int j = 0; j < s[i]; j++) {
if (j >= d[i]) {
if (cnt[ans[i][j - d[i]]] > 0) {
cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]});
}
}
if (cubes.empty()) {
cout << "-1\n";
return;
}
ans[i][j] = (*cubes.rbegin()).second;
cubes.erase(*cubes.rbegin());
cnt[ans[i][j]]--;
}
for (int j = s[i]; j < s[i] + d[i]; j++) {
if (cnt[ans[i][j - d[i]]] > 0) {
cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]});
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < s[i]; j++) {
cout << ans[i][j] << ' ';
}
cout << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
Hint 1
Cacti is a trap, don't think about it for now, it will help later.
Hint 2
Well, you need to make some observations. Start with observations about determining edges weights, it seems reasonable because edge always have exactly $$$2$$$ adjacent vertices.
Hint 3
Edge is good <=> Exactly one of the adjacent vertexes have a same weight as an edge.
Hint 4
Direct edges, such that every edge goes from vertex with same weight as edge to another vertex. In this reality try to find easier equivalent condition for ``vertice is good``.
Hint 5
Vertex is good <=> OutDegree of vertex is an odd integer.
Hint 6
Now you just have two separate problems: 1) Direct all edges, such that OutDegree of each vertex is odd; 2) Color all vertexes in 3 colors such that any 2 adjacent vertexes have different color. Time to remember about cacti.
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
using namespace std;
const int M = 998244353;
const int N = 500500;
vector<pair<int, int>> g[N];
set<int> bridgesV[N];
bitset<N> used;
int h[N], d[N];
ll bridges = 0;
ll solo = 0;
int binpow(ll a, ll x) {
ll ans = 1;
while (x) {
if (x % 2) {
ans *= a;
ans %= M;
}
a *= a;
a %= M;
x /= 2;
}
return (int) ans;
}
void dfs(int v, int p = -1) {
if (p != -1) {
d[v] = h[p] + 1;
h[v] = h[p] + 1;
}
used[v] = true;
for (auto &[u, w] : g[v]) {
if (u == p) continue;
if (!used[u]) {
dfs(u, v);
d[v] = min(d[v], d[u]);
if (h[v] < d[u]) {
bridgesV[v].insert(u);
bridgesV[u].insert(v);
bridges += w + 1;
solo += w;
}
} else {
d[v] = min(d[v], h[u]);
}
}
}
int calc_dp(ll n) {
n %= (M - 1);
if (n == 1) return 3;
if (n == 2) return 0;
int val = binpow(2, n);
if (n % 2 == 1) {
val += M - 2;
} else {
val += 2;
}
val %= M;
return val;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
a--;
b--;
g[a].pb({b, w});
g[b].pb({a, w});
}
if (n % 2 != m % 2) {
cout << "0\n";
return 0;
}
dfs(0);
used.reset();
ll ans = 1;
for (int v = 0; v < n; v++) {
if (!used[v]) {
ll cs = 0;
vector<int> q = {v};
used[v] = true;
while (!q.empty()) {
int u = q.back();
q.pop_back();
for (auto &[uu, w] : g[u]) {
if (bridgesV[u].find(uu) != bridgesV[u].end()) continue;
cs += w + 1;
if (!used[uu]) {
used[uu] = true;
q.pb(uu);
}
}
}
cs /= 2;
cs = max(cs, 1LL);
ans *= calc_dp(cs);
ans %= M;
}
}
ans *= binpow(3, solo);
ans %= M;
int w = (2 * binpow(3, M - 2)) % M;
ans *= binpow(w, bridges);
ans %= M;
int cycles = (m + 1) - n;
ans *= binpow(2, cycles);
ans %= M;
cout << ans << '\n';
}
