Thank you all for participating in the round.
All the problems were created by BiNARyBeastt during our classes in winter.
There are 2 observstions needed to solve the problem:
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 5 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 can't 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)
For both versions let's assume the array $$$b$$$ is sorted in increasing order.
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.
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 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, you only need to know which letter you reached from the previous selections.
Let's loop through the $$$n$$$ strings and define $$$dp_i$$$ as the maximal answer if we’re currently looking for the $$$i$$$-th letter in the word Narek. Initially, $$$dp_0 = 0$$$, and $$$dp_1 = \cdots = dp_4 = -\infty$$$. We loop through the $$$n$$$ strings. 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 $$$1 \leq j \leq 5$$$. If $$$dp[j]$$$ is not $$$\text{INT_MAX}$$$, we can replicate the process of choosing this string for our subset and count how many letters we used. We will reach some $$$z$$$-th letter in the word “Narek,” where $$$1 \leq z \leq 5$$$. If reaching $$$dp_z$$$ from $$$dp_j$$$ is more optimal than the previous value of $$$dp_z$$$, then we update $$$dp[z]$$$ by $$$dp[j] + \text{new_score}$$$. At the end, we can output $$$dp[i] - 2 \times 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 opponent’s score, so we subtract this from our score and add it to the opponent’s.
