Problems A, B, C, D1 and E were authored by me and Adam_GS authored D2 and F.
Hint
If $$$k$$$ is greater or equal to $$$2$$$ you can always swap adjacent elements.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
int arr[n];
for(int i = 0;i < n;i++){
cin>>arr[i];
}
if(is_sorted(arr,arr+n) || k > 1){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
return 0;
}
Hint
Think of each bit independently.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int m[n][n];
int arr[n];
for(int i = 0;i < n;i++){
arr[i] = (1<<30) - 1;
}
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
cin>>m[i][j];
if(i != j){
arr[i] &= m[i][j];
arr[j] &= m[i][j];
}
}
}
bool ok = true;
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(i != j && (arr[i] | arr[j]) != m[i][j]){
ok = false;
}
}
}
if(!ok){
cout<<"NO\n";
}
else{
cout<<"YES\n";
for(int i = 0;i < n;i++){
cout<<arr[i]<<" ";
}
cout<<"\n";
}
}
}
Hint
Think of suffixes.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n];
long long suf[n+1] = {0};
for(int i = 0;i < n;i++){
cin>>arr[i];
}
for(int i = n-1;i >= 0;i--){
suf[i] = suf[i+1] + arr[i];
}
long long ans = suf[0];
for(int i = 1;i < n;i++){
if(suf[i] > 0){
ans += suf[i];
}
}
cout<<ans<<"\n";
}
}
1903D1 - Maximum And Queries (easy version)
Hint
Try using greedy to construct the answer bit by bit.
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
ll T[LIM], P[LIM], n, k;
void solve() {
rep(i, n) T[i]=P[i];
ll ans=0;
for(ll i=60; i>=0; --i) {
ll sum=0;
rep(j, n) {
if(T[j]&(1ll<<i)) continue;
ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i);
p+=ans^(p&ans);
sum+=p-T[j];
if(sum > k){
break;
}
}
if(sum>k) continue;
rep(j, n) {
if(T[j]&(1ll<<i)) continue;
ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i);
p+=ans^(p&ans);
T[j]=p;
}
ans+=1ll<<i;
k-=sum;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int q;
cin >> n >> q;
rep(i, n) cin >> P[i];
while(q--) {
cin >> k;
solve();
}
}
1903D2 - Maximum And Queries (hard version)
Hint
Try optimizing the greedy approach from $$$O$$$($$$n$$$) to $$$O$$$($$$1$$$).
Solution
Tutorial is loading...
Code (C++)
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7;
ll dpsum[1<<20][20], dpcnt[1<<20], T[LIM];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
ll n, q;
cin >> n >> q;
ll sto=0, sfrom=0;
rep(i, n) {
cin >> T[i];
sto+=(1ll<<20ll)-T[i];
sfrom+=T[i];
++dpcnt[T[i]];
ll sum=0;
rep(j, 20) {
sum+=T[i]&(1ll<<j);
dpsum[T[i]][j]+=sum;
}
}
rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) dpcnt[j]+=dpcnt[j+(1<<i)];
rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) rep(l, 20) dpsum[j][l]+=dpsum[j+(1<<i)][l];
while(q--) {
ll k;
cin >> k;
if(k>=sto) {
k+=sfrom;
cout << k/n << '\n';
continue;
}
ll ans=0;
for(ll i=19; i>=0; --i) {
ll x=(n-dpcnt[ans|(1<<i)])*(1ll<<i);
x-=dpsum[ans][i]-dpsum[ans|(1<<i)][i];
if(x<=k) {
k-=x;
ans|=1<<i;
}
}
cout << ans << '\n';
}
}
Hint
Do mod $$$2$$$ in all coordinates and see how many different types of points you have in the end.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int sx,sy;
cin>>sx>>sy;
int x[n],y[n];
set<int>p[2];
for(int i = 0;i < n;i++){
cin>>x[i]>>y[i];
p[(x[i] % 2) ^ (y[i] % 2)].insert(i+1);
}
int v = (sx % 2) ^ (sy % 2);
if(p[v].size() >= p[v^1].size()){
cout<<"First"<<endl;
v ^= 1;
for(int i = 0;i < n;i++){
if(i % 2 == 0){
int j;
if(!p[v].empty()){
j = (*p[v].begin());
p[v].erase(j);
}
else{
j = (*p[v^1].begin());
p[v^1].erase(j);
}
cout<<j<<endl;
}
else{
int j;
cin>>j;
if(p[0].count(j)){
p[0].erase(j);
}
else{
p[1].erase(j);
}
}
}
}
else{
cout<<"Second"<<endl;
for(int i = 0;i < n;i++){
if(i % 2 == 1){
int j;
if(!p[v].empty()){
j = (*p[v].begin());
p[v].erase(j);
}
else{
j = (*p[v^1].begin());
p[v^1].erase(j);
}
cout<<j<<endl;
}
else{
int j;
cin>>j;
if(p[0].count(j)){
p[0].erase(j);
}
else{
p[1].erase(j);
}
}
}
}
}
}
Hint
Use binary search the answer and 2-sat.
Solution
Tutorial is loading...
Code (C++)
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
vector<vector<ll> >adj,rev;
vector<ll>order;
vector<ll>vis,comp;
ll c;
ll cur;
ll val(ll idx,bool v){
return cur + (2 * idx + v);
}
void dfs1(ll idx){
vis[idx] = true;
for(auto x:adj[idx]){
if(!vis[x]){
dfs1(x);
}
}
order.pb(idx);
}
void dfs2(ll idx){
comp[idx] = c;
for(auto x:rev[idx]){
if(!comp[x]){
dfs2(x);
}
}
}
void build(ll s,ll e,ll idx){
if(s == e){
adj[idx].pb(val(s,0));
rev[val(s,0)].pb(idx);
return;
}
ll mid = (s+e)/2;
build(s,mid,idx*2);
build(mid+1,e,idx*2+1);
adj[idx].pb(idx*2);
adj[idx].pb(idx*2+1);
rev[idx*2].pb(idx);
rev[idx*2+1].pb(idx);
}
void update(ll s,ll e,ll qs,ll qe,ll idx,ll k){
if(qs <= s && e <= qe){
adj[val(k,1)].pb(idx);
rev[idx].pb(val(k,1));
return;
}
if(s > qe || qs > e){
return;
}
ll mid = (s+e)/2;
update(s,mid,qs,qe,idx*2,k);
update(mid+1,e,qs,qe,idx*2+1,k);
}
int main(void){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t;
cin>>t;
while(t--){
ll n,m;
cin>>n>>m;
ll u[m],v[m];
f(i,0,m){
cin>>u[i]>>v[i];
}
ll l = 1,r = n;
ll ans = 1;
cur = 4*n;
while(l <= r){
ll mid = (l+r)/2;
order.clear();
vis.assign(6*n+5,0);
comp.assign(6*n+5,0);
adj.assign(6*n+5,vector<ll>());
rev.assign(6*n+5,vector<ll>());
f(i,0,m){
adj[val(u[i],0)].pb(val(v[i],1));
adj[val(v[i],0)].pb(val(u[i],1));
rev[val(u[i],1)].pb(val(v[i],0));
rev[val(v[i],1)].pb(val(u[i],0));
}
build(1,n,1);
f(k,1,n+1){
ll l = max(1,k - mid + 1),r = k-1;
update(1,n,l,r,1,k);
l = k+1;
r = min(n,k + mid - 1);
update(1,n,l,r,1,k);
}
bool ok = true;
c = 1;
f(i,1,n+1){
if(!vis[val(i,0)]){
dfs1(val(i,0));
}
if(!vis[val(i,1)]){
dfs1(val(i,1));
}
}
reverse(order.begin(),order.end());
for(auto x:order){
if(!comp[x]){
dfs2(x);
c++;
}
}
f(i,1,n+1){
ok &= comp[val(i,0)] != comp[val(i,1)];
}
if(ok){
l = mid + 1;
ans = max(ans,mid);
}
else{
r = mid - 1;
}
}
cout<<ans<<"\n";
}
}
jeroenodb's solution O(M log N)
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<basic_string<int>> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
template<int (*merge)(int,int), int (*init)(int)> struct DSU{
vi sz, dat;
DSU(int n) : sz(n,-1),dat(n) {
for(int i=0;i<n;++i) dat[i] = init(i);
}
void link(int a, int b) {
if(sz[a]>sz[b]) {
swap(a,b);
}
sz[a]+=sz[b];
sz[b]=a;
dat[a] = merge(dat[a],dat[b]);
}
bool unite(int a, int b) {
int pa = find(a),pb = find(b);
if(pa!=pb) link(pa,pb);
return pa!=pb;
}
int get(int i) {
return dat[find(i)];
}
int find(int a) {
if(sz[a]<0) return a;
return sz[a] = find(sz[a]);
}
};
int dec(int i) {return i-1;}
int inc(int i) {return i+1;}
int mymin(int a, int b) {return min(a,b);}
int mymax(int a, int b) {return max(a,b);}
bool solve(const vvi& adj, const vvi& rev, int mid) {
int n = rev.size()/2;
DSU<mymin, dec> dsuL(n);
DSU<mymax, inc> dsuR(n);
auto getL = [&](int i) {
if(i>=n) i-=n;
int l = dsuL.get(i);
if(l==-1 or abs(i-l)>=mid) return 0;
return l+1;
};
auto getR = [&](int i) {
if(i>=n) i-=n;
int r = dsuR.get(i);
if(r==n or abs(i-r)>=mid) return 0;
return r+1;
};
auto rem = [&](int at) {
if(at>=n) at-=n;
if(at) dsuR.unite(at-1,at);
if(at+1<n) dsuL.unite(at,at+1);
};
vector<bool> vis(n*2);
vi ord;
auto dfs = [&](auto&& self, int at) -> void {
vis[at]=1;
if(at<n) {
while(int l = getL(at)) self(self,l-1+n);
while(int r = getR(at)) self(self,r-1+n);
} else rem(at);
for(int to : adj[at]) if(!vis[to]) self(self,to);
ord.push_back(at);
};
for(int i=0;i<2*n;++i) if(!vis[i]) dfs(dfs,i);
reverse(all(ord));
fill(all(vis),0);
dsuL = DSU<mymin,dec>(n);
dsuR = DSU<mymax,inc>(n);
int comp=0;
vi comps(2*n);
auto dfs2 = [&](auto&& self, int at) -> void {
comps[at]=comp;
vis[at]=1;
if(at>=n) {
while(int l = getL(at)) self(self,l-1);
while(int r = getR(at)) self(self,r-1);
} else rem(at);
for(int to : rev[at]) if(!vis[to]) self(self,to);
};
for(int i : ord) if(!vis[i]) {
dfs2(dfs2,i);
comp++;
}
for(int i=0;i<n;++i) if(comps[i]==comps[i+n]) return false;
return true;
}
void solve() {
int n,m; cin >> n >> m;
vvi adj(2*n),rev(2*n);
auto addE = [&](int u, int v) {
adj[u].push_back(v);
rev[v].push_back(u);
};
for(int i=0;i<m;++i) {
int u,v; cin >> u >> v;
--u,--v;
addE(u+n,v);
addE(v+n,u);
}
int lo=1,hi=n;
while(lo<hi) {
int mid = (lo+hi+1)/2;
if(solve(adj,rev,mid)) {
lo= mid;
} else hi = mid-1;
}
cout << lo << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin >> t;
while(t--) solve();
}
Great contest! Solved A and C, i guess i should practice bit operations
I'm too, I can accept some hard DP problems but, bit operations I can't, it is so much trick. :((
(Array Splitting) 1900
Tutorial came too early :D
Mij = ai | aj should be the statement in editorial of B
Yes , a typo from their side. Other than this , the solution was brilliant.
BITFORCES
who can explain why C greedy works ?
If your suffix sum is positive, it's more optimal to make an extra group on your current position since making another group will double the values on the suffix.
thank you ! this explanation was way better than in editorial, or only i think so.
Definitely
Very nice explanation buddy. Thank You.
Nice explanation but an extra group will make another group +1 times the values of the suffix.
Right?
yup
Thanks
Consider scanning from front to back, deciding at each position whether to open a new subarray.
If I start a new subarray from the current position, then according to the question, the multiplier of this subarray will be 1 more than the previous one, which also means that the multipliers of all subsequent numbers will also be "pulled high" at the same time. (It can be found that we do not need to know how the following numbers are divided)
Obviously, it is not advisable to "increase" the multiplier if the suffix is negative, as that will make the answer smaller.
thank you too friend !
Very nice explanation. Well deserved CM.
Any subdivision can always be written as a sum of suffix sums, which should always include the very first suffix sum, i.e. 1*(subarray starting at 1) + 2*(subarray starting at i)+3*(subarray starting at j).. = suff[1] + suff[i] + suff[j]+. Once you are convinced, there is one to one correspondence between these 2 functions, you can just pick suff[1] and rest positive suffix sums.
thanks a lot :)
Better than editorial
Greedy or DP is just a construct. What if I told you that the editorial's solution is just refactored DP solution?
Here's a question for you: You might have heard of Kadane's algorithm. We define $$$dp[i]$$$ to be the maximum sum subarray ending at index $$$i$$$. When written in this form
You can confidently say that it's DP.
But, notice that $$$a[i] + dp[i - 1] > a[i]$$$ iff $$$dp[i - 1] > 0$$$. So if you do a space optimization, and keep a
max_so_far
andmax_ending_here
, you can see thatmax_ending_here
would bea[i] + max_so_far
ifmax_so_far
is positive. And intuitively, that makes sense since you should keep the left extension if it gives you a net positive value. Would you still call this approach Greedy or DP since now the decisions make sense intuitively? I also talk more about Greedy vs DP for this problem hereIn case anyone's interested,I've added hints and thought process for problems:
on CF Step
Hey, Thanks for the dp approach, i was actually able to solve the problem but wasn't sure why it would work, Really appreciate the efforts you put in the explanation!!
I feel like these are indeed solutions, but sometimes there are no... proofs. Which is especially important for first problems so that beginners can understand the difference between a correct solution and an incorrect solution.
P.S. And the comment above perfectly illustrates my point.
Yeah, there is no intuition and approach. Just reading the code. What's the point in making editorials if they can't be understood by a learner.
why it's not truth that |(mat[0][0..n-1]) = |(mat[1][0..n-1]) = ... = |(mat[n-1][0..n-1]) in problem B?
I checked it and it crashed my solution! lets look on example with 3x3 matrix:
a_i — ith element of our array then:
1st row: 0 | (a_1|a_2) | (a_1|a_3) = a_1 | a_2 | a_3
2nd row: (a_2|a_1) | 0 | (a_2|a_3) = a_1 | a_2 | a_3
3rd row: (a_3|a_1) | (a_3|a_2) | 0 = a_1 | a_2 | a_3
help me pls
I found mistake..
Here's how I solved E:
So, first we realise that checking if the sum of integers is even or odd should motivate reducing everything $$$\pmod{2}$$$. We note that $$$\text{distance}^2((x_1,y_1),(x_2,y_2)) \equiv (x_1-y_1) - (x_2-y_2) \pmod{2}$$$
(this follows from casework on the possible values of $$$x_i$$$ and $$$y_i$$$).
Nice, so we can reduce this 2D problem to a 1D problem. Create a new array $$$a$$$ satisfying $$$a_i = x_i - y_i \pmod{2}$$$
Then, the parity of the squared distance between points $$$i$$$ and $$$j$$$ is captured simply as $$$a_j - a_i \equiv a_i - a_j \pmod{2}$$$. (Doesn't matter the order, we'll see why this is nice).
Let's give the starting value its own special place in the array, Start $$$\to a_0$$$.
Now, let's make a couple moves. Suppose we choose to go to $$$(x_i,y_i)$$$ from Start. This is equivalent to going to $$$a_i$$$ from $$$a_0$$$. If the squared distance between $$$(x_i,y_i)$$$ and Start happens to be even, then it's necessarily true that $$$a_i - a_0 \equiv 0 \pmod{2}$$$. If the distance happens to be odd, then $$$a_i - a_0 \equiv 1 \pmod{2}$$$
After we make our move, our new Start is $$$a_i$$$. Let's choose another point $$$(x_j,y_j)$$$. What will the parity of the squared distance between points $$$j$$$ and $$$i$$$ be? Well, it'll just be $$$a_j - a_i \pmod{2}$$$. Note, that we care only about the sum of the parity of the squared distances, and what that's going to be. So if we keep a running tally of our score so far, we have:
$$$(a_i - a_0) + (a_j - a_i) + \dotsc \pmod{2}$$$. Isn't it weird that the $$$a_i$$$'s cancel?
Turns out that this pattern continues. It telescopes so that only the $$$0^{\text{th}}$$$ and the last index of the game, let's call that $$$k$$$, are the only ones remaining, i.e.
$$$a_k - a_0 \pmod{2}$$$
Now, we see that if we go first, we want to ENSURE that $$$a_k$$$ is the same value as $$$a_0$$$. This is a lot simpler to think about. Let's count the number of zeroes and ones in $$$a$$$ (disregarding $$$a_0$$$) and enumerate their indices into two sets, the zero set and the one set.
An optimal adversary will want to prevent us from ensuring the last element selected is the same value as $$$a_0$$$, so on each turn, they will try to use them up. That means, they will choose the points with those values. We can see that the only possible way for us to win if we go FIRST is if there are at least as many "$$$a_0$$$" values as non-"$$$a_0$$$" values. This is because we'll take the non-$$$a_0$$$ values and as long as there are at least as many $$$a_0$$$ values, the non-$$$a_0$$$ values will deplete first, guaranteeing a victory for us.
If there are strictly more non-$$$a_0$$$ values, we would want to go second, because then we'll just take the $$$a_0$$$ values and ensure the total sum parity is $$$1$$$, aka odd.
235128893 (Code is really bad, I went through each case individually because I was rushing to get it in before contest ended).
It's pretty easy if just expand the formula, let the points chosen be 1,2,....,n+1, then the formula expands to s1^2+2*s2^2+.....+sn^2,-2*s1*s2.... You can eliminate all the terms with 2 coefficient for even sum , so the answer is just dependant on the first and last point and the starting point is fixed
Hey, I used the same logic. I counted the even and odd parity coordinates and parity of the $$$s_x^2 + s_y^2 = v$$$. Then, I claim that if $$$v \oplus (\text{#odd} > \text{#even})$$$ equals 1, I will go second, or else I'll go first. If I go first, I will try to use all coordinates with parity $$$(1-v)$$$ (where v was the parity of the starting point).
But unfortunately, my code is giving WA. Can you please help me out?
There are 4 cases not 2 look at my submission
Can you explain your approach in short? I am not getting which cases you are talking about?
There are 2 cases if n is even and n is odd to determine who plays last further if the other player(who isnt playing last) can play all the points the last player needs to play on his last turn we go with the other player otherwise the last player
beautiful explanation !
Why is this solution giving WA for test case 4 although I feel I have done what is mentioned in the editorial. Submission- 235137669
could be integer overflow cum*count in your code (i have not looked very carefully)
Thanks for the reply but I dont think the reason can you please look into the following--> I discarded the cum variable cause its unnecessary 235118044
Can someone explain C in more detail? Didn’t understand the editorial(
If you open a new subarray at an index i, then it is like you are adding the suffix sum from index i to n to your answer. So, you would start first subarray at index 1, so you would add whole array sum to your answer, now if you start a second subarray at index i, then you only need to add the sum of second array one more time because you have already added it once when you added suffix sum of index 1. For the k-th subarray, you have already added it's sum (k-1) times, so you would add it just once.
Now, it is beneficial to add the suffix sum only when it is positive, so we will do only that
Completely understand after reading your solution. Thanks
amazing explanation man, almost every soln or comment had dp which I am unfortunately not well versed with, this one cleared it though, thanks again :)
Thanx bro, i couldn't understand anything from the editorial! But you made it so much more clearer.
Man, your explanation is a million times better than the editorial solution. Thanks.
This was the best explanation,thanks
this is how I did it.
assume a b c d
we have two choices at after a, divided it or don't divide. "cuts" is how many subarrays we already made.
and
now let's see why ((b+c+d)*(cuts+1)) will never decrease, after placing a cut after "a" we have this subproblem to solve the "b c d" similarly, we will repeat the process and only place a cut again if it is increasing the overall sum of our array hence it won't decrease.
my solution 235124903
for B, is there any way to confirm that solution doesn't exist without going through entire solution array?
I have another solution to the problem C (maybe more intuitive):
Let $$$dp_e$$$ denote the maximum division value for the array $$$[a_e, a_{e+1} ... a_n]$$$.
Then if we add some block $$$[s...e)$$$ in front the division value gets updated by $$$\sum_{s}^{e-1}{a_i} + \sum_e^{n}{a_i} = \sum_{s}^{n}{a_i}$$$ (that is because every element after $$$e$$$ adds $$$a_i$$$ to its corresponding block).
Thus we have $$$dp_i = max(dp_j) + \sum_{i}^{n} a_i$$$, where $$$j > i$$$.
This is ridiculously slick. Nice solution!
Such an elegant solution! Thank you for sharing!
That is a brilliant solution! Hope someday even I can think of such solutions.
If we try to do this from front instead of back, we would face the problem of computing dp i = max(dpj + summation of a's from j to i) for j < i. Thus this would take O(n^2) time to compute. Is this the reason we compute the dp from behind or I am wrong?
Excellent analysis. Implementation of the above idea 236158727.
I think editorial in C should include that sum of suffix sums, results in what the problem is asking to maximize, i.e 1*(1st subarray sum) + 2*(2nd subarray sum)+..... This 'trick' is arguably the hardest part in the problem to figure out. The editorial just assumes that everyone knows this.
True. I was trying to figure out what was going on until I saw your comment.
Thanks for the comment
A great explaination! Although I solve it with greedy,but still have some trouble about correctness.Help me a lot.
Could somebody explain to me why the solution of problem C in the editorial works, like a solid proof ?
Let $$$w_i$$$ be the id of subarray that contains $$$a_i$$$.
It is not hard to see that $$$w$$$ is non decreasing sequence where each adjacent element can differ by at most 1. ($$$a_i + 1 = a_{i+1}$$$ or $$$a_i = a_{i+1}$$$ for $$$i \in [1..n-1]$$$
Initially let $$$w_i$$$ be 1 for all i.
For each element (excluding first element) $$$a_i$$$ we can either do nothing or increase $$$w_j$$$ by 1 for every $$$j >= i$$$, doing so will increase the cost by $$$suff_i$$$ so if $$$suff_i$$$ is nonnegative we can get not-worse answer by increasing $$$w_j$$$
Can anyone explain the binary operation of question B? It’s not suitable for understanding.
Check my submission, you can get another approach, somewhat similar but easy to undersatnd
thans,it is good for me
Sad. Int overflow in D
Same, I wasted time trying to find mistake in my code. I used __int128 to deal with overflow.
Great problem Indeed!! Enjoyed very much..should have able to solve C and D. I even calculate the suffix array for C and still not able find suf[i]>0 contribute in the answer..Very frustrating!
How greedy works on problem C?Can someone explain me?
F is absolutely brilliant. Amazing problem!
Can anyone tell me why we are doing AND operation in B problem what we get from common set bit
We use AND to unset bits.
solution array: 5 2 3 0 4 ---> 101 010 011 000 100
Now, if you compare every elements of M that ai contributes. Their bits(bitwise) are gonna be either(ignoring i == j):
in latter case ai's corresponding bit has to be 0. Otherwise it could be 1. And AND gives us this operation.
What's the purpose of putting incorrect outputs in E's example testcases? I think it had confused people who didn't read problem statements carefully enough.
They were correct, but then you'd have to pray for the interactions to go your way hahahahah
As Dr. Emix I can say that all of you helped in solving 1903C - Theofanis' Nightmare and now he can finally sleep peacefully!
As a solver, I want you to pay me for the help!
can anyone explain DP approach for problem-C?
It has already been nicely explained in this comment.
ohh I see, thanks
Can anyone explain the solution of D2?
Although I solved D2, I found the editorial quite confusing as well, so my explanation might differ a bit from the post above.
First, we are still using a similar greedy approach from D1 to iterate through all of the bits from most significant to least and turning it on when we can. However, because
N * Q
is no longer <= 10^5, we are motivated to come up with a way to check the cost of turning on a bit in the final answer faster thanO(N)
.We can see that we want to increment each element by 1 until it has the bit we want on. If the bit is already on, the cost is 0. Otherwise, there are two cases we need to consider:
First, if an earlier bit was already turned on. This means that the cost to turn on this bit will always be the bit itself. (proof: to turn on a more significant bit that was considered earlier, the number was incremented just enough so that that bit is on, meaning that any smaller bits are off). Since the value of the bit will be constant for all of the numbers, we can simply count how many numbers have already been turned on in a previous bit.
Second, if this is the first bit that has to be turned on. This is a little harder to compute all at once, since the cost will be
bit - (num % bit)
.We can also observe that if the bit that we want to turn on is greater than 2^20, all of the numbers will fall into the same category. So, we can compute the cost for bits greater than 2^20 quite quickly.
If a bigger bit has been turned on: (sum of all the numbers mod bit is equal to zero) cost = bit * n
If a bigger bit has not been turned on: (sum of all the numbers mod bit is equal to the sum of all the numbers) cost = bit — sum of numbers
So we simply need to keep track of whether a bit greater than
2^20
has previously been turned on to deal with these cases. However, we still do not have a way to calculate the cost when we turn on bits smaller than2^20
. That's when SOS DP comes into play. Since we only need to keep track of which of the 20 bits has been turned on, we can turn this into a bitmasking DP problem, where we calculate the cost needed to turn on a bit when a set of bits has already been calculated already. Something likedp[20][1<<20]
. However, to calculate this, we run into a problem, in that this will require us to iterate through all of the subsets of each number, which makes our runtimeO(N * 2^20 * 20)
. This is obviously too big to compute, so we need to use a DP Optimization aforementioned called SOS DP. I will not explain this trick here since it is already better explained in other CF Blogs (ex. https://codeforces.net/blog/entry/45223). This allows us to calculate the cost to turn on bits when a set of bits has already been turned on inO(1)
afterO(2 ^ 20 * 20 * 20)
precalculation.Hope this helps!
Why in b we don't have to remove anything else ? Since there just one of ai or aj need to have it . so ai can have it and ai can don't obtain that bit too if aj have it. Why we do not have to remove anything else? If there a situation that ai doesn't have a bit then solution exists but we assume that ai need to have it then it seems not work properly. I understand that i may misunderstand or miss sth. Can anyone give me some explanations plz. Thx alot.
I had the same question during the contest and took quite some time to figure out why we don't have to care about this thing.
Suppose we had $$$x^{th}$$$ bit turned on in $$$a[i]$$$. Now, you are asking how about we just turn it in from a[i] and leave it turned on in the corresponding $$$a[j]$$$.That should be equivalent isn't it ?
Well, we calculated a[i] as the cumulative bitwise AND of the entire row $$$M[i]$$$. This means $$$x^{th}$$$ bit of $$$a[i]$$$ got turned on because it was turned on in all cells of the row $$$M[i]$$$. That means, if you turn off $$$x^{th}$$$ bit from $$$a[i]$$$, then you will have to turn on the $$$x^{th}$$$ bit in all columns from $$$1$$$ to $$$n$$$ except the $$$i^{th}$$$ column. Why ? Because remember $$$x^{th}$$$ bit got turned on only because every cell of $$$M[i]$$$ required that to be turned on. (thats what taking the AND of the entire row means, right).
Now, if all the elements $$$a[1],a[2]...,a[n]$$$ except a[i] have the $$$x^{th}$$$ bit turned on, then the entries in matrix $$$M[1][i], M[2][i], M[3][i],..., M[n][i]$$$ will have to get the $$$x^{th}$$$ bit turned on. But, isn't that exactly what would happen if we did not turn off $$$x^{th}$$$ bit of $$$a[i]$$$ ? Only the entry $$$M[i][i]$$$ will not have this constraint but it is anyways guaranteed to be zero in problem statement.
Thus, conclusion, if you wish to turn off the $$$x^{th}$$$ bit from some $$$a[i]$$$, then you will have to turn this bit on in not just the corresponding $$$a[j]$$$, but in all of $$$a[1],a[2],...,a[n]$$$ (except $$$a[i]$$$). This will ultimately have such an effect which is exactly same as just leaving the $$$x^{th}$$$ bit on in a[i] in the first place.
Hope you understood.
Can anyone explain D1
In problem B you wrote "We check if Mij = ai & aj holds for all element" Here it will be Mij = ai | aj. Isn't it?
Yes sorry. It will be fixed.
In problem F, how is it possible to only use one segment tree structure? Won't you need two (also for the negation nodes — whose edges go to the parents, instead of towards the children)?
Interesting problem specially C and D
But C is similar to an old problem I solved before called (Array Splitting) 1900
In the solution to problem C, I think it should be suff[i] >= 0 in the if condition.
It doesn't change anything.
Hello Theo830 Can you please tell me how you avoid making TWO segment tree graphs in F? I could only do 2, one which has down orientation and one which has up. source code here: https://codeforces.net/contest/1903/submission/235239350 Thank you in advance!
So in that case of 0 we are adding 0 only which is same ultimately.
Can someone explain D in detail I could get the core idea :\
Problem C Detailed Editorial : DETAILED EDITORIAL FOR PROBLEM C
I think problem E has a simpler explanation.
After doing the math and finding out that going from ($$$x_0$$$, $$$y_0$$$) to ($$$x_1$$$, $$$y_1$$$) changes your overall parity by $$$x_0 \oplus y_0 \oplus x_1 \oplus y_1$$$. You can do some more math and find out that going from ($$$x_0$$$, $$$y_0$$$) to ($$$x_1$$$, $$$y_1$$$) to ($$$x_2$$$, $$$y_2$$$) changes your overall parity by $$$(x_0 \oplus y_0 \oplus x_1 \oplus y_1) \oplus (x_1 \oplus y_1 \oplus x_2 \oplus y_2) = x_0 \oplus y_0 \oplus x_2 \oplus y_2$$$.
Then we can easily see that this extends as follows: going from ($$$x_0$$$, $$$y_0$$$) to ($$$x_1$$$, $$$y_1$$$) to ($$$x_2$$$, $$$y_2$$$) to ... to ($$$x_n$$$, $$$y_n$$$) changes your overall parity by $$$x_0 \oplus y_0 \oplus x_n \oplus y_n$$$. This means that only the parity of the first and last points matter, all other points get cancelled out by the XOR. Additionally, the first point is fixed, so we only care about the last point.
Let's call points of the same parity as the starting point good, and the other points bad. If you are the first player, you want to make the last point be good, you can do this if the number good points are not less than the the number of bad points. You can do this by repeated choosing the bad points to deplete them until your last turn, then choosing (or forcing the other player to choose) a good point. Similarly, if you are the second player and the number of good points is greater than the number of bad points, you can just keep choosing the good points until the last turn, then choose (or force the other player to choose) a bad point.
[Doubt][Problem D] — Can someone explain how the formula 2^b — ai(mod)2^b comes in the editorial.
Consider $$$bin(num) = 111001*0101$$$. I ask you to apply bit manipulation to clear all the bits to the left of * (eventually converting it to $$$000000*0101$$$).
One way to do it is to iterate over higher order bits and manually turn them off one by one. But if you want a fancy way, you can just do $$$num \% 2^4$$$. This works because any number can be represented as $$$\sum 2^{set\_bit\_index}$$$, and all the set bits that we want to clear have index $$$\geq 4$$$. So their modulo is zero and they would be unset. The lower order bits won't be touched because $$$z \% 2^4 = z$$$ if $$$z < 2^4$$$.
You already know a trick to unset the $$$i^{th}$$$ bit. Now you've learnt about a trick to unset all bits with indices $$$\geq i$$$.
Why exactly do we want to unset the higher order bits is something specific to the problem. I'll leave it upto you to figure that out, feel free to respond to the comment if you are not able to.
Thankyou so much adaptatron. I got the clear understanding.
anyone with binary search solution for D1?
Great problemset! I liked E a lot, since we don't get game theory that often, and this one was an especially cool problem.
Problem F can be solved using dfs on implicit graph. As mentioned in the editorial, the problem reduces to be able to visit all vertices in range $$$[l,r]$$$ from vertex $$$v$$$, but without creating actual edges. We can store unvisited vertices in the set. In the dfs we first visit all vertices in the main graph, and after that use lower_bound to find next vertex in range $$$[l,r]$$$ which is still not visited.
The code looks something like this
I used odd and even vertices, because in 2-sat graph we only have edges from even vertices to odd vertices and vice versa
P
I'm not able to undersand any part of the editorial for problem F.
Can anyone help me understand the logic for problem F?
Great Editorial.learn useful trick.Thank you..
I am trying D using binary search but getting TLE, I don't think the time complexity of my code is that bad. Here is my submission. https://codeforces.net/contest/1903/submission/235400941
My solution for Problem E: say the first point is $$$(x_0,y_0)$$$ and the remaining points (in the order in which they are chosen) be $$$(x_i,y_i)$$$ $$$(1 \le i \le n)$$$. The overall expression comes out to:
Clearly the parity of the final sum is decided by the first (given) point and the last selected point. Since the parity of first point is fixed we can only try and select the ideal last point. If
is odd, the first player will try to select
such that the parity changes i.e
is odd. Hence he will try to eliminate all even sum of squares if possible. Hence we can choose the winner for each case based on the parity of the sum of square of the first point and the number of points with odd or even sum of squares of their respective components. My Solution: https://codeforces.net/contest/1903/submission/235405790
wtf the editorial is totally a piece of shit
Can somebody please explain why this Binary search for Problem D1 fails on Test 5 236231559
Is $$$O(M \log(n))$$$ solution to F added?
In the editorial code for problem D, what does p+=ans^(p&ans) does??
why it has been used ?
I think in the editorial for D1, the two lines of
p+=ans^(p&ans);
are probably redundant? Because $$$ans$$$ would start with a series of '1's $$$p$$$ would start with the same series of '1', too.i did'nt expected that i would get stuck on this problem for 3hr . i was trying to actually reverse the array for the elements where there is decreasing order and repeat this step n times , but when i read hint i felt very dumb that we can sort any array of size k = 2 .
for c problem (let's take all elements are positive ) how the summation is the suffix sum array elements is equal to summation of i*a[i]
example:
suppose elements are 1 2 5 6 8 suf sum =22 21 19 14 8 summetion of suf sum =84
also if we do 1*1 +2*2+ 3*5 +4*6 + 5*8 =84
how it is doing any proof please Theo830
Start by having only one time each element (only one big group). Then as you add another suffix group you will have two groups. The first group/subarray with one time for each element and the second group/subarray with two times for each element.
In the example that you are saying. We start with
$$$[1,1,1,1,1]$$$ (This is how many times we take each element)
Then it becomes $$$[1,2,2,2,2]$$$
Then $$$[1,2,3,3,3]$$$ etc.
In the end we will have $$$[1,2,3,4,5]$$$
now it's better to understand.
Thanks!
How can I figure out patterns and problems faster in different types of questions. Is there a certain common way of approaching certain category of problems like for greedy we have to think in 1st way or for graphs in 2nd way???????
Like I couldn't think about Suffix in Problem C. I was thinking about something like Kadane.