We hoped you enjoyed the problems. 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.
ProofThe cost to transform $$$a_i$$$ to $$$c^i$$$ is $$$\lvert a_i - c^i \rvert$$$, and $$$\lvert a_i - c^i \rvert + \lvert a_j - c^j \rvert \le \lvert a_j - c^i \rvert + \lvert a_i - c^j \rvert$$$ when $$$i < j$$$ and $$$a_i \le a_j$$$, thus it is optimal to have $$$a_i \le a_j$$$ for each $$$0 \le i < j < n$$$.
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)
solution$$$1 \space \space 1$$$
$$$0$$$
$$$1 \space \space 1$$$
$$$0$$$
$$$1 \space \space 1$$$
$$$-a_1$$$
solution$$$1 \space \space 1$$$
$$$-a_1$$$
$$$1 \space \space n$$$
$$$0 \space \space -n \cdot a_2 \space \space -n \cdot a_3 \dots -n \cdot a_n$$$
$$$2 \space \space n$$$
$$$(n-1) \cdot a_2 \space \space (n-1) \cdot a_3 \space \space \dots \space \space (n-1) \cdot a_n$$$
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 $$$a_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;
}