Thank you for participating, and I hope you enjoyed the problems!

### 1395A - Boboniu нравится раскрашивать шары

Idea: dqa2021

**Tutorial**

Tutorial is loading...

**Solution**

```
def check(r,g,b,w):
return False if r%2 + g%2 + b%2 + w%2 > 1 else True
if __name__ == '__main__':
T = int(input())
for ttt in range(T):
r,g,b,w = map(int,input().split())
if check(r,g,b,w):
print("Yes")
elif r>0 and g>0 and b>0 and check(r-1,g-1,b-1,w+1):
print("Yes")
else :
print("No")
```

### 1395B - Boboniu играет в шахматы

Idea: Xiejiadong

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
int n,m,sx,sy;
void f(int i,int j){
printf("%d %d\n",(i+sx-2)%n+1,(j+sy-2)%m+1);
}
int main(){
scanf("%d%d%d%d",&n,&m,&sx,&sy);
FOR(i,1,n){
if(i&1)FOR(j,1,m)f(i,j);
else ROF(j,m,1)f(i,j);
}
return 0;
}
```

### 1395C - Boboniu и битовые операции

Idea: xryjr233

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
#define ci const int&
using namespace std;
int n,m,p[210],d[210],ans;
bool Check(ci x){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)if(((p[i]&d[j])|x)==x)goto Next;
return 0;
Next:;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&p[i]);
for(int i=1;i<=m;++i)scanf("%d",&d[i]);
ans=(1<<9)-1;
for(int i=8;i>=0;--i)Check(ans^(1<<i))?ans^=(1<<i):0;
printf("%d",ans);
return 0;
}
```

### 1394A - Boboniu общается с Du

Idea: sshwyR

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= int(b); i++)
using namespace std;
typedef long long ll;
const int maxn = 1e5;
int n, d, m, k, l;
ll a[maxn + 5], b[maxn + 5];
void solve(ll a[], int n) {
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
rep(i, 1, n) a[i] += a[i - 1];
}
int main() {
scanf("%d %d %d", &n, &d, &m);
for (int i = 0, x; i < n; i++) {
scanf("%d", &x);
if (x > m) a[++k] = x;
else b[++l] = x;
}
if (k == 0) {
ll s = 0;
rep(i, 1, n) s += b[i];
printf("%lld\n", s);
exit(0);
}
solve(a, k);
solve(b, l);
fill(b + l + 1, b + n + 1, b[l]);
ll res = 0;
rep(i, (k + d) / (1 + d), k) if (1ll * (i - 1) * (d + 1) + 1 <= n) {
res = max(res, a[i] + b[n - 1ll * (i - 1) * (d + 1) - 1]);
}
printf("%lld\n", res);
return 0;
}
```

### 1394B - Boboniu ходит по графу

Idea: sshwyR

**Tutorial**

Tutorial is loading...

**Solution**

```
//by Sshwy
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=2e5+5,HS=3,K=10;
int n,m,k;
vector< pair<int,int> > g[N];
int mod[HS];
struct hash_number{
int a[HS];
hash_number(){ fill(a,a+HS,0); }
hash_number(long long x){
FOR(i,0,HS-1)a[i]=(x%mod[i]+mod[i])%mod[i];
}
hash_number operator+(hash_number x){
hash_number res;
res.a[0]=(a[0]+x.a[0])%mod[0];
res.a[1]=(a[1]*1ll*x.a[1])%mod[1];
res.a[2]=(a[2]+x.a[2])%mod[2];
return res;
}
bool operator==(const hash_number& x)const {
FOR(i,0,HS-1)if(a[i]!=x.a[i])return 0;
return 1;
}
}val[N],c[K][K],s;
int ans;
int status[K];
void dfs(int x,hash_number hsh){
if(x==k){
if(hsh == s) ++ans;
return;
}
FOR(i,1,x+1){
status[x+1]=i;
dfs(x+1,hsh+c[x+1][i]);
}
}
int main(){
mod[0]=998244353;
mod[1]=1e9+7;
mod[2]=std::uniform_int_distribution<int>(1e8,1e9)(mt_rand);
fprintf(stderr,"%d %d %d\n",mod[0],mod[1],mod[2]);
scanf("%d%d%d",&n,&m,&k);
FOR(i,1,m){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[u].pb({w,v});
}
std::uniform_int_distribution<long long> rg(1,1e18);
FOR(i,1,n)val[i]=hash_number(rg(mt_rand));
FOR(i,1,n)s=s+val[i];
FOR(u,1,n){
int d=g[u].size();
sort(g[u].begin(),g[u].end());
for(int i=1;i<=g[u].size();++i){
int v=g[u][i-1].second;
c[d][i]=c[d][i]+val[v];
}
}
dfs(0,hash_number());
printf("%d\n",ans);
return 0;
}
```

### 1394C - Boboniu и строка

Idea: sshwyR

**Tutorial**

Tutorial is loading...

**Solution**

```
//by Sshwy
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
const int INF=1e9;
int n;
int main(){
cin>>n;
int lx=INF,rx=-INF,ly=INF,ry=-INF,lz=INF,rz=-INF;
FOR(i,1,n){
string s;
cin>>s;
int x=0,y=0;
for(char c:s){
if(c=='B')++x;
else ++y;
}
//printf("%d %d\n",x,y);
lx=min(lx,x), rx=max(rx,x);
ly=min(ly,y), ry=max(ry,y);
lz=min(lz,x-y), rz=max(rz,x-y);
}
int ans=INF,ax=0,ay=0,az=0;
auto calc = [&](){
int l=0,r=lz-(lx-ry),mid;
auto check = [&](int a){
return lx+a+a>=rx && lx-ry+a+a+a>=rz && ry-a-a<=ly;
};
if(check(r)==0)return INF;
while(l<r)mid=(l+r)>>1, check(mid)?r=mid:l=mid+1;
return l;
};
FOR(_,1,6){
assert(lx<=rx && ly<=ry && lz<=rz);
int v=calc();
if(v<ans){
ans=v;
ax=lx+v, ay=ry-v, az=ax-ay;
}
int Lx=ly,Rx=ry,Ly=-rz,Ry=-lz,Lz=lx,Rz=rx;
lx=Lx, rx=Rx, ly=Ly, ry=Ry, lz=Lz, rz=Rz;
int Ax=ay,Ay=-az,Az=ax;
ax=Ax,ay=Ay,az=Az;
}
cout<<ans<<endl;
FOR(i,1,ax)cout<<'B';
FOR(i,1,ay)cout<<'N';
cout<<endl;
return 0;
}
```

### 1394D - Boboniu и Jianghu

Idea: Z18

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5;
int n, h[maxn + 3], t[maxn + 3], in[maxn + 3], out[maxn + 3];
vector<int> G[maxn + 3];
bool vis[maxn + 3];
ll ans, f[maxn + 3], g[maxn + 3], a[maxn + 3];
void dfs(int u, int fa = 0) {
vis[u] = true;
for (int i = 0, v; i < G[u].size(); i++) {
if ((v = G[u][i]) == fa) continue;
dfs(v, u);
}
int s = 0;
ll cur = 0;
for (int i = 0, v; i < G[u].size(); i++) {
if ((v = G[u][i]) == fa) continue;
cur += g[v], a[++s] = f[v] - g[v];
}
sort(a + 1, a + s + 1);
reverse(a + 1, a + s + 1);
for (int i = 0; i <= s; i++) {
cur += a[i];
if (fa) {
f[u] = max(f[u], 1ll * min(in[u] + 1 + s - i, out[u] + i) * t[u] + cur);
g[u] = max(g[u], 1ll * min(in[u] + s - i, out[u] + 1 + i) * t[u] + cur);
} else {
f[u] = max(f[u], 1ll * min(in[u] + s - i, out[u] + i) * t[u] + cur);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &t[i]);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
ans += t[u] + t[v];
if (h[u] == h[v]) {
G[u].push_back(v), G[v].push_back(u);
} else {
if (h[u] > h[v]) swap(u, v);
in[u]++, out[v]++;
}
}
for (int i = 1; i <= n; i++) if (!vis[i]) {
dfs(i), ans -= f[i];
}
printf("%lld\n", ans);
return 0;
}
```

