A — Burenka Plays with Fractions
Authors: glebustim
Note that we always can make fractions equal in two operations: Multiply first fraction's enumerator by $$$bc$$$, the first fraction is equal to $$$\frac{abc}{b} = ac$$$, Multiply second fraction's enumerator by $$$ad$$$, the second fraction is equal to $$$\frac{acd}{d} = ac$$$.
That means that the answer does not exceed 2.
If fractions are equal from input, the answer is 0. Otherwise, it can't be 0.
Now we have to check if the answer is 1. Let's assume that for making fractions equal in 1 operation we have to multiply first fraction's enumerator by $$$x$$$. Then $$$\frac{ax}{b} = \frac{c}{d}$$$ must be true. From this we can see that $$$x = \frac{bc}{ad}$$$. $$$x$$$ must be integer, so $$$bc$$$ must be divisible by $$$ad$$$. If we assume that we multiplied first fraction's denumerator by $$$x$$$, we can do the same calculations and see that $$$ad$$$ must be divisible by $$$bc$$$. So, for checking if the answer is $$$1$$$ we need to check if one of $$$ad$$$ and $$$bc$$$ is divisible by another one. If we multiply second fraction's enumerator or denumerator by $$$x$$$ we will get the same conditions for answer being equla to 1.
If the answer is not 0 or 1, it's 2.
Complexity: $$$O(1)$$$
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define sfor(i, l, r) for (int i = l; i <= r; ++i)
#define bfor(i, r, l) for (int i = r; i >= l; --i)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
void solve() {
ll a, b, c, d;
cin >> a >> b >> c >> d;
ll x = a * d, y = b * c;
if (x == y)
cout << "0\n";
else if (y != 0 && x % y == 0 || x != 0 && y % x == 0)
cout << "1\n";
else
cout << "2\n";
}
int main() {
fast;
int t;
cin >> t;
while (t--)
solve();
}
B — Interesting Sum
Obviously, answer does not exceed $$$max_{1} + max_{2} - min_{1} - min_{2}$$$, where $$$max_{1}, max_{2}$$$ are two maximum values in the array, and $$$min_{1}, min_{2}$$$ are two minimum values. Let's find a segment, such as this is true. For that we will look at all positions containing $$$max_{1}$$$ or $$$max_{2}$$$ ($$$S_{1}$$$) and all positions containing $$$min_{1}$$$ or $$$min_{2}$$$ ($$$S_2$$$). After that we choose a pair $$$l \in S_1$$$, $$$r \in S_2$$$, such as $$$abs(r - l)$$$ is minimum possible. Complexity: $$$O(n\log n)$$$
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
vector<ll> vec;
ll n;
int main() {
fastInp;
ll t;
cin >> t;
while (t--) {
cin >> n;
vec.resize(n);
for (auto& c : vec) cin >> c;
sort(vec.begin(), vec.end());
cout << vec[n - 1] + vec[n - 2] - vec[0] - vec[1] << "\n";
}
return 0;
}
C — Corners
Authors: daubi
Let's say that $$$cnt_1$$$ is the number of ones in the table.
Note that if there is a connected area of zeros in the table of size at least 2, then we can add one $$$0$$$ to this area by replacing only one 1 in the table. That means that if we have such area we can fill the table with zeros in $$$cnt_1$$$ operations (we can't make more opertions because we need to replace at least one 1 by operation).
There can be no such area in the beginning, but after first operation it will appear. So, for finding the answer we just need to find an angle with minimal number of 1 in it, and which we can replace.
Complexity: $$$O(nm)$$$
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <cassert>
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <random>
#include <iomanip>
#include <chrono>
#include <bitset>
#include <queue>
#include <complex>
#include <functional>
using namespace std;
const int INF = 1e9;
const int MAXN = 2000;
int a[MAXN][MAXN];
inline void solve1() {
int n, m, sum = 0;
cin >> n >> m;
string s;
for (int i = 0; i < n; ++i) {
cin >> s;
for (int j = 0; j < m; ++j) {
a[i][j] = s[j] - '0';
sum += a[i][j];
}
}
int minn = INF;
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < m - 1; ++j) {
int cnt = a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1];
if (cnt == 0) continue;
minn = min(minn, max(1, cnt - 1));
}
}
if (sum == 0) cout << "0\n";
else cout << 1 + sum - minn << "\n";
}
signed main() {
int t = 1;
cin >> t;
while (t--) {
solve1();
}
}
D1 — Xor-Subsequence (easy version)
Authors: kirill.kligunov
Let's use dynamic programming to solve this task. $$$dp_i$$$ -- maximum length of good subsequence, that ends int $$$i$$$-th element of $$$a$$$, than naive solution is
Let's observe that $$$a_j \oplus i$$$ changes $$$i$$$ not more than by $$$200$$$.
This way we can relax $$$dp_i$$$ not from $$$j = 0$$$, but $$$j = i - 512$$$, because xor operation changes only last 8 bits, so for $$$j' < i - 512$$$, definitely $$$a_{j'} \oplus j > a_{j} \oplus j'$$$.
Additional idea:
It not so hard to proove that we can try $$$j$$$ from $$$i - 256$$$ to $$$i - 1$$$.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
vector<ll> vec;
ll n;
const ll CHECK = 512;
int solve() {
cin >> n;
vec.resize(n);
for (auto& c : vec) cin >> c;
vector<ll> dp(1);
ll bst = 0;
for (int i = 0; i < n; i++) {
ll cur = 0;
dp.push_back(1);
for (int j = i - 1; j >= max(0ll, i - CHECK); j--) {
if ((vec[i] ^ j) > (vec[j] ^ i)) {
dp.back() = max(dp.back(), dp[j + 1] + 1);
}
}
bst = max(bst, dp.back());
}
cout << bst << "\n";
return 0;
}
int main(){
fastInp;
int t;
cin >> t;
while(t--) solve();
}
D2 — Xor-Subsequence (hard version)
Authors: kirill.kligunov
Let's calculate answer for each prefix. Let's find answer if the last number in our subsequence is number with index $$$i$$$.
Let there be such $$$j$$$ that $$$a[j] \oplus i < a[i] \oplus j $$$. That means that there are $$$k$$$ bits in numbers $$$a[j] \oplus i$$$ and $$$a[i] \oplus j$$$ which are the same, and after that $$$a[j] \oplus i$$$ has different $$$k + 1$$$-th bit. Let's notice that if first $$$k$$$ bits are the same in $$$a[j] \oplus i$$$ and $$$a[i] \oplus j$$$, then these bits are the same in $$$a[j] \oplus j$$$ and $$$a[i] \oplus i$$$
Let's keep our answer in bit trie. We will add numbers $$$a[j] \oplus j$$$ for our prefix. To find dp value for index $$$i$$$, we will descend in our trie with pair of integers $$$a_i \oplus i$$$ and $$$i$$$. Each time we descend with bit $$$l$$$(0 or 1), in the opposite subtree there might be numbers which we can use to recalculate our answer. If in that subtree exists indexс $$$j$$$, then $$$k+1$$$-th bit of $$$a[j] \cdot i$$$ to $$$0$$$. Let's keep such dp for every subtree: maximum value of $$$dp[j]$$$ for every $$$j$$$, such that $$$j$$$ lies in the subtree (but we need to keep answer if $$$k$$$-th bit of $$$j$$$ is 0, and if it's equals 1). We should try to improve our answer using $$$j$$$ if we descend to the opposite subtree. Then we can easily find answer for current $$$i$$$. After that we only need to add our number in the trie and recalculate the dp.
Complexity: O(n * logC) where C its max value
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxlog = 30;
const int maxn = 300000;
int nodes[maxn * maxlog + maxlog][2];
int nodev[maxn * maxlog + maxlog][2];
int last;
inline int f() {
nodes[last][0] = 0;
nodes[last][1] = 0;
nodev[last][0] = 0;
nodev[last][1] = 0;
return last++;
}
int solve() {
int n;
cin >> n;
vector <int> v(n);
for (auto& i : v) cin >> i;
int ans = 0;
last = 0;
f();
for (int i = 0; i < n; i++) {
int a = 0;
int b = v[i] ^ i;
int c = i;
int getmax = 0;
for (int j = maxlog; j >= 0; j--) {
if (nodes[a][((b >> j) & 1) ^ 1]) getmax = max(getmax, nodev[nodes[a][((b >> j) & 1) ^ 1]][(((b ^ c) >> j) & 1) ^ 1]);
if (!nodes[a][(b >> j) & 1]) break;
a = nodes[a][(b >> j) & 1];
}
ans = max(ans, getmax + 1);
a = 0;
b = v[i] ^ i;
c = i;
int d = getmax + 1;
for (int j = maxlog; j >= 0; j--) {
if (!nodes[a][(b >> j) & 1]) nodes[a][(b >> j) & 1] = f();
nodev[nodes[a][(b >> j) & 1]][(c >> j) & 1] = max(nodev[nodes[a][(b >> j) & 1]][(c >> j) & 1], d);
a = nodes[a][(b >> j) & 1];
}
}
cout << ans << "\n";
return 0;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
E — Misha and Paintings
Authors: daubi, pakhomovee
If $$$k$$$ is greater than the number of different numbers in the matrix, then the answer is $$$k$$$ minus the number of different elements.
Otherwise the answer does not exceed 2.
Let's proof that: choose the maximum square (let its side be equal to $$$L$$$), containing the top left corner of the matrix, such as recolouring it to some new colour makes the number of different colours in the table at least $$$k$$$.
If the number of different colours after recolouring is greater than $$$k$$$, then choose a square with bottom right corner in $$$(L + 1, L + 1)$$$, such as recolouring it makes the number of different colours at least $$$k$$$. If we got exactly $$$k$$$ colours then we are done. Otherwise let's extend the square by one. We got $$$k$$$ or $$$k - 1$$$ different colours. This way, by choosing the correct colour of the square we can get exactly $$$k$$$ colours. Otherwise we are done.
It remains to learn how to check whether the answer is equal to 1. We will iterate over length of the side of the square of the answer. Now we need $$$O(n^2)$$$ to check whether the required square with such a side exists. To do this, we calculate for each square in the table with such a side length (there are $$$n^2$$$ such squares), how many numbers this square completely covers (all appeareances of this numbers are in thsi square). To do this, let's iterate over the number $$$c$$$. Having considered its occurrences, it is easy to understand that the upper left corners of all squares with our side length, covering all cells with the number $$$c$$$, lie in some subrectangle of the table, so you can simply add 1 on this subrectangle using offline prefix sums. Having processed all the numbers in this way, we can count for each square how many numbers it covers completely, and therefore check whether it fits the requirements.
Complexity: $$$O(n^3)$$$
#include <iostream>
#include <vector>
#include <cmath>
#include <array>
using namespace std;
const int INF = 1e9;
inline int min(int a, int b) {
if (a < b) return a;
return b;
}
inline int max(int a, int b) {
if (a > b) return a;
return b;
}
inline void solve1() {
int n, k, cnt = 0;
cin >> n >> k;
vector <vector <int>> a(n, vector <int>(n)), pref(n + 1, vector <int>(n + 1));
vector <array <int, 4>> all(n * n, { INF, -INF, INF, -INF });
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> a[i][j]; --a[i][j];
all[a[i][j]][0] = min(all[a[i][j]][0], i);
all[a[i][j]][1] = max(all[a[i][j]][1], i);
all[a[i][j]][2] = min(all[a[i][j]][2], j);
all[a[i][j]][3] = max(all[a[i][j]][3], j);
}
}
for (auto& i : all) {
if (i[0] != INF) ++cnt;
}
if (cnt <= k) {
cout << k - cnt;
return;
}
for (int len = 1; len <= n; ++len) {
for (auto& i : all) {
if (i[0] == INF) continue;
int mn_x = i[0], mx_x = i[1], mn_y = i[2], mx_y = i[3];
mx_x = max(0, mx_x - len + 1);
mx_y = max(0, mx_y - len + 1);
mn_x = min(mn_x, n - len);
mn_y = min(mn_y, n - len);
if (mx_x <= mn_x && mx_y <= mn_y) {
++pref[mx_x][mx_y];
--pref[mx_x][mn_y + 1];
--pref[mn_x + 1][mx_y];
++pref[mn_x + 1][mn_y + 1];
}
}
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (x == 0 && y == 0) continue;
else if (x == 0) pref[x][y] += pref[x][y - 1];
else if (y == 0) pref[x][y] += pref[x - 1][y];
else pref[x][y] += pref[x - 1][y] + pref[x][y - 1] - pref[x - 1][y - 1];
}
}
for (int x = 0; x < n; ++x) {
for (int y = 0; y < n; ++y) {
if (cnt - pref[x][y] == k || cnt - pref[x][y] + 1 == k) {
cout << 1;
return;
}
}
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
pref[i][j] = 0;
}
}
}
cout << 2;
}
int main() {
if (1) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
if (1) {
int t = 1;
// cin >> t;
while (t--) {
solve1();
}
}
return 0;
}
We are sorry for statement of problem D being unclear :( We will do our best to write cleaner and easier to understand statements next time! We hope you enjoyed solving our problems though.
But this problem is really good!
Thank you!
Hey, thanks for the round. The problems were definitely enjoyable!
Just to clarify, the statement was not unclear, it was wrong. On top of trying to write cleaner and easier statements, please update statements during the contest if it is pointed out as wrong.
Thanks, hoping to see more rounds from you!
Why was it wrong?
I don't think it was wrong.
Maybe the word subsequence can mislead someone, but there is no scientific mistakes in the statement.
The use of "subsequence" was wrong.
It is mentioned that array $$$b$$$ is a subsequence of array $$$a$$$. But this is not the case. $$$b$$$ is a subsequence of $$$[0, 1, 2,..., n-1]$$$.
I'm not complaining about the problem being not understandable. If you read the statement and examples, you understand what $$$b$$$ actually is.
I'm just saying that not fixing an obvious mistake after being pointed out is a bit insincere.
You thought the use of "subsequence" was wrong, just because you have believed that:
if you use the word "subsequence" and say that an array $$$b$$$ is a subsequence of $$$a$$$, then the objects in $$$b$$$ must occur in $$$a$$$.
and the definition is opposite your normal comprehension of the word "subsequence".
But the statement gave us a different definition of "subsequence", then no wonder how the definition was odd, the following description with the word "subsequence" must obey the definition.
In the statement, it said that an array $$$b$$$ is a subsequence of $$$a$$$ means that:
$$$0 \le b_0 \le b_1 \le ... \le b_{m-1} < n$$$
and the following statements did not conflict with this definition, so you can say the definition is trash and not understandable, but you can't say it is wrong.
I'm just saying that the statement wasn't scientifically wrong even if it is not understandable.
I know the word subsequence normally means picking some values in a. And I even didn't see any usage of subsequence that means picking some indexes.
But I want to say, if the problem provider explicitly redefinite a word, then he has the right to use this word to express a different idea in his problem.
Just like you can overload operators in your code, and use it in your meaning of the operators. This operator has normal meaning, but in this code, what it means depends on how you definite it.
Why downvotes while I am explaining reasonably? I don't understand.
How could you come up with "statement gave us a different definition of 'subsequence'"? If you choose numbers in $$$a$$$ which satisfy $$$a_i \leq n$$$, you can still get $$$0 \leq b_i < b_{i+1} \leq n$$$. Maybe by your standards, ambiguity doesn't affect correctness?
Yes, you can choose numbers in $$$a$$$ which satisfy $$$a_i \le n$$$. But how it matters?
The statement is pretty clear that you can pick such $$$b$$$ only if $$$a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$$$.
Maybe you don't know even basic logic, the statement didn't say that you have to pick numbers within $$$a$$$, but if you want to pick numbers within $$$a$$$ which satisfy the condition, that's OK.
It's just the difference between sufficient condition and necessary condition. It's not ambiguity.
I hope you can understand.
Just look at the statement, and tell me what two sentences conflicts, which means wrong. If there is no such sentences, don't say it is wrong.
if you want to pick numbers within a which satisfy the condition, that's OK
No, it's OBVIOUSLY not OK. You can only choose one of them: pick it from $$$a$$$, or pick it from indexes of $$$a$$$. If statements don't declare which one you should choose, it's totally ambiguous. Again, if you think ambiguity is not wrong, that's good for you.
Seems that you can't understand what a "definition" is.
Let me give you an example that probably helps you understand:
I can definite a diameter of a graph which means the length of the longest chain in the graph.(normal version)
I can also definite a diameter of a graph which means the length of an edge which is the longest of all shortest path between any two vertexes.(definition in 1712D - Пустой граф)
See? We can definite the same word in two different situations, and you didn't say that 1712D - Пустой граф was wrong, right?
Same for this problem.
In the normal sight, a subsequence of $$$a$$$ is a set which contains some of the numbers in $$$a$$$.
In this problem, a subsequence of $$$a$$$ is a set which doesn't matter with $$$a$$$.(You can understand it as $$$index$$$ of $$$a$$$, but actually it is just a set of numbers which satisfy the definition $$$0 \le b_0 \le...\le b_{m-1 }< n$$$.)
And you can use the set of numbers to do something: use $$$a_{b_p} \oplus b_{p+1}$$$ to compare with $$$a_{b_{p+1}}⊕b_p$$$.
But it is just a usage of this set of numbers, it doesn't means that $$$b$$$ was born to be a sequence of index of a. No one claims that, it is just your guess.
So understand? the definition of Subsequence in this problem is OBVIOUSLY not AMBIGUOUS. It is not AMBIGUITY. It just mislead you and other participants, but it's pretty clear that you are misleaded badly because you just can't understand what a definition is.
it doesn't means that b was born to be a sequence of index of a. No one claims that, it is just your guess.
lmao. If it's my gusee, then where's the defination of the special meaning of subsequense in this statement?
By the way, shouldn't you google what "ambiguous" means first before you reply me?
where's the defination of the special meaning of subsequense in this statement
An array b=[b0,b1,…,bm−1], where 0≤b0<b1<…<bm−1<n, is a subsequence of length m of the array a.
Here. You can find it in the statement.
By the way, If you are too lazy to look again at the statement, then don't tell me to GOOGLE the definition of a word that I understand much better than you.
Also, your words of "choosing" one of the normal definitions in your mind and sight is absolutely ridiculous and absurd.
The word subsequence implies that you are only allowed to pick values in a. When one looks at the examples it is clear that this isn't what it meant, but it is what it said. The condition on these values restricts which values you can pick (they have to be increasing and less than n).
If one interprets the text of the problem literally, the only acceptable subsequence in example 1 would be [1] (which is trivially beautiful) so the answer to example 1 would be 1.
Seems that you still don't understand what I am saying.
I know the word subsequence normally means picking some values in $$$a$$$. And I even didn't see any usage of subsequence that means picking some indexes.
But I want to say, if the problem provider explicitly redefinite a word, then he has the right to use this word to express a different idea in his problem.
Just like you can overload operators in your code, and use it in your meaning of the operators. This operator has normal meaning, but in this code, what it means depends on how you definite it.
The issue is that there are two ways of reading the sentence:
It can be read either as a definition of a subsequence, or as simply a definition of b.
If read as a definition of "b" it means:
The word order implies that it is defining "b", not "subsequence". "X is a Y" is normally telling you about "X" not about "Y"; particularly if it is the first time X has been mentioned, and Y is already well known.
No doubt it is a definition of a subsequence.
Let me simplify the sentence:
b which satisfy (condition) is a subsequence of length m of the array a.
Haven't you ever saw this kind of definitions?
An array b is a permutation of an array a if b consists of the elements of a in arbitrary order. For example, [4,2,3,4] is a permutation of [3,2,4,4] while [1,2,2] is not a permutation of [1,2,3].
It defines what a permutation is, not what b is.
The difference between "where" and "if" matters.
Consider:
vs.
The first is telling you that all reks are fafis, but that a fafi is a rek if and only if the top is red, the second is telling you all reks with red tops are fafis, and may be defining fafi. There may, however, be other reks with green tops that are not fafis.
The difference between "where" and "if" sure matters.
but you just ignored the word order.
look at the following two sentences:
an array a, where (condition), is a xxx of b.vs.
an array a is a xxx of b where (condition).The first is telling you that a is an array, and if the array fits (condition), it is a xxx.
The second is telling you that a is an array, and also it is a xxx, which also fits (condition).
Same as this sentence.
An array b=[b0,b1,…,bm−1], where 0≤b0<b1<…<bm−1<n, is a subsequence of length m of the array a.No it doesn't. It says that this is a condition on the subsequence. Consider the sequence
a = [1,5,2.3.7]
a valid subsequence satisfying the condition would be: [1,2,3]
[0,1,2,3,4] would not be a valid subsequence of a since 0 and 4 aren't in a, so it isn't a subsequence of a.
[1,5,2] is a subsequence of a, but would not satisfy the condition.
The point is that b is not a subsequence of a, it is a subsequence of the indecies of a. It took me two readings of the problem to realise that the term subsequence was not being used with its normal meaning.
The problem would have been clearer if it had simply said:
Never mind, the whole contest is really enjoyable, and the problems are interesting (I like C and D1 best).
My solution to the misunderstood version of D1 has come out. The link is out there. :)
Can anyone solve the misunderstood version of D2? I can't figure out. qaq
Hey , Can u help me understand how can we prove that in D , we only need to check from i-256 to i-1 ?
Observation forces
very fitting handle for today's contest
thanks for fast editorial)
A was a bit too tedious for a task in such a place, and I think many contestants today gave up completely because they cannot finish A.
All of the other problems are really nice, though.
Didn't gave up. Tried till last minute. Yet couldn't manage to solve A :V
I just quit A, and thankfully I solved C, which I usually dont do in a div 2
Deciding to quit before submitting A is not giving up, it is strategy.
I agree with you, I did this strategy in this contest.
I'm confused. In D1 Wouldn't i-256 also work, since it toggles the 9'th bit (which cannot be toggled by any number in the array).
I think it does, but 500 works as well and might be easier to see why.
i tought "xor 200 will add or subtract at most 200". So i went with 402 just to be sure. It feels like the most intuitive lower bound to me, but i didn't think about it too much
The best bound I could think of is i-2*max+1 (and it does not need to be the maximum of the entire array, just of the elements before and including the current one, from 0 to i):
If j < i-2*max+1, then j <= i-2*max and j^ai <= i-max <= i^aj. So, if j < i-2*max+1 we do not need to check this j.
But maybe this is not the best possible bound: I just manually binary-searched the problem and i-255 is accepted, i-254 is not.
This is correct. Technically, $$$i - 256$$$ and below are guaranteed to fail the condition (since the prefix before the last 8 bits cannot be XOR'd out), so you can start checking from $$$i - 255$$$ onwards.
In fact, you can do something more interesting — simply tile n in sections of 256 and solve each section separately.
168859265
In the solution of D2, an 'equal' is wrong spelled.
and if it's equels 1).We will fix it quickly. Thank you)
C was a nice problem
d1 and d2 are two good problem!
I can't get the editorial of Problem E. Is it too simple or poorly explained? Can somebody please explain the solution ?
There is a trivial case when the number of distinct values ($$$d$$$) is less than $$$k$$$. In that case we have to increase this value. So the best way to do is by doing $$$d - k$$$ operations of choosing $$$1 \times 1$$$ matrices and setting some values.
Now, if $$$d \ge k$$$, it can be proven that the answer is at max $$$2$$$. Let's prove it. Choose a submatrix of size $$$L$$$ from the top left corner such that colouring the entire submatrix to some new colour makes the new value of $$$d$$$ at least $$$k$$$. We will choose the maximum possible such $$$L$$$. Since $$$L$$$ is the maximum possible, if we increase it by even one more, we will end up getting $$$d < k$$$. This means that the extra row and extra column that we are adding by shifting from $$$L$$$ to $$$L + 1$$$ contains a some distinct values that makes the value of $$$d$$$ cross over $$$k$$$ in a big jump. We only need to change some of these values. So we are looking from small jump instead of this big jump.
So instead of changing these extra values from the top left, let's try to change them from the bottom right i.e. in our second operation we will choose a different submatrix such that it's bottom right corner lies at $$$(L, L)$$$ (the intersection of the row and column that makes all the difference). Notice, that we can tweak the size of this second operation submatrix to our own choice such that we can make a jump as close as possible to $$$k$$$. Increasing the length of this submatrix, can atmost create a difference of $$$2$$$ (one in row and one in column). So we can land our $$$d$$$ at $$$k$$$ or at $$$k - 1$$$. If we land at $$$k$$$, we're good to go but if we land at $$$k - 1$$$, we will still be good to go since, we can change the colour of this second operation to some new colour altogether which will increment our $$$d$$$ to $$$k$$$.
So it has been proven that we can obtain the final state in atmost two operations.
Let's first define a term I'll call complete coverage. A submatrix $$$S$$$ is said to completely cover a value $$$v$$$ if the complement of the submatrix (w.r.t. the original matrix) does not contain the value $$$v$$$ at all. Another term, I'll define is bounding box. The bounding box of a value is the smallest matrix that completely covers it.
Now, we have to find out whether we can get the answer in one operation or not else the answer will be two. For the one operation that we want to do, we can iterate over the length $$$len$$$ of the submatrix of the operation and check whether there exists a submatrix such that treating it as our operation gives us the final state. For each possible length, we can iterate over all the possible values in the matrix and figure out which submatrices of size $$$len$$$ will completely cover this value. If we find a submatrix which completely covers exactly $$$d - k$$$ or $$$d - k + 1$$$ values, we can do 1 operation on this submatrix and get the new value of $$$d$$$ to be equal to $$$k$$$. We can do this in $$$O(n^2)$$$ time using 2D Lazy Addition using Prefix Sums (explained below). So this gives a total of $$$O(n^3)$$$ time complexity.
For finding the number of complete coverages for each submatrix, what we can do is we can represent the submatrix firstly by just it's top-left cell. Now, for each value, we can calculate it's bounding box. We will use 2D Lazy Update on the extreme corners of this bounding box to add 1 (the submatrices of length $$$len$$$ that contain this bounding box have 1 more value completely covered). And then we can calculate 2D prefix sum to get the final number of complete coverages.
Submission
In Problem-B it's mentioned that you cannot take subsegment of length = n (r — l — 1 < n) but it is taking subsegment of length=n as a correct solution, please let me know if I am wrong.
In which test case ?
I don't know in which test case, but i am getting it wrong considering max length=n-1, and i have seen some correct solutions considering max length=n
u didn't take n size and the logic is simple behind it u just have to maximized last answer so for that reason u need only 4 index of sorted array first second last second last
then i will just select any of two index which doesn't have n size actually i can make it using r-l+1<=n-1 just think
1 6 2 1 3 6 10 9 In this case, to satisfy your condition we have to take subsegment with l=1 and r=6 which is not satisfying r-l+1<n. Please tell me where am i getting it wrong? Thanks
Oh sorry, got it I misunderstood problem statement
also an answer in this case (n=8) is l=3,r=7, 7-3+1<8
The code for problem E in the Editorial is incorrect. Countertest:
Thanks for noticing! I posted correct solution.
Here we go, Thanks for the lightning fast editorial:)
kirill.kligunov bring a new word for our: subsequence, mean for index of some array.
Learn a lot from statement of problem D.
yeah D statement is really confusing
can anyone explain why we dont have to go beyond 256 for checking for a particular i... i am not able to get this by editorial
It's because when xoring a[i] with j, you will get j modified by maximum 8 bits (because a[i] <= 200), therefore you need to check only the last 256 to make it bigger than a[i] ^ j
I'm sorry, but I didn't get you, could you explain a bit further?
We have known that because $$$a[i],a[j]\leq 200$$$, so that utmost changes of j and i is 256. However, as j added 256 and i decreased 256, the gap between j and i was 512 in total.
The editorial said the it was correct as well despite you started j from i-256, which is beyond my comprehension. Could you please explain why, if in your comfort?
You have to see it as binary representation to understand it better.
You are now at position j, a[i] ^ j is gonna range between j and j — 256, because only the first 8 bits can change. Now you have to find this is i that satisfies the property that a[j] ^ i is bigger than a[i] ^ j. Because of what I said earlier, to achieve that the only posibilities of i are between j and j — 256.
Thanks for your reply.
Did it help you at least?
Could you explain it a bit more ?
What exactly?
a[j]⊕i changes i not more than by 200. This part in the editorial
visualize in binary to understand better
when xoring, all that matters are the set bits (1)
because you have a[i] <= 200 => a[i] can have 8 set bits (from 0th to 7th)
so when you are xoring i with a[j], only the last 8 bits change in the binary represation of i, if you convert those possible outcomes in base 10, you get a maxmum of 256
Of course. Thank you for your timely comment（and sorry for the time gap）！
However, what I really want to know is the following. In your clarification, you have explained a[i] ^ j is in range(j-256, j), and you concluded that thus " that the only posibilities of i are between j and j — 256"，but what about the i? a[j] ^ i makes it possible that i may increase 256 as well.(An obvious property is that $$$a-b \leq a \bigoplus b \leq a+b$$$), Then the maximum gap between a[i]^j and a[j]^i may be 512 instead of 256. The editorial said "it's not hard that we could prove j from i-256"(note that i and j have different meanings in your explanation and the editorial), which really confused me.
Thank you again for making such timely explanation and I'm looking forward to your further comments! :)
Because you are doing a[i] ^ j that is the boundary, because you habe to make a[i] ^ j < a[j] ^ i, because of that, the range of i is between j, j — 256 (the same observation applies here)
Get it. Thank you~
skytyf Can you explain it to me why it's not 512? how are we reaching 256?
I believed Sochu's clarification is one of the proof. To me, I understood it in this way:
（Please copy it into notepad to read more comfortably） If the gap between i and j is over 256, the last 9th digit of i and j in binary representation is bound to change by at least 1.(That is, the pattern of i and j in binary representation is like (1..M********)_2 and (1..(M-1)********)_2 [Of course we didn't consider the M=0 case because the reason is the same and '*' can be 0 or 1 arbitrarily] )
emphasis:We want to find a[j] ^ i < a[i] ^ j (when j<i) Suppose the case I raised above, why we didn't take the 512 into account?Let us consider why (i-512, i-257) definitely don't fit in the case. Due to the reason above, j in this range have the last 9th digit different from the i(or maybe 10th, 11th...), and a[i] <= 200, which is only have a (********)_2 format. And after a[j]^i a[i]^j，the last 9th digit didn't change, and then we reach that a[i] ^ j still less than a[j] ^ i(Because 9th digit is less), which didn't meet our condition.
So we just have to start j from i-256
https://codeforces.com/contest/1720/submission/168870933 can anyone pls tell whats wrong in this submission?
Maybe it's due to the floating-point error.
Try to compare
a * candb * dto comparea / bandc / d.Don't forget to use bigger data type such as
long long!Never use doubles and floats if you can avoid it.
Floating Point precision error. Try this test case:
It should return 1, since you need to multiply the first numerator by 0, but your code seems to print 0, because it incorrectly calculated the first fraction as 0 due to precision errors.
Didn't get the 'C' problem. Can anyone explain?
Suppose you have two 0s that are next to each other, either horizontally, vertically, or diagonally. Then either the entire matrix is filled with 0s, or there exists a 1 that can be covered by an L-piece that also covers 2 zeros. The nice thing is that even after covering this 1, the property must continue to hold, so there is another 1 that can be covered by a single L-piece that also covers 2 zeros, and so on. As a result, if there are $$$k$$$ 1s in the matrix, then we can perform $$$k$$$ operations to zero them all, covering exactly one 1 with each operation. Try this out with Sample Input #2.
But if you don't have two 0s aligned (horizontally, vertically or diagonally) at first, then you have to place the first piece in an area with two 1s (if a 0 exists), or in an area with three 1s (if there is no 0 at all initially). After that, however, the remaining 1s can be covered one at a time.
Basically: if there exists two 0s aligned horizontally/vertically/diagonally, then the answer is the number of 1s initially. Otherwise, if there exists at least one 0, then the answer is (number of 1s) minus 1. Otherwise, if there is no 0, then the answer is (number of 1s) minus 2.
Weak pretest for A, there wasn't even a test case in pretest with b==d and a and c being coprime, (or variant of it) and many answers got failed in system test due to that. I guess it is easy to have all such simple combinations for pretest., Especially for current A question.
I actually think this is a good thing for Problem A when the logic is actually simple, since it punishes those who try to speedsolve it without actually thinking properly about whether their answer is correct, while also rewarding the careful solvers with an opportunity to hack them.
I can understand the annoyance if it was a really tricky edge case, but for this one, the system tests that are destroying A submissions are stuff that the solver really should have considered before submitting, instead of being so impatient.
The point is pretest should represent minimum possible validation of correctness or trivial cases. And if the solution wrong, then penalty would do the job for wrong submission.
A and B harder than C ngl
I hate to say this but I believe the statement for B isn't clear enough. When I read the equation to determine beauty of subsegment, I thought it's max(a) — min(a) + max(a[l:r]) — min(a[l:r]). So my intuition to that problem is we want the subsegment to be as long as possible since we can include more elements for the max of the subsegment to be bigger and min to be smaller. So what I thought was that the answer max of max(a) — min(a) + max(a[1:n-1]) — min(a[1:n-1]) and max(a) — min(a) + max(a[2:n]) — min(a[2:n]). (Here [l:r] both sides are inclusive) But it turned out to be different and I still can't turn my head around that. Only reason why I got to the answer was deducing from the sample explanation.
The reason it's different is that your formula is slightly wrong. Instead of the max and min of a, the first two terms should be the max and min of a excluding the subsegment [l, r]. Notice that in the equation for a subsegment's beauty, in the first two terms, the indices jump from l-1 to r+1.
I succeeded to solve D2 using bit tree on two values: 168855514. I struggle to evaluate the complexity of this solution. Can somebody explain it to me? I guess there is some countertest for getting TLE
Yeah, same to you, except that I didn't implement this idea because of its confusing complexity. In normal Trie problem, we only need to choose one son (or we say direction) to go down. But here we might need to choose two out of four.
So one possible countertest is that: we sue the first half to construct a trie exclusively for one certain pattern. And then we repeat this pattern in the latter half so that we need to go through all the leaves in Trie constructed by first half.
Cool... problem set was good.
Didn't get the logic of i-512 in question D. Can anyone explain it in detail.
I think 400 is clearer. Because we need $$$a_{j}$$$ ^ $$$i$$$ < $$$a_{i}$$$ ^ $$$j$$$ with $$$i>j$$$ and $$$i,j$$$ is belong to the subseqenuce. We have $$$a_{} \le 200$$$，and operation xor can change the number +200 or -200 at most. So the extreme case is $$$i - 200 < j + 200$$$,then it is $$$j > i - 400$$$.
It means for each j we have to iterate till i-400?
It's just a easier solution for me. Its complexity is right. I learned we can use i-256 in this blog.
I do not understand the solution to D2. Are we solving for each prefix in order ? Is i the index of the last element of the prefix ? Is j the index of the element before it ? Are the k bits the k most significant bits or least significant bits ? Are the "answers" the length of the subsequences for each prefix ?
I have the same questions. The editorial is quite unclear and has some grammatically wrong sentences that are hard to comprehend. Please, in case you finally understand how to solve D2, share an explanation
I'm working on it. I would recommend to check -is-this-fft-'s submission.
Basically you are solving like the dp brute force. Because of the fact that a[i] ^ i has the same prefix of a[j] ^ j, you are trying to track it with a trie. Now if you traversed k bits, the k + 1'th bit should satisfy the property. Because of that you need to keep track in the trie the maximum answer which has the prefix of a[i] ^ i, between of all possible js, that has the k + 1 th bit of j and k + 1 th bit a[j]
Check my submission: https://codeforces.com/contest/1720/submission/168889011
Thanks for taking the time to explain !
I still do not understand, why would a[i]^i and a[j]^j have the same prefix ? What are those bits that we are traversing ? Which property are you talking about ?
There is a prefix which is equal in a[i] ^ j , and a[j] ^ i, now think of that prefix as a number: (imagine now that you have only the common prefix) a[i] ^ j = a[j] ^ i, xor it with j => a[i] = a[j] ^ j ^ i, xor it wity i => a[i] ^ i = a[j] ^ j
We are traversing the bits of a[i] ^ i, the only thing that remains is to satisfy the property, by tracking what I explained last
See my comment below, I explained it in more detail (Also the guy above my comment explained it well)
could someone explain c . editorial is not at all clear
https://codeforces.com/blog/entry/106136?#comment-944849
but in the question they mentioned that take L shape such that one square at corner is left .
I do not understand your remark.
If there are two zeroes in a 2 by 2 submatrix and at least a one is still present in the grid, you are certain to be able to remove a single one in a single step, by including two zeroes in the L shape. Thus the answer will be the number of one in the grid.
Otherwise, if there is at least one zero in the grid, you will be able to remove only two one in one step, by including a zero in the L shape. Then, you are left with the first case, so you just removed an extra one in the first step. The answer is the number of one in the grid, minus one.
Finally, if there are no zeroes in the grid, your first step will remove two extra ones. The answer will be the number of one in the grid, minus two.
can a[j]^i really reduce i by 256. I mean according to me, it can reduce it by 200 atmost. If it can, can you please give any example.
Would someone mind explaining to me why if x=bc/ad then bc must be divisible by ad in problem A
Because if bc/ad=x and x is an integer, then bc is divisible by ad by definition.
For $$$D2$$$, what I got from the editorial is that for each $$$i$$$ from $$$0$$$ to $$$n-1$$$ we will calculate $$$dp[i]$$$ which is the maximum size of a valid subset ending at $$$i$$$, then insert it into the trie by descending with value $$$a[i]\oplus i$$$.
My question is: While we are descending the trie to calculate $$$dp[i]$$$, if the $$$k^{th}$$$ bit is $$$0$$$ in $$$a[i]\oplus i$$$, we will descend in the left subtree but before that we want to know the best possible answer in the right subtree. So, we actually want the maximum value in the right subtree which corresponds to $$$j$$$ whose $$$k^{th}$$$ bit has a specific value (which will make $$$a[j]\oplus i < a[i]\oplus j$$$). How can we do this part?
note that since the prefix of the bitstrings of $$$a_i \oplus i$$$ and every other string in this specific subtree of the trie must be identical. as such, the kth bit should be the first one to differ. We also know that this bit is identical in $$$i$$$ and $$$a_i$$$(because $$$i \oplus a_i = 0$$$). So, if it is on in both we want a $$$j$$$ such that the kth bit is on in $$$a_j$$$(since this is the other subtree of the trie where $$$a_j \oplus j = 1$$$, this means that the kth bit is off in $$$j$$$ by default). Otherwise, if it is off in both then we want the kth bit in $$$a_j$$$ to be off. Similar casework can be done for all other configurations of $$$i$$$ and $$$a_i$$$. As such, for each node in the trie, we can keep track of the max $$$dp$$$ value where the kth bit in $$$a_j$$$ is on, and the max $$$dp$$$ value where the bit is off separately.
'We also know that this bit is identical in i and ai(because i⊕ai=0)' Can you explain how?
It's because the original question proposed travelling to the left subtree as an example for that bit
Suppose all the element idxs in the subtree you don't descend are {j1, ...}. If you are on the kth bit, you know for sure that the previous bits are equal, so the only important bit is the kth.
So you only need to save the max dp for j's with kth bit equal to 0, and another for j's with kth bit equal to 1
If kth bit of a[i] is 1, you'll need the answer for j with kth bit 0. If kth bit of a[i] is 0, you'll need the answer for j with kth bit 1.
Thanks all for your insights, they are appreciated.
Can someone explain D2 to me like I'm stupid? Because I couldn't quite understand the editorial after storing the answer in a bit trie and also because I pretty much am
We can build the longest subsequence iteratively by sweeping from $$$0$$$ to $$$n$$$ and finding the longest subsequence so far that our current index(lets call it $$$i$$$) can add on to. Naively, this is $$$dp$$$ solution is $$$O(n^2)$$$.
The main intuition behind the speedup to this problem is that, when comparing two numbers $$$a$$$ and $$$b$$$ in their binary representation, the only important digit $$$k$$$ is the first digit where they differ. Conveniently, there are only 30 possible values of $$$k$$$. This motivates us to use a binary trie that stores prefixes, and for each prefix we can keep track of the maximum $$$dp$$$ value where some bitstring with said prefix exists.
However, how do we know if for some digit $$$k$$$, the required configuration of $$$j$$$ and $$$a_j$$$ such that we satisfy the inequality $$$a_j \oplus i < a_i \oplus j$$$? Let's do some casework and see if that simplifies anything.
Case 1: $$$k$$$ is off in both $$$i$$$ and $$$a_i$$$.
In this case, to satisfy the inequality, we want the kth bit to be set in $$$a_i \oplus j$$$ but not $$$a_j \oplus i$$$, so the kth bit should be set in $$$j$$$ but not in $$$a_j$$$. We can then update $$$dp_i$$$ accordingly. To figure out which subtree of the trie we should descend to, note that the prefixes of $$$a_j \oplus i$$$ and $$$a_i \oplus j$$$ should remain identical, so we want the status of $$$k$$$ in $$$a_j$$$ and $$$j$$$ to be the same. This raises a little bit of a problem, since this is two subtrees that we must visit. For now, lets look at the other cases.
Case 2: $$$k$$$ is off in $$$i$$$ but on in $$$a_i$$$:
In this case, to satisfy the inequality, $$$k$$$ should be off in both bits. The subtrees that we must descend to (so we can find answers where the differing digit between $$$a_j \oplus i$$$ and $$$a_i \oplus j$$$ is greater than k) are those where $$$k$$$ is on in one of $$$j$$$ or $$$a_j$$$ but off in the other.
Case 3: $$$k$$$ is on in $$$i$$$ but off in $$$a_i$$$:
Here, to satisfy the inequality, we want the kth bit to be on in both bits. The subtrees that we should descend to are those where the $$$k$$$ bits differ.
Case 4: $$$k$$$ is on in both bits.
And lastly, for this case, the kth bit should be on in $$$a_j$$$ but off in $$$j$$$. The subtrees that we should descend to are the ones where the kth bits are the same.
We can notice one major observation so that we only visit one subtree, instead of $$$2$$$: only the value of $$$a_j \oplus j$$$ matters, since we wish to make the prefixes indentical.
However, then there is the final question of, for the subtree that we don't visit, how do we know if the maximum $$$dp$$$ value is valid? For example, if we are on the kth bit where it is off in both $$$i$$$ and $$$a_i$$$, the maximal $$$dp$$$ value may have some configuration where the kth bit is on in $$$a_j$$$ and not $$$j$$$. This will obviously cause $$$a_j \oplus i$$$ to be greater than $$$a_i \oplus j$$$. Well, thankfully, there are only 2 possible configurations for such a subtree where $$$a_j$$$ and $$$j$$$ differ in their kth bit: either $$$a_j$$$ has the kth bit set and $$$j$$$ doesn't, or $$$j$$$ has the kth bit set and $$$a_j$$$ doesn't. Similarly, for the subtree where $$$j$$$ and $$$a_j$$$ have the same status for their kth bit, there are only two cases: either it is set in both or off in both. So we can keep track of such $$$dp$$$ values separately.
So, our trie nodes only need to know: The child where the next bit is indentical in $$$a_j \oplus j$$$, the child where the kth bit differs, and the maximum dp values for the case where the kth bit is on in $$$j$$$, and the case where the kth bit is off.
When we are finished processing $$$i$$$, all we have to do is insert it into the trie and update the max $$$dp$$$ values accordingly. Then we can move on to $$$i+1$$$. The answer should obviously be the max value of $$$dp_i$$$ for all $$$i$$$.
Now I feel Happy to be stupid rather than understanding this BS
Our goal will be to calculate $$$dp[i]$$$, which is the longest valid subsequence starting at index $$$i$$$. We will calculate $$$dp[i]$$$ in decreasing order of $$$i$$$. In addition, we will maintain a trie which somehow stores elements of the array / $$$dp$$$ values. The flow of our solution would be something like:
a) For $$$0 \le i \le n - 1$$$: (decreasing)
a1) Calculate $$$dp[i]$$$ based on previous $$$dp$$$ values, using our trie.
a2) Insert the $$$i$$$'th element to the trie, somehow.
The $$$O(n^2)$$$ $$$dp$$$ formula is something like: $$$dp[i] = max_{j > i, a[i] \oplus j < a[j] \oplus i}(dp[j] + 1)$$$. Therefore, we want to insert the elements into the trie in such a way that retrieving the maximal $$$dp[j]$$$ for all $$$j$$$ such that $$$a[i] \oplus j < a[j] \oplus i$$$ is easy.
Recall that comparing two binary numbers can be done lexicographically. Assume that up to the $$$k$$$'th leftmost bit, the two expressions are equal. Then, LHS will be smaller than RHS for some $$$(j, a[j])$$$ if and only if one of two happens:
The first condition is equivalent to $$$(a[i] \oplus i)_{k} \neq (a[j] \oplus j)_{k}$$$ and $$$a[j]_{k} \neq i_{k}$$$. The second condition is equivalent to $$$(a[i] \oplus i)_{k} = (a[j] \oplus j)_{k}$$$, and in a later bit, 1 happens.
We can already start to see that it might be worth it to save $$$a[j] \oplus j$$$ values. These are exactly the values we will insert into the trie at step a2). It is only left to figure out how to perform step a1). We will traverse the trie bit-by-bit. For the $$$k$$$'th bit, we will
If we maintain these values, we will get $$$O(n \cdot log(C))$$$ total complexity, and total trie nodes.
Why is it sufficient to check only for the first $$$k_{th}$$$ different bit in our trie and no not see further down the trie for the condition $$$(j > i), (a[i] \oplus j) < (a[j] \oplus i)$$$ to be true, as the value of successive bit increases as we go down the trie example : $$$2^{k+2} > 2^{k}$$$, for some bit k+2 and k. $$$\newline$$$ Or like can you help me in understanding how does $$$a[i] \oplus i$$$ helps in finding $$$j$$$ for our original inequality $$$(a[i] \oplus j) < (a[j] \oplus i)$$$ to satisfy. $$$\newline$$$
We're going from MSB to LSB (Values are inserted MSB first). So we know which expression is bigger on the first such bit which is different.
Thank You!
1.) Can u explain
kth bit in a[j] ≠ kth bit in i? It seems ifkth bit in a[i] = 0 and i = 0, it will fail. 2.) Also, can u explain in detail how to calculate this using dp?I think either it should be
kth bit in a[j] = iorkth bit in a[i] ≠ jThis is because if $$$a[j]_{k} \neq i_{k}$$$, it necessarily means that $$$a[j]_{k} \oplus i_{k} = 1$$$, which is what we want (this also implies that $$$a[i]_{k} = j_{k}$$$, or equivalently $$$a[i]_{k} \oplus j_{k} = 0$$$
For each trie node we save two values: $$$max_0, max_1$$$. $$$max_i$$$ is the maximal $$$dp$$$ value in the subtree of that node, amongst all $$$j$$$ s such that $$$a[j]_{k} = i$$$. Best way to go with it is an example: Initialize $$$bestSoFar = 0$$$. Suppose we're at the $$$k$$$th bit, and $$$a[i]_{k} = 1, i_{k} = 0$$$. For condition (1) to hold, we need $$$j_{k} = 1, a[j]_{k} = 1$$$ which is equivalent to $$$a[j]_{k} \oplus j_{k} = 0$$$ and $$$a[j]_{k} = 1$$$. From the current trie node, check its child that has $$$a[j]_{k} \oplus j_{k} = 0$$$, and update $$$bestSoFar$$$ accordingly ($$$bestSoFar = max(bestSoFar, max_1)$$$). Then, go to the other child (with $$$a[j]_{k} \oplus j_{k} = 1$$$) and continue recursively.
Oliviera better
Yeah understood. In my case I assumed
j < iThnx for the explanationGoing back to problem statement. It says
For **any** p (0≤p<m−1) holds $condition. Does it not mean we need to find single closest pair of (i, j) matching that condition and we are done?Codeforces Round #815 (Div. 2) video Editorial for Chinese ：
Bilibili
It seems that $$$cur$$$ is not used in the solution of Div2 D1.
The pretest for A is too weak, I had just wrote a weird code and got a FST status :(
Can Somebody explain how to use "offline prefix sums" in problem E ?
thx.
If a square with top left corner in $$$(x,y)$$$ completely covers number $$$c$$$ , let its side be equal to $$$L$$$, then for all $$$a_{i,j}=c$$$, $$$i-L+1\le x\le i,j-L+1\le y\le j$$$.Thus, we just care about the maximum and minimum values of $$$i,j$$$.After getting these values,we will add $$$1$$$ to each top left corners of squares which following above conditions,which can be done by offline prefix sums.
d1 and d2 are two good problem!
need to clarify if there is not such subsequence satisfying the condition, should we output 1 or 0 ?
There will always be a subsequence satisfying the condition. Just pick any element, it is a subsequence of length 1.
but it does not make sense for the inequality to hold if there is only one element
Hi, can someone explain why my submission for D2 168922715 has an MLE for test case 2? As far as I'm concerned, the memory complexity is $$$O(n\log10^9)$$$, which should be good, but it doesn't pass the memory. I've tried to make the code as clean as possible, so I'd appreciate it if someone could take a look.
My solution basically uses a trie, and to consider the value of the bitstring of $$$a_i \oplus i$$$ as we traverse down the trie. Most of the memory complexity thus comes from the set of indices that I store in each trie node, indicating that these indices $$$i$$$ at this node have the same prefix in the bitstring $$$a_i\oplus i$$$. Thanks!
Video Editorial of Problem D1
Task D is nice, except the misleading statement
Is the TL on D2 too tight? My submission TLEs on test 3, even though it is $$$O(n \log (a_i))$$$. 168961089
Most correct solutions pass in less than 500ms, something might be wrong in your code. Maybe try to run it with 300,000 elements to see how far you are from the 2s limit?
It takes around 3500ms. Any fixes to improve that?
Edit: It takes <500 ms on some n=300000 cases, custom hash for unordered_map didnt help either
——(In the tutorial of E)
I have a problem with task B. The condition says we can take any subarray. But then why for the input data "1 2 3 100 200" the answer is 297? We can take the subarray 2 3 100 200 and the answer will be 100 more than in the example. Or I don't understand something. Please explain.
If we take the subarray 2 3 100 200, then the beauty of this subsegment is $$$200-2+1-1=198$$$. Why is the answer more than the example 100?
omg. I understood... we exclude this sub-segment. aah, thanks!
Couldnt problem B be done with complexity O(n) ? I believe my solution does it in O(n).
Yes, you can find the minimum and maximum in $$$O(n)$$$. But doing it twice is unnecessarily painful compared to sorting.
for second problem NlogN ( sorting the array )solution give timeout for Java , however for other languages c++ and python same solution works , Please work on test cases and time set for diff languages
You can also find 2 maximums and 2 minimums of the array in linear time. Such implementation passes if you code it in Java too
The answer of problem B doesn't only exceed max1+max2-min1-min2, but also is equal to max1+max2-min1-min2. So the best complexity is O(n).
For D1, please let me know why my solution 169032390 WA on test 3 while for j′<i−512, definitely aj′⊕j>aj⊕j′.
my mx is used to caculate the maximum dp[j] (j from 0 to i — 512)
I love constructive div 2 E's where the key observation is answer turns out to be at most [small number] like 2. Other recent examples like 794 E and 798 E though these are different kinds of problems. But I wonder how you come up with these constructions or guesses that you can the construction can be done in a small number of moves because it seems like the problem is easily hit or miss if you don't see the idea or think this is possible.
Can anyone please explain the editorial code for D2? I don't understand this implementation of trie.
fix D statement please !!! it's wrong
I don't quite understand, why can't the proper subsegment contain the maximum or minimum values of the whole array or both? It's not stated in the problem that it can't.. the only constraint over the subsegment that it can cover at most n-1 elements, stated as (r — l + 1 < n).
for example in the second test case where n = 5 and the values are 1 2 3 100 200 we can choose l = 2 and r = 5 so the subsegment is (2 3 100 200) and the answer should be (200 — 1) + (200 — 2) = 397
so can anyone explain what I'm missing?