We hoped you find our problems interesting. We apologize for the late editorial. Hopefully you were still able to enjoy our contest.
Anyway, here are the tutorials for each of the problems:
If the total number of occurrences of some character $$$c$$$ is not a multiple of $$$n$$$, then it is impossible to make all $$$n$$$ strings equal — because then it is impossible for all $$$n$$$ strings to have the same number of $$$c$$$.
On the other hand, if the total number of occurrences of every character $$$c$$$ is a multiple of $$$n$$$, then it is always possible to make all $$$n$$$ strings equal. To achieve this, for every character $$$c$$$ we move exactly ((the total number of occurrences of $$$c$$$) $$$/$$$ $$$n$$$) characters $$$c$$$ to the end of each string, and by the end we will have all $$$n$$$ strings equal each other.
We can easily check if the condition satisfies by counting the total number of occurrences of each character $$$c$$$ and check its divisibility by $$$n$$$. The final complexity is $$$O(S \cdot 26)$$$ or $$$O(S)$$$ where $$$S$$$ is the sum of lengths of all strings.
C++ solution
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests--) {
int n;
cin >> n;
vector<int> cnt(26);
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
for (char ch : s) {
++cnt[ch - 'a'];
}
}
bool ans = true;
for (int i = 0; i < 26; ++i) {
if (cnt[i] % n != 0) {
ans = false;
break;
}
}
cout << (ans ? "YES" : "NO") << endl;
}
}
Python solutionnumTests = int(input())
for testNo in range(numTests):
n = int(input())
cnt = [0 for i in range(26)]
for _ in range(n):
s = input()
for i in s:
cnt[ord(i) - 97] += 1
ans = True
for i in range(26):
if cnt[i] % n != 0:
ans = False
break
if ans:
print('YES')
else:
print('NO')
First of all, the optimal way to reorder is to sort $$$a$$$ in non-decreasing order.
ProofNote that the cost the transform $$$a_i$$$ to $$$c^i$$$ is $$$\lvert a_i - c^i \rvert$$$. While there is a pair $$$(a_i, a_j)$$$ such that $$$i < j$$$ and $$$a_i > a_j$$$, swap $$$a_i$$$ and $$$a_j$$$. Since $$$\lvert x \rvert + \lvert y \rvert = max \{ \lvert x + y \rvert, \lvert x - y \rvert \}$$$, we have
$$$\lvert a_i - c^i \rvert + \lvert a_j - c^j \rvert$$$
$$$= max \{ \lvert (a_i + a_j) - (c^i + c^j) \rvert, \lvert (a_i - a_j) - (c^i - c^j) \rvert \}$$$
$$$\ge max \{ \lvert (a_j + a_i) - (c^i + c^j) \rvert, \lvert (a_j - a_i) - (c^i - c^j) \rvert \}$$$
$$$= \lvert a_j - c^i \rvert + \lvert a_i - c^j \rvert$$$
when $$$a_i > a_j$$$ and $$$c^i \le c^j$$$, so the total cost does not increase. Hence, it is best to have $$$a_0 \le a_1 \le \cdots \le a_{n-1}$$$.
From now on, we assume $$$a$$$ is sorted in non-decreasing order.
Denote $$$a_{max} = a_{n - 1}$$$ as the maximum value in $$$a$$$, $$$f(x) = \sum{\lvert a_i - x^i \rvert}$$$ as the minimum cost to transform $$$a$$$ into $$${x^0, x^1, \cdots, x^{n-1}}$$$, and $$$c$$$ as the value where $$$f(c)$$$ is minimum.
Note that $$$c^{n - 1} - a_{max} \le f(c) \le f(1)$$$, which implies $$$c^{n - 1} \le f(1) + a_{max}$$$.
We enumerate $$$x$$$ from $$$1, 2, 3, \dots$$$ until $$$x^{n - 1}$$$ exceeds $$$f(1) + a_{max}$$$, calculate $$$f(x)$$$ in $$$O(n)$$$, and the final answer is the minimum among all calculated values. The final complexity is $$$O(n \cdot max(x))$$$.
But why doesn't this get TLE? Because $$$f(1) = \sum{(a_i - 1)} < a_{max} \cdot n \le 10^9 \cdot n$$$, thus $$$x^{n - 1} \le f(1) + a_{max} \le 10^9 \cdot (n + 1)$$$. When $$$n = 3, 4, 5, 6$$$, $$$max(x)$$$ does not exceed $$$63245, 1709, 278, 93$$$ respectively; so we can see that $$$O(n \cdot max(x))$$$ comfortably fits in the time limit.
C++ solution#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
const int64_t INF = 1e17;
inline int64_t mul(int64_t a, int64_t b)
{
return (INF / a > b ? a * b : INF);
}
inline int64_t add(int64_t a, int64_t b)
{
return (a + b >= INF ? INF : a + b);
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
sort(a.begin(), a.end());
if (n <= 2) {
cout << a[0] - 1 << endl;
} else {
int64_t ans = accumulate(a.begin(), a.end(), 0ll) - n;
for (int x = 1; ; ++x) {
int64_t curPow = 1, curCost = 0;
for (int i = 0; i < n; ++i) {
curCost = add(curCost, abs(a[i] - curPow));
curPow = mul(curPow, x);
}
if (curPow == INF || curPow / x > ans + a[n - 1]) break;
ans = min(ans, curCost);
}
cout << ans << endl;
}
}
Python solutionn = int(input())
a = [int(x) for x in input().split()]
a.sort()
inf = 10**18
if n <= 2:
print(a[0] - 1)
else:
ans = sum(a) - n
for x in range(1, 10**9):
curPow = 1
curCost = 0
for i in range(n):
curCost += abs(a[i] - curPow)
curPow *= x
if curPow > inf:
break
if curPow > inf:
break
if curPow / x > ans + a[n - 1]:
break
ans = min(ans, curCost)
print(ans)
In this problem, the answer is rather simple. Here is one possible solution to this task.
Solution for n = 1$$$1 \space \space 1$$$
$$$0$$$
$$$1 \space \space 1$$$
$$$0$$$
$$$1 \space \space 1$$$
$$$-a_1$$$
Solution for n != 1$$$1 \space \space 1$$$
$$$-a_1$$$
$$$1 \space \space n$$$
$$$0, \space -n \cdot a_2, \space -n \cdot a_3, \space \dots , \space -n \cdot a_n$$$
$$$2 \space \space n$$$
$$$(n-1) \cdot a_2, \space (n-1) \cdot a_3, \space \dots , \space (n-1) \cdot a_n$$$
C++ solution#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int N;
cin >> N;
vector<ll> A(N);
for (int i = 0; i < N; ++i) cin >> A[i];
if (N == 1) {
for (int z = 0; z < 3; ++z) {
cout << "1 1\n";
cout << -A[0] << "\n";
A[0] = 0;
}
return 0;
}
cout << "1 " << N << "\n";
for (int i = 0; i + 1 < N; ++i) cout << -A[i] * N << " "; cout << "0\n";
cout << "1 " << N - 1 << "\n";
for (int i = 0; i + 1 < N; ++i) cout << A[i] * (N - 1) << " "; cout << "\n";
cout << N << " " << N << "\n";
cout << -A[N - 1] << "\n";
return 0;
}
Python solutionn = int(input())
a = list(map(int, input().split()))
if n == 1:
print('1 1', -a[0], '1 1', '0', '1 1', '0', sep='\n')
exit(0)
print(1, n)
for i in range(n):
print(-a[i] * n, end = ' ')
a[i] -= a[i] * n
print()
print(1, n - 1)
for i in range(n - 1):
print(-a[i], end = ' ')
a[i] = 0
print()
print(2, n)
for i in range(1, n):
print(-a[i], end = ' ')
a[i] = 0
print()
Let us denote $$$S$$$ as the current total number of stones.
Consider the following cases:
Case A: There is a pile that has more than $$$\lfloor \frac{S}{2} \rfloor$$$ stones.
The first player (T) can always choose from this pile, thus he (T) is the winner.
Case B: Every pile has at most $$$\lfloor \frac{S}{2} \rfloor$$$ stones, and $$$S$$$ is even.
It can be proven that the second player (HL) always wins.
Proof 1Let us prove by induction:
When $$$S = 0$$$, the second player obviously wins.
When $$$S \geq 2$$$, consider the game state after the first player moves. If there is a pile that now has more than $$$\lfloor \frac{S}{2} \rfloor$$$ stones, then we arrive back at case A where the next player to move wins. Otherwise, the second player can choose from any valid pile (note that the case condition implies that there are at least two non-empty piles before the first player's move). Now $$$S$$$ has been reduced by $$$2$$$, and every pile still has at most $$$\lfloor \frac{S}{2} \rfloor$$$ stones.
Proof 2The condition allows us to assign a perfect matching of stones, where one stone is matched with exactly one stone from a different pile.
A greedy way to create such a matching: Give each label $$$0, 1, \dots, S - 1$$$ to a different stone so that for every pair of stones with labels $$$l < r$$$ that are from the same pile, stones $$$l + 1, l + 2, \dots, r - 1$$$ are also from that pile; then match stones $$$i$$$ with $$$i + \frac{S}{2}$$$ for all $$$0 \le i < \frac{S}{2}$$$.
For every stone that the first player removes, the second player can always remove its matching stone, until the first player can no longer make a move and loses.
Case C: Every pile has at most $$$\lfloor \frac{S}{2} \rfloor$$$ stones, and $$$S$$$ is odd.
The first player (T) can choose from any pile, and we arrive back at case B where the next player to move loses.
So the first player (T) wins if and only if there is a pile that has more than $$$\lfloor \frac{S}{2} \rfloor$$$ stones or $$$S$$$ is odd. This can be easily checked in $$$O(n)$$$.
C++ solution#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int maxPile = *max_element(a.begin(), a.end());
int numStones = accumulate(a.begin(), a.end(), 0);
if (maxPile * 2 > numStones || (numStones & 1)) cout << "T" << endl;
else cout << "HL" << endl;
}
}
Python solutiont = int(input())
for _ in range(t):
n = int(input())
a = [int(x) for x in input().split()]
maxPile = max(a)
numStones = sum(a)
if maxPile * 2 > numStones or (numStones & 1):
print('T')
else:
print('HL')
In this problem, it is useful to note that when the boss only has $$$1$$$ hp left, just use the pistol because it has the least reloading time. So there are 3 strategies we will use when playing at stage $$$i$$$ $$$(1 \le i \le n)$$$:
- Take $$$a_i$$$ pistol shots to kill first $$$a_i$$$ monsters and shoot the boss with the AWP.
- Take $$$a_i + 1$$$ pistol shots and move back to this stage later to take another pistol shot to finish the boss.
- Use the laser gun and move back to this stage later to kill the boss with a pistol shot.
Observation: We will always finish the game at stage $$$n$$$ or $$$n - 1$$$. Considering we are at stage $$$i$$$ $$$(i \le n - 1)$$$ and the boss at both stage $$$i$$$ stage $$$i - 1$$$ has $$$1$$$ hp left, we can spend $$$2 * d$$$ time to finish both these stages instead of going back later, which costs us exactly the same.
Therefore, we will calculate $$$dp(i,0/1)$$$ as the minimum time to finish first $$$i - 1$$$ stages and 0/1 is the remaining hp of the boss at stage $$$i$$$. The transitions are easy to figure out by using 3 strategies as above. The only thing we should note is that we can actually finish the game at stage $$$n - 1$$$ by instantly kill the boss at stage $$$n$$$ with the AWP so we don't have to go back to this level later.
Answer to the problem is $$$dp(n, 0)$$$. Time complexity: $$$O(n)$$$.
C++ solution/*input
4 2 4 4 1
4 5 1 2
*/
#include <bits/stdc++.h>
using namespace std;
int read() {
int x = 0, c = getchar();
for(; !(c > 47 && c < 58); c = getchar());
for(; (c > 47 && c < 58); c = getchar()) x = x * 10 + c - 48;
return x;
}
void upd(long long &a, long long b) {
a = (a < b) ? a : b;
}
const int N = 1e6 + 5;
long long f[N][2];
int n, r1, r2, r3, d, a[N];
int main(){
n = read(), r1 = read(), r2 = read(), r3 = read(), d = read();
for(int i = 1; i <= n; a[i ++] = read());
for(int i = 2; i <= n; ++ i) f[i][0] = f[i][1] = 1e18;
f[1][0] = 1ll * r1 * a[1] + r3;
f[1][1] = min(0ll + r2, 1ll * r1 * a[1] + r1);
for(int i = 1; i < n; ++ i) {
// 0 -> 0
// so we clear this one and the next one as well
upd(f[i + 1][0], f[i][0] + d + 1ll * r1 * a[i + 1] + r3);
// 0 -> 1
// this one is cleared, but next one isnt
upd(f[i + 1][1], f[i][0] + d + min(0ll + r2, 1ll * r1 * a[i + 1] + r1));
// 1 -> 0
upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r3 + 2 * d + r1);
upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r1 + d + r1 + d + r1);
upd(f[i + 1][0], f[i][1] + d + r2 + d + r1 + d + r1);
// 1 -> 1
upd(f[i + 1][1], f[i][1] + d + r2 + d + r1 + d);
upd(f[i + 1][1], f[i][1] + d + 1ll * r1 * a[i + 1] + r1 + d + r1 + d);
if(i == n - 1) {
upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r3 + d + r1);
}
}
cout << f[n][0] << endl;
}
Tutorial is loading...
C++ solution#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
int L;
ll sum[8040];
int len[8040];
int last[8040];
int lazy[8040];
void init(int v, int l, int r, const vector<int> &xs) {
len[v] = xs[r] - xs[l - 1];
if (l < r) {
int md = (l + r) >> 1;
init(v << 1, l, md, xs);
init(v << 1 | 1, md + 1, r, xs);
}
}
void reset(int v, int l, int r, const vector<int> &go) {
lazy[v] = -1;
if (l == r) {
sum[v] = ll(len[v]) * (L - go[l]);
last[v] = go[l];
return;
}
int md = (l + r) >> 1;
reset(v << 1, l, md, go);
reset(v << 1 | 1, md + 1, r, go);
sum[v] = sum[v << 1] + sum[v << 1 | 1];
last[v] = last[v << 1 | 1];
}
void push(int v, int l, int r) {
if (lazy[v] != -1) {
last[v] = lazy[v];
sum[v] = ll(len[v]) * (L - lazy[v]);
if (l < r) {
lazy[v << 1] = lazy[v];
lazy[v << 1 | 1] = lazy[v];
}
lazy[v] = -1;
}
}
void modify(int v, int l, int r, int L, int R, int qv) {
push(v, l, r);
if (L > r || R < l) return;
if (L <= l && r <= R) {
lazy[v] = qv;
push(v, l, r);
return;
}
int md = (l + r) >> 1;
modify(v << 1, l, md, L, R, qv);
modify(v << 1 | 1, md + 1, r, L, R, qv);
sum[v] = sum[v << 1] + sum[v << 1 | 1];
last[v] = last[v << 1 | 1];
}
int walk(int v, int l, int r, int qv) {
push(v, l, r);
if (last[v] <= qv) return -1;
if (l == r) return l;
int md = (l + r) >> 1;
int ans = walk(v << 1, l, md, qv);
if (ans == -1) ans = walk(v << 1 | 1, md + 1, r, qv);
return ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int N, K; cin >> N >> K >> L;
vector<int> X(N), Y(N), C(N);
vector<int> xs = {-1, L};
vector<int> ys = {-1, L};
for (int i = 0; i < N; ++i) {
cin >> X[i] >> Y[i] >> C[i];
--C[i];
xs.emplace_back(X[i]);
ys.emplace_back(Y[i]);
}
sort(xs.begin(), xs.end());
xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
int NX = xs.size();
int NY = ys.size();
{
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return make_pair(Y[i], -X[i]) > make_pair(Y[j], -X[j]);
});
vector<int> newX(N), newY(N), newC(N);
for (int i = 0; i < N; ++i) {
newX[i] = X[order[i]];
newY[i] = Y[order[i]];
newC[i] = C[order[i]];
}
X.swap(newX), Y.swap(newY), C.swap(newC);
}
init(1, 1, NX - 2, xs);
int ans = 0;
for (int yr = 1; yr + 1 < NY; ++yr) {
vector<vector<int>> addAt(NX);
for (int i = 0; i < N; ++i) {
if (Y[i] <= ys[yr]) {
int xi = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
addAt[xi].emplace_back(C[i]);
}
}
int bad = K;
vector<int> cnts(K);
auto inc = [&](int z) {
if (++cnts[z] == 1) --bad;
};
auto dec = [&](int z) {
if (--cnts[z] == 0) ++bad;
};
vector<int> go(NX);
int ptr = 0;
for (int i = 1; i + 1 < NX; ++i) {
while (bad && ptr + 2 < NX) {
ptr++;
for (int z : addAt[ptr]) inc(z);
}
if (bad) go[i] = L;
else go[i] = xs[ptr];
for (int z : addAt[i]) dec(z);
}
reset(1, 1, NX - 2, go);
vector<int> prv(N);
vector<int> nxt(N);
vector<map<int, int>> mp(K);
for (int i = 0; i < N; ++i) {
if (Y[i] <= ys[yr]) {
auto it = mp[C[i]].lower_bound(X[i]);
if (it == mp[C[i]].end()) {
nxt[i] = -1;
} else {
nxt[i] = it->second;
}
it = mp[C[i]].upper_bound(X[i]);
if (it == mp[C[i]].begin()) {
prv[i] = -1;
} else {
prv[i] = prev(it)->second;
}
mp[C[i]][X[i]] = i;
}
}
auto remove = [&](int i) {
int xprv = (prv[i] == -1 ? -1 : X[prv[i]]);
int xcur = X[i];
int xnxt = (nxt[i] == -1 ? L : X[nxt[i]]);
int l = lower_bound(xs.begin(), xs.end(), xprv) - xs.begin() + 1;
int r = walk(1, 1, NX - 2, xnxt);
if (r == -1) r = NX - 1; --r;
r = min(r, int(lower_bound(xs.begin(), xs.end(), xcur) - xs.begin()));
if (l <= r) modify(1, 1, NX - 2, l, r, xnxt);
};
ptr = N - 1;
for (int yl = 1; yl <= yr; ++yl) {
ll add = sum[1] % MOD * (ys[yr + 1] - ys[yr]) % MOD * (ys[yl] - ys[yl - 1]) % MOD;
ans = (ans + add) % MOD;
while (ptr >= 0 && Y[ptr] == ys[yl]) remove(ptr--);
}
assert(sum[1] == 0);
}
cout << ans << "\n";
return 0;
}
Tutorial is loading...
C++ solution#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int N; ll K;
cin >> N >> K;
vector<vector<int>> adj(N);
for (int i = 0; i < N - 1; ++i) {
int v, u;
cin >> v >> u;
adj[--v].emplace_back(--u);
adj[u].emplace_back(v);
}
vector<int> sz(N);
function<void(int, int)> dfs1 = [&](int v, int p) {
sz[v] = 1;
for (int u : adj[v]) if (u != p) {
dfs1(u, v);
sz[v] += sz[u];
}
};
dfs1(0, -1);
int root = 0;
for (int i = 1; i < N; ++i) {
if (sz[i] >= N / 2 && sz[i] < sz[root]) root = i;
}
vector<int> dist(N);
vector<int> top(N, -1);
vector<int> par(N, -1);
ll low = 0, high = 0;
function<void(int, int, int)> dfs2 = [&](int v, int p, int r) {
dist[v] = dist[p] + 1;
top[v] = r;
par[v] = p;
{
auto it = find(adj[v].begin(), adj[v].end(), p);
assert(it != adj[v].end());
adj[v].erase(it);
}
sz[v] = 1;
for (int u : adj[v]) {
dfs2(u, v, r);
sz[v] += sz[u];
}
low += (sz[v] & 1);
high += sz[v];
};
for (int v : adj[root]) {
dfs2(v, root, v);
}
if (low > K || high < K || (high - K) % 2) {
cout << "NO\n";
return 0;
}
set<pair<int, int>> sizes;
for (int v : adj[root]) {
sizes.emplace(sz[v], v);
}
vector<set<pair<int, int>>> lcas(N);
vector<int> deg(N);
for (int v = 0; v < N; ++v) deg[v] = adj[v].size();
for (int v = 0; v < N; ++v) if (v != root) {
if (deg[v] == 0) {
} else {
lcas[top[v]].emplace(dist[v], v);
}
}
vector<bool> matched(N);
function<void(int)> kill = [&](int v) {
assert(deg[v] == 0);
if (--deg[par[v]] == 0) {
v = par[v];
lcas[top[v]].erase(pair<int, int>(dist[v], v));
}
};
cout << "YES\n";
while (high > K) {
assert(sizes.size());
int v = (--sizes.end())->second;
sizes.erase(pair<int, int>(sz[v], v));
assert(lcas[v].size());
int mdist = (--lcas[v].end())->first;
if (high - 2 * mdist <= K) {
int x = lcas[v].lower_bound(pair<int, int>((high - K) / 2, -1))->second;
int y = -1;
for (int z : adj[x]) if (!matched[z]) {
y = z;
break;
}
high = K;
cout << x + 1 << " " << y + 1 << "\n";
matched[x] = true;
matched[y] = true;
break;
} else {
high -= 2 * mdist;
assert(lcas[v].size());
int u = (--lcas[v].end())->second;
vector<int> nxts;
while (nxts.size() < 2 && adj[u].size()) {
int w = adj[u].back();
adj[u].pop_back();
if (!matched[w]) {
nxts.emplace_back(w);
}
}
if (nxts.size() < 2) nxts.emplace_back(u);
assert(nxts.size() == 2);
cout << nxts[0] + 1 << " " << nxts[1] + 1 << "\n";
matched[nxts[0]] = true;
matched[nxts[1]] = true;
kill(nxts[0]);
kill(nxts[1]);
sz[v] -= 2;
if (sz[v]) sizes.emplace(sz[v], v);
}
}
vector<int> seq;
function<void(int)> dfs3 = [&](int v) {
if (!matched[v]) seq.emplace_back(v);
for (int u : adj[v]) dfs3(u);
};
dfs3(root);
int h = seq.size() / 2;
for (int i = 0; i < h; ++i) {
cout << seq[i] + 1 << " " << seq[i + h] + 1 << "\n";
}
}