### sshwyR's blog

By sshwyR, history, 3 months ago, Thank you for participating, and I hope you enjoyed the problems!

Idea: dqa2020

Tutorial
Solution

Tutorial
Solution

Idea: xryjr233

Tutorial
Solution

Idea: sshwyR

Tutorial
Solution

Idea: sshwyR

Tutorial
Solution

Idea: sshwyR

Tutorial
Solution

### 1394D - Boboniu and Jianghu

Idea: ZZZZZZZZZZZZZZZZZZ

Tutorial
Solution

### 1394E - Boboniu and Banknote Collection

Idea: sshwyR

Tutorial
Solution Tutorial of Codeforces Round #664 (Div. 1) Tutorial of Codeforces Round #664 (Div. 2) Comments (252)
 » 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.
 » 3 months ago, # | ← Rev. 3 →   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!
•  » » » 3 months ago, # ^ | ← Rev. 3 →   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.
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   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.
 » Problems are really good! But pretests... rrrrrrr
 » Great contest ruined by bad pretests.
•  » » 3 months ago, # ^ | ← Rev. 2 →   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
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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?
 » 3 months ago, # | ← Rev. 2 →   Problem Div2 (D) / Div1 (A): Why is this code failing on the last test case (test case 30)? Please help!! sshwyR
 » 3 months ago, # | ← Rev. 4 →   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. int main(){ int n,m; cin>>n>>m; int a[n]; for(int i=0;i>a[i]; int b[m]; for(int i=0;i>b[i]; vector c; for(int i=0;i
•  » » 3 months ago, # ^ | ← Rev. 2 →   UPD: Yes, I didn't get him and everything below is irrelevant. for the minimum answer to be obtained, every 'c' should be as minimum as possible 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)
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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 minimum UPD : 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 = 6
•  » » » » OMG 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 choosec1=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... #include using namespace std; #define int long long int f; int solvebit(vector& b,int bit,int ans,int n) { if(bit==-1)return ans; if(f[bit]==0)return solvebit(b,bit-1,2*ans,n); vector zeroes; for(int i:b) { if((i>>bit)&1)continue; else zeroes.push_back(i); } if(zeroes.size()>0)return solvebit(zeroes,bit-1,2*ans,n); return solvebit(b,bit-1,(2*ans)+1,n); } signed main() { int n,m; cin>>n>>m; int a[n]; vector b(m); for(int i=0;i>a[i];} for(int i=0;i>b[i];} for(int j=0;j>i)&1)f[i]++; } } int ans=0; cout<
•  » » 3 months ago, # ^ | ← Rev. 2 →   Problem B For some reason, brute force does not give the minimum answer. Just look at the example case... case:1 cx = 00010 c2 = 10101 cx | c2 = 10111 case:2 cy = 10000 c2 = 10101 cy | c2 = 10101cx 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
•  » » 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.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   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.
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   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 :DInterestingly, 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?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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 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.
•  » » 3 months ago, # ^ | ← Rev. 2 →   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 12435 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 223You 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.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   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?
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   Yes. Take the test case2 2 10 7 13 6Here 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!
 » 3 months ago, # | ← Rev. 2 →   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.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   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.
•  » » » » 3 months ago, # ^ | ← Rev. 2 → 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
 » 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
•  » » » 3 months ago, # ^ | ← Rev. 3 →   This solution is wrong UPD: Hacked test case54 12435 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)
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   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 :pMy 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.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   please ignore
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   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<
 » 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 ?
•  » » 3 months ago, # ^ | ← Rev. 4 →   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? Spoilervviwv(dp, 210, 520, INF); // int dpint main() { fastIO; cin>>n>>m; FE(i,1,n) cin>>a[i]; FE(i,1,m) cin>>b[i]; FE(j,1,m) { int c = a&b[j]; dp[c] = c; } FE(i,2,n) { FE(j,1,m) { int prev = a[i-1]&b[j]; FE(k,1,m) { int cur = a[i]&b[k]; dp[i][cur] = min(dp[i][cur], (dp[i-1][prev])|(cur)); } } } int ans = INF; FE(j,1,m) { int cur = a[n]&b[j]; ans = min(ans, dp[n][cur]); } cout<
•  » » dp[i][v] is the best result if you reach index i with value v. code#include using namespace std; const int M = 205; int a[M],b[M]; int dp[M]; int n,m; int solve(int index,int value){ if(dp[index][value]!=-1)return dp[index][value]; if(index == n){ // if you're out of a return current value return value; } int mn = 1e9; // for every element in b : choose that element and move to the next index for(int i=0;i>n>>m; for(int i=0;i>a[i]; for(int i=0;i>b[i]; //start from index 0 with value = 0 ( 0|x = x ) cout <
•  » »
 » In Div2C, we can have $O(9nm)$ time with $O(nm)$ additional memory. First, let $s_i$ be a copy of $b$ for each $i$ -- that's the values in $b$ that we can still use for this $i$. Now let's iterate bits $b$ from 8 down to 0: for every $i$ try to choose such an item from $x \in s_i$ that $a_i \land x$ does not have bit $b$ set; if we can do this for every $i$, then we remove from all $s_i$ all values that have bit $b$ set; otherwise, we set bit $b$ in the answer. 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.
•  » » 3 months ago, # ^ | ← Rev. 2 →   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 :)
•  » » » 3 months ago, # ^ | ← Rev. 2 →   can you tell your approach? UPD: I figured it out. But you may write if you want.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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
 » 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 ?
•  » » 3 months ago, # ^ | ← Rev. 2 →   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??
•  » » 3 months ago, # ^ | ← Rev. 2 →   https://miro.medium.com/max/700/1*RoyONSeJY_UsGPGOib9RXw.gifsee 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!!
•  » »
 » 3 months ago, # | ← Rev. 2 →   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.
 » 3 months ago, # | ← Rev. 2 →   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 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
•  » »
 » 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.
•  » » 3 months ago, # ^ | ← Rev. 3 →   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).
•  » » » » 3 months ago, # ^ | ← Rev. 4 →   Consider this case: 8 3 19 30 20 20 20 19 19 25 20 AC output: 93 Your output: 75 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
 » 3 months ago, # | ← Rev. 3 →   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?
•  » » If you know rook move its so easy.. 1.from your 1st position 1st go all of position of that row.. 2 then check all row from up to down..if you in the left then start from left and next you must be in right and start from right.next again left next right.continue the process until all row complete... 
•  » » » but i m not able to implement it:(
 » 3 months ago, # | ← Rev. 2 →   DIV2 C Can someone help me with this ,it is not passing 3rd pretest #include using namespace std; #define int long long map dp; int f; int solvebit(vector& b,int bit,int ans,int n) { if(bit==-1)return ans; if(f[bit]==0)return solvebit(b,bit-1,2*ans,n); vector zeroes; for(int i:b) { if((i>>bit)&1)continue; else zeroes.push_back(i); } if(zeroes.size()>0)return solvebit(zeroes,bit-1,2*ans,n); return solvebit(b,bit-1,(2*ans)+1,n); } signed main() { int n,m; cin>>n>>m; int a[n]; vector b(m); for(int i=0;i>a[i];} for(int i=0;i>b[i];} for(int j=0;j>i)&1)f[i]++; } } int ans=0; cout<
 » 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.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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 Bfor x = 2, g(2) = 1, as we can add N to the end of the string BBIn 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: 5 2 10 11 11 8 8 8 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.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   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
 » 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: We can choose two challenges In 1394E there are several corrections: To be exact, the origin problem isn't asking us to calculate the number of folds, but rather the number of folding marks. but you have different methods to fold it The first method can be represented by But is it really? Firstly to be noticed the definition of fold in statement always leads to But you can also use different folding methods because any results can be transformed If you understand the folding operation intuitively, it'll be quite easy to come up with a naive algorithm that runs in polynomial time. If you have already understood them, skip this section and read the algorithm part two even palindromic substrings Blue lines denote the center position I suggest proof by contradiction is place of reduction to absurdity
 » Can somebody explain div2 C? The editorial is confusing.
•  » » 3 months ago, # ^ | ← Rev. 3 →   The editorial is confusing It isAll 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
 » 3 months ago, # | ← Rev. 3 →   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|)$.
•  » » 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 That is indeed true,because hexagon = intersection of square with "infinite diagonal slice".And in general:if C = intersection of A and Bthen 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.
 » 3 months ago, # | ← Rev. 2 →   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
 » 3 months ago, # | ← Rev. 2 →   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=20big [ 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)).
•  » » » 3 months ago, # ^ | ← Rev. 2 →   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): Let's call elements ai>m as Y and elements ai<=m as X. We need to fill these into the n slots(X takes up 1 slot and Y takes d+1 slots) The largest Y fills the last slot(so that there are no subsequent slots left to waste). lets call slots left to fill as N. (initially N=n-1) while N: if N >= d+1 : to fill d+1 slots, we can either use one largest unused Y or d+1 largest unused Xs (whichever adds more to the final answer). N decreases by d+1. if N
 » 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??
 » 3 months ago, # | ← Rev. 2 →   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: 89685485Accepted: 89846084
•  » » vector used1(m + 1, false);
•  » » » but then how did it got AC in c++17(64) ?
 » About question 1395C - Boboniu and Bit Operations: what is the point of this piece of code? I think I understood the explanation but not the code below. ans=(1<<9)-1; for(int i=8;i>=0;--i)Check(ans^(1<
»

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,b; int d; int check(int ans,int i,int n,int m,int d,int k) { if (i >= n ) return ans;

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

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

if(p< mm)
mm= p;
}

d[i][k] = mm;

} 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&b[j],1,n,m,d,j);

if(p< mm)
mm= p;`

}

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

 » Hi, sshwyRThanks 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 Chats with Du