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";
}
}
D — Alter the GCD (Check this comment or the video editorial for an easier solution).
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 <= 300) { // 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 appears in $$$a$$$ more than once?
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. Can you eliminate one of the states?
Instead of $$$dp_{k,i,j}$$$, eliminate $$$k$$$ from the state. Instead, assign some array index to the $$$dp$$$ value to keep information about the array.
Keep $$$dp0_{i,j}$$$ which shows the smalles even $$$k$$$, such that $$$dp_{k,i,j}$$$ wins. Do the same for odd ones.
Let's define $$$dp0_{i,j}$$$ as the minimal even index $$$k$$$ ($$$1 \le k \le l$$$), such that $$$dp_{k,i,j}$$$ wins. Define $$$dp1_{i,j}$$$ similarly for odds. First, fill all of them with $$$\infty$$$. Then, compute them from the bottom-right cell of the matrix to the top-left cell of the matrix. $$$dp0_{i,j}$$$ will be the minimal of the following three values:
$$$dp0_{i+1, j}$$$ (if $$$i=n$$$ there will be no submatrix left, so $$$dp0_{i+1,j}$$$ will be $$$\infty$$$)
$$$dp0_{i,j+1}$$$
Let's define by $$$ind$$$ the index of $$$b_{i,j}$$$ in $$$a$$$ (there are no duplicates in $$$a$$$ and if there is no $$$b_{i,j}$$$ there, assign $$$\infty$$$ to $$$ind$$$). If $$$dp1_{i+1,j+1}>ind+1$$$, which means that $$$dp_{ind+1,i+1,j+1}$$$ loses and ensues the current player's win, then the value of this part will be $$$ind$$$. Otherwise, $$$\infty$$$. This is because, in other cases, the opponent either had a winning position starting from $$$ind+1$$$ or even earlier in the game, so we can't win from that index.
We count $$$dp1$$$ similarly (but we count $$$dp0$$$ and $$$dp1$$$ simultaneously for every $$$(i,j)$$$).
Lastly, if $$$dp1_{1,1}=1$$$, then Tsovak wins, otherwise, Narek wins.
#include <bits/stdc++.h>
using namespace std;
const int L = 305, N = 305, M = 305;
int a[L], b[N][M];
int l, n, m;
int ind[8];
bool dp[8][N][M];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t; // test cases
while (t--) {
int i, j, k;
cin >> l >> n >> m;
for (i = 1; i <= l; i++) cin >> a[i];
for (i = 1; i <= l; i++) {
if (ind[a[i]]) { // checking if a[i] has already appeared
l = i - 1;
break;
}
ind[a[i]] = i; // keeping index of each number
}
for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) cin >> b[i][j];
for (i = n; i >= 1; i--) {
for (j = m; j >= 1; j--) {
for (k = 1; k <= l; k++) {
if (i < n && dp[k][i + 1][j]) { // if a smaller submatrix wins
dp[k][i][j] = 1;
continue;
}
if (j < m && dp[k][i][j + 1]) { // if a smaller submatrix wins
dp[k][i][j] = 1;
continue;
}
if (b[i][j] == a[k]) { // if we can take the number (i,j)
if (k == l) dp[k][i][j] = 1;
else if (i < n && j < m) dp[k][i][j] = !dp[k + 1][i + 1][j + 1];
else dp[k][i][j] = 1;
}
else dp[k][i][j] = 0;
}
}
}
if (dp[1][1][1]) cout << "T\n";
else cout << "N\n";
for (i = 1; i <= l; i++) ind[a[i]] = 0; // changing used ind[i]-s back to 0-s for the next test case
}
}
#include <bits/stdc++.h>
using namespace std;
const int L = 1505, N = 1505, M = 1505;
int a[L], b[N][M];
int l, n, m;
int ind[N * M];
int dp0[N][M], dp1[N][M];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t; // test cases
while (t--) {
int i, j;
cin >> l >> n >> m;
for (i = 1; i <= l; i++) cin >> a[i];
for (i = 1; i <= l; i++) {
if (ind[a[i]]) { // checking if a[i] has already appeared
l = i - 1;
break;
}
ind[a[i]] = i;
}
for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) cin >> b[i][j];
for (i = 0; i <= n + 1; i++) for (j = 0; j <= m + 1; j++) dp0[i][j] = dp1[i][j] = int(1e9); // initializing dp0 and dp1
for (i = n; i >= 1; i--) {
for (j = m; j >= 1; j--) {
dp0[i][j] = min(dp0[i + 1][j], dp0[i][j + 1]); // default update
dp1[i][j] = min(dp1[i + 1][j], dp1[i][j + 1]); // default update
if (!ind[b[i][j]]) continue; // if there is no b[i][j] in a then it cannot be taken by a player
if (ind[b[i][j]] % 2 == 0 && ind[b[i][j]] + 3 <= dp1[i + 1][j + 1]) dp0[i][j] = min(dp0[i][j], ind[b[i][j]]); // if dp1 cannot win after dp0 choosing b[i][j]
if (ind[b[i][j]] % 2 == 1 && ind[b[i][j]] + 3 <= dp0[i + 1][j + 1]) dp1[i][j] = min(dp1[i][j], ind[b[i][j]]); // if dp0 cannot win after dp1 choosing b[i][j]
}
}
if (dp1[1][1] == 1) cout << "T\n";
else cout << "N\n";
for (i = 1; i <= l; i++) ind[a[i]] = 0; // changing used ind[i]-s back to 0-s for the next test case
}
}
We trained Tsovak to post this faster than the speed of light, but we failed miserably due to the AI situation.
We actually leart about that super-smart AI two days ago and it appeared to be able to solve the problems A to D, and almost E1, so we had to change D within less than 24 hours)
damn, thank you for the dedication
It actually solved E1 https://codeforces.net/contest/2005/submission/281146546
That is most likely because the person doing the prompts did a really good job with smart prompts. Many of us tried the new paid version a few times, and it didn't manage to get past test 6.
He claims no special prompt here: https://codeforces.net/blog/entry/133962
Then maybe we got unlucky. For example, when I was checking for D, it managed to solve it the first two times I asked. Later, I copied the statement and sent it again, but it gave a wrong answer. I guess its results are not consistent all the time.
I'm not sure how it works to be honest, so I'm still not sure if this is the reason.
I have an idea, maybe we don't need to be afraid of AI, if people can use AI to solve problems, we can also use AI to generate problem sets that can confuse itself. But to do that, maybe we need knowledge and experience in both CP and writing prompts.
can you fool yourself ?
then what is the point of my life ? ToT
281181064 Can somebody tell me why this is giving WA? Suppose array is 2 3 4 5 , and teachers are at 2 5 , the possible values for mid can be both 3 and 4 . I simply calculated the min value for both the possible mid values from each of the teachers. If the array was something like 2 3 4 , then there was only 1 mid (ie 3) hence no issue.
281191926 This passes , wherein I am taking only the (min_max)/2 value, ie 3 for array 2 3 4 5.
The thing is, when teachers travel a distance of
min(x - b[0], b[1] - x), then x can choose to remain at its current place. After this, you can directly calculate the mid point of the new locations of the teachers, because x would try to go towards the teacher, which is farther from it."you can directly calculate the mid point of the new locations of the teachers"
The midpoint and the distance from the teachers will same regardless, wont it?
2 3 4 5 if I take 3 as mid, 3-2=1, 5-3=2. min=1; if I take 4 as mid, 4-2-2, 5-4=1. min=1;
Since the teachers will always be moving towards the middle, the mid value will remain the same every time right?
You can say that with this insight, I could just find the answer for mid=(max+min)/2 and it would satisfy the answer, but at the same time finding min distance from both and then printing the minimum shouldn't result in WA.
Apologies if I missed something.
Yes. You're right. Mid point doesn't change. But the mid point you are talking about, is the array mid point, and not the actual mid point. The actual mid point of two teachers would be
(b[0] + b[1]) / 2, and NOT the middle element of the subarray from b[0] to b[1]. Hence, for array[2, 3, 4 ,5], the mid point of the array is (5 + 2) / 2 = 4, and not b[4/2] or b[4/2-1]. Hence, the number of steps required would be(b[0] + b[1]) / 2 - b[0], which is nothing but(b[1] - b[0]) / 2.Thankyou for your time. The code got accepted, I missed putting the condition in brackets. So demotivating.
for B, i didnt see that he can choose not to move, and i coded the completely wrong solution for 20 mins, tragic. great problem C, i absolutely loved it.
can someone help me why this code gets wrong answer for problem C
submission: https://codeforces.net/contest/2005/submission/281243184
I think your algorithm is n^2 which is too slow, regardless of correctness.
how to train for problems like C?
I think that the best way is to solve lots of DP problems. I suggest the DP section of USACO guide.
solve knapsack dp problems, usaco guide is great
$$$\mathcal O(n * m * 7)$$$
You shouldn't write the constant $$$7$$$ in the time complexity lol.
How did you go from having 6k rank to 476 and then 11?
Can someone explain how did I get TLE in C? I thought my code works in $$$O(N * M * 25)$$$: 281197818
It is $$$O(nm + n^2)$$$, no?
I made the same mistake as you. Your actual complexity is $$$O(25NM + 25N^2)$$$ due to the for loop calculating
dp, and there's no upper bound on the sum of $$$N^2$$$ across all test cases, only upper bound on $$$NM$$$ :sob:Oh, it makes sense thanks :sob:
The contest is amazing!
my only complaint is the protests on problem C could have been better ):
I was going to become a CM for the first time If there were stronger protests.
Thank you for the contest as usual!
281249215 can anyone explain why this code getting wa on pt 11 problem c ! i dont think there is an wrong idea !
for problem A
Expected output : aaeiou , palindromes subsequences a , a , e , i , o , u , aa
My output : aeioua , a , e , i , o , u , a , aa
Why my output is considered as wrong answer , can anyone explain?
For the string aeioua, other palindrome subsequences include aea, aia, aoa, and aua.
My bad , Thankyou
You missed palindromes like aea , aia , aoa , aua
I got TLE at C problem and I think it works in (5 * n * m)
solution
am I missing something ?
How ? I wrote a function that works in (m) and I loop only once over n
you just need a little bit of optimization. using vector to replace map is ok. see this submission : 281260161
OMG...just the map that works over only 5 chars have 1.5 second difference !
thanks for the accepted code it was annoying me
lol, so fast
... thanks :D
Anyone else lost question C by initializing dp to -1 instead of -inf? :(
Nice round.
thanks for the fast editorial!
in the problem $$$B1/B2$$$, C++ upper_bound and lower_bound both should point to element strictly $$$>a[i]$$$ (david's position) since $$$b[i]$$$ only contains teacher's positions. or is it not so? my contest submission using both lower_bound and upper_bound got WA.
my contest submission
You didn't sort
thank you!
You
return;in yoursolvefunction, and you only output one answer with two queries.Bitset helps to solve E2 without any observation. 281264340
Why is my submission for C getting TLE on test 11? I think the complexity is $$$O(5*N*M+10*N)$$$.
Submission: 281248462
You're initializing your dp with -1, so if the answer at a certain state was -1 it will call the solve() function again instead of returning the previously calculated answer (which is -1). Instead you can initialize with -INF or create another array to check for visited states.
Thanks, that was an overlook.
Although, I realized I linked the wrong submission earlier. Updated the submission link.
For problem E1, can someone help me understand why Narek wins in this testcase :
This is my submission which is failing for this test : [submission:https://codeforces.net/contest/2005/submission/281255124]
Move $$$1$$$. Tsovak takes $$$(1, 1)$$$.
Move $$$2$$$. Narek takes $$$(2, 2)$$$.
Move $$$3$$$. Tsovak takes $$$(3, 3)$$$.
Move $$$4$$$. Narek takes $$$(4, 4)$$$.
Move $$$5$$$. Tsovak takes $$$(5, 5)$$$.
Move $$$6$$$. Narek takes $$$(6, 6)$$$.
Move $$$7$$$. Tsovak loses since the array ended. Narek wins.
Oh, I seem to have misunderstood the problem. I thought that they can only choose elements from the array A. Since the array A has only the element 6, how can Tsovak pick (1, 1) or (2, 1)?
Nvm, I read the test case wrong.
I've updated the testcase correctly. Can you look and tell me now why Narek wins?
Edited my comment since it would be misleading for the readers otherwise.
funny how in problem C "problem tags" there is greedy and the first thing editorial says is that greedy approach doesn't work.
It is my bad for not properly stating what I meant by greedy in the hint section. The tag is relating to the fact that you can greedily count the score when you choose one string. I meant that you can't do greedy on each string without considering their connection with each other by dp.
can you please share some tests for C, cant debug it :(
I solved E1 in O(n*m*l) time complexity. Can anyone uphack this solution?
I think this is the intended complexity for E1
anyone know why it can pass O(nml) even when you iterate the full 300^3?
I fail to understand why they have given the upper limit of the numbers as 7. I never used that fact in my O(n*m*l) dp
This is only required in E2. For E1, a solution with O(n * m * l) should pass
But in E2 they have not mentioned the upper limit to be 7
That is to help you make an important observation for E2. If you check all the hints, you can see what I mean.
why make O(nml) passable when the intended for E1 is O(nm) based on the 7 observation?
To kind of help people make that observation for E2. Also, we were not allowing O(nml) pass initially. The difference between E1 and E2 used to be only between the matrix numbers. Testers struggled to find this observation though, so we changed it.
what is wrong in my recursive dp soltuion 281269592 please help me to debug, tried for so long but not able to find
I made some changes to it and now it passes. I know this part was a problem:
because I made the same mistake during the contest. It should be (-2) * the current "narek" index, which in your code is
last. 281276687Thanks really helpful
the reason for wrong answer is
Tsovak BiNARyBeastt Kaey TheScrasse
I tried uphacking my solution 281180437 for problem D, and it got an unexpected verdict.
I believe one of the correct marked solutions on polygon also gets TLE on this hack test case.
Can you please take a look at it and fix it?
We were aware of this, and we also know a solution that won’t exceed the time limit. We are currently working on updating the editorial and the main solution accordingly. TheScrasse coded the solution to D just minutes before the start. We took a risk by making the problem harder, asking for the number of ways to get the maximum GCD, so that AI wouldn’t be able to solve it. Thanks for noticing this though!
I solved E1(2100 rating on clist) but was not able to submit it because of internet connetion problem.
can someone help me with why we cant solve problem c with take not take dp?
Why can't?
please can u explain take not takw dp solution for this problem
I tried top down approach for C, but am getting WA on test 2, can somebody tell me what's wrong? 281270159
I found the bug, got it now. 281277888
https://codeforces.net/contest/2005/submission/281282507
Why this solution is accepted after sorting and not without it
Because sorting it puts all the
a's together, all thee's together, all thei's together and so on. It doesn't have to be sorted but the occurrences of every vowel need to be grouped together. And sorting is one way to do that. This is an example of a string that's not sorted but still works:eeeoooiiiaauuBecause for example n = 6 Then without sorting it would print: uoieau It also contains the following palindromic subsequences: uou, uiu, etc Whereas after sorting it prints: aeiouu, which doesn't contain these subsequences Basically you were missing the core logic
My submission for C can someone please help me figure out why this solution TLE'd? This seems to be O(5*m*n) :(
well your solution looks exactly same as mine and even i got TLE on pretest 11 during contest so i am assuming we did same mistake, the thing is you have intialised your dp array with -1. during calculation of dp[i][j], some of the states answers can be negetive when gpt gets better score, and there is some case where your dp[i][j] is getting calculated as -1 itself. and hence your just going on in that cycle where your dp[i][j] is always -1. i just replaced -1 with -1e18 and it worked.
Ahh yes! An oversight from my side as well:( Thanks a lot!
About C：Since you want $$$O(n^2)$$$ algorithm got a TLE, why don't put the data in pretest? $$$n \le 10^3$$$ is very deceptive!
Sorry! We overlooked that there might be a solution with that complexity. Unfortunatly, none of the testers came up with anything like that as well.
I have no idea why "if $$$dp_{k,i,j}$$$ wins, then $$$dp_{k + 2, i, j}$$$ also wins".
In fact, I add an assertion in my code, and it received RE(assertion failed) on E1, test 2.
The submission is here: 281298383
Here is (probably) the hack:
Note that $$$dp_{1,1,2}$$$ is $$$1$$$, while $$$dp_{3,1,2}$$$ is $$$0$$$.
/bx
In your example, regardless of the value of k, i, or j, the starting player can always start with the last 6 (the one at (n, m)), and the subrectangle starting at (n+1, m+1) will be empty. According to the rules, this means the second player loses. So actually all dp values are 1 in that case.
You are right though. I think it's not correctly written there.
We fixed the editorial. The solution was still correct. We just had a wrong hint there for some reason.
rare c d e dp contest
/
Why in problem C, I let define int long long in my compiler output 0 5 0 7 (correct result of test 1) but in my submission it is 0 5 0 6. After deleting define int long long then it has AC.
My submission
A (probably) more simple solution to D.
We will also make use of the fact that there are only $$$O\left(\log(\max(a))\right)$$$ different prefix gcd, but we will use it on all subsegments instead:
To find the ranges for $$$(r, n]$$$, we can simply iterate the arrays in reverse and maintain the gcd ranges, leading to $$$O(n\log(\max(a)))$$$.
To find the ranges for $$$[l, r]$$$, build a sparse table with gcd, and keep expanding the divisible ranges to find the points where the continuous gcd changes. This will take $$$O(n\log(n)\log(\max(a)))$$$ to build and $$$O(\log(n)\log(\max(a)))$$$ to find the ranges for each $$$l$$$.
You can see my implementation in contest: 281217872
This solution have since been uphacked by 415411. The test seems to put the algorithm in the worst case and that was slower than model.
Thanks to the hack, I was able to improve upon the algorithm:
The above actually improve the algorithm to $$$O(n\log(max(a))$$$, except for the calculating answer part:
Applying the same idea as above to the ranges we have:
Finally we have to calculate the answer once we have all the ranges. I can't seem to find a way to improve this to $$$O(n\log(\max(a))$$$, so it's still $$$O(\log(\max(a))^2)$$$
You can see my new code: 281316893. And the sanity check version where I reversed the array (so I don't take advantage of the fact that most interesting stuffs happen at the end of the hack array): 281316958
B2 — The Strict Teacher (Hard Version), Why did he find index through upperbound? Can't we do it by lowerbound? In upperbound case, the index-1 value teacher can be in same cell as studentright?
You can use lower_bound
here is my solution https://codeforces.net/contest/2005/submission/281167542
can anybody explain the recursive approach of E1
https://codeforces.net/contest/2005/submission/281279780 why this is getting tle? I think its complexity is
N*M*5
can somebody help me in figuring out why my E1 solution tles? i'm using minimax technique which uses 1 for the win of Tsokav and -1 otherwise. the time complexity is $$$ O(l * n * m) $$$ which is fine, no?
Submission
Can anyone tell me why I am getting a WA? I have reviewed my solution many times and I can't seem to find the problem.
https://codeforces.net/contest/2005/submission/281266413
Why are you sorting your q vector? You are supposed to answer the q queries in order Example: q = 5 2 Lets say answer for 5 is x and answer to 2 is y So expected output is: X Y
But you will output Y X
Due to sorting
Ohhhhhhhh now I get it, I was sorting because I thought the problem might be solved using two pointers, so I needed to sort both the m and q vectors, but I forgot that by this I would change the order of output. Also, Do you know why I am getting TLE in this solution https://codeforces.net/contest/2005/submission/281314216, while this one is fine https://codeforces.net/contest/2005/submission/281314471, the only difference is that I was using a set in the first one, but changed it to a vector and sort in the second one. Thanks in advance.
the TLE in sets is because the syntax for lowerbound and upperbound is a bit different for sets. doing set.lower_bound(set.begin(), set.end(), x) is actually O(n*logn), while that is O(logn) for vectors. for sets you do: set.lower_bound(x), this is O(logn) in case of sets
you can refer to this blog for more insights https://codeforces.net/blog/entry/55450
Thanks a lot :)
For B1, when david is between both the teachers. How about going towards the teacher1 till he finds he is safe and moving back towards teacher2 till he finds he is safe?
Giving WA. 281236022
problem E2
If $$$dp_{k,i,j}$$$ wins, then $$$dp_{k+2,i,j}$$$ also wins.
Why is that true ?
if the grid is
4 2
2 2
and the array is 4 1 3
$$$dp_{1,1,1}$$$ is winning but $$$dp_{3,1,1}$$$ isn't
You are correct! I think the solution is correct as well, but we just explained with a wrong hint there. we'll fix it very soon.
We fixed the editorial. The solution was still correct. We just had a wrong hint there for some reason.
Thanks a lot , for the problems , editorial and kindness
No problem. Thank you too for pointing this out.
why was there no pretest in C that crush solution O(n^2)
Sorry! We overlooked that there might be a solution with that complexity. Unfortunately, none of the testers came up with anything like that as well.
E1 can be solved with a complete search using minimax algorithm. It ac's with alpha-beta pruning
Submission
Also, does anyone know how to calculate time complexities of programs like this?
Fun Fact: I didn't read the constraints in C carefully and submitted O(n^2) dp solution. It passed pretests but sadly it failed system test. So happy.
why for problem A , for n=6 , aeioua is not a right answer ?
Because the string aaeiou only has 6 palindromes a,aa,e,i,o,u. The string aeioua has all those as aaeiou, but also has aea, aia,aoa,aua. So its a suboptimal answer
D can be solved in $$$O(nlog^2(maxA))$$$ with a simple divide-and-conquer formulation. In the merge step, we only consider the $$$log$$$ unique gcds of suffixes in left half and prefixes for right half and store counts in map. Then just brute force the maximum and update counts (taking care to add up counts if maximums are equal). 281328508
This should be official solution. Not only it's several times faster but also, its lot clearer and easier to implement, understand and it doesn't separate small and large testcases (🤢).
On first it looks like $$$O(nlog^3(maxA))$$$ but when you consider the fact that on lower levels of DnQ you have $$$min(log(maxA),len)$$$ elements in map with simple for loop you can calculate that for $$$n = 200000$$$ in total you have ~16.000.000 operations.
My code: 281365054 (tried to make it as crisp as possible)
How do we know the map's size will be $$$log(maxA)$$$ ? If there are $$$log(maxA)$$$ possibilities for each array, then the map of pair of int should be $$$log^2(maxA)$$$ right? (As there are that many combinations?)
As you scan in one direction, either the gcd of first array changes or gcd of second array changes. If we pick the positions where either one changes, you should have the union of these positions, which is $$$2 \cdot log$$$ positions.
This is actually a great way to solve the problem! We changed the problem from only asking for max gcd to asking the amount of ways to get it, so we had a very short time to code two solutions and compare them. With the help of the coordinator, we managed to code something. This is why our official solution is messy and weird. We didn't have enough time to find something good.
I added your comment and my updated video editorial in the blog to have something that's easier.
in merge step, why are you not considering gcd of suffix or prefix ?
I'm not sure what you mean.
Hi Newtech66 can you please write this again in detail, so that person of my level can also understand. means can you break down the solution in different parts. Thank you
Solve A B C E1. Nice dp contest!
can i know why i am getting a wrong answer on problem B1 281322308?
In case of l = 5, r = 3 (when l is maximum), you are losing the value of l. Maybe you want this: if(l > r) swap(l, r);
Submission
can anyone find out what is wrong with this solution for C problem using dp.
281345109
Can someone explain why this solution for problem C results with WA on test 11?
A actually has a much easier solution, you can just fill the string with equal amounts of vowels and then sort it. It's AC. It does essentially the same thing but fsr people took a long time figuring A out.
Why is my submission for D getting TLE on test40? I think my complexity is $$$O(nlog^2n)$$$. And on test37 it needs a long time (over 3000ms) running.
submission 281364038
can someone please help me figure out why I am getting runtime error.
Even tho i think i am not accessing anything out of bound. am I missing edge case where it could happen?
my submission : https://codeforces.net/contest/2005/submission/281249882
edit : didnt know CF shows which line error occured once contest is done. It is showing out of bound in prefix[i — 1] . But i will be always between 1 <= i <= n so not understanding why it will go out of bound
check out this test case
if prefix is of size n .what's its largest size .
"n" can reach 1e9 but the compiler can't create a vector of such size .
so you can't do
the test case you have mentioned is not within the constraints here ai is 100000 and n is 8 ai <= n is not true in the given case
sorry for that ,i changed it
Thanks a lot for your help. I was not aware of this fact. one more question what is the max size of vector i am allowed to create in contest?
i don't know but the largest i have ever created was 1e7
Hello mates Help, I am getting TLE in problem C[submission:281406037].Even though i have used the time complexity of O(n*m*25) <= 2.5*10^7..which should run as per my knowledge..Please look into this i want to know why am i getting TLE...
Why My code fails in test case 2 for problem C
link: https://codeforces.net/contest/2005/submission/281415696
also I found a testcase to which my code gives wrong answer which is
My Answer: 0
Correct Answer: 2
Got it!
For Problem C: Another way to do it which does not require thinking about $$$dp_i - 2 \cdot i$$$ is to modify the score: Add a $$$-1$$$ to each occurrence of the letters in
"narek"and add a $$$+10$$$ when you complete one instance of the full word"narek", in your $$$dp$$$.plz help me. I can't understand why this code is on time limit of B2. https://codeforces.net/contest/2005/submission/281483618 I've made a empty set and inserted. I know it is not faster than vector, but anyway, is the time complexity M*O(lgM)?
I didn't quite follow the editorial for E, but here's another way to look at it.
As usual for such problems, we can define winning states as those from which you cannot reach a losing state and likewise. Now, let's try to process the game starting from the last element, and at each point, what we want is to mark each cell on the board as a winning or losing position.
It actually turns out, that such a set can be easily marked by maintaining the set of "innermost" positions of numbers (those cells $$$(r,c)$$$, such that no other cell $$$(r',c')$$$ exists with the same value such that $$$r'>r$$$ and $$$c'>c$$$). Note that this set has size $$$O(n+m)$$$.
As we process, we need to update a set of "dominant" positions $$$S_i$$$. Basically, the next set $$$S_i$$$ for the next value is that subset of "innermost" positions which "dominates" the previous set. That is the subset of "innermost" positions $$$(r,c)$$$ for $$$a_i$$$ such that no element $$$(r',c')$$$ of $$$S_{i+1}$$$ exists with $$$r'>r$$$ and $$$c'>c$$$.
Updating this set is simple: due to the structure of "innermost" positions, we can find any violations in $$$O(\log(n+m))$$$ time with a binary search. I think, even two pointers can work. Tsovak wins if the dominant set $$$S_1$$$ for $$$a_1$$$ is nonempty.
The overall solution works in $$$O(n \cdot m + l \cdot (n+m) \log(n+m))$$$.
My explanation could greatly benefit with diagrams and care, but here's the submission: 281490495
test"> test2 test3
Why in problem E2 we need to store two dp's? Why we can't just do dp[i][j] — min k that dp[k][i][j] wins?
https://codeforces.net/contest/2005/submission/281529257 — submission with one dp
agree, it's working for me too with only 1 dp. I don't understand the point to have 2 dp's here.
Can someone please explain why is this code giving TLE, It is code of C problem
Can anyone please help me, I am getting wrong answer on test case 2 281575266
can some one find the counter test case for this E1 solution which is failing at case 36 it's just same as the editorial but I'm using the whole L array https://codeforces.net/contest/2005/submission/281680950
Can someone point out what is wrong in my solution of C. 281726079
Maybe rewrite it, and decrease number of states. There's no need for so many states for this problem.
https://codeforces.net/contest/2005/submission/281714678 Can someone tell me why my code is giving tle for problem C , my complexity is o(n*m) which should work
How can you achieve O(n*m*5) for problem C? I found the solution in tutorial with a complexity of O(n*m*25), and found no ways optimizing the solution to O(n*m*5).
Oh, sorry. I found that If you preprocess the matched types for each character in string before calculating the score for each string, it will be O(n*m*5). (I named state variables as cur_type and matched_type, in my code here https://codeforces.net/contest/2005/submission/281816751)
[submission:281823254]the problem C, can someone tell me what fault in my code? I think we can use the end of the previous string to transfer the following string.
please