how many words per minute you type?
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 162 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 154 |
8 | pajenegod | 147 |
9 | Um_nik | 145 |
9 | BledDest | 145 |
Hi guys! Today I had an exam on algorithms and data structures, where one of the tasks was to write down an algo for finding longest common increasing subsequence in $$$O(n^2)$$$ (yeah, using pen and paper...) For whatever reason, I came up with only $$$O(n^2logn)$$$ solution. However, this solution could be easily simplified to $$$O(n^2)$$$ and many students from my course wrote this algorithm. I guess it happened because when you don't know segtree it is much easier to avoid wrong paths and reach good solution.
Then I caught myself on the thought that in many problems before I also implemented very dumb overkilled solutions with segment tree simply because I know this data structure (thank god I don't know treaps that well). Then I came up with the name of this phenomenon: "The Curse of Segment Tree". So I wonder have anybody also stumbled with this "curse"? (or I am the only orange guy who cannot come up with stupid dp on the uni exam TᴖT)
We will hold AtCoder Regular Contest 174.
The point values will be 300-300-500-500-700-900.
We are looking forward to your participation!
Sorry for the delay in publishing the editorial. If anything is unclear or missing, please let me know in the comments.
In all the problems, reading the hints is a must as the solution continues from there.
Idea: Dominater069
Preparation: Dominater069
Editorial: Dominater069
What is the minimum number of bridges to burn if we want to make exactly $$$i$$$ islands visitable from $$$1$$$?
Atleast $$$i \cdot (n - i)$$$ bridges need to burnt (the bridges connecting the $$$i$$$ reachable islands and the $$$n - i$$$ non-reachable islands).
A simple $$$O(n)$$$ solution is for every $$$i$$$ from $$$1$$$ to $$$n$$$, check if $$$i \cdot (n - i) \le k$$$, in which case print $$$i$$$ and break.
What is the answer when $$$k \ge n - 1$$$.
When $$$k < n - 1$$$, is it possible to make any island non-visitable?
When $$$k \ge n - 1$$$, the answer is $$$1$$$ since we can just destroy all bridges $$$(1, i)$$$ for $$$2 \le i \le n$$$.
Otherwise, suppose we tried to make some set of $$$i$$$ islands non-visitable, and the other $$$n - i$$$ nodes reachable from $$$1$$$. Then we need to burn atleast $$$i \cdot (n - i)$$$ bridges (the bridges connecting the $$$2$$$ sets). It is not hard to see that this function attains the minimum value when $$$i = 1$$$ or $$$i = n - 1$$$ for $$$1 \le i < n$$$. Hence the minimum number of bridges to burn always exceeds $$$n - 1$$$.
The function $$$f(x) = x \cdot (n - x)$$$ is a quadratic function in $$$x$$$, which attains maximum value at $$$x = \frac{n}{2}$$$, and the value decreasing proportionally as the distance from $$$\frac{n}{2}$$$ increases. This means that $$$f(1) = f(n - 1)$$$, and $$$f(1) > f(i)$$$ for all ($$$2 \le i \le (n - 2)$$$).
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while (t--){
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++){
if (i * (n - i) <= k){
cout << i << "\n";
break;
}
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while (t--){
int n, k; cin >> n >> k;
if (k >= n - 1) cout << 1 << "\n";
else cout << n << "\n";
}
return 0;
}
Idea : satyam343
Preparation : satyam343
Editorial : Dominater069
Group numbers according to how many times they occur in $$$a[1...n]$$$.
The group of numbers having $$$0$$$ occurrences in $$$a[1...n]$$$ is of the same size as the group of numbers having $$$2$$$ occurences in $$$a[1...n]$$$.
Try to use the $$$0$$$ and $$$2$$$ occurrence numbers first, and then if we still need more, we can use the $$$1$$$ occurence numbers. Remember that we have to form sequences of size $$$2 \cdot k$$$ which is even.
We can append any $$$2$$$ occurrence numbers to our sequence $$$l$$$ and any $$$0$$$ occurrence numbers to our sequence $$$r$$$ without any issue because the xor value will cancel out. We do this while our sequence sizes are less than $$$2 \cdot k$$$. At the end of this process, $$$l$$$ and $$$r$$$ will have the same size due to Hint $$$2$$$.
Now, we use as many $$$1$$$ occurrence numbers appending to both $$$l$$$ and $$$r$$$ as needed. Since we append to both sequences, the xor value of the $$$2$$$ sequences will be the same.
If we had to solve for odd sequence sizes, we could take a $$$1$$$ occurrence number at the very start to make it even, and then run the same process, but if there are no $$$1$$$ occurrence numbers at all, we fail with this method.
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while (t--){
int n, k;
cin >> n >> k;
k = 2 * k;
vector <int> a(2 * n), occ(n + 1, 0);
for (auto &x : a) cin >> x;
for (int i = 0; i < n; i++) occ[a[i]]++;
vector <int> g0, g1, g2;
for (int i = 1; i <= n; i++){
if (occ[i] == 0) g0.push_back(i);
else if (occ[i] == 1) g1.push_back(i);
else g2.push_back(i);
}
int v = 0;
for (auto x : g2){
if (v < k){
v += 2;
cout << x << " " << x << " ";
}
}
for (auto x : g1){
if (v < k){
v++;
cout << x << " ";
}
}
cout << "\n";
v = 0;
for (auto x : g0){
if (v < k){
v += 2;
cout << x << " " << x << " ";
}
}
for (auto x : g1){
if (v < k){
v++;
cout << x << " ";
}
}
cout << "\n";
}
return 0;
}
Idea : Dominater069
Preparation : Dominater069
Editorial : Dominater069
Alice can adapt to Bob's strategy. Try to keep that in mind.
Whenever Bob chooses $$$i$$$, and if there are any copies of $$$i$$$ left, Alice can take $$$i$$$ on her next move.
Let $$$f$$$ be the frequency array of $$$a$$$. You can ignore all $$$f(i) \ge 2$$$ due to the previous hint. Now the answer is some simple casework.
For any $$$i$$$ s.t. $$$f_i \ge 2$$$, whenever Bob chooses to remove an occurence of $$$i$$$, on the next move Alice simply chooses $$$i$$$ herself (if she hasn't already taken $$$i$$$ before that). Thus, we only focus on $$$f_i \le 1$$$ now.
The answer is min(first $$$i$$$ s.t. $$$f(i) = 0$$$, second $$$i$$$ s.t. $$$f(i) = 1$$$).
Obviously, Alice can't do better than the mex of array (first $$$i$$$ s.t. $$$f(i) = 0$$$). Further, among $$$f(i) = 1$$$, Alice can save atmost $$$1$$$ $$$i$$$ after which Bob will remove the smallest $$$f(i) = 1$$$ he can find. This is optimal for Bob as well because he cannot do better when Alice removes the (first $$$i$$$ s.t. $$$f(i) = 1$$$) on her first move.
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while (t--){
int n; cin >> n;
vector <int> f(n + 1, 0);
for (int i = 0; i < n; i++){
int x; cin >> x;
f[x]++;
}
int c = 0;
for (int i = 0; i <= n; i++){
c += (f[i] == 1);
if ((c == 2) || (f[i] == 0)){
cout << i << "\n";
break;
}
}
}
return 0;
}
1943B - Non-Palindromic Substring
Idea : errorgorn, Dominater069
Preparation : Dominater069
Editorial : Dominater069
When is a string not $$$k$$$-good? (Ignore the trivial edge cases of $$$k = 1$$$ and $$$k = n$$$).
What happens when $$$s[i....j]$$$ and $$$s[i + 1....j + 1]$$$ are both palindromes?
We first try to find the answer for a string
Let $$$k = j - i + 1$$$, $$$s[i....j]$$$ -> I and $$$s[i + 1...j + 1]$$$ -> II are both palindromes.
Then $$$s_i = s_j$$$ (due to I)
$$$s_j = s_{i + 2}$$$ (due to II)
$$$s_{i + 2} = s_{j - 2}$$$ (due to I)
$$$s_{j - 2} = s_{i + 4}$$$ (due to II)
and so on.... you can see that it forces $$$s_i = s_{i + 2} = s_{i + 4} = ....$$$. A similiar reasoning gives you $$$s_{i + 1} = s_{i + 3} = s_{i + 5}$$$.
Further, if $$$k$$$ is even, $$$i$$$ and $$$j$$$ have different parities, but $$$s_i = s_j$$$ implies that all characters must be equal actually.
We mentioned that the edge cases are $$$1$$$ and $$$n$$$, but why exactly? How does the analysis fail for them?(Left as a exercise)
So, the condition for a string to be $$$k$$$-good can be written as follows : $$$k = 1$$$ : never possible
$$$1 < k < n$$$, odd : not an alternating string
$$$1 < k < n$$$, even : not all characters same
$$$k = n$$$ : non-palindromic string
Now onto substring queries. The second and third things are easy to handle, you can store the next position where $$$s_i \ne s_{i + 2}$$$ and $$$s_i \ne s_{i + 1}$$$ respectively. Checking if a substring is a palindrome is standard with various methods such as string hashing or manacher's algorithm.
#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
vector<int> manacher_odd(string s) {
int n = s.size();
s = "$" + s + "^";
vector<int> p(n + 2);
int l = 1, r = 1;
for(int i = 1; i <= n; i++) {
p[i] = max(0, min(r - i, p[l + (r - i)]));
while(s[i - p[i]] == s[i + p[i]]) {
p[i]++;
}
if(i + p[i] > r) {
l = i - p[i], r = i + p[i];
}
}
return vector<int>(begin(p) + 1, end(p) - 1);
}
vector<int> manacher(string s) {
string t;
for(auto c: s) {
t += string("#") + c;
}
auto res = manacher_odd(t + "#");
return vector<int>(begin(res) + 1, end(res) - 1);
}
#define int long long
void Solve()
{
int n, q; cin >> n >> q;
string s; cin >> s;
auto v = manacher(s);
for (auto &x : v) x--;
// we also need to know if all same, and all alternating
set <int> s1, s2;
for (int i = 0; i < n - 1; i++){
if (s[i] != s[i + 1]) s1.insert(i);
if (i != n - 1 && s[i] != s[i + 2]) s2.insert(i);
}
while (q--){
int l, r; cin >> l >> r;
l--;
r--;
if (l == r){
cout << 0 << "\n";
continue;
}
int len = r - l + 1;
int ans;
auto it = s1.lower_bound(l);
if (it == s1.end() || (*it) >= r){
ans = 0;
} else {
it = s2.lower_bound(l);
if (it == s2.end() || (*it) >= r - 1){
ans = ((len - 1)/ 2) * (((len - 1) / 2) + 1);
} else {
ans = len * (len - 1) / 2 - 1;
}
}
if (v[l + r] < (r - l + 1)) ans += len;
cout << ans << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Idea: Everule
Preparation: Dominater069
Editorial: Dominater069
Try to solve for line case.
You may have to use more than $$$1$$$ node for certain cases.
Extend the solution for the line to the general tree version (consider the diamater).
For a line, an obvious bound on the answer is $$$\lceil \frac{n}{2} \rceil$$$, as we can colour atmost $$$2$$$ nodes per operation. I claim this is achieveable except for when $$$n$$$ mod $$$4 = 2$$$, where we do $$$1$$$ worse. That is however still provably optimal as you can bicolour the line and operations only colours nodes black which are in the same bicolouring.
When $$$n$$$ mod $$$2 = 1$$$, simply use the centre of the line and do operations of the form $$$(centre, i)$$$ ($$$0 \le i \le \lfloor \frac{n}{2} \rfloor$$$).
When $$$n$$$ mod $$$4 = 0$$$, for convenience let the line be $$$1, 2, ...., n$$$. Then, we can do operations like $$$(2, 1), (3, 1), (6, 1), (7, 1)....$$$.
When $$$n$$$ mod $$$4 = 2$$$, either of the above $$$2$$$ methods can be adapted to work because we are allowed $$$1$$$ "extra" operation.
Now that we have the solution for the line case, lets divide into $$$2$$$ cases based on parity of diamater (maximum number of nodes on a path) :
diameter mod $$$2 = 1$$$ : Find the centre of the diamater. Then we can simply do operations of the form $$$(centre, i)$$$ (for all $$$0 \le i \le \lfloor \frac{diameter}{2} \rfloor$$$). If this doesn't colour all nodes, then one can easily check that the diamater we found is not the real diamater, as the node which is not coloured is an endpoint of a larger diameter.
diamater mod $$$2 = 0$$$ : Find the $$$2$$$ centres of the diameter. Then the following set of operations satisfy the requirements : $$$(centre1, i)$$$ and $$$(centre2, i)$$$ for all odd $$$i$$$ satisfying $$$1 \le i \le \frac{diameter}{2}$$$. The intuition behind this is to basically split the nodes into $$$2$$$ sets according to a bicolouring, and then $$$1$$$ centre colours all nodes of a certain colour, while the other centre colours all nodes of the other colour.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n;
cin >> n;
vector<vector<int>> E(n);
for (int i = 1; i < n; i++){
int u, v; cin >> u >> v;
u--; v--;
E[u].push_back(v);
E[v].push_back(u);
}
auto bfs = [&](int s){
vector<int> d(n, -1);
d[s] = 0;
queue<int> Q;
Q.push(s);
while (!Q.empty()){
int v = Q.front();
Q.pop();
for (int w : E[v]){
if (d[w] == -1){
d[w] = d[v] + 1;
Q.push(w);
}
}
}
return d;
};
vector<int> d1 = bfs(0);
int a = max_element(d1.begin(), d1.end()) - d1.begin();
vector<int> d2 = bfs(a);
int b = max_element(d2.begin(), d2.end()) - d2.begin();
vector<int> d3 = bfs(b);
int diam = d3[max_element(d3.begin(), d3.end()) - d3.begin()] + 1;
//if 3 we want 1, 1 if 4 we want 1 2
vector <int> ans;
for (int i = 0; i < n; i++){
if ((d2[i] + d3[i] == diam - 1) && ((d2[i] == diam/2) || (d3[i] == diam/2)))
ans.push_back(i);
}
if (diam & 1) assert(ans.size() == 1);
else assert(ans.size() == 2);
vector <pair<int, int>> ok;
if (diam & 1){
//print everything from 0 to diam/2
for (int i = 0; i <= diam/2; i++){
ok.push_back({ans[0], i});
}
} else {
//2 => 2 ops, 4 => 2 ops , 6 => 4 ops, 8 => 4 ops
int ops = ((n - 2)/4) + 1;
int need = (diam/2) - 1;
while (need >= 0){
ok.push_back({ans[0], need});
ok.push_back({ans[1], need});
need -= 2;
}
}
cout << ok.size() << "\n";
for (auto [u, r] : ok){
cout << u + 1 << " " << r << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
// cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
1943D1 - Counting Is Fun (Easy Version)
Idea : satyam343
Preparation : satyam343
Editorial : Dominater069
Try to come up with some necessary and sufficient conditions of a good array.
Apply dp once you have a good condition.
All operations which include $$$i$$$ must also either include $$$i - 1$$$ or $$$i + 1$$$. Hence $$$a_i \le a_{i - 1} + a_{i + 1}$$$ must hold. Throughout the editorial treat $$$a_i = 0$$$ for $$$(i \le 0)$$$ or $$$(i > n)$$$.
But, is this sufficient? Infact, it is and we can prove it by strong induction.
Group arrays according to the sum of the array. We will now apply strong induction on the sum of the array.
Base Cases (sum = 0, 1 or 2) are all trivial.
Now, assume that the condition is sufficient for all arrays with sum $$$< x$$$ ($$$x \ge 3$$$).
Let us consider some array $$$a_1, a_2, ...., a_n$$$ with sum $$$x$$$. Let $$$a_i$$$ be the first non-zero element of $$$a$$$.(Observe that $$$a_{i + 1}$$$ can't be $$$0$$$).
We claim that either operating on $$$[i, i + 1]$$$ or $$$[i, i + 2]$$$ will give still satisfy the condition $$$a_j \le a_{j - 1} + a_{j + 1}$$$ for all $$$j$$$.
Let's check it. The only time $$$[i, i + 1]$$$ operation causes an issue is when $$$a_{i + 2} > a_{i + 1} - 1 + a_{i + 3}$$$, i.e. it should necessarily hold that $$$a_{i + 2} > a_{i + 3}$$$, but then $$$a_{i + 3} \le a_{i + 2} - 1$$$, and so, $$$a_{i + 3} \le a_{i + 2} - 1 + a_{i + 4}$$$, meaning $$$[i, i + 2]$$$ is valid.
Now that we have the condition, we can define a dynamic programming as follows :
dp(index, second last element(call it a), last element(b)) = number of ways (since only the last $$$2$$$ elements are relevant)
Let the new element be $$$c$$$, then it is a valid way iff $$$b \le a + c$$$. So we have a $$$\mathcal{O}(n^4)$$$ by iterating over all possibilities.
As a final optimization, we can speed it up to $$$\mathcal{O}(n^3)$$$ by using prefix sums. Note that the valid values of $$$a$$$ for fixed $$$b$$$ and $$$c$$$ satisfy $$$a \ge max(0, b - c)$$$, and hence maintaining prefix sums over $$$a$$$, we can speed it up.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, k, mod; cin >> n >> k >> mod;
vector<vector<int>> dp(k + 1, vector<int>(k + 1, 0));
dp[0][0] = 1; // dp[a][b]
for (int i = 1; i <= n + 2; i++){
vector<vector<int>> ndp(k + 1, vector<int>(k + 1, 0)); // dp[b][c]
vector<vector<int>> pref(k + 1, vector<int>(k + 1, 0)); // pref[b][a]
for (int b = 0; b <= k; b++){
pref[b][0] = dp[0][b];
for (int a = 1; a <= k; a++){
pref[b][a] = (pref[b][a - 1] + dp[a][b]) % mod;
}
}
for (int b = 0; b <= k; b++){
for (int c = 0; c <= k; c++){
if (b > c){
// a must be atleast b - c
ndp[b][c] = (pref[b][k] - pref[b][b - c - 1] + mod) % mod;
} else {
ndp[b][c] = pref[b][k];
}
}
}
dp = ndp;
}
cout << dp[0][0] << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
1943D2 - Counting Is Fun (Hard Version)
Idea : satyam343
Preparation : satyam343
Editorial : Dominater069
Try to apply Principle of Inclusion Exclusion (PIE).
You do not need to store both last elements! Only the last is enough.
Since there are $$$n^3$$$ states in our dp, we will have to optimize the number of states somehow.
Let us consider all arrays and not just good arrays. Let $$$b$$$ denote the number of "bad" elements in the array. An element is bad if $$$a_i > a_{i - 1} + a_{i + 1}$$$.
Suppose we could find $$$f(x) = $$$ number of arrays with atleast $$$x$$$ bad elements (I am not satisfied with this definition, note that an array with $$$5$$$ bad elements should be counted $$$\binom{5}{2}$$$ for $$$f(2)$$$).
By PIE, the answer is $$$\sum_{i = 0}^{n} (-1)^i \cdot f(i)$$$.
Define dp(i, last element, x) = number of arrays with atleast $$$x$$$ bad indices among indexes $$$\le i$$$. This still has $$$n^3$$$ states, but only the parity of $$$x$$$ matters. Hence, we are down to $$$2n^2$$$ states.
Transitions :
Both the transitions are optimizable using some prefix sums or running totals, and thus the solution works in $$$\mathcal{O}(n^2)$$$. There are other ways to optimize the solution, but this was the easiest to us.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, k, mod; cin >> n >> k >> mod;
vector<vector<int>> dp(2, vector<int>(k + 1, 0));
auto prev2 = dp;
dp[0][0] = 1;
for (int i = 1; i <= n + 1; i++){
vector<vector<int>> ndp(2, vector<int>(k + 1, 0));
vector<int> sum(2, 0);
for (int j = 0; j < 2; j++) for (int x = 0; x <= k; x++){
sum[j] += dp[j][x]; sum[j] %= mod;
}
for (int j = 0; j < 2; j++){
int s1 = 0, s2 = 0;
for (int x = k; x >= 0; x--){
ndp[j][x] += sum[j]; // normal transition
ndp[j][x] += s2; ndp[j][x] %= mod; // with one wrong
s1 += prev2[j ^ 1][k - x]; s1 %= mod;
s2 += s1; s2 %= mod;
}
}
prev2 = dp;
dp = ndp;
}
int ans = (dp[0][0] - dp[1][0] + mod) % mod;
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
1943E1 - MEX Game 2 (Easy Version)
Idea: Dominater069
Preparation: Dominater069
Editorial: Dominater069
It might be optimal for Bob to reduce multiple elements at the same time, thus making Alice choose between which element she wants to take.
Suppose you are only checking whether $$$ans \ge i$$$ for now, what would Alice's strategy be?
Try fixing the element that Bob wants to make sure Alice is not able to get. What would be his strategy then?
For now, lets try to see if $$$ans \ge i$$$. This is equivalent to Alice being able to take $$$1$$$ occurence of everything when the game is reduced to numbers $$$[0, i - 1]$$$.
Alice's strategy here is actually easy to find. At every step, Alice will choose the minimum $$$f_j$$$ such that $$$0 \le j < i$$$, and she hasn't chosen $$$i$$$ yet. You can reason this with greedy stays ahead, exchange argument, whatever you want.
This gives us a nice definition of Alice's moves, however we seemingly have to maintain the sorted sequence of $$$f_i$$$ always. But we can actually rewrite Bob's moves such that it does not affect the sorted order of $$$f_i$$$ and always keeps it sorted. Here, by sorted order, we mean some permutation $$$p = [p_1, p_2, ...., p_i]$$$ of $$$[0, i - 1]$$$ such that $$$f_{p_i} \le f_{p_j}$$$ whenever $$$i \le j$$$.
First, instead of subtracting $$$k$$$, we will do $$$k$$$ subtractions of only $$$1$$$. Then, the only case when sorted order can be destroyed is when there exists $$$k1$$$ and $$$k2$$$ such that $$$f_{k1} = f_{k2}$$$ and we do an operation on $$$k1$$$ but $$$k2$$$ occurs before $$$k1$$$ in the sorted order. This issue can simply be fixed by doing the operation on the smallest $$$x$$$ (according to sorted order) such that $$$f_x = f_{k1}$$$.
Now, we have a good way of representing Alice moves. Suppose we fixed the element that Bob "wins" on. Then, Bob's strategy will obviously be to make the frequency of that element as small as possible, but he must make sure to never violate sorted condition. Since Bob will make at most $$$m$$$ moves, you can just simulate his moves.
The main details of the simulation is that you need to figure out upto what index all values will become equal when doing k operations (or nearly equal, off by 1), and then first take all elements to that state. Let $$$w$$$ be the remaining operations from the $$$k$$$ operations after this, and $$$l$$$ the length of the equal sequence. Then you will reduce every frequency by $$$k / l$$$, and finally reduce the first $$$k$$$ mod $$$l$$$ numbers of this sequence. Check the code for more details.
A naive implementation takes $$$O(m)$$$ per move, so $$$O(m^2)$$$ per element we fix => $$$O(m^3)$$$ total to check $$$ans \ge i$$$. With a binary search on the answer, you get $$$O(m^3 logm)$$$. It can be optimized further, but it wasnt needed to pass. Most other polynomial solutions should pass this.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, k; cin >> n >> k;
vector <int> a(n + 1);
for (auto &x : a) cin >> x;
auto check = [&](int x){
vector <int> b;
for (int i = 0; i < x; i++){
b.push_back(a[i] - k);
}
sort(b.begin(), b.end());
for (int fix = 1; fix < x; fix++){
// this is element where bob wins
deque <int> c;
for (int i = 0; i <= fix; i++){
c.push_back(b[i]);
}
assert(c.size() >= 2);
while (c.size() != 2){
c.pop_front();
// find suffix which works
int sz = c.size();
int works = 0;
int sum = 0;
for (int j = 1; j < sz; j++){
// sum(elements of c - current element)
// this shud be >= k
sum += c[sz - j];
int loss = sum - c[sz - j - 1] * j;
if (loss >= k){
works = sz - j;
break;
}
}
int have = k;
// make everything = c[works]
for (int j = works + 1; j < sz; j++){
have -= c[j] - c[works];
c[j] = c[works];
}
assert(have >= 0);
for (int j = works; j < sz; j++){
c[j] -= have / (sz - works);
}
have %= (sz - works);
for (int j = works; j < sz; j++){
if (have){
c[j]--;
have--;
}
}
for (int j = 0; j < sz - 1; j++){
assert(c[j] <= c[j + 1]);
}
}
c.pop_front();
if (c[0] <= 0) return false;
}
return true;
};
int l = 1, r = n + 1;
while (l != r){
int mid = (l + r + 1) / 2;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
1943E2 - MEX Game 2 (Hard Version)
Idea: Dominater069
Solution : ffao
Preparation: Dominater069
Editorial: errorgorn
Instead of doing the check for $$$ans \geq i$$$ in $$$O(m^3)$$$, we will do it in $$$O(m)$$$.
For an array $$$f$$$ of length $$$n$$$. Let $$$s=f_1+f_2+\ldots+f_n$$$ be the sum of the element. $$$f$$$ will be called flat if $$$f_i = \lfloor \frac{s+i-1}{n} \rfloor$$$. That is, it has the form $$$x, \ldots, x, x+1, \ldots x+1$$$. All flat array can be characters by $$$2$$$ integers $$$(n,s)$$$ only.
Imagine simulating Bob's strategy without simulating Alice's moves of removing the first element of the array. For some prefix of the moves, the actual simulation will be a suffix of this simulation. This is because to subtract something from index $$$\leq i$$$, we must have $$$f_{i+1} = f_{i+2} = \ldots = f_n$$$.
As an example, let $$$k=4$$$.
With Alice moves: $$$[1,2,3,5,5] \to [2,2,3,4] \to [1,2,2]$$$
Without Alice moves: $$$[1,2,3,5,5] \to [1,2,2,3,4] \to [1,1,2,2,2]$$$
$$$[1,2,2]$$$ is not a suffix of $$$[1,1,2,2,2]$$$ and is the first time such a thing happens.
Suppose that the first time this happens is after $$$p$$$ moves. Then the resulting array is the flat array $$$(n-p,f_{p+1}+f_{p+2}+\ldots+f_n-pk)$$$. To find the necessary value of $$$p$$$, we can binary search or run $$$2$$$-pointers to check if the suffix of the array can reach $$$f_p$$$ with the amount of subtraction operations till then. (What we basically did is find the suffix of the array that actually gets operated on, since that makes it much more easier to solve)
Then, since the flat array $$$(n,s)$$$ becomes $$$(n-1,s-\lfloor \frac{s}{n} \rfloor - k)$$$, we can figure out whether each flat array evantually becomes a losing or winning state as we can calculate for each $$$n$$$, the minimum $$$s$$$ such that $$$(n,s)$$$ is a winning state.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,k;
int arr[200005];
int temp[200005];
bool solve(vector<int> v){
sort(all(v));
rep(x,0,sz(v)) temp[x]=1e18;
int l=1,curr=0;
rep(x,1,sz(v)){
curr+=v[x];
while (l<x && (curr-v[l])-(x-l)*v[l] >= l*k){
curr-=v[l];
l++;
}
temp[x-l]=min(temp[x-l],curr-l*k);
}
rep(x,sz(v),1) temp[x-1]=min(temp[x-1],(temp[x]-temp[x]/(x+1))-k);
return temp[0]>0;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
int TC;
cin>>TC;
while (TC--){
cin>>n>>k;
rep(x,0,n+1) cin>>arr[x];
// solve(vector<int>(arr,arr+n+1));
// continue;
int lo=0,hi=n+2,mi;
while (hi-lo>1){
mi=hi+lo>>1;
if (solve(vector<int>(arr,arr+mi))) lo=mi;
else hi=mi;
}
cout<<lo<<endl;
}
}
1943F - Minimum Hamming Distance
Idea: satyam343
Preparation: satyam343
Editorial: satyam343
Assumption: 0 is the mode of string t. If 1 occurs more times than 0 in t, we will flip all characters of s and t so that 0 is the mode of string t.
Let us say index $$$i$$$ nice if there exists $$$l$$$ and $$$r$$$($$$1 \le l \le i \le r \le n$$$) such that $$$s_i$$$ is the mode of substring $$$t[l,r]$$$.
So we might have some not nice indices $$$i$$$ such that $$$s_i =$$$ $$$\mathtt{1} $$$. We will not have any index $$$i$$$ such that i is not nice and $$$s_i =$$$ $$$\mathtt{0} $$$, as $$$\mathtt{0} $$$ is the mode of $$$t$$$. So, we need to fix the not nice indices.
Now we will start changing some $$$\mathtt{0} $$$ to $$$\mathtt{1} $$$. So it might be possible that in final $$$t$$$, the frequency of $$$\mathtt{1} $$$ is more than that of $$$\mathtt{0} $$$, and $$$\mathtt{0} $$$ is no longer the mode. So should we worry about indices $$$ i $$$ such that $$$ i $$$ was nice in the beginning, and now that we made some flips, $$$ i $$$ may become not nice?
No! It will never be possible.
In case $$$\mathtt{1} $$$ occurs more times than $$$\mathtt{0} $$$ in the updated $$$t$$$, we will have $$$frequency[1] = frequency[0] + 1$$$ and $$$t[1] = t[n] =$$$ $$$\mathtt{1} $$$(we will have such cases for pairs like ($$$s =$$$ $$$\mathtt{011} $$$, $$$t =$$$ $$$\mathtt{100} $$$; for this pair final $$$t$$$ should be $$$t =$$$ $$$\mathtt{101} $$$). So the substrings $$$t[1, n - 1]$$$ and $$$t[2, n]$$$ will have equal numbers of $$$\mathtt{0} $$$ and $$$\mathtt{1} $$$, and thus all indices should be nice. So our claim is that we should change some $$$\mathtt{0} $$$ to $$$\mathtt{1} $$$, without caring about indices $$$i$$$(which were nice initially) becoming not nice such that $$$s_i =$$$ $$$\mathtt{0} $$$.
We can use dynamic programming here.
So let us have $$$dp$$$, such that $$$dp[i][j]$$$ gives the minimum number of flips required to make $$$t[1, i]$$$ friend of $$$s[1, i]$$$ and the maximum suffix sum is $$$j$$$.
String $$$x$$$ is called to be friend of string $$$y(|x| = |y|)$$$, if for every $$$i$$$($$$1 \le i \le |x|$$$), there exists indices $$$l$$$ and $$$r$$$ such that:
1. $$$1 \le l \le i \le r \le |x|$$$
2. $$$x_i$$$ is a mode of the string $$$y[l,r]$$$
Please read hints $$$1$$$ and $$$2$$$ if you haven't as they contain some claims and definitions.
Note that when we find some sum, we add $$$1$$$ when we get $$$\mathtt{1} $$$ and subtract $$$-1$$$ when we get $$$\mathtt{0} $$$.
Suppose we have found $$$dp$$$ values for the first $$$i - 1$$$ indices, and we want to find $$$dp[i][j]$$$ for $$$0 \le j \le n$$$. Now, we need to perform the transitions.
Let us try to have a $$$O(n^3)$$$ solution first, which we can optimise after making some observations.
Take some $$$l$$$($$$0 \leq l \leq i - 1$$$). We will iterate over $$$suff$$$_$$$sum = 0$$$ to $$$n$$$, here $$$suff$$$_$$$sum$$$ is the maximum suffix sum of substring $$$t[1, l]$$$, and use $$$dp[l][suff$$$_$$$sum]$$$ to find optimal values for $$$dp[i][x]$$$ for some $$$x$$$.
So we need to do some flips to substring $$$t[l + 1, i]$$$, as $$$s[1, l]$$$ and $$$t[1, l]$$$ are already friends. So we only care to make all indices $$$j$$$ ($$$l + 1 \le j \le i$$$) nice. So there are two possibilities(either $$$\mathtt{1} $$$ occurs in substring $$$s[l + 1, i]$$$ or not):
If $$$\mathtt{1} $$$ does not occur, we can perform the transition without making any flips.
Assume $$$\mathtt{1} $$$ occurs in substring $$$s[l + 1, i]$$$. So firstly, find the sum(say $$$cur$$$_$$$sum$$$) of substring $$$t[l + 1, i]$$$. Now, if we do some flips to substring $$$t[l + 1, i]$$$, $$$cur$$$_$$$sum$$$ will change accordingly. We will do a minimum number of flips such that $$$suff$$$_$$$sum + cur$$$_$$$sum \ge 0$$$. Note that we are talking here about updated $$$cur$$$_$$$sum$$$. So we can find the minimum number(say $$$cost$$$) of flips, which will be $$$\lfloor \frac{\max(0, 1 -d )}{2} \rfloor$$$, where $$$d=suff$$$_$$$sum + initial$$$_$$$cur$$$_$$$sum$$$. So we know how many flips to make.
But which ones to flip? Here is one more claim. We should only flip the last $$$cost$$$ $$$\mathtt{0} $$$ of substring $$$t[l + 1, i]$$$.
So this is a sufficient condition, as we can certainly say that $$$t[1, i]$$$ will be friend of $$$s[1, i]$$$ now. So we know the required number of flips, which is $$$dp[l][suff$$$_$$$sum] + cost$$$. We need to find one more thing — what would be the maximum suffix sum if we flip the last $$$cost$$$ characters of $$$t[l + 1, i]$$$? We can precompute.
But we have an issue now. We know that what we performed is sufficient. But is it necessary? What if we did not need to flip cost characters of $$$t[l + 1, i]$$$?
It might be possible that we could have done less number of flips and still made all indices $$$l + 1 \le j \le i$$$ nice. The reasoning behind this is we made sure that $$$suff$$$_$$$sum + cur$$$_$$$sum \ge 0$$$, but what if it was not needed?
Like it is possible that total sum is negative, but all indices $$$j$$$($$$l + 1 \le j \le i$$$) such that $$$s_j =$$$ $$$\mathtt{1} $$$ are satisfied. So here, we can use exchange arguments and conclude that all cases will be covered if we check for all pairs of ($$$l, suff$$$_$$$sum$$$) $$$0 \le l, suff$$$_$$$sum \le i - 1$$$.
Now we need to optimise this to $$$O(n^2)$$$.
Notice that when we do the flips, there will be a suffix(possibly empty when $$$cost=0$$$) of $$$t[l + 1, i]$$$ containing only $$$\mathtt{1} $$$ s. Suppose we are at index $$$i$$$ and need to find $$$dp[i][j]$$$ for $$$0 \le j \le i$$$. We can iterate over all $$$j$$$($$$1 \le j \le i$$$), assume that all the characters in substring $$$t[j,i]$$$ are $$$\mathtt{1} $$$ s, and find the $$$dp$$$ values. Maximum suffix sum will be $$$i-j+1+max$$$_$$$suffix$$$_$$$sum[j-1]$$$. So we can find the smallest index $$$p$$$ such that the sum of the elements in substring $$$t[p,l]$$$ is greater than or equal to $$$0$$$ if we make all the characters in substring $$$t[j,i]$$$ $$$\mathtt{1} $$$.
Notice that we already have the new suffix maximum, and we know the $$$cost$$$ too, which is equal to the number of $$$\mathtt{0} $$$ s in the original substring $$$t[j,i]$$$. So our transition will be $$$dp[i][new$$$_$$$suffix$$$_$$$max]=\max(dp[i][new$$$_$$$suffix$$$_$$$max], \min\limits_{k = p-1}^{i} best[k] + cost)$$$, where $$$best[i]= \min\limits_{k = 0}^{i} dp[i][k]$$$.
So, our final complexity will be $$$O(n^2)$$$, as we can perform the transition in $$$O(1)$$$ if we precompute the needed things.
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll int
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
const ll MOD=998244353;
const ll MAX=10005;
ll dp[MAX][MAX];
ll suffix_min[MAX];
ll suffix_max[MAX];
ll can_go_till[MAX][MAX+5];
void solve(){
ll n; cin>>n;
ll shift=n;
for(ll i=-n;i<=0;i++){
can_go_till[0][shift+i]=0;
}
string s,t; cin>>s>>t;
s=" "+s,t=" "+t;
ll sum=0;
for(ll i=1;i<=n;i++){
sum+=2*(t[i]-'0')-1;
}
suffix_max[0]=0;
if(sum>=0){
for(ll i=1;i<=n;i++){
s[i]='0'+'1'-s[i];
t[i]='0'+'1'-t[i];
}
}
ll max_sum=0;
for(ll i=1;i<=n;i++){
max_sum+=2*(t[i]-'0')-1;
max_sum=max(0,max_sum);
suffix_max[i]=max_sum;
}
for(ll i=1;i<=n;i++){
sum=0;
for(ll j=-n;j<=0;j++){
can_go_till[i][shift+j]=i+1;
}
for(ll j=i;j>=1;j--){
sum+=2*(t[j]-'0')-1;
ll use=min(sum,0);
can_go_till[i][shift+use]=j;
}
for(ll j=n-1;j>=0;j--){
can_go_till[i][j]=min(can_go_till[i][j],can_go_till[i][j+1]);
}
}
for(ll i=0;i<=n+1;i++){
for(ll j=0;j<=n+1;j++){
dp[i][j]=MOD;
}
}
dp[0][0]=0;
vector<ll> best(n+5,MOD);
best[0]=0;
for(ll i=1;i<=n;i++){
for(ll l=0;l<=i-1;l++){
dp[i][l+1]=dp[i-1][l]+(t[i]=='0');
}
for(ll l=0;l<=i;l++){
ll new_sum=l+2*(t[i]-'0')-1;
if(s[i]=='1' and new_sum<=-1){
continue;
}
new_sum=max(0,new_sum);
dp[i][new_sum]=min(dp[i][new_sum],dp[i-1][l]);
}
suffix_min[i]=MOD;
for(ll j=i-1;j>=0;j--){
suffix_min[j]=min(suffix_min[j+1],best[j]);
}
ll cnt=0;
for(ll j=i;j>=1;j--){
cnt+=(t[j]=='0');
ll now=i-j+1;
ll cur_suff_max=now+suffix_max[j-1];
ll pos=max(0,can_go_till[j-1][shift-now]-1);
dp[i][cur_suff_max]=min(dp[i][cur_suff_max],suffix_min[pos]+cnt);
}
for(ll j=0;j<=n;j++){
best[i]=min(best[i],dp[i][j]);
}
}
ll ans=MOD;
s[0]='1';
for(ll i=n;i>=0;i--){
ans=min(ans,best[i]);
if(s[i]=='1'){
cout<<ans<<nline;
return;
}
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Anyone has some advice for practice? Sometimes I can solve difficulty up to 2400 but sometimes can't.
upd: Can anyone suggest some difficult and important algorithm that a GM needs to learn?
During Codeforces Round 934 (Div. 2) I submitted problem D hoping to get the green AC but unfortunately got the red WA (submission 251770538). I spent the rest of the time in the contest trying to figure out the problem in vain. After the contest, I checked the accepted solutions and found that they were exactly like mine which made me more confused.
I stress-tested my solution using a brute-force approach during the contest and using AC solutions after the contest time but couldn't find a single test case. Even after a million random test cases, my solution is still steadfast. I know that a few hundred test cases are enough.
My implementation of string hashing is inspired by Usaco.guide, which uses random bases and a fixed modulus (1LL << 61) -1
). I used multiple bases to make sure no collisions happen, but this also didn't help.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
// BeginCodeSnip{HashedString}
class HashedString {
public:
// change M and B if you want
static const ll M = (1LL << 61) - 1;
static const ll B;
static __int128 mul(ll a, ll b) { return (__int128)a * b; }
static ll mod_mul(ll a, ll b) { return mul(a, b) % M; }
private:
// pow[i] contains P^i % M
static vector<ll> pow;
// p_hash[i] is the hash of the first i characters of the given string
vector<ll> p_hash;
public:
HashedString(const string &s) : p_hash(s.size() + 1) {
while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); }
p_hash[0] = 0;
for (int i = 0; i < s.size(); i++) {
p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M;
}
}
ll get_hash(int start, int end) {
ll raw_val =
p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]);
return (raw_val + M) % M;
}
};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
vector<ll> HashedString::pow = {1};
const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng);
// EndCodeSnip
const auto M = HashedString::M;
const auto B = HashedString::B;
const auto mul = HashedString::mul;
const auto mod_mul = HashedString::mod_mul;
ll inv(ll base, ll MOD) {
ll ans = 1, expo = MOD - 2;
while (expo) {
if (expo & 1) { ans = mod_mul(ans, base); }
expo >>= 1;
base = mod_mul(base, base);
}
return ans;
}
string n, h;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> h;
if (n.size() > h.size()) return cout << 0, 0;
HashedString hs(h);
set<ll> good;
ll h_hsh = 1, n_hsh = 1;
for (int i = 0; i < n.size(); i++) {
// Compute product hashes
h_hsh = mod_mul(h_hsh, B + h[i] - 'a');
n_hsh = mod_mul(n_hsh, B + n[i] - 'a');
}
for (int i = n.size() - 1; i < h.size(); i++) {
if (i >= n.size()) {
// Update product hashes using modular inverse
h_hsh = mod_mul(h_hsh, inv(B + h[i - n.size()] - 'a', M));
h_hsh = mod_mul(h_hsh, B + h[i] - 'a');
}
if (n_hsh == h_hsh) { good.insert(hs.get_hash(i + 1 - n.size(), i)); }
}
cout << good.size() << '\n';
}
Unfortunately, I couldn't get AC during the contest but now I'm curious about this weird behavior of string hashing. Why using many random bases doesn't help and the solution is to use a prime modulus (i.e. $$$10^9 + 7$$$)?
Now the situation is more complex, I tried to submit a solution (submission 252010026) with only one base and $$$10^9 + 7$$$ as a modulus and got AC. Isn't the collision probability high for such a case?
Another thing to note is the inability to use GNU C++20 compiler caused all of this chaos because I couldn't use __int128
and (1LL << 61) - 1
as a modulus which I think will get AC.
We are pleased to invite you to participate in Codeforces Round 936 (Div. 2), which will start on Thursday, March 21, 2024 at 17:35.
The round was prepared by exhausted, max0000561, azureglow and myself.
This round will be rated for participants whose rating is below 2100. Participants with higher ratings may participate out of the competition.
You will be given 6 problems and 2 hours to solve them. We hope you find them interesting.
We would like to thank:
Special thanks to KoT_OsKaR and teraqqq for their help in creating tasks.
Good luck on the round and high rankings to everyone!
Score Distribution: 500−1000−1500−1750−2250−2750.
Hello MikeMirzayanov,
In Codeforces Round 934 (Div. 2), as per the common standings my rank is 1192. However in the contests page my rank is 4811, as a result of which I got a rating change of negative 106. Please address my problem. standings
Proofs are attached below
Idea: BledDest
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n % 2 == 1) {
cout << "NO" << '\n';
continue;
}
cout << "YES" << '\n';
for (int i = 0; i < n / 2; ++i)
for (int j = 0; j < 2; ++j)
cout << "AB"[i & 1];
cout << '\n';
}
}
Idea: BledDest
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
vector<int> b({a[n - 1]});
for (int i = n - 2; i >= 0; --i) {
if (a[i] > b.back()) {
b.push_back(a[i] % 10);
b.push_back(a[i] / 10);
} else {
b.push_back(a[i]);
}
}
cout << (is_sorted(b.rbegin(), b.rend()) ? "YES" : "NO") << '\n';
}
}
Idea: BledDest
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<char> ok1(n / 2), ok2(n / 2);
for (int i = 0; i < 2; ++i) {
string s;
cin >> s;
for (int j = 0; j < n; ++j) if ((i + j) & 1) {
ok1[(i + j) / 2] |= (s[j] == '>');
ok2[(j - i + 1) / 2] |= (s[j] == '>');
}
}
bool ans = true;
for (int i = 0; i < n / 2; ++i) ans &= ok1[i] && ok2[i];
cout << (ans ? "YES" : "NO") << '\n';
}
}
Idea: BledDest
for _ in range(int(input())):
s = input()
n = len(s)
ans = 0
for d in range(1, n // 2 + 1):
cnt = 0
for i in range(n - d):
cnt += s[i] == s[i + d] or s[i] == '?' or s[i + d] == '?'
if i - d >= 0:
cnt -= s[i - d] == s[i] or s[i - d] == '?' or s[i] == '?'
if i - d >= -1 and cnt == d:
ans = 2 * d
print(ans)
Idea: BledDest
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n), c(n);
for(int i = 0; i < n; i++)
{
a[i] = i + 1;
c[i] = i / k + 1;
}
int q = *max_element(c.begin(), c.end());
for(int i = 1; i <= q; i++)
{
int l = find(c.begin(), c.end(), i) - c.begin();
int r = c.rend() - find(c.rbegin(), c.rend(), i);
int m = (l + r) / 2;
reverse(a.begin() + l, a.begin() + m);
reverse(a.begin() + m, a.begin() + r);
}
for(int i = 0; i < n; i++)
cout << a[i] << " \n"[i == n - 1];
cout << q << "\n";
for(int i = 0; i < n; i++)
cout << c[i] << " \n"[i == n - 1];
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
}
Idea: BledDest
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y) {
x += y;
if (x >= MOD) x -= MOD;
return x;
}
int mul(int x, int y) {
return x * 1LL * y % MOD;
}
int binpow(int x, int y) {
int z = 1;
while (y) {
if (y & 1) z = mul(z, x);
x = mul(x, x);
y >>= 1;
}
return z;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
vector<int> suma(n + 1), sumb(n + 1);
for (int i = 0; i < n; ++i) {
suma[i + 1] = suma[i] + a[i];
sumb[i + 1] = sumb[i] + b[i];
}
int m = sumb[n];
vector<int> f(m + 1), invf(m + 1);
f[0] = 1;
for (int i = 1; i <= m; ++i) f[i] = mul(f[i - 1], i);
invf[m] = binpow(f[m], MOD - 2);
for (int i = m; i > 0; --i) invf[i - 1] = mul(invf[i], i);
vector<int> sumc(m + 2);
for (int i = 0; i <= m; ++i)
sumc[i + 1] = add(sumc[i], mul(f[m], mul(invf[i], invf[m - i])));
int pw2 = binpow(binpow(2, MOD - 2), m);
while (q--) {
int l, r;
cin >> l >> r;
--l;
int k = 2 * (suma[r] - suma[l]) - suma[n];
int cur = sumb[r] - sumb[l];
int mx = max(0, min(k + cur, m + 1));
int cnt = sumc[mx];
cout << mul(cnt, pw2) << ' ';
}
}
Idea: BledDest
#include<bits/stdc++.h>
using namespace std;
int n, c;
int g[21][21];
const int INF = int(1e9);
int primMST(int vertex_cover_mask)
{
vector<int> d(n, INF);
vector<bool> used(n, false);
d[0] = 0;
int ans = 0;
for(int i = 0; i < n; i++)
{
int idx = -1;
for(int j = 0; j < n; j++)
{
if(!used[j] && d[j] < INF && (idx == -1 || d[j] < d[idx]))
idx = j;
}
if(idx == -1) return INF;
used[idx] = true;
ans += d[idx];
for(int k = 0; k < n; k++)
{
if(used[k])
continue;
if((vertex_cover_mask & (1 << idx)) == 0 && (vertex_cover_mask & (1 << k)) == 0)
continue;
d[k] = min(d[k], g[idx][k]);
}
}
return ans;
}
int main()
{
cin >> n >> c;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> g[i][j];
if(g[i][j] == 0) g[i][j] = INF;
}
}
int ans = INF;
for(int mask = 0; mask < (1 << n); mask++)
{
int cur = primMST(mask);
if(cur != INF) ans = min(ans, cur + c * __builtin_popcount(mask));
}
cout << ans << endl;
}
In the vibrant world of rhythm and beats, where music pulses through every player's veins, there existed a young enthusiast named Alexandru Ardelean. His love for music led him to Ohio State University's rhythm gaming community, where he immersed himself in the electrifying atmosphere of competitive gameplay.
One fateful evening, amidst the flashing lights and thumping bass of an intense match, Alexandru found himself facing a formidable opponent: a skilled player known as Lily. As their fingers danced across the buttons, a fierce yet friendly rivalry ignited between them, each determined to claim victory.
With each match, Alexandru and Lily's admiration for each other's skills grew, and they soon found themselves spending more time together outside of the game, bonding over their shared passion for music and gaming. Late nights turned into early mornings as they challenged each other to matches, traded tips and tricks, and shared stories of their favorite songs and artists.
As their connection deepened, Alexandru realized that his feelings for Lily went beyond just friendship. With butterflies in his stomach and a pounding heart, he mustered the courage to invite her to a real-life meetup at a local café near the university.
Nervously sipping their drinks, Alexandru and Lily laughed and chatted as if they had known each other for years. It was in that cozy café, surrounded by the warmth of their budding romance, that Alexandru knew he had found someone truly special.
Their love story continued to flourish, with music serving as the soundtrack to their journey. From impromptu jam sessions in Alexandru's dorm room to heartfelt conversations under the stars, Alexandru and Lily's bond only grew stronger with each passing day.
And so, in the midst of Ohio State University's vibrant music gaming community, Alexandru found not only a fierce competitor but also the love of his life. Together, they continued to conquer challenges, set new high scores, and dance to the rhythm of their own love story.
Name |
---|