Thank you for participating, and I hope you enjoyed the problems!
1395A - Boboniu Likes to Color Balls
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 Plays Chess
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 and Bit Operations
Idea: Retired_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 Chats with 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 Walks on Graph
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 and String
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 and 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 and Banknote Collection
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 party of $$$r, b, g, w.$$$"
I think it should be parity of $$$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 :)
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
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!! sshwyR
Can someone please tell why my code for div2 C gives 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 thata1 > a2, but(a1 & b) < (a2 & b)Try this small test case:
$$$2$$$ $$$2$$$
$$$15$$$ $$$6$$$
$$$4$$$ $$$10$$$
Your answer is $$$6$$$, but correct answer is $$$4$$$.
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
A should have less than or equal to, not just less than
Thank you :)
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.
Div2. C can be solved in $$$9 * n^2$$$ by greedily eliminating possible values for every i. https://codeforces.com/contest/1395/submission/89696347
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
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
(
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??
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 :)
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?
For 1394A, how is the starting value of i in the code ( (k + d)/(d + 1) ) determined? I don't understand what it does.
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.
Banging my head because solution of Div2/C turned out to be way simpler than I thought
Why DFS does not work for problem B??
https://miro.medium.com/max/700/1*RoyONSeJY_UsGPGOib9RXw.gif
see this see the move 13th
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 any line.
Thus for any line, $$$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 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 k big values then you have to cover k*d days. Which is not always true. You can also take k big values but with (k-1)*d days and placing the remaining one big value in the nth position, which will not cover d days. For better understanding you can see my code. Hope that helps. code
In 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).Can someone please explain the second problem 1395B — Boboniu Plays Chess I am unable to understand the editorial as to how the formula for f(i,j) is getting derived?
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
fillcall 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 out8 8 8 11 11is 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 bounds of 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?
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.
Can 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 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!
I know that editorial for Div1C mentioned the randomized solution because it was considered to be simpler than 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 Ox and Oy, why adding diff to every projection on Ox and keeping Oy same 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 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)).
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 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
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.
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) ?
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?
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 Chats with Du
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 :)
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.
A query: If in 1:C we had equality instead of similarity & it considered total cost-> summation of min-distances instead of max, how could it be approached? Would really appreciate the help! Thanks