Thank you all for participating in the round.
All the problems were created by BiNARyBeastt during our classes in winter.
If the the numbers of vowels are fixed, how to arrange them to get the best possible answer?
How to choose the numbers of vowels? Should they be as close, as possible?
Let's define the numbers of vowels by $$$a_0, \cdots, a_4$$$ and assume we have fixed them. Obviously, $$$a_0 + \cdots + a_4 = n$$$.
At first, let's not consider the empty string as it doesn't change anything. Then, the number of palindrome subsequences will be at least $$$A = 2^{a_0} + \cdots + 2^{a_4} - 5$$$ (every subsequence consisting of the same letter minus the five empty strings). Now, notice that if we put the same characters consecutively then the answer would be exactly $$$A$$$, and that would be the best possible answer for that fixed numbers (there cannot be other palindrome subsequences because if the first and last characters are the same, then all the middle part will be the same as well).
Now, we need to find the best array $$$a$$$. To do this, let's assume there are 2 mumbers $$$x$$$ and $$$y$$$ in the array such that $$$x + 2 \leq y$$$. Then, $$$2^x + 2^y > 2 \cdot 2^{y-1} \geq 2^{x+1} + 2^{y-1}$$$. This means, that replacing $$$x$$$ and $$$y$$$ with $$$x+1$$$ and $$$y-1$$$ will not change the sum of the array $$$a$$$ but will make the number of palindrome subsequences smaller. We can do this replacing process until no two numbers in $$$a$$$ have difference bigger than $$$1$$$. Actually, there is only one such array (not considering its permutations) and it contains only $$$(n / 5)$$$-s and $$$((n / 5) + 1)$$$-s.
#include <bits/stdc++.h>
using namespace std;
const string VOWELS = "aeiou";
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t; // test cases
while (t--) {
int n; cin >> n; // string length
vector<int> v(5, n / 5); // n - (n % 5) numbers should be (n / 5)
for (int i = 0; i < n % 5; i++) v[i]++; // and the others should be (n / 5) + 1
for (int i = 0; i < 5; i++) for (int j = 0; j < v[i]; j++) cout << VOWELS[i]; // output VOWELS[i] v[i] times
cout << "\n";
}
}
B1 — The Strict Teacher (Easy Version), B2 — The Strict Teacher (Hard Version)
There are only few cases. Try finding them and handling separately.
For the easy version, there are three cases and they can be considered separately.
Case 1: David is in the left of both teachers. In this case, it is obvious that he needs to go as far left as possible, which is cell $$$1$$$. Then, the time needed to catch David will be $$$b_1-1$$$.
Case 2: David is in the right of both teachers. In this case, similarly, David needs to go as far right as possible, which is cell $$$n$$$. Then, the time needed to catch David will be $$$n-b_2$$$.
Case 3: David is between the two teachers. In this case, David needs to stay in the middle (if there are two middle cells, it doesn't matter which one is picked as the middle) of two teachers, so they both have to come closer to him simultaneously. So, they will need the same amount of time, which will be $$$(b_2-b_1) / 2$$$. Notice, that David can always go to the middle cell not depending on his cell number.
What changes in Case 3 if there are more than two teachers?
For this version, there are three cases, too. Case 1 and Case 2 from the above solution are still correct, but the last one should be changed a bit because now it is important between which two consecutive teachers David is. To find that teachers, we can use binary search (after sorting $$$b$$$, of course). After finding that David is between teachers $$$i$$$ and $$$i+1$$$, the answer is $$$(b_{i+1}-b_i) / 2$$$, just like the easy version.
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t; // test cases
while (t--) {
int n, m, q; cin >> n >> m >> q;
vector<int> a(m);
for (int i = 0; i < m; i++) cin >> a[i];
sort(a.begin(), a.end());
for (int i = 1; i <= q; i++) {
int b; cin >> b;
int k = upper_bound(a.begin(), a.end(), b) - a.begin(); // finding the first teacher at right
if (k == 0) cout << a[0] - 1 << ' '; // case 1
else if (k == m) cout << n - a[m - 1] << ' '; // case 2
else cout << (a[k] - a[k - 1]) / 2 << ' '; // case 3
}
cout << "\n";
}
}
A greedy approach doesn’t work because the end of one string can connect to the beginning of the next. Try thinking in terms of dynamic programming.
Before processing the next string, we only need to know which letter we reached from the previous selections.
Let's loop through the $$$n$$$ strings and define $$$dp_i$$$ as the maximal answer if we are currently looking for the $$$i$$$-th letter in the word "Narek". Initially, $$$dp_0 = 0$$$, and $$$dp_1 = \cdots = dp_4 = -\infty$$$. For the current string, we brute force on all five letters we could have previously ended on. Let’s say the current letter is the $$$j$$$-th, where $$$0 \leq j < 5$$$. If $$$dp_j$$$ is not $$$-\infty$$$, we can replicate the process of choosing this string for our subset and count the score difference (the answer). Eventually, we will reach to some $$$k$$$-th letter in the word "Narek". If reaching $$$dp_k$$$ from $$$dp_j$$$ is bigger than the previous value of $$$dp_k$$$, we update $$$dp_k$$$ by $$$dp_j + counted\texttt{_}score$$$.
Finally, the answer is $$$dp_i - 2 \cdot i$$$. This is because if $$$i$$$ is not $$$0$$$, then we didn’t fully complete the entire word (the problem states that in this case, these letters are counted in the GPT’s score, so we subtract this from our score and add it to the GPT’s).
Note: Updating the array $$$dp$$$ is incorrect, because we may update some $$$dp_i$$$ for some string, and then use that updated $$$dp_i$$$ for that same string. To avoid this, we can use two arrays and overwrite one to the other for each string.
Time complexity: $$$O(n*m*5)$$$ or $$$O(n*m*25)$$$, depending on the implementation.
#include <bits/stdc++.h>
using namespace std;
const string narek = "narek";
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t; // test cases
while (t--) {
int n, m; cin >> n >> m;
vector<string> s(n);
for (int i = 0; i < n; i++) cin >> s[i];
vector<int> dp(5, int(-1e9)), ndp;
dp[0] = 0;
for (int i = 0; i < n; i++) {
ndp = dp; // overwriting dp
for (int j = 0; j < 5; j++) {
if (dp[j] == int(-1e9)) continue;
int counted_score = 0, next = j;
for (int k = 0; k < m; k++) {
int ind = narek.find(s[i][k]);
if (ind == -1) continue; // if s[i][k] is not a letter of "narek"
if (next == ind) { // if s[i][k] is the next letter
next = (next + 1) % 5;
counted_score++;
}
else counted_score--;
}
ndp[next] = max(ndp[next], dp[j] + counted_score);
}
dp = ndp; // overwriting dp back
}
int ans = 0;
for (int i = 0; i < 5; i++) ans = max(ans, dp[i] - 2 * i); // checking all letters
cout << ans << "\n";
}
}
Find the the maximal sum of $$$\gcd$$$-s first.
Try checking whether it is possible to get some fixed $$$\gcd$$$-s for $$$a$$$ and $$$b$$$ (i.e. fix the $$$\gcd$$$-s and try finding a sufficient range to swap)
Choosing a range is equivalent to choosing a prefix and a suffix. Which prefixes and suffixes are needed to be checked to find the maximal sum of $$$\gcd$$$-s?
There are only few different values in the $$$\gcd$$$-s of prefixes and suffixes. Try finding a limit for them.
After finding the maximal sum of $$$\gcd$$$-s, try dynamic programming to find the nubmer of ways.
Let $$$M$$$ be the maximal value of $$$a$$$.
Finding the maximal sum of $$$\gcd$$$-s.
Let's define $$$p_i$$$ and $$$q_i$$$ as the $$$\gcd$$$-s of the $$$i$$$-th prefixes of $$$a$$$ and $$$b$$$, respectively. Then, for each index $$$i$$$, such that $$$1 < i \leq n$$$, $$$p_i$$$ is a divisor of $$$p_{i-1}$$$, so either $$$p_i=p_{i-1}$$$ or $$$p_i \leq p_{i-1} / 2$$$ (the same holds for $$$q$$$). This means, that there are at most $$$\log(M)$$$ different values in each of $$$p$$$ and $$$q$$$. The same holds for suffixes.
Now, let's assume we have fixed the $$$\gcd$$$-s of $$$a$$$ and $$$b$$$ after the operation as $$$A$$$ and $$$B$$$. Now, let's consider the shortest of the longest prefixes of $$$a$$$ and $$$b$$$ having $$$\gcd$$$ $$$A$$$ and $$$B$$$, respectively. If the swapped range has intersection with that prefix, we can just not swap the intersection as it cannot worsen the answer. The same holds for the suffix. This means, that the swapped range should be inside the middle part left between that prefix and suffix. But the first and last elements of the middle part have to be changed, because they didn't allow us to take longer prefix or suffix. So, the part that has to be swapped is that middle part.
Then, we can see that the only sufficient lengths of the longest prefixes and suffixes are the places where one of them (i.e. in array $$$a$$$ or $$$b$$$) changes (i.e. $$$i$$$ is a sufficient prefix if $$$p_i \neq p_{i+1}$$$ or $$$q_i \neq q_{i+1}$$$, because otherwise we would have taken longer prefix). So, we can brute force through the sufficient prefixes and suffixes (the number of each is at most $$$\log(M)$$$). All we are left with is calculating the $$$\gcd$$$-s of the middle parts to update the answer, which can be done with sparse table. Now, let's brute force through the sufficient prefixes. Assume we are considering the prefix ending at $$$i$$$. This means the left border of the range will start at $$$i+1$$$. Then, we can brute force the right border starting from $$$i+1$$$. In each iteration, we keep $$$\gcd$$$-s of the range and update the answer. To proceed to the next one, we only need to update the $$$\gcd$$$-s with the next numbers of $$$a$$$ and $$$b$$$.
Finding the number of ways.
Let's fix the $$$\gcd$$$-s of $$$a$$$ and $$$b$$$ and compute $$$dp_{i,j}$$$ ($$$1 \leq i \leq n$$$ and $$$0 \leq j < 3$$$), which shows:
the number of ways to get the fixed $$$\gcd$$$-s in the interval $$$[1, i]$$$ without swapping a range, if $$$j=0$$$
the number of ways to get the fixed $$$\gcd$$$-s in the interval $$$[1, i]$$$ with a range started swapping but not ended yet, if $$$j=1$$$
the number of ways to get the fixed $$$\gcd$$$-s in the interval $$$[1, i]$$$ with an already swapped range, if $$$j=2$$$
In all $$$dp$$$-s we assume we don't swap $$$a_1$$$ and $$$b_1$$$
Then, we calculate the $$$dp$$$ with $$$i$$$ starting from $$$1$$$. In each iteration, we check if the pair $$$(a_i, b_i)$$$ is sufficient, or no (we consider them swapped, if $$$j=1$$$). If it is not sufficient, we don't do anything. Otherwise:
$$$dp_{i,0} = dp_{i-1,0}$$$
$$$dp_{i,1} = dp_{i-1,0}+dp_{i-1,1}$$$
$$$dp_{i,2} = dp_{i-1,0}+dp_{i-1,1}+dp_{i-1,2}$$$
After the calculations the answer is $$$dp_{n,0}+dp_{n,1}+dp_{n,2}$$$. But we have to subtract $$$n$$$ from the answer if not swapping any range gives the expected sum of $$$\gcd$$$-s, because we counted that case once in $$$dp_{n, 0}$$$ and $$$n-1$$$ times when adding $$$dp_{i-1,0}$$$ to $$$dp_{i,2}$$$. We also check the swaps of prefixes separately.
Finally, the only thing left is to brute force through the $$$\gcd$$$-s of $$$a$$$ and $$$b$$$ in a smart way. As $$$a_1$$$ and $$$b_1$$$ are not swapped, the $$$\gcd$$$-s of the arrays should be their divisors. Then, it is enough to brute force through the divisors of $$$a_1$$$ only (the $$$\gcd$$$ of $$$a$$$), as the other $$$\gcd$$$ is derieved from their sum. And since $$$a_1$$$ has at most $$$\sqrt[3]{a_i}$$$ ($$$1344$$$, to be precise) divisors, the solution will be fast enough (actually, there are way too less cases when the derieved $$$\gcd$$$ of $$$b$$$ is actually a divisor of $$$b_1$$$).
Finalizing.
But this solution is not fast enough when all $$$a_1$$$-s are $$$10^9$$$, because they have $$$\sqrt[3]{a_1}$$$ divisors, but in order to find them, we need to do $$$\sqrt{a_1}$$$ checks. It means, that the time complexity is $$$O(t * \sqrt{a_1})$$$, which is slow. To handle this, we can write another slower solution which doesn't depend on $$$a_1$$$. One of them is the following solution working in $$$O(n^2* \log(M))$$$, but $$$\log(M)$$$ comes from $$$\gcd$$$, which is actually amortized and faster.
We brute force through the left border, and then through the right border of the swapping range, keeping its $$$\gcd$$$ and checking each of them.
The reason we need this slow solution is that now, we can use it for $$$n\leq20$$$. But for bigger $$$n$$$-s, the first solution will work, because there are at most $$$t/20$$$ such $$$n$$$-s. So the time complexity for them will be $$$O(n*\log^2(M))$$$ for the sum of the $$$\gcd$$$-s and $$$O(t/20*\sqrt{M} + \sqrt[3]{M} * n)$$$ for the number of ways.
For the small $$$n$$$-s, the time complexity will be $$$O(n*\log(M)*20)$$$. See the formal proof below.
Let's say there are $$$c_i$$$ $$$n$$$-s equal to $$$i$$$. We know, that $$$\displaystyle\sum_{i=1}^{20} (c_i\cdot i) \leq n$$$. Then the time complexity will be $$$O(\displaystyle\sum_{i=1}^{20} (c_i\cdot i^2* \log(M))) \leq O((\displaystyle\sum_{i=1}^{20} (c_i\cdot i))*\log(M)*20) \leq O(n*\log(M)*20)$$$.
Time complexity: $$$O(n*\log^2(M) + t/20*\sqrt{M} + \sqrt[3]{M} * n + n*\log(M)*20) \approx O(10^9)$$$. It is actually a very rough estimation with amortized $$$\log(M)$$$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int a[N], b[N];
int pa[N], pb[N], sa[N], sb[N];
int n;
ll dp[N][3];
ll solve_one(ll ga, ll gb)
{
if (ga <= 0 || gb <= 0) return 0; // invalid fixed gcd(s)
if (b[1] % gb) return 0; // ivanlid gcd of b
for (int i = 0; i <= n; i++) for (int j = 0; j < 3; j++) dp[i][j] = 0; // intializing
dp[1][0] = 1; // base case
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k <= j; k++) {
bool flag = 1;
if (j == 1) swap(a[i], b[i]); // if swapping
if (a[i] % ga) flag = 0; // checking sufficiency
if (b[i] % gb) flag = 0; // checking sufficiency
if (j == 1) swap(a[i], b[i]); // if swapping
if (flag) dp[i][j] += dp[i - 1][k];
/*
if j is 0, we can use only k=0 (not started swapping yet)
if j is 1, we can use both k=0 (starging swapping) and k=1 (currently swapping)
if j is 2, we can use k=0 (no swaps at all), k=1 (finishing swapping), k=2 (already finished swapping)
*/
}
}
}
return dp[n][0] + dp[n][1] + dp[n][2];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t; // test cases
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
sa[n + 1] = sb[n + 1] = 0; // initializing
for (int i = 1; i <= n; i++) { // calculating the gcd-s of prefixes and suffixes of a and b
pa[i] = gcd(pa[i - 1], a[i]);
pb[i] = gcd(pb[i - 1], b[i]);
sa[n - i + 1] = gcd(sa[n - i + 2], a[n - i + 1]);
sb[n - i + 1] = gcd(sb[n - i + 2], b[n - i + 1]);
}
if (n <= 20) { // slower solution
int max_gcd = 0, ways = 0;
for (int i = 1; i <= n; i++) {
int ga = 0, gb = 0; // current gcd-s of the range
for (int j = i; j <= n; j++)
{
ga = gcd(ga, a[j]);
gb = gcd(gb, b[j]);
int ca = gcd(pa[i - 1], gcd(sa[j + 1], gb)); // gcd of a after the operation
int cb = gcd(pb[i - 1], gcd(sb[j + 1], ga)); // gcd of b after the operation
if (ca + cb > max_gcd) {
max_gcd = ca + cb;
ways = 1;
}
else if (ca + cb == max_gcd) ways++;
}
}
cout << max_gcd << ' ' << ways << "\n";
continue;
}
int max_gcd = pa[n] + pb[n];
for (int i = 2; i <= n; i++) {
if (pa[i] == pa[i - 1] && pb[i] == pb[i - 1]) continue; // checking sufficiency of the prefix
int ga = 0, gb = 0; // current gcd-s of the range
for (int j = i; j <= n; j++) {
ga = gcd(ga, a[j]); // updating gcd of the range of a
gb = gcd(gb, b[j]); // updating gcd of the range of b
int ca = gcd(pa[i - 1], gcd(sa[j + 1], gb)); // gcd of a after the operation
int cb = gcd(pb[i - 1], gcd(sb[j + 1], ga)); // gcd of b after the operation
max_gcd = max(max_gcd, ca + cb); // updating the answer
}
}
ll ans = 0;
for (int ga = 1; ga * ga <= a[1]; ga++) {
if (a[1] % ga) continue;
ans += solve_one(ga, max_gcd - ga); // counting for fixed gcd-s
if (ga * ga == a[1]) continue;
ans += solve_one(a[1] / ga, max_gcd - a[1] / ga); // counting for fixed gcd-s
}
if (pa[n] + pb[n] == max_gcd) ans -= n; // n-1 times updated with j=2 and k=0 and one time with no swaps at all (dp[n][0])
for (int i = 1; i <= n; i++) {
if (gcd(pa[i], sb[i + 1]) + gcd(pb[i], sa[i + 1]) == max_gcd) ans++; // checking prefixes
}
cout << max_gcd << ' ' << ans << "\n";
}
return 0;
}
E1 — Subtangle Game (Easy Version), E2 — Subtangle Game (Hard Version)
What happens, when some number accurs more than once in $$$a$$$?
How to use the constraint on the numbers of the array and the matrix?
Let's say some number $$$x$$$ accures in $$$a$$$ more than once. Let's define by $$$u$$$ and $$$v$$$ the first two indexes of $$$a$$$, such that $$$u<v$$$ and $$$a_u=a_v=x$$$. When a player reahces $$$a_u = x$$$, it is always optimal to choose such cell that after it no $$$x$$$ can be choosen (there is no other $$$x$$$ in the remaining submatrix). This is true, because if the player would win when choosing that "inside" $$$x$$$ (let's call him $$$x_2$$$), he would also win in that bigger matrix. But if he would lose, that means there is some number inside the submatrix left from $$$x_2$$$ that is winning for the other player, so the latter can choose that not depending on the opponent's choose. So, when a player reaches $$$a_v$$$, he will lose, which is the same as the array $$$a$$$ ends there. This gives us the chance to "stop" array $$$a$$$ at the first index where some number appears the second time.
Now, as all the numbers are not greater than $$$7$$$, we can shorten array $$$a$$$ to at most $$$7$$$ elements. Then, we can keep $$$dp_{k,i,j}$$$ which shows whether the player, starting from $$$k$$$-th position of the array $$$a$$$ (i.e. considering only the suffix starting at $$$k$$$, but not necessarily Tsovak has to start), will win, or not. To calculate the $$$dp$$$, we can go from the bottom-right cell of the matrix to the upper-left cell. $$$dp_{k,i,j}$$$ wins, if at least ono of these happens:
$$$i<n$$$ and $$$dp_{k,i+1,j}$$$ wins
$$$j<m$$$ and $$$dp_{k,i,j+1}$$$ wins
$$$b_{i,j}=a_k$$$ and ($$$k=l$$$ or $$$i=n$$$ or $$$j=m$$$ or $$$dp_{k+1,i+1,j+1}$$$ loses)
Finally, if $$$dp_{1,1,1}$$$ wins, Tsovak wins, otherwise, Narek wins.
Time complexity: $$$O(n*m)$$$.
Consider the same $$$dp$$$ as in E1. What can we say about $$$dp_{k,i,j}$$$ and $$$dp_{k+2,i,j}$$$?
If $$$dp_{k,i,j}$$$ wins, then $$$dp_{k+2,i,j}$$$ also wins.
Keep $$$dp0_{i,j}$$$ which shows the smalles even $$$k$$$, such that $$$dp_{k,i,j}$$$ wins. Do the same for odd ones.
Define dp0[i][j] as the maximal even index in the array, such that if the game were to start from that index and the submatrix starting at (i, j) is considered the 1st player would have won. Similarly dp1[i][j] shows the same thing for the odd array indices. With hint 1, we know that each number appears once in the array. This means we can also find the array index $$$idx$$$ where the number at (i, j) appears. In order to count dp0[i][j] we find the minimal value of dp1-s inside the submatrix starting at (i+1, j+1). If it is smaller than or equal to i + 1 then our opponent wins. However, if it is bigger than or equal to i + 3, then they can't reply to us with a winning state by finding the next number in the array which is i + 1-th number. At the end, we can check if any of the dp0[i][j] values is equl to 0. If it is, the first player wins. Otherwise, the 2nd player wins.