### 1394E - Boboniu и коллекция банкнот

Idea: sshwyR

**Tutorial**

Tutorial is loading...

**Solution**

```
//by Sshwy
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
const int N=1e5+5;
int n,a[N],xyx,q[N],c[N],p[N];
vector<int> v[N];
int pos;
void get_v(int pos){
v[pos].clear();
if(pos==1)return;
if(a[pos]==a[pos-1])v[pos].pb(2);
for(auto x:v[pos-1])if(a[pos]==a[pos-x-1])v[pos].pb(x+2);
}
bool check_even_pal(int L,int R){
assert(R<=pos);
for(auto x:v[R])if(x==R-L+1)return 1;
return 0;
}
int qry(){
int res=xyx+c[pos];
int cur=pos;
while(p[cur] && q[pos]<=cur-p[cur]/2){
cur-=p[cur]/2;
++res;
}
return res;
}
int main(){
scanf("%d",&n);
q[0]=1;
FOR(i,1,n){
++pos;
scanf("%d",&a[pos]);
get_v(pos);
int x;
if(v[pos].size() && (x=v[pos][0], check_even_pal(pos-x/2-x+1,pos-x/2))){
pos-=x;
xyx+=2;
}else {
p[pos]=v[pos].size()? v[pos][0]:0;
q[pos]=q[pos-1],c[pos]=c[pos-1];
if(check_even_pal(q[pos],pos)){
q[pos]+=(pos-q[pos]+1)/2;
c[pos]++;
}
}
printf("%d%c",qry()," \n"[i==n]);
}
return 0;
}
```

Auto comment: topic has been updated by sshwyR (previous revision, new revision, compare).I have a doubt in $$$E$$$. The question is asking us to count the number of $$$k$$$ tuples, but I noticed the example had provided a set of $$$4$$$ edges instead of $$$3$$$. Can you please clarify why $$$4$$$ edges were considered ?

K is the maximum outdegree of a node. It has nothing to do with the number of edges.

They have asked to count the number of $$$k$$$ tuples $$$(c_1, c_2, \dots, c_k)$$$

I don't understand your doubt.

In Example 1, the 4 blue edges are just a path that you can follow to start from 1 and end at 1.

In 1395A, "It is meaningless to do operation more than once because we only care about the

partyof $$$r, b, g, w.$$$"I think it should be

parityof $$$r, b, g, w$$$.In 1394A, it should be "Thus they

take$$$(x - 1)(d + 1) + 1$$$" days.thanks!

I think this statement is not clear: " Pick a red ball, a green ball, and a blue ball and then change their color to white ". I thought that the 3 white balls are added in one operation!! But that might just be me!! Anyways, Good problems :)

even i considered it to be 3

i ALSO considered it to be 3

you thought correctly. It indeed mean that 3 white balls are added.

it doesn't matter you consider it 3 or 1 as both the numbers are odd and both of them will change the parity of the white ball

I got WA just because of that line.

In the same question, I am not able to understand why we did this

`fill(b + l + 1, b + n + 1, b[l]);`

Please help me to understand the reason behind it.Thanks in advance!!

Problems are really good! But pretests... rrrrrrr

Great contest ruined by bad pretests.

I agree, skittles1412.

Sorry for that :(

Can someone plz explain his approach for div2D/div1A. I am not able to get the editorial :(

go to second Thread's channel on youtube.....It's well explained over there.

Where can i found it?

Ok, i found it. https://www.youtube.com/watch?v=CvXJ80IIg34

Auto comment: topic has been updated by sshwyR (previous revision, new revision, compare).Auto comment: topic has been updated by sshwyR (previous revision, new revision, compare).Auto comment: topic has been updated by sshwyR (previous revision, new revision, compare).A lot of people FST on Div. 1A (test case 16, 24, ..). Were these test cases intentionally made or just random?

I think all the test case of D1A is random

How is it possible to think that not having multitest and having only random test cases is a good idea?

For me, I can not know most of your thoughts about this problem before contest, so I have no idea about strengthening test cases. It's my first time to prepare Codeforces Round and there will be some shortcomings.

Really sorry for that.

If you don't know how to make good test cases against WA then just use multitest.

I do not know why people complain. Random test cases make it a bit more wild :-)

There is nothing wild about it. It is just frustrating.

test24 is a hack test

The Problems are wonderful! But I think some problems should have stronger pretests (like D1A&B).

I m not sure about my solutin for Div. 2/C 89732880 can anyone counter or prove it?

Problem Div2 (D) / Div1 (A): Why is this code failing on the last test case (test case 30)? Please help!! sshwyRGetting the same failed test case

Can someone please tell why my code for

div2 Cgives wrong output for sample test 3 itself, I have done brute force O(n*m).My idea:for the minimum answer to be obtained, every 'c' should be as minimum as possible i.e (a&b) for corresponding 'c' should be minimum, that's why i have brute forced every 'b' with 'a' to get corresponding (a&b) as minimum.`

UPD: Yes, I didn't get him and everything below is irrelevant.

What can I say, but that's just the wrong way to solve it.

For example (in binary for easier understanding),

`a1 = 10001, a2 = 01110 and b = 00110`

, you can see that`a1 > a2`

, but`(a1 & b) < (a2 & b)`

You didn't get me, your example is irrevelant.

for the minimum answer to be obtained, every 'c' should be as minimum as possiblehere i mean, by performing OR operation b/w two integers, we can never get the answer less than the maximum of the chosen two integers. So when we are doing

`c1|c2|c3....`

we can never get the answer less than the`max(c1,c2,c3....)`

which is why we should try to have each`'ci'`

as minimum as possible, so that the final answer will be minimum. Now for each`'ci'`

to be minimum we must have corresponding`(ai&bj)`

minimum , to get that we check every`b`

with`ai`

and then select that`(ai&b)`

which is minimumUPD :My logic is wrong , In the above i was right till`max(c1,c2,c3....)`

part. Every 'c' being small may not help always. Eg: (provided by pavlovoleg4889) 4|4 = 4 but 4|2 = 6OMG I am relieved to understand why its wrong because I was also thinking like this

Try this small test case:

$$$2$$$ $$$2$$$

$$$15$$$ $$$6$$$

$$$4$$$ $$$10$$$

Your answer is $$$6$$$, but correct answer is $$$4$$$.

Thank you so much brother for the test case, now I understand where i went wrong :)

bro can u help in this..i was also doing in the same fashion as u were doing

Let's say we have choice to choose

`c1 and c2`

from set`{2, 4, 4, 6}`

. Our code chooses`c1 = 2 and c2 = 4`

thinking minimum`c`

's give minimum answer, hence we print 2|4 =`6`

as the answer. But but the right thing to do is to choose`c1=4 and c2 = 4`

so that the answer is 4|4 =`4`

. And it is clear that we were wrong initially because`4 < 6`

Can you please me with this solution ..... failing on third case...

Problem B For some reason, brute force does not give the minimum answer. Just look at the example case...

cx is smaller than cy, but after the or operation, cy gives a smaller result. In brute force, we are always choosing the smaller value for c.

I apologize if I am unclear.

Check the above replies...you'll understand

i am not able to understand 1395 B please help me

You already underestand? U must visit all the cells, you can "jump" in the same row or in the same column doesnt matter the order

Div1B can also be solved without hashing.

The idea is that a permutation is good iff no two chosen edges point to the same vertex. If two edges point to the same vertex, then one of their origins won't loop to itself. The backwards direction is also true: if no two edges point to the same vertex, then the function that maps a vertex to its following vertex is 1-to-1, and is therefore a bijection (since the function is from a finite set to itself).

So, to test a permutation, we need to know that for all i and j, the choices i->c_i and j->c_j don't cause two edges to point to the same vertex. In this case we call the pairs {i,c_i} and {j,c_j} "conflicting".

We can find all conflicting pairs by looking at each vertex in the graph, then seeing for each incoming edge what pair would cause that edge to appear. This can be done in N* ((K*(K+1))/2)^2 time which is good enough.

Actually the complexity itself is not good enough. It requires certain test case based optimisations and imo it can be hacked but I am not sure. It took me quite some time to optimise the solution to work so I'm not sure if it would work for every test case as the TL is pretty strict.

My code's runtime has quite a bit of leeway and no testcase based optimizations despite being O(n * k^4), so I doubt it's hackable. I think the key is just to have simple code with good constant factor by making sure you never iterate in areas that the pair doesn't exist and don't iterate over same pair of combinations twice, and if you math it out constant factor should be p good. Feel free to prove me wrong and hack though!

Hmm, maybe that's true — the true worst case is on the order of 5e8 which might pose some problems.

However, I think the real bound is probably less than N K^4 — since the outdegrees are bounded by 9, that means the sum of the indegrees must not be too big (on average, it's also less than 9). That means at worst, we have N/5 vertices with indegree 45, so it's already 5 times faster than the original calculation.

Similarly, the recursive step can bail out early a lot of the time, and not check every permutation.

It would be interesting to see if there can be really bad test cases that will make it fail though.

The recursive step requires only k! if done correctly using bitmasking. I have inspected SuperJ6 code and have come to the conclusion that even if the complexity seems to be NK^4, but it is not the case. The complexity comes out to be N*KC4 if coded correctly which easily fits in the TL. The complexity and worst case of my code however is still in question as I have applied slightly random method to improve upon the worst case.

Uh O(n * kC4) is equivalent to O(n * k^4), though referring to it as that does show why it fits in time limit more clearly. This is what I mean by if you never check same combination twice constant factor is good when you math it out (which I see you did orz).

Actually, there is an implementation which won't need $$$ N * K ^ 4 $$$ time. We find the reverse graph and for each edge that comes into a node find the pair $$$(i, c_i)$$$ it corresponds to. There can only be $$$O(K^2)$$$ edges at max for a particular node. Calculating the invalid pairs for this node will obviously take $$$O(K^4)$$$. But the fun fact is, $$$ \sum_{i=1}^N E_i = M$$$ , where $$$E_i$$$ is the count of edges coming into node $$$i$$$. So, the amortized time will actually be $$$O(M*K^2)$$$.

why K^4 ? it can be done in O(N*K^2), my code

Or, more precisely, it's O(N*K^2/64) since the extra K^2 factor comes from the bitmask optimization :D

Interestingly, our solution performance times are not that far off, so there weren't any stressful test cases (or maybe the bottleneck was always the permutation bruteforce).

Can you briefly explain your idea? Sorry I wasn't able to clearly understand your code.

it's basically the same as Svlad_Cjelli's solution (see his original comment) but I use bitmasks to reduce the complexity, the number of choices of $$$c_d$$$ is $$$d$$$ so in worst case we have $$$\frac{K*(K+1)}{2} = 45$$$ choices when $$$K = 9$$$, so instead of using hashes or sets, I use bits stored in long longs, I maintain for each $$$(d, c_d)$$$ a mask of bad choices (choices that can't happen if I choose $$$(d, c_d)$$$) called hate, in the backtracking step I maintain a mask called forbidden and to update it I or it with the value of hate[the current choice] and never use a choice that is in the forbidden mask or that invalidates itself

Thanks a lot! I am relatively new to bitmasks so I had difficulties of understanding, thank you for the clear explanation.

I did reverse of approach given for Div2D. First I calculated sum for all small items and found how many remaining days we have for big items. Then everytime we take minimum of small item we check if we can add big item with given number of days left. Print maximum for all those cases.

Submission

Why are you adding negative of small items to mn pq and subtracting from the sum?

For smaller items, we need to take minimum at each step but CPP priority_queue is max heap by default. So we add negative values to use it as min heap.

you can use priority_queue<int, vector, greater> for min heap

I have a better approach for Div 2 C.For each a[i],find the minimum value of c[i].Then find the maximum among all the c[i].Now brute force this maxi with all possible a[i]*b[j] to get the ans. Time complexity(O(n*m)). Link to my submission:- https://codeforces.com/contest/1395/submission/89722222. Think a little bit and you will get why it works.

hi could you please explain why you ORed maxi with x in your last loop? thanks!

By now,I know that one among c[i..n] is maxi.So I checked that for a particular i, for which value of a[i]&b[j],the OR with maxi comes out to be minimum.That's it.

Your solution is flawed and only works because of weak test cases. A hack was submitted against it. Try submitting the same code again.

Or try case:

54 12

435 115 422 469 19 176 292 395 273 217 160 343 277 500 124 360 315 59 2 477 465 138 175 392 146 438 4 96 231 182 257 183 51 117 430 125 167 107 238 66 236 96 319 62 365 186 83 414 166 198 224 129 60 195 327 62 310 278 300 228 295 113 502 320 463 223

You will get 63, while the correct answer is 62

(Case created by GlobalElite)

can u explain why his method is wrong? why the solution is incorrect?

I don't know. I just tried the same logic and it failed. So I thought I would tell him too.

Yah I got it bro.Thanks for the test case.It also fails for the this test case also:- 3 2 3 10 128 130 137.

Nice test case, but in both hack test cases, the expected answer and the participant's answer differs by 1 :/. Is it just a coincidence or there's some logic behind it? UPD: i got it, it was a mere coincidence

Any idea why it fails bro?

Yes. Take the test case

2 2 10 7 13 6

Here if you take the bitwise and between ai & bj with a bruteforce you get the following matrix(candidates for c1 and c2) {8,2} {5,6} this code chooses {2,5}, so my code here chooses 5 as it maximum and in first case compares 5|8 which is greater than 5|2 so 5|2(7) is printed. But, if u look carefully u can choose c1 as 2 and c2 as 6 and get 6 as the answer. So, this greedy solution is completely flawed.

Got it. Thanks!

sshwyR For Div 1 E, where are key points 2 and 3 proven?

The formal proof will be too verbose so I'm trying to explain it intuitively using pictures and examples

For key point 2, basically, we can use "change blue to red" skill (picture in S 1.2) to prove that, for two different folding methods A and B resulting in the same sequence, we can do "change blue to red" several times to make A equal to B.

key point 3 is obvious, beacuse the method it discribed leads to alternate mountain and valley folds. So each fold contains exactly one layer of paper.

For key point 2, aren't we trying to show that "all folding methods result in the same sequence," not "given two folding methods that result in the same sequence, we can convert one to the other"?

Also, I don't see why it is obvious that the method produces alternating mountain and valley folds.

Specifically，we trying to show that "all folding methods,

which don't have any more available folds, result in the same sequence".And yes, we can convert one to the other.

For example, in this picture, the first method is physically not correct because you may damage the paper to make it.

But the second one is physically correct, and also the result of both are the same. Thus we don't care about how you fold -- even it is physically not correct. Because you can always trasform it to be physically correct. And alternating mountain and valley folds is always physically correct. Thus we say the method produces alternating mountain and valley folds, it actually means we don't need to care about whether it's mountain or valley.

We just care about the position of fold marks

Yes, I see why you can convert one to the other. But I still don't see how this relates to "all folding methods, which don't have any more available folds, result in the same sequence."

Maybe we can use proof by contradiction. Suppose method A results in a[l1,r1] and method B results in a[l2,r2] and we can prove that one (or both) of them has more available folds

I still don't know why "all folding methods, which don't have any more available folds, result in the same sequence."

By the way, I think you were just proving key point 1 in the previous messages. Isn't "We just care about the position of fold marks" key point 1?

The sentence "For key point 2, basically, we can use "change blue to red" skill (picture in S 1.2) to prove that, for two different folding methods A and B resulting in the same sequence, we can do "change blue to red" several times to make A equal to B." is also to prove key point 1, although you start it with "For key point 2,".

Can anyone tell why my code of Div-2 D is giving RE on testcase 3

See this. link

A should have less than or equal to, not just less than

Thank you :)

could u plz explain me just this one line in brief..why all shuld be equal to A?

Can anyone explain why we check that A[i] & B[j] | A == A for problem C?

None of c1,c2,c3...cn can have any bit set that's not set in the result, because of the OR operation. Hence if we can find a ci = Ai&Bj whose set bits are a subset of the result's set bits then we are good with the ith value in the size n array. Hence, this line.

because A[i]&B[j] can be substituted for C[i]

Can anyone explain Div2 C?Didn't understand the Editorial.

Div2. C can be solved in $$$9 * n^2$$$ by greedily eliminating possible values for every i. https://codeforces.com/contest/1395/submission/89696347

2^9 right?

you can also solve with sort of minimum for each a[i] https://codeforces.com/contest/1395/submission/89690151

This solution is wrong UPD: Hacked

test case54 12

435 115 422 469 19 176 292 395 273 217 160 343 277 500 124 360 315 59 2 477 465 138 175 392 146 438 4 96 231 182 257 183 51 117 430 125 167 107 238 66 236 96 319 62 365 186 83 414 166 198 224 129 60 195

327 62 310 278 300 228 295 113 502 320 463 223

(

very strong tests)

Why this test case hacks that submission. What is wrong with that submission? Can you please explain with a small test case??

Could you please explain your solution?

look at this solution for c https://codeforces.com/contest/1395/submission/89690151 why is it works?

Can Anyone Share A dp solution for Div-2 D ?

i have only prev solutoin((

if prev_sum is dp i have https://codeforces.com/contest/1395/submission/89716126

No I'm looking for some other approach :p

My Idea was to store the number of items of $$$type1$$$ and $$$type2$$$ ( Where $$$type1$$$ are the types for items which are greater then m and $$$type2$$$ for less.) and transitons based on their corresponding values using prefix-sums.

However I'm get WA5 and would be nice to hear some similar (or other?) $$$DP$$$ approach.

please ignore

This is Div-2 C I reckon. Though Thanks Anyways.

Can Someone please elaborate the 1394C problem. Plz explain what this part is doing Check(ans^(1<<i))?ans^=(1<<i):0;

Can someone explain the logic behind to find the point $$$(x_{t}, y_{t})$$$ when the radius $$$r$$$ is fixed, in the problem 1394C?

I enjoyed the problems :)

Can someone please explain the dp solution to Div 2C ?

I wrote the following DP solution to Div 2C which is giving wrong output on sample 3. Can someone please help me why is this wrong?

Спойлерvviwv(dp, 210, 520, INF); // int dp[210][520]

int main() {

}

dp[i][v] is the best result if you reach index i with value v.

codeThanks a lot for such a beautiful solution sir!

Solution

In Div2C, we can have $$$O(9nm)$$$ time with $$$O(nm)$$$ additional memory.

Submission

I did the same (although couldn't submit during contest). And Rank 1 fellow also did the same way. I liked how he/she used ok[][] matrix instead of set to take care of adding and removing number :D

Can someone explain the solution of Div 1-B with hashing?

I solved it (although after the contest), but without hashing and I have no idea what hashing has to do with it.

If you assign a random integer to every element in a set, then for any subset you can compute the sum (or other associative operation — for example xor), Then if two subsets are different, they are highly unlikely to have the same hash value. That is much faster than comparing the sets directly.

In this problem for each assignment i -> c[i], you can figure out the set of vertices pointed to under that assignment. An array c is good if all those sets cover {1,...,N}.

Ok, thanks.

So with hashing solution we check with a hash that each vertex has exactly one incoming edge.

While with normal solution we check that each vertex has no more than one incoming (from which it follows that there is exactly one) edge, by computing rule (i->c[i]) incompatibility matrix.

Can someone help me solve div2C with DP? By the way, let's see what's wrong with me. https://codeforces.ml/contest/1395/submission/89746733

Here's my code using DP approach, I commented it a little bit but if you have any doubt, just ask me :)

can you tell your approach? UPD: I figured it out. But you may write if you want.

can u tell me what's wrong with my transition function ??89813834

I'm sorry but i don't get what are you saving in dp[i][j] and ae[i][j], can you explain it a little bit?

dp[i][j] stores pair wise and values ith in 1st array jth in 2nd array

ae[i][j] builds the solution upto ith index optimum answer if ya use jth value in latter array

Here's is my top-down dp approach :> 172519561

Hey, can anyone help me out with what is wrong in my code (Div2D/Div1A)? Can't seem to understand as to what should I do?

For 1394A, how is the starting value of i in the code ( (k + d)/(d + 1) ) determined? I don't understand what it does.

Those are the minimum no of funFactors(of type-1) which can be added to the answer,this case is when all the type-1 funFactors are consecutive.

i dont get how this works in div2 C (ai&bj)|A=A ? Any help ?

Could someone help me please with Div2-D? Can't understand why my submission fails on test 6 https://codeforces.com/contest/1395/submission/89750243

Can someone show me how to do the condition test in Div1/C Div2/F. I mean, how can we do binary search on two coordinates x and y?

Tutorial for Div2 C is great , but is there any other non brute force approach ?

Yes of course. In fact $$$9n^2$$$ is easy too, and I think there should be a $$$n\log^2$$$ solution.

Please share the approach.

:v

Banging my head because solution of Div2/C turned out to be way simpler than I thought

Hi SevenDeadlySins, Can you let me know what's wrong with my approach? I am using the properties of & and| OR of two numbers is greater than or equal to the maximum of those two numbers. AND of two numbers is less than or equal to the minimum of those two numbers. so if I do AND of a[i] and the smallest element of B then I will essentially minimize each element of C. And this way we can minimize the OR of all elements of c

Thanks a lot :)

Nevermind, I understood what the issue was :)

@Code_M I tried your approach, but got wrong answer. I didn't get the issue yet. Can you please help me by explaining what the issue is ??

In the 1395A, in the solution part,in the elif statement it should be "check(r-1,g-1,b-1,w+3)"

Parity will be same for w+3 and w+1.

Ohh yaa thanks

Why DFS does not work for problem B??

https://miro.medium.com/max/700/1*RoyONSeJY_UsGPGOib9RXw.gif

see this see the move 13th

got it thanks

This is my code for Div2A can someone pls tell me what is wrong in this logic .89736361

Problem B: Can any one tell me whats wrong in my code?

My code

Initial position is wrong in your solution. I mean that first move should always be at square sx,sy as it is given in question that initially it is at square sx,sy.

So initially you are at (sx,sy). So first square will be this,then cover squares in that column or row. Then move to (1,1) and cover rest rows/columns in a sequential manner.

Hope you got the point.

I didn't got editorial solution for div2 C.

can anyone explain in some clear way with some example??

Please!!

check this

Can someone please explain why I am getting wrong answer on test 5 of Div 2D. Here is the link to my code:- My submission

The big ones are placed on first day, then after d days, and one as last element.

For this last element we need to check if we used small elements at all, and if one big element is available. I think these checks are not correct in your code.

Can you provide some test case as well. I still didn't get what's wrong with my logic.

Now I get what you are saying. Thanks for your help. I found my mistake now.

Hi sshwyR, in the problem div1-C how to prove that the function in xOy is unimodal?

The sum of unimodal function is still unimodal. This is the key to prove it :)

The sum of two sharp peaks that are far away from each other is a function with two sharp peaks, which isn't unimodal.

please consider the function in this problem instead of any unimodal function

Okay, but the question was how to prove that this function is unimodal. We can't use a statement that isn't always correct to prove it and we can't use the fact itself to prove itself either.

The first thing is to prove $$$dist$$$ is unimodal on a line. Take x axis for example, any other line can be rotated and shifted to be it.

Let's say $$$f(x) = dist((x,0),(X,Y))$$$ where $$$(X,Y)$$$ is fixed. Thus it is obvious that $$$f(x)$$$ is unimodal.

Well, let's say $$$f_2(x) = dist((x,0),(X_1,Y_1)) + dist((x,0),(X_2,Y_2))$$$ where $$$(X_1,Y_1)$$$ and $$$(X_2,Y_2)$$$ are both fixed. Thus we can prove that $$$f_2(x)$$$ is still unimodal.

Thus for $$$g(x) = \sum dist((x,0),s_i)$$$, we can also prove that $$$g(x)$$$ is unimodal.

Notices that this proof can apply to

anyline.Thus for

anyline, $$$g$$$ is unimodal.So we get the final part: the function in xOy is unimodal. you can use reduction to absurdity.

Were you or anyone else was able to prove that the function in xOy is unimodal? I'm still struggling to prove it.

u can read my reply to Xellos :)

can someone tell me how the complexity of div2 problem c is O(2^9*n*m). We run a loop from i=8 to 0, then the complexity should be O(9*n*m) as what I think. Please correct me because I know I am wrong but don't know where I misses out....

Can anyone tell why dfs traversal is not working for Div2B problem. My solution https://codeforces.com/contest/1395/submission/89697375

https://miro.medium.com/max/700/1*RoyONSeJY_UsGPGOib9RXw.gif see 13th move

Can someone please tell me what I'm doing wrong in my Div2D submission? The idea is to enumerate all the possible combinations of numbers which are bigger than m and calculate the result with prefix sum. Code: https://codeforces.com/contest/1395/submission/89766414.

If I understood correctly from your code that you are only considering the case of, if you take

kbig values then you have to coverk*ddays. Which is not always true. You can also takekbig values but with(k-1)*ddays and placing the remaining one big value in thenthposition, which will not coverddays. For better understanding you can see my code. Hope that helps. codeIn the code I'm trying to cover that case with

`if(space >= d) space -= d;`

(i.e. whenever we can put one big value in last position, we put it).In this case you have to put the last element in the (n-1)th position which will cover 1 day instead of 0 day which is optimal in this case.

Need help with DIV 2D...fails on TC 16

Can someone please explain the second problem

1395B — Boboniu Plays ChessI am unable to understand the editorial as to how the formula foris getting derived?f(i,j)but i m not able to implement it:(

DIV2 CCan someone help me with this ,it is not passing 3rd pretestsomeone please help.....

How to check if there is a hexagon cover all points on a fixed radius?

Can C be solved without explicitly checking all the possible values?

Can someone suggest some good blog or video to understand the execution of hashing used in div 2 e/ div 1 b 1394B — Boboniu Walks on Graph.....I understand the idea I just need to understand the implementation.....

For Div-1 C if the function is unimodal can we use ternary search over x's that is number of B's in the final answer to solve it?

I think simple ternary search over the number of Bs and Ns is not an intended solution. I upsolved it with simple ternary search with some optimizations, but it was barely within the time limit. It might just be because my code is badly written though. If you're interested anyway, here's my submission.

Should ternary search work for this problem?

let f(x,y) be the distance if answer string has x B's and y N's.

let g(x) = min(f(x,y))

If we consider a string s = "BBN".

for x = 1. g(1) = 1, as we can add BN to the end of the string B

for x = 2, g(2) = 1, as we can add N to the end of the string BB

In this case g(x) = g(x+1), doesn't ternary search fail if there are equal values.

I was trying to write a soln based on ternary search but got WA 90523331

You might be getting WA because you're comparing values right next to each other. I can't think of any other explanation. For example in classic ternary search you investigate the points $$$mid1 = (2 * lo + hi) / 3$$$ and $$$mid2 = (lo + 2 * hi) / 3$$$. These points are far away enough to work well (in this problem at least). In your case the values have a high probability of being the same, since you are investigating points that are very close to each other, and if they are equal you always move $$$lo$$$ to $$$mid$$$, although the optimal point may be to the left of $$$lo$$$. Do correct me if I'm wrong about anything I said though, I'm not exactly an expert on ternary search or unimodal functions.

Yeah, this might be the issue with my solution. You are right, my ternary search won't work in this case.

can anyone please explain DIV2B?? I am unable to understand the tutorial.

You could give some hint on which part you did understand, and which not.

I have a question about Div. 1-A.

Does anybody know why in the tutorial they are filling the array of the smaller elements with the last value as if there were more small elements?

I have made two submissions 89774711 and 89774745. The only difference between them is that in the second one I have commented out line 96 which is equivalent to the

`fill`

call in the tutorial. And the way I see it by adding those values to the end of the prefix sum we would be considering cases that are not valid because they have too many small elements.Can anybody please explain this to me?

It an array of prefix sums. Ie setting the elements all same is like adding zero elements to the end of the set of smaller elements.

Thanks!!

I was trying to argue back but thinking of it as adding zeroes made me understand why it works.Just in case anybody has the same doubt I'll elaborate on why I got confused with this:

For this testcase, the best I had been able to find was

`11 8 8 8 11`

. But it turns out`8 8 8 11 11`

is better.However if you don't add the zeroes you won't find the second one since the code (at least mine) expects two days of being muzzled after each big number but that is not always the case.

I also had a similar problem, which resulted in the

out of boundsof the smallSum elements. I think the reason why we fill the array with some elements (I think they are zeros) is not to reach out of bounds --> avoid this case wisely by the addition of the elements. However, I found an alternate solution rather than filling the array which is taking minof (smallSum.size(), n — 1LL * (i — 1) * (d + 1) — 1). It handles the case efficiently without any operations.WA submission : 90204055 AC submission : 90206949

Thanks ,got it why they fill with last elements with same number

How to solve Div. 2B (Bononiu Plays Chess) if a rook when travelling from (X1 Y1) to (X2 Y2) also travels all squares between the two points? (that is unlike the problem, you cannot "lift" the rook.

I think then we should go in spiral but there will be some cases when we can not fill it in any combination

yes I was thinking it involves Euler Trials, wanted a rigorous solution or atleast ideas for one..

Were the test cases hard to prepare for div1B? How did you go about it? Also, is there any test case where both (a). for any out degree from 1 to k, there is at least one vertex having that out degree; and (b). the answer is big (i.e. > 1000, say); hold? I can't think of any test case like this, but I find it a relevant question: If there are only a few solutions, some more permissive heuristics + brut-force check would also solve the problem.

How to solve Div2C using dp?

Why is he using XOR operation in Div2C solution (in tutorial)?

I know it is apparent but still, Div2 E doesn't mention clearly that array c should be a permutation of 1,2...k so someone could mistake it by using repeated values in c.

Why it should be a permutation of 1,2,...k? In the example they clearly used repeated values.

In 1394D:

challengesIn 1394E there are several corrections:

askingus to calculate the number of folds, butratherthe number of folding marks.methodsto fold itrepresentedbyis itreally?noticedleadstomethodstransformedyou understandthe folding operation intuitively, it'll be quite easy to come up with a naive algorithmthatruns in polynomial time.understoodthem, skip this section and read the algorithm partsubstringsdenotethe center positionproof by contradictionis place ofreduction to absurdityCan somebody explain div2 C? The editorial is confusing.

It is

All numbers are up to 511 so there are only 512 (from 0 to 511) possible answers. You can just check all of them from 0 to 511 (because we need the minimum we check from lowest to biggest). Check each guess directly, without any optimizations (~ n*m operations) — I believe you'll figure out this part.

Thanks, it helped.

I wrote a simple backtracking solution for Div2C during the contest which obviously got a TLE verdict. After the contest I applied DP on top of it and got AC. If anyone's interested, here's the submission: 89782618

Can you explain the base case? Like why are you returning the value of Xor computed along that path?

The index variable refers to the values stored in vector $$$a$$$. For each value in vector $$$a$$$, it can be AND-ed with each value in vector $$$b$$$. The for loop denotes that part. Remember the $$$c$$$ vector stores the OR of each AND $$$(a_i \& b_j)$$$. The OR variable is just doing that. It can be solved by DP because there are overlapping sub-problems. The base case happens when you reach the end of vector $$$a$$$ i.e. you have constructed the a $$$c$$$ vector of $$$n$$$ elements whose ORs are stored in the OR variable.

Can someone explain me Boboniu Chats with Du approach??

I just finished Div 1-C and after reading the editorial, I may say that the proposed solutions are strange: hashing for 'B', Hill Climbing Algorithm for 'C'...

for C , when distance is fixed (say d), we have to check whether every region has a common point. Each hexagon can be described as (lx<=x<=rc) and (ly<=y<=ry) and (lxy <= x-y <= rxy). So for each dimension we can easily get a common interval, and the common area is also of that form. Then we can check in O(1) time.

Nice wow!

For the second question, I got this output for the first test case. But I am getting Wrong Answer. Can anyone help pls? 2 2 1 2 3 2 2 3 1 3 3 3 2 1 1 1 3 1

I know that editorial for Div1C mentioned the randomized solution because it was considered to be

simplerthan binary searching + checking one. But here I want to discuss the later solution with brute force instead of binary search, which is actually simple to implement.The core idea of this solution that we need to find $$$x_t, y_t$$$ and $$$r$$$ such that the hexagon covered all the points. To make this simpler, let's project all the points onto 3 axes: $$$Ox, Oy$$$ and the line $$$y = -x$$$. I do claim that hexagon can cover all the points iff we project the hexagon onto these 3 axes, the ranges made by the hexagon also cover the projections of the points. I don't have formal proof yet, but this is intuitively true. Feel free to share it if you guys have one.

Now we can fix either $$$x_t$$$ or $$$y_t$$$ and find the other one. But I like to fix $$$y_t - x_t = diff$$$, i.e the projection (or 2 times the projection) of $$$(x_t, y_t)$$$ onto $$$y = -x$$$, and find the coordinates. Firstly, we can find minimum $$$r$$$ for covering the points on the axis $$$y = -x$$$. Secondly, since we have known $$$diff$$$, we can actually combine projection on $$$Ox$$$ and $$$Oy$$$ into one: we keep all projections on $$$Oy$$$ the same, and add $$$diff$$$ to every projections on $$$Ox$$$. Sound like $$$O(n)$$$, but we don't care about the points, only the endpoints of the range made by projection, so this is instead $$$O(1)$$$. After that, we got a big range of projections, and the middle points is the optimal one. The optimal $$$r$$$ is the minimum of $$$r$$$ for $$$y = -x$$$ and $$$r$$$ for the combined axis.

Finally we brute force $$$diff$$$. Since $$$0 \le x, y \le 5\times 10^5$$$, the range for $$$diff$$$ is not that big. Hence complexity is $$$O(\max |S|)$$$.

That is indeed true,

because hexagon = intersection of square with "infinite diagonal slice".

And in general:

if C = intersection of A and B

then P is in C <=> P is in A and P is in B

(by definition of intersection)

Although I didn't understand your solution. Can you link to your submission?

If you dig up my submissions it is still around at the top tho. But here you go submission

Hi, I was unable to understand how you combined projection on

OxandOy, why addingdiffto every projection onOxand keepingOysame will combine the two range of projections. Can you help? Thanks!As I said before we can either fix $$$x$$$ and find $$$y$$$, or fix $$$y$$$ and find $$$x$$$. But I don't like that so I fix $$$diff = y - x$$$. And because of that, we also have $$$y = diff + x$$$. So yeah, we can project all the points from $$$Ox$$$ onto $$$Oy$$$ simply by adding $$$diff$$$.

Thanks, I found your solution much easier to follow and understand. I felt like the editorial one was missing a lot of details that are not necessarily trivial.

I found A somewhat tricky for A and found B harder than C or D. In C and D, I knew approximately what to do — what exactly and how to do it were mostly details. Also, all my solutions were deterministic and those hashing solutions are way too risky, especially in C compared to binsearch + checking 6 nice types of inequalities.

My solution to div1B is based on rewriting the rule for "at most 1 incoming edge to each vertex" to forbidden equalities and pairs of equalities "$$$c_x=y$$$" and then the rule for "at least 1 incoming edge to each vertex" into "if we choose $$$c_x=y$$$, how many edges do we add?", where we want exactly $$$N$$$ edges in total. There are $$$O(K^4)$$$ pairs of equalities, which gives $$$O((K+4)!)$$$ time complexity, but the constant in it is nice and the checks are simple enough that it's very fast. Still, miss one idea and you can be stuck with what ends up as just $$$O(NK!)$$$ heuristic.

What! Div2 C was that easy. I wasted 1 hour over complicating such an easy problem!!

Div2 problem C Can anyone explain, why if answer is A, then for all i (1<=i<=n) ci | A is A?

Let a|b = k and consider a = 100110 and b = 111001 now a|b = 111111, if you check the condition then it hold up. This is occurring because k will be greater than both a and b and there is no possibility remain that a bit in k is 0 while it is 1 in either of a and b. Hope it helps

Ok, got it, thanks

Please anyone help me understand the div2D/div1A solution

Problem div2D/div1A is one of the Prettiest Greedy Problems I've seen so far!Honestly, I gave up on it 30 minutes before the contest, but just Love the Problem.

My Attempt to Problem DMy approach is pretty similar to editorial's . I'm just going to explain my Code.

Create 2 vectors big and small and descending sort them.

Prefix sum them both.

For every i in big, [0-indexed]

We take [0...i] big numbers.Now we keep 1 big number at the end of permutation always, and we now have to muzzle/skip (i*d) numbers.

We muzzle all the rest [i+1...big.size()] big numbers. Also muzzle some small numbers [small.size()...j] , if needed.

Calculate answer for each i in O(1) as we know how many to muzzle in big , and how many to muzzle in small, to keep [0...i] big numbers. Calculate maximum!

My Submission

But instead of muzzling the remaining big numbers shouldn't we muzzle the small numbers instead?

Not Always.

Assume a case where n=12, d=4, m=20

big [ 23 22 21]

small [19 19 19 19 19 19 19 19 19 ]

Here we take the first big number 23 and keep it at the end of Permutation. No Problem.

Now if you take the number 22, you have to muzzle 4 small numbers, resulting in losing 19+19+19+19=76 for 22. Not a good option.

For anyone interested, I implemented it based on satashun comment in $$$log(maxDist)$$$, where $$$maxDist$$$ is the maximum distance between any two strings ($$$+ O(n)$$$ for reading the data).

https://codeforces.com/contest/1394/submission/89813839

Hey, Isn't the solution given for Div2/C of complexity $$$O(9nm)$$$?

The for loop in

main()runs only 9 times.When using the big-oh notation, O(c ⋅ f(x)) (where c is a constant) is the same as O(f(x)).

Yep they had given 2^9 in editorial that's why I asked. Loop runs only 9 times right?

Do you guys call "tutorial" of B a tutorial? I would see the same information about this problem in others code.

Here are my video solutions for all div. 2 problems (A-F, A-C for div. 1). Sorry that they're a bit late, I was mostly grappling with trying to upsolve 1C (unsuccessfully).

I have tried the following approach for div.2D( div.1A):

onelargest unused Y or d+1 largest unused Xs (whichever adds more to the final answer). N decreases by d+1.usedXs. (This is done only if the final answer increases)Why does this approach fail?

I guess there might be a solution of Div2 C with the a complexity of $$$\mathcal O(n^2 \log a)$$$ instead of $$$\mathcal(n^2 a)$$$ in tutorial.

enumerate bits from the highiest bit to see whether each $$$a_i$$$ has a $$$b_j$$$ satisfies $$$a_i \verb'&' b_j$$$ is $$$0$$$ in the current bit. If so, mark every $$$b_j$$$ of $$$a_i$$$ where $$$b_j \verb'&' a_i$$$ is $$$1$$$ in the current bit in a two-dimensional array to show that that $$$b_j$$$ is not good for $$$a_i$$$. And we wouldn't consider that $$$b_j$$$ in the following bits of $$$a_i$$$. If not, add $$$1$$$ to the current bit of the ans.

https://codeforces.com/contest/1395/submission/89796424

Can anyone Explain The div2 D. I don't understand whether I have misunderstood the question or missing any important point.

Errata: Example 2 in 1E should be [1,1,−1,1,−1,−1,1,1,-1], the last element is wrong.

I think?

Can anyone explain why the red case in 1E 4.3 Key point 4 is neccessary true? I can se it for the other two cases but not that one.

I have a question which might be bad Doesn't taking lowest possible ci always result in best result we can achieve since OR is like addition what's wrong in my process??

During the system test, I got WA41 in task B. When I submitted the same code, but after the final results, I received an OK verdict, while I checked my code on test 41 using my checker and the answer turned out to be correct. Can someone explain the reason for UB in my code?

Wrong answer: 89685485

Accepted: 89846084

`vector<bool> used1(m + 1, false);`

but then how did it got AC in c++17(64) ?

About question 1395C - Boboniu и битовые операции: what is the point of this piece of code? I think I understood the explanation but not the code below.

It seems to be updating the answer while checking if each bit can be achieved according the logic described on tutorial. Still I couldn't get this part.

how can i apply dp in Div2 C ?

i tried but it failed test case 9. Here is my code :

## include<bits/stdc++.h>

using namespace std; int a[201],b[201]; int d[201][201]; int check(int ans,int i,int n,int m,int d[201][201],int k) { if (i >= n ) return ans;

if(d[i][k] == -1) { int mm = INT_MAX;

} return d[i][k]; }

int main() { int n,m; cin>>n>>m;

for(int i =0;i<n;i++) { cin>>a[i];

} for(int j =0;j<m;j++) { cin>>b[j];

}

for(int i =0;i<n;i++) { for(int j =0;j<m;j++) { d[i][j]=-1; } }

//int ans = check(0,0,n,m,d,0); int mm = INT_MAX; for(int j = 0;j<m;j++) { // cout<<i<<" "<<j<<"\n"; int p = check(a[0]&b[j],1,n,m,d,j);

}

cout<<mm<<"\n"; return 0; }

Hi, sshwyR

Thanks a lot for great problems and your extensive effort. Problem D was one of the most elegant greedy problems I have ever solved.

For div1B , can anyone please discuss about the probability of collisions?

Editorial to the problem D1A/D2D is not clear. Can someone please explain the approach clearly?

In problem A, it's actually w+3, as each ball we select becomes a white ball, although w+1 does not change the parity,it would be more correct to make it w+3

Bobonui Chats with Du: I feel like instead of writing (x-1)(d+1) + 1 for big items, if we write (x-1)d+x then it will make more sense and intuitive.1394A - Boboniu общается с Du

Didn't Understand Div2- Problem C tutorial. Can someone please explain the logic more clearly? Please help. Write login in reply

div2 c...

solution with comment

For B if we define:

F(i, j) = ((S_x + i — 1) % n + 1, (S_y + j — i — 1) % m + 1)

And we print the value of F in row first order for 0<= i <= n and 0 <= j <= m, we can get the answer without odd / even branching. We just need to define the mod for negative numbers properly.

In problem C what happens if I choose the best b[j] for any a[i] ?

If I get the Minimum (a[i] & b[j]) for every i why am I not getting the Minimum c1|c2|..cn ?

it is wrong because of bits.

let min(a[i1]&b[j]) is 101001

let a[i2]&b[j] is 1)000101 or 2)001001 or 3)101001 if we

select min of a[i2]&b[j] i.e the first one 000101 then

our final ans is min(a[i1]&b[j])|min(a[i2]&b[j]) then it is

101001

000101

or

101101 =a

****but if you take the 3rd one i.e 101001

then final ans is

101001

101001

or

101001=b

you see that

a>b

so your approach is not right

..i think this will helpfull

solution with comment

I have a submit for Div1E and it may O(nlog^2n). I write a Chinese explain for it.

sshwyR SecondThread Monogon — Since this post is ~ 2 months old, hence tagging few members. Please don't mind.

Can someone please explain the hashing part in Div2E? I understand that we want to compare the union of sets to {1, 2, 3, ..., n} using hashing e.g. union of {1, 2, 4} and {3, 5, 6} is equal to {1, 2, 3, 4, 5, 6}

I tried hash as product modulo prime but I got an error on 8th test case and I realized that this is not a good way to hash because it can generate same hash for distinct sets

Is there any blog/tutorial that I can follow to understand this? Any help will be appreciated

you may use multihash with random value, like val[i] in the solution :)

what do parity mean?

Nice solution. In Div1B, as you mentioned, we can use many functions h(T) for an integer set T, like \pi or \sigma mod(-ed), or even XOR; but I tested AND and OR operator, they were not strong enough. Also, the idea of creating val[x] randomly is smart, without it, none of the function is strong enough to pass the tests.