I made this draft 7 months ago and I haven't published it. I went into some form of depression (cuz of the my stupidity in the final) so I got embarrassed to publish anything about it. But I spent a lot of time in this and since I don't care that much anymore, I'll publish this anyway. Hope you enjoy!
A couple of MHT students in Indonesia decided to hold a contest for local Competitive Programming students. It is called PLC TOC 16 and it is inspired by PLC TOC 12. We have prepared original problems for this contest. For people who want to see the problems, it can be seen through links in the editorial. Here is the editorial.
How many possible subarrays are there in an array sized $$$n$$$?
There is a maximum amount of $$$n^2$$$ possible subarrays.
To consider solutions, always look at the constraints. What is a possible time complexity of a solution for this subtask?
Remember, the GCD operation is associative.
With $$$n \le 100$$$, $$$O(n^3)$$$ is passable. Iterate over all possible subarrays. To find the GCD of a subarray, we can iterate over the values such that $$$GCD(a_l, a_{l+1}, ... a_{r+1}) = GCD(GCD(a_l, a_{l+1}, ..., a_r), a_{r+1})$$$. The process starts as $$$x_1 = a_l$$$ then $$$x_2 = GCD(x_1, a_{l+1})$$$ then $$$x_3 = GCD(x_2, a_{l+2})$$$ and so on.
To compute the GCD of two values, $$$x$$$ and $$$y$$$, we can use the $$$GCD$$$ function in c++ or try iterating from $$$1$$$ to $$$100$$$ and see which is the greatest value that divides both $$$x$$$ and $$$y$$$.
For all subarrays, take the maximum GCD value and output it.
Time complexity: $$$O(n^3)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
const ll mod = 1e9+7;
ll test, n, a[1001], ans, fpb;
void solve() {
//begin!!
ans = 0;
cin >> n;
for (ll i = 1; i <= n; i++) {cin >> a[i];}
for (ll l = 1; l <= n; l++) {
for (ll r = l+1; r <= n; r++) {
fpb = a[l];
for (ll i = l+1; i <= r; i++) {
fpb = __gcd(fpb, a[i]);
}
ans = max(ans, fpb);
}
}
cout << ans << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
Think simple. It might be useful to make some testcases.
There is a crucial yet simple observation, the GCD of two values will never exceed the two values itself.
As a result, we can just iterate over all adjacent elements and check their GCD.
Time complexity: $$$O(n)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
const ll mod = 1e9+7;
ll test, n, a[200001], ans;
void solve() {
//begin!!
ans = 0;
cin >> n >> a[1];
for (ll i = 2; i <= n; i++) {cin >> a[i]; ans = max(ans, __gcd(a[i-1], a[i]));}
cout << ans << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
There was a total of 18 fully accepted solutions on contest. While the question might seem intimidating, the answer is very simple. Questions like these should encourage people to actually try computing as the computer. By doing it manually, it becomes obvious.
This question was inspired by the harder version of this question, problem H.
There are a possible amount of $$$2^n$$$ subsequences, which is too much to handle. However, the problem doesn't ask for the chosen subsequence but the score itself. Can we limit the amount of scores needed to handle?
The score relies on only the smallest $$$b_i$$$ and largest $$$b_j$$$, therefore there are only $$$O(n^2)$$$ scores needed to handle.
Instead of iterating over all subsequences, iterate through all pairs $$$(b_i, b_j)$$$ and check if their exists a subsequence such that the sum is over than $$$k$$$.
There is a greedy observation to check if there exists subsequence such that the sum is over than $$$k$$$.
We can choose all elements that have $$$b_i$$$ under the maximum and above the minimum. Adding an element always adds to the sum of the subsequence, so it is best to choose all of those elements.
For every single pair, how can we find all of those elements quickly?
Instead of choosing subsequences, lets choose subarrays instead. Because the possible amount of scores are up to $$$O(n^2)$$$, we can sort by $$$b_i$$$ and iterate over two indexes $$$l$$$ and $$$r$$$ as the indexes of the lowest and highest elements. We are left with the sum requirement. However, we can just greedily take all elements within $$$l$$$ and $$$r$$$ because it will always add to the sum. This can be optimized with prefix sums. We take the minimum score of all $$$(l, r)$$$ that fit the sum requirement.
Time complexity: $$$O(n^2)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
#define b fi
#define a se
const ll mod = 1e9+7;
ll test, n, k, psum[200001], ans;
pll val[200001];
void solve() {
//begin!!
ans = 1e16;
cin >> n >> k;
for (ll i = 1; i <= n; i++) {cin >> val[i].a;}
for (ll i = 1; i <= n; i++) {cin >> val[i].b;}
sort(val+1, val+n+1);
for (ll i = 1; i <= n; i++) {psum[i] = psum[i-1]+val[i].a;}
for (ll l = 1; l <= n; l++) {
for (ll r = l; r <= n; r++) {
if (psum[r]-psum[l-1] >= k) {ans = min(ans, val[r].b-val[l].b);}
}
}
if (ans == 1e16) {cout << "-1\n"; return;}
cout << ans << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
There was a monotonic property for the sum requirement. There is also a monotonic property for the differences.
For some fixed $$$r$$$, taking the closest $$$l$$$ is optimal. But it's not always possible. How do we find the best $$$l$$$?
Instead of choosing subsequences, lets choose subarrays instead. Because the possible amount of scores are up to $$$O(n^2)$$$, we can sort by $$$b_i$$$ and iterate over two indexes $$$l$$$ and $$$r$$$ as the indexes of the lowest and highest elements. We are left with the sum requirement. However, we can just greedily take all elements within $$$l$$$ and $$$r$$$ because it will always add to the sum. This can be optimized with prefix sums.
Not all possible scores must be checked. For all $$$r$$$, take the closest $$$l$$$ such that it fits the sum requirement. This can be sped up using two pointers or binary search.
We take the minimum score of all $$$(l, r)$$$ that fit the sum requirement.
Time complexity: $$$O(n)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
#define b fi
#define a se
const ll mod = 1e9+7;
ll test, n, k, psum[200001], p1, ans;
pll val[200001];
void solve() {
//begin!!
ans = 1e16;
cin >> n >> k;
for (ll i = 1; i <= n; i++) {cin >> val[i].a;}
for (ll i = 1; i <= n; i++) {cin >> val[i].b;}
sort(val+1, val+n+1);
for (ll i = 1; i <= n; i++) {psum[i] = psum[i-1]+val[i].a;}
p1 = 1;
for (ll i = 1; i <= n; i++) {
while (psum[i]-psum[p1] >= k) {p1++;}
if (psum[i]-psum[p1-1] >= k) {ans = min(ans, val[i].b-val[p1].b);}
}
if (ans == 1e16) {cout << "-1\n"; return;}
cout << ans << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
This question was made one day before the actual contest. It's a simple question using classic techniques.
The operations can be simplified to flip element $$$i$$$ and flip the entire array. What are the possible ways to turn all lights into 1?
There are only two ways to turn on all lights, either turn each element $$$i$$$ that equals to $$$0$$$ into $$$1$$$ or turn each element $$$i$$$ that equals to $$$1$$$ into $$$0$$$ and then flip the entire array. We take the minimum amount of operations from both methods.
Time complexity: $$$O(m)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
const ll mod = 1e9+7;
ll test, n, m, a[200001], ans1, ans2;
char inp;
void solve() {
//begin!!
cin >> n >> m;
for (ll i = 1; i <= m; i++) {cin >> inp; a[i] = inp-'0';}
ans1 = 0; for (ll i = 1; i <= m; i++) {ans1 += !a[i];}
ans2 = 1; for (ll i = 1; i <= m; i++) {ans2 += a[i];}
cout << min(ans1, ans2) << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
The amount of possible ways are simpler than you think. Find all possible ways!
Similar to subtask 1, we handle for the first row. We need to handle rows below the first row. However, it is important to not break the first row itself when handling rows below it. The only way to not disturb the first row itself is to either have no column operations or all column operations. Therefore, after handling the first row, we can only turn on all lights if every other row is either full of $$$0$$$ or full of $$$1$$$. Similar to subtask 1, there are only two methods that can turn on all lights. We take the minimum of the two possible methods.
Time complexity: $$$O(n \cdot m)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
const ll mod = 1e9+7;
ll test, n, m, ans1, ans2;
char inp;
void solve() {
//begin!!
cin >> n >> m;
vector<vector<bool>> a (n+1, vector<bool>(m+1));
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= m; j++) {
cin >> inp; a[i][j] = inp-'0';
}
}
for (ll j = 2; j <= m; j++) {
for (ll i = 1; i <= n; i++) {
if ((a[i][j] == a[1][j]) != (a[i][1] == a[1][1])) {cout << "-1\n"; return;}
}
}
ans1 = 0;
for (ll j = 1; j <= m; j++) {ans1 += !a[1][j];}
for (ll i = 1; i <= n; i++) {ans1 += !(a[i][1]==a[1][1]);}
ans2 = 0;
for (ll j = 1; j <= m; j++) {ans2 += a[1][j];}
for (ll i = 1; i <= n; i++) {ans2 += (a[i][1]==a[1][1]);}
cout << min(ans1, ans2) << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
Thank you, Thau, for playing with the light switches and originating the idea of the question.
Because $$$n \le 2 \cdot 10^5$$$, we can simulate the process. To find the digits of a number $$$x$$$, we can take the remainder of $$$x$$$ by 10 then divide it to move on to the next digit. Keep repeating the process until the number is finished. We can iterate through the digits and count of occurrences of a digit $$$6$$$ and $$$7$$$ being adjacent.
Time complexity: $$$O(n \cdot log_{10}n)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
const ll mod = 1e9+7;
ll test, n, cur, bef, ans;
vector<ll> digits;
void solve() {
//begin!!
ans = 0; bef = 0;
cin >> n;
for (ll i = 1; i <= n; i++) {
cur = i;
digits.clear(); while (cur) {digits.pb(cur%10); cur /= 10;}
reverse(digits.begin(), digits.end());
for (ll j : digits) {if (bef == 6 && j == 7) {ans++;} bef = j;}
}
cout << ans << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
There are only 2 cases of the occurrence of the sacred number $$$67$$$. Try dividing your code to handle both cases separately.
For counting some number, it is useful to divide per digit. Sometimes we must count the amount of numbers of a prefix or a suffix of a number. Sometimes, a digit can be filled with any digit.
There are a good amount of special cases. From the base answers, find the special cases.
We have to handle for each test case in either $$$O(1)$$$ or $$$O(log_{10}n)$$$. It is clear that there are only two cases of the sacred number $$$67$$$.
Case 1: Count the amount of $$$67$$$ for the numbers $$$\le n$$$.
Imagine counting all numbers such that $$$_$$$...$$$_$$$ $$$67$$$ $$$_$$$...$$$_$$$
For every box on the left of the sacred number $$$67$$$, that is the prefix of the number up until that point. For every box on the right, it can be filled with any digit. For all possible positions of the sacred number $$$67$$$, we can calculate the prefix up until that position multiplied by ten to the power of the amount of boxes on the right.
There is a special case, if the sacred number $$$67$$$ is on the start, the amount of numbers would be the suffix up until that point.
Case 2: Count the amount of adjacent numbers such that the first number ends with $$$6$$$ and the second number starts with $$$7$$$.
For some number with $$$x$$$ digits, assume it starts with $$$7$$$. We have $$$x-1$$$ digits that can be iterated. However, the last digit must be $$$6$$$. So that leaves $$$x-2$$$ digits. All of those digits can be filled with any digits, so we can multiply by ten to the power of $$$x-2$$$.
Of course, there are still some special cases. When $$$x=1$$$, if $$$n \ge 7$$$, then there exists an occurence.
The starting digit also is a special case. If the starting digit is under $$$7$$$, we do not need to count until all digits. If the starting digit is above $$$7$$$ we need to count all digits. That leaves if the starting digit is $$$7$$$, which means all numbers of it's suffix and ends with $$$6$$$ must be counted.
Time complexity: $$$O(log_{10}n)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
const ll mod = 1e9+7;
ll test, n, cur, strt, sec, lvl, ans;
ll ten[19];
void solve() {
//begin!!
ans = 0; lvl = 0; sec = 0;
cin >> n;
cur = n;
for (ll i = 0; cur; i++) {
if (cur == 67) {ans += sec+1; lvl++; sec += (cur%10)*ten[i]; strt = 6; break;}
if (cur < 10) {strt = cur;}
else {lvl++; sec += (cur%10)*ten[i];}
ans += ((cur+33)/100)*ten[i]; cur /= 10;
}
if (strt == 7) {ans += (sec+3)/10;}
else if (strt > 7) {lvl++;}
if (lvl) {ans++;} for (ll i = 2; i <= lvl; i++) {ans += ten[i-2];}
cout << ans << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ten[0] = 1; for (ll i = 1; i <= 18; i++) {ten[i] = ten[i-1]*10;}
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
Thank you, JoPanszz, for being a bot. This question probably made the participants dislike the contest, the resulting solution is concise, but the idea is not. Questions like these still must be mastered, as implementation problems (while annoyingly simple) are tricky.
Assume we have a mega name. We can add more contacts that can be sent through the mega name, as long as there exists a full name such that its first name is the same as the last name of the mega name. Does this signal anything?
To check if we can add a name, we must make connections of every first name to their last name. This means we can graph out the question.
Analyze the shape of the graph. What can you see?
The graph consists of many trees.
We can perceive the names as directed edges of a graph. The requirements in the question actually describe the question as finding the longest path in a directed acyclic graph. A mega name can be perceived as a path within the graph and it can be guaranteed that cycles cannot be created.
Because of the restriction, the graph consists of trees. Drawing the tree vertically, we can show that the maximum depth is the answer. We can DFS or BFS from the root of each tree and keep the maximum depth.
Time complexity: $$$O(n)$$$
Lol I didn't make this one.
The only important property to extend the mega name is the last name of the mega name.
Let's give each node a value, the maximum length of a path that ends at that node. The value can be calculated by the maximum of the values of the nodes directed to it plus one.
We can only operate on a node if all nodes directed to it have been handled. We can use topological sorting to handle the order.
Time complexity: $$$O(n)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define ppll pair<pll, pll>
#define fi first
#define se second
#define rizz fi.fi
#define id fi.se
#define r se.fi
#define c se.se
const ll mod = 1e9+7;
ll test, n, ans;
string inpa, inpb;
set<string> st;
map<string, vector<string>> adj;
map<string, ll> to, mx;
queue<string> q;
void solve() {
//begin!!
ans = 0;
adj.clear(); st.clear(); to.clear(); mx.clear();
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> inpa >> inpb;
st.insert(inpa); st.insert(inpb);
adj[inpa].pb(inpb); to[inpb]++;
mx[inpa] = mx[inpb] = 1;
}
for (string i : st) {if (to[i] == 0) {q.push(i);}}
while (!q.empty()) {
string i = q.front(); q.pop();
ans = max(ans, mx[i]);
for (string j : adj[i]) {
mx[j] = max(mx[j], mx[i]+1);
to[j]--; if (to[j] == 0) {q.push(j);}
}
}
cout << ans-1 << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
Thank you, Joy3li, for making the question. My "restatement" of the question might've made the question skipped by many. (and also the fact that it was changed to "dislike" made me a bit sad)
F. Alfizo and a Specific Someone
Because $$$q \le 5$$$, we can simply simulate the process. We can use flood fill and find which cell is the closest.
Time complexity: $$$O(q*n*m)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
const ll mod = 1e9+7;
ll test, n, m, Q, a[200001], vis[200001], x, y, b;
ll ff(ll ix, ll iy) {
if (ix < 0 || iy < 1 || ix >= n || iy > m) {return 1e9;}
if (vis[ix*m+iy] || a[ix*m+iy] > b) {return 1e9;} vis[ix*m+iy] = true;
return min(ix+iy-1, min(min(ff(ix-1, iy), ff(ix+1, iy)), min(ff(ix, iy-1), ff(ix, iy+1))));
}
void solve() {
//begin!!
cin >> n >> m;
for (ll i = 0; i < n; i++) {
for (ll j = 1; j <= m; j++) {
cin >> a[i*m+j];
}
}
cin >> Q;
while (Q--) {
for (ll i = 0; i < n; i++) {
for (ll j = 1; j <= m; j++) {
vis[i*m+j] = 0;
}
}
cin >> x >> y >> b; x--;
cout << ff(x, y) << " ";
}
cout << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
From subtask 1, we used flood fill to find the best cell. But this actually signifies something. Think of the cells of the flood.
Every cell within the flood has the same answer. This signifies something even more.
All cells can be grouped with each other. This signifies the most.
Use DSU.
We have to make the floods quickly for each query. However, we have to reset the floods for each query, which will take too long. When do we not have to completely reset a flood?
When the next query has a higher rizz level than the query before it.
Remember offline query techniques.
We can sort queries based off their rizz level. This optimizes the flooding sequence. For some try, we can extend the flood it's in by adding the adjacent cells of the flood which has rizz lower than the try. This process actually incentivizes adding cells to the flood from lower to higher rizz level. We can use sort the cells and add whenever it's rizz level is lower than the current try.
Because all cells within one flood has the same answer, all cells can be grouped together using DSU. Adding cells also counts as a DSU process. The parent should be the connected cell with the best closeness.
Time complexity: $$$O((nm)log(nm))$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define ppll pair<pll, pll>
#define fi first
#define se second
#define rizz fi.fi
#define id fi.se
#define r se.fi
#define c se.se
const ll mod = 1e9+7;
ll test, n, m, Q, a[200001], par[200001], ans[200001];
ppll event[400001];
ll fnd(ll ix) {
if (par[ix] == ix) {return ix;}
par[ix] = fnd(par[ix]); return par[ix];
}
void join(ll ix, ll iy) {
if ((fnd(ix)-1)/m+1 + (fnd(ix)-1)%m+1 > (fnd(iy)-1)/m+1 + (fnd(iy)-1)%m+1) {par[fnd(ix)] = fnd(iy);}
else {par[fnd(iy)] = fnd(ix);}
return;
}
void solve() {
//begin!!
cin >> n >> m;
for (ll i = 0; i < n; i++) {
for (ll j = 1; j <= m; j++) {
cin >> a[i*m+j]; par[i*m+j] = 0;
event[i*m+j] = {{a[i*m+j], 0}, {i+1, j}};
}
}
cin >> Q;
for (ll i = 1; i <= Q; i++) {
event[n*m+i].id = i;
cin >> event[n*m+i].r >> event[n*m+i].c >> event[n*m+i].rizz;
}
sort(event+1, event+n*m+Q+1);
for (ll it = 1; it <= n*m+Q; it++) {
ppll i = event[it];
ll idx = (i.r-1)*m + i.c;
if (i.id) {
ans[i.id] = (fnd(idx)-1)/m+1-1 + (fnd(idx)-1)%m+1-1;
}
else {
par[idx] = idx;
if (idx%m != 1 && par[idx-1]) {join(idx, idx-1);}
if (idx%m != 0 && par[idx+1]) {join(idx, idx+1);}
if (idx > m && par[idx-m]) {join(idx, idx-m);}
if (idx <= (n-1)*m && par[idx+m]) {join(idx, idx+m);}
}
}
for (ll i = 1; i <= Q; i++) {cout << ans[i] << " ";} cout << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
Thank you, alfio_kaloko, for making the question. As I write this comment 7 months after the name of this problem was decided, congrats on getting with her and sorry because it was just not meant to be. LOL
We need to play exactly $$$m$$$ games.
Assume it is optimum for Mr. Sawit to end at game $$$i$$$, Mr. Sawit's previous game must be from $$$i-1$$$ to $$$i-k$$$. Assume it is optimum to pick game $$$j$$$ as the previous game. How should we handle the previous game?
If we pick game $$$j$$$, then the next previous game must be from $$$j-1$$$ to $$$j-k$$$. However, we only need to play exactly $$$m-1$$$ games now because we already know that we will play game $$$i$$$.
Hint 1 is actually just a possible thought process that can be evolved further.
There exists a recurrence of handling games. The only conditions are the games that we can take previously and the amount of games we must take. This means we can use DP.
Define $$$dp[i][j]$$$ as the maximum satisfaction where Mr. Sawit plays game $$$i$$$ and has now played $$$j$$$ games. The transition can be defined as $$$dp[i][j] = max(dp[i-1][j-1], dp[i-2][j-1], ..., dp[i-k][j-1])+a[i]$$$.
To optimize the max function, we can use maximum sliding window using monotonic deque, priority queue, etc.
Time complexity: $$$O(n)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define ppll pair<pll, pll>
#define fi first
#define se second
#define vl fi
#define id se
const ll mod = 1e9+7;
ll test, n, m, k, x, a[1001], pbt, ans;
ll dp[1001][1001];
deque<ll> dq;
void solve() {
//begin!!
ans = -1e16; pbt = 0;
cin >> n >> m >> k >> x;
for (ll i = 1; i <= n; i++) {cin >> a[i]; for (ll it = 0; it <= m; it++) {dp[i][it] = -1e16;}}
for (ll it = 1; it <= m; it++) {
dq.push_back(it-1);
for (ll i = it; i <= n; i++) {
while (!dq.empty() && dq.front() < i-k-1) {dq.pop_front();}
dp[i][it] = a[i] + dp[dq.front()][it-1];
while (!dq.empty() && dp[dq.back()][it-1] <= dp[i][it-1]) {dq.pop_back();}
dq.push_back(i);
}
while (!dq.empty()) {dq.pop_back();}
}
for (ll i = m; i <= n; i++) {ans = max(ans, dp[i][m]);}
cout << ans << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
Whenever there is a problem using some bitwise operation, it is always wise to consider handling per bit.
It only asks for the bitwise AND of all games to be at least $$$x$$$. For all numbers from $$$x$$$ up until some number, try writing the binary version of each number. Why do these binary numbers work?
Because there exists a bit, such that all bits before are the same as the bits in $$$x$$$, and this bit is $$$1$$$ while this bit in $$$x$$$ is $$$0$$$.
Define $$$dp[i][j]$$$ as the maximum satisfaction where Mr. Sawit plays game $$$i$$$ and has now played $$$j$$$ games. The transition can be defined as $$$dp[i][j] = max(dp[i-1][j-1], dp[i-2][j-1], ..., dp[i-k][j-1])+a[i]$$$.
To optimize the max function, we can use maximum sliding window using monotonic deque, priority queue, etc.
To handle the requirement of the bitwise AND of all games to be at least $$$x$$$, we can repeat the DP process, such that no matter how the games are played, the requirement is handled. We can start from a bit that is $$$0$$$ in $$$x$$$ and turn on all games such that their prefix binary up until this bit is the same as in $$$x$$$ and the current bit is $$$1$$$. We find all other cases of this possibility plus if we only use $$$x$$$. Then we take the maximum out of all those possibilities.
Time complexity: $$$O(nlogn)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
const ll mod = 1e9+7;
ll test, n, m, k, x, a[1001], pbt, ans;
ll dp[1001][1001];
deque<ll> dq;
void solve() {
//begin!!
ans = -1e16; pbt = 0;
cin >> n >> m >> k >> x;
for (ll i = 1; i <= n; i++) {cin >> a[i]; for (ll it = 0; it <= m; it++) {dp[i][it] = -1e16;}}
for (ll bt = 30; bt >= 0; bt--) {
pbt += (1<<bt);
if ((x & (1<<bt))) {continue;}
for (ll it = 1; it <= m; it++) {
dq.push_back(it-1);
for (ll i = it; i <= n; i++) {
dp[i][it] = -1e16;
while (!dq.empty() && dq.front() < i-k-1) {dq.pop_front();}
if (dq.empty()) {break;}
if ((a[i]&pbt) != pbt) {continue;}
if (dp[dq.front()][it-1] > -1e16) {dp[i][it] = a[i] + dp[dq.front()][it-1];}
while (!dq.empty() && dp[dq.back()][it-1] <= dp[i][it-1]) {dq.pop_back();}
dq.push_back(i);
}
while (!dq.empty()) {dq.pop_back();}
}
for (ll i = m; i <= n; i++) {ans = max(ans, dp[i][m]); dp[i][m] = -1e16;}
pbt -= (1<<bt);
}
for (ll it = 1; it <= m; it++) {
dq.push_back(it-1);
for (ll i = it; i <= n; i++) {
dp[i][it] = -1e16;
while (!dq.empty() && dq.front() < i-k-1) {dq.pop_front();}
if (dq.empty()) {break;}
if ((a[i]&pbt) != pbt) {continue;}
if (dp[dq.front()][it-1] > -1e16) {dp[i][it] = a[i] + dp[dq.front()][it-1];}
while (!dq.empty() && dp[dq.back()][it-1] <= dp[i][it-1]) {dq.pop_back();}
dq.push_back(i);
}
while (!dq.empty()) {dq.pop_back();}
}
for (ll i = m; i <= n; i++) {ans = max(ans, dp[i][m]);}
if (ans == -1e16) {cout << "-1\n"; return;}
cout << ans << "\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
Thank you, faizxyz, for making subtask 1 and originating the question. As AI (olympiad of AI) buddies, hope to get a medal together.
Remember that the restriction turns the question into an offline query question.
Remember that this problem H is actually just a stronger problem A. Maybe an observation from problem A can help?
The GCD of a subarray will never increase.
To what extent does the GCD of a subarray then decrease?
The critical observation is that the GCD of a subarray cannot increase, but also that the GCD of a subarray cannot decrease many times. For a GCD of a subarray to decrease, we must erase a single factor from that GCD. The maximum amount of factors that can be erased for some number under $$$x$$$ would be the highest power of two that is under $$$x$$$. Therefore, the maximum amount of times a is only $$$logn$$$.
Let's imagine all subarrays from $$$(1, i)$$$, $$$(2, i)$$$, .. $$$(i-1, i)$$$. Because there are many values that have the same value, we can imagine them as ranges. From the observation above, there are a maximum amount of $$$log$$$ $$$n$$$ ranges.
For this restriction, we can use offline query and sort based off $$$r$$$. Lets say we had the answer from the ranges $$$(1, i)$$$, $$$(2, i)$$$, .. $$$i-1, i$$$. If we want to extend each range to $$$i+1$$$, for some range $$$j$$$, we can add all GCD of the subarrays from $$$(j, i+1)$$$, $$$(j+1, i+1)$$$, ... $$$(i, i+1)$$$. To optimize this, we can use the range observation and range update segment tree.
Time Complexity: $$$O(nlog$$$ $$$n)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
#define vl fi
#define id se
const ll mod = 1e9+7;
ll test, n, a[200001], psum[200001], Q, typ, lef, rig, cur, sz;
vector<pll> event[200001]; ll ans[10001];
vector<pll> rng[200001];
struct Seg{
ll cnt;
Seg() {cnt = 0;}
};
Seg merge(Seg l, Seg r) {
Seg res;
res.cnt = l.cnt+r.cnt;
return res;
}
Seg seg[200001*6], laze[200001*6];
void propogate(ll nd, ll le, ll ri) {
laze[2*nd] = merge(laze[2*nd], laze[nd]); laze[2*nd+1] = merge(laze[2*nd+1], laze[nd]);
seg[nd].cnt += laze[nd].cnt*(ri-le+1); laze[nd] = Seg(); return;
}
void cstruct(ll nd, ll l, ll r) {
laze[nd] = Seg();
if (l == r) {seg[nd] = Seg(); return;}
cstruct(2*nd, l, (l+r)/2);
cstruct(2*nd+1, (l+r)/2+1, r);
seg[nd] = merge(seg[2*nd], seg[2*nd+1]);
return;
}
void upd(ll nd, ll l, ll r, ll le, ll ri, ll vlue) {
propogate(nd, l, r);
if (l > ri || r < le) {return;}
if (le <= l && r <= ri) {laze[nd].cnt += vlue; propogate(nd, l, r); return;}
upd(2*nd, l, (l+r)/2, le, ri, vlue);
upd(2*nd+1, (l+r)/2+1, r, le, ri, vlue);
seg[nd] = merge(seg[2*nd], seg[2*nd+1]);
return;
}
Seg read(ll nd, ll l, ll r, ll le, ll ri) {
propogate(nd, l, r);
if (l > ri || r < le) {return Seg();}
if (le <= l && r <= ri) {return seg[nd];}
return merge(read(2*nd, l, (l+r)/2, le, ri), read(2*nd+1, (l+r)/2+1, r, le, ri));
}
void solve() {
//begin!!
cin >> n;
for (ll i = 1; i <= n; i++) {cin >> a[i]; psum[i] = psum[i-1]+a[i]; event[i].clear(); rng[i].clear();}
cstruct(1, 1, n);
cin >> Q;
for (ll i = 1; i <= Q; i++) {cin >> typ >> lef >> rig; event[rig].pb({lef, i});}
for (ll rig = 1; rig <= n; rig++) {
cur = a[rig]; rng[rig].pb({cur, rig});
sz = rng[rig].size()-1;
for (ll i = 0; i < (ll)rng[rig-1].size(); i++) {
if (cur == __gcd(cur, rng[rig-1][i].vl)) {continue;}
upd(1, 1, n, rng[rig-1][i].id+1, rng[rig][sz].id, rng[rig][sz].vl);
cur = __gcd(cur, rng[rig-1][i].vl); rng[rig].pb({cur, rng[rig-1][i].id});
sz = rng[rig].size()-1;
}
upd(1, 1, n, 1, rng[rig][sz].id, rng[rig][sz].vl);
for (pll i : event[rig]) {ans[i.id] = read(1, 1, n, i.vl, rig).cnt-(psum[rig]-psum[i.vl-1]);}
}
for (ll i = 1; i <= Q; i++) {cout << ans[i] << "\n";}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
With the addition of type 1, this becomes an obvious segment tree question.
Using the critical observation, how would we merge two segments?
The critical observation is that the GCD of a subarray cannot increase, but also that the GCD of a subarray cannot decrease many times. For a GCD of a subarray to decrease, we must erase a single factor from that GCD. The maximum amount of factors that can be erased for some number under $$$x$$$ would be the highest power of two that is under $$$x$$$. Therefore, the maximum amount of times a is only $$$logn$$$.
Let's imagine all subarrays from $$$(1, i)$$$, $$$(2, i)$$$, .. $$$(i-1, i)$$$. Because there are many values that have the same value, we can imagine them as ranges. From the observation above, there are a maximum amount of $$$log$$$ $$$n$$$ ranges.
However, because we must handle point updates, we must use segment tree. Define $$$cnt[l][r]$$$ as the sum of the GCD of all subarrays within a range $$$l$$$ and $$$r$$$. To calculate $$$cnt[l][r]$$$ for a segment with range $$$l$$$ and $$$r$$$, we can sum up $$$cnt[l][mid]$$$ + $$$cnt[mid+1][r]$$$. However, there are still the subarrays that exist in both segments. To calculate those subarrays, we can use suffix and prefix GCD to calculate.
For each segment, we keep 3 values, $$$cnt$$$, $$$preGCD[]$$$ and $$$sufGCD[]$$$. To merge, we can count for all pairs $$$sufGCD$$$ and $$$preGCD$$$.
Time complexity: $$$O(nlog^2n + qlog^3n)$$$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define fi first
#define se second
#define vl fi
#define amo se
const ll mod = 1e9+7;
ll test, n, a[200001], Q, typ, u, v, lef, rig, cur, sz;
vector<pll> empt;
struct Seg{
ll cnt;
vector<pll> pgcd, sgcd;
Seg() {cnt = 0; pgcd = sgcd = empt;}
};
Seg merge(Seg l, Seg r) {
Seg res = Seg();
if (l.pgcd.empty() && r.pgcd.empty()) {return Seg();}
if (l.pgcd.empty()) {return r;}
if (r.pgcd.empty()) {return l;}
res.cnt = l.cnt+r.cnt;
for (pll i : l.sgcd) {
for (pll j : r.pgcd) {
res.cnt += __gcd(i.vl, j.vl)*i.amo*j.amo;
}
}
res.pgcd = l.pgcd;
for (pll i : r.pgcd) {
sz = res.pgcd.size()-1;
if (res.pgcd[sz].vl == i.vl) {res.pgcd[sz].amo += i.amo;}
else {res.pgcd.pb({__gcd(res.pgcd[sz].vl, i.vl), i.amo});}
}
res.sgcd = r.sgcd;
for (pll i : l.sgcd) {
sz = res.sgcd.size()-1;
if (res.sgcd[sz].vl == i.vl) {res.sgcd[sz].amo += i.amo;}
else {res.sgcd.pb({__gcd(res.sgcd[sz].vl, i.vl), i.amo});}
}
return res;
}
Seg seg[200001*5];
void cstruct(ll nd, ll l, ll r) {
if (l == r) {seg[nd] = Seg(); seg[nd].pgcd.pb({a[l], 1}); seg[nd].sgcd.pb({a[l], 1}); return;}
cstruct(2*nd, l, (l+r)/2);
cstruct(2*nd+1, (l+r)/2+1, r);
seg[nd] = merge(seg[2*nd], seg[2*nd+1]);
return;
}
void upd(ll nd, ll l, ll r, ll indx, ll vlue) {
if (l > indx || r < indx) {return;}
if (indx <= l && r <= indx) {seg[nd] = Seg(); seg[nd].pgcd.pb({vlue, 1}); seg[nd].sgcd.pb({vlue, 1}); return;}
upd(2*nd, l, (l+r)/2, indx, vlue);
upd(2*nd+1, (l+r)/2+1, r, indx, vlue);
seg[nd] = merge(seg[2*nd], seg[2*nd+1]);
return;
}
Seg read(ll nd, ll l, ll r, ll le, ll ri) {
if (l > ri || r < le) {return Seg();}
if (le <= l && r <= ri) {return seg[nd];}
return merge(read(2*nd, l, (l+r)/2, le, ri), read(2*nd+1, (l+r)/2+1, r, le, ri));
}
void solve() {
//begin!!
cin >> n;
for (ll i = 1; i <= n; i++) {cin >> a[i];}
cstruct(1, 1, n);
cin >> Q;
while (Q--) {
cin >> typ;
if (typ == 1) {
cin >> u >> v;
upd(1, 1, n, u, v);
}
else {
cin >> lef >> rig;
cout << read(1, 1, n, lef, rig).cnt << '\n';
}
}
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
/*
g++ -o code codeforces.cpp
*/
Thank you, Neu2daysago, for creating an incorrect solution for subtask 1 for me to be confused about it for an hour straight when it was simply me forgetting to reset the lazy propagation between testcases. And (I'm guessing you read all of it), thank you for reading this. It might've not been helpful, but I'm happy that my work isn't completely useless. And even though there were some (extremely) stressfull moments, I had fun.
Also, if any of these problems have a wrong solution / editorial is weird, please comment below.
