### FastestFinger's blog

By FastestFinger, history, 5 months ago,

1365A - Игра с таблицей

Tutorial
Code

This problem was prepared by Ashishgup

1365B - Проблематичная сортировка

Tutorial
Code

This problem was prepared by Ashishgup

1365C - Соответствия поворотом

Tutorial
Code

This problem was prepared by Ashishgup and ridbit10

1365D - Решить лабиринт

Tutorial
Code

This problem was prepared by Vivek1998299

1365E - Максимальное значение подпоследовательности

Tutorial
Code

This problem was prepared by Ashishgup and ridbit10

1365F - Снова обмены

Tutorial
Code

This problem was prepared by FastestFinger, Ashishgup and Vivek1998299

1365G - Надежный пароль

Tutorial
Code

This problem was prepared by FastestFinger

Tutorial of Road to CM(Round 7)

• +626

 » 5 months ago, # | ← Rev. 4 →   -36 ..
•  » » 5 months ago, # ^ | ← Rev. 2 →   -18 I don't know what is the point of making A is the hardest problem !UPD: after reading the editorial , problem A is easy but I understood it wrong
•  » » » 5 months ago, # ^ |   +87 I think A is simple, I misunderstood the statement, and I thought cells that share sides, and it was cell that share columns or rows (I assumed something that was not in the statement and that is my fault)
•  » » » » 5 months ago, # ^ |   -23 Yeah,me too.And during the contest I felt stupid enough to come up with an approach for D and not A
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +49 Can anyone solve this if we consider this variant of problem?It seems to be quite interesting one.
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   -89 deleted.
•  » » » » » 5 months ago, # ^ | ← Rev. 3 →   +3 I calculated a few Grundy numbers for small cases. Maybe someone can see some pattern in them. Table of Grundy numbers1 1 2 0 3 1 1 0 3 3 2 2 4 0 5 2 2 3 3 0 1 1 3 0 2 1 1 0 4 5 2 7 4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 - - - - - - 2 1 1 0 3 3 2 2 2 3 3 5 2 4 1 3 2 2 - - - - - - - - - - - - - - - - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - - - - - - - - - - - - - - - - 3 1 3 0 3 3 2 0 4 1 3 - - - - - - - - - - - - - - - - - - - - - - - 1 0 3 0 3 0 3 0 5 - - - - - - - - - - - - - - - - - - - - - - - - - 1 1 2 0 2 3 1 0 - - - - - - - - - - - - - - - - - - - - - - - - - - 0 0 2 0 0 0 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - 3 1 2 0 4 5 - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3 0 3 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2 1 3 0 3 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2 0 5 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 4 1 2 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 0 4 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 5 1 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2 0 3 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2 1 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3 0 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 3 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 4 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 5 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 2 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 7 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 4 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 0 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  Code#include #define x first #define y second #define mp make_pair #define ull unsigned long long int #define ii pair #define rep(i,from,to) for (int i=from; i<=to; i++) #define repn(i,n) for (int i=0; i, int> dp; ii d[4] = {{0,-1},{0,1},{1,0},{-1,0}}; void decor(int lvl) { repn(i, lvl) { cout << " - "; } } inline bool gd(ull shape, int digit) { return (shape >> digit) & 1; } inline void sd(ull& shape, int digit, bool to) { if (gd(shape, digit)!=to) { shape ^= 1ULL< shape, int reclvl = 0, bool verbose = false) { if (verbose) { repn(i,shape.x.x) { decor(reclvl); repn(j,shape.x.y) { int ind = i*shape.x.y+j; cout << gd(shape.y, ind); } cout << endl; } } if (dp.count(shape)!=0) { if (verbose) { decor(reclvl); cout << "Answer: " << dp[shape] << endl; } return dp[shape]; } ull mexar = 0; repn(i,shape.x.x) { repn(j,shape.x.y) { int ind = i*shape.x.y+j; if (!gd(shape.y,ind)) { if (verbose) { decor(reclvl); cout << "Possible move: " << i << " " << j << endl; } ull newshape = shape.y; sd(newshape, ind, 1); repn(k,4) { ii p2 = mp(i+d[k].x, j+d[k].y); int ind2 = (p2.x)*shape.x.y+(p2.y); if (p2.x < 0 || p2.y < 0 || p2.x >= shape.x.x || p2.y >= shape.x.y) continue; if (!gd(newshape, ind2)) sd(newshape,ind2,1); } ii comps[64]; ull visited = 0; int cnt = 0; int xored = 0; repn(i,shape.x.x) { repn(j,shape.x.y) { int ind = i*shape.x.y+j; if (!gd(newshape,ind) && !gd(visited,ind)) { cnt++; int currcompsize = 0; comps[currcompsize++] = mp(i,j); sd(visited,ind,1); queue qu; qu.push(mp(i,j)); while(!qu.empty()) { ii curr = qu.front(); qu.pop(); repn(k, 4) { ii curr2 = mp(curr.x+d[k].x, curr.y+d[k].y); int ind2 = (curr2.x)*shape.x.y+(curr2.y); if (curr2.x < 0 || curr2.y < 0 || curr2.x >= shape.x.x || curr2.y >= shape.x.y) continue; if (!gd(newshape,ind2) && !gd(visited,ind2)) { sd(visited,ind2,1); comps[currcompsize++] = curr2; qu.push(curr2); } } } int minx=100; int miny=100; int maxx=0; int maxy=0; repn(k, currcompsize) { ii curr = comps[k]; minx = min(minx, curr.x); miny = min(miny, curr.y); maxx = max(maxx, curr.x); maxy = max(maxy, curr.y); } int xsize = maxx-minx+1; int ysize = maxy-miny+1; ull subshape = (1ULL<<(xsize*ysize))-1; repn(k, currcompsize) { ii curr = comps[k]; ii translcurr = mp(curr.x-minx, curr.y-miny); int translcurrind = translcurr.x*(ysize)+translcurr.y; sd(subshape,translcurrind,0); } if (verbose) { decor(reclvl); cout << "Subshape found: " << endl; } xored ^= get(mp(mp(xsize,ysize), subshape), reclvl+1, verbose); } } } if (verbose) { decor(reclvl); cout << "Resulting number from move: " << xored << endl; } sd(mexar,xored,1); } } } int minmex = 0; repn(i,65) { if (!gd(mexar,i)) { minmex = i; break; } } if (verbose) { decor(reclvl); cout << "Answer: " << minmex << endl; } ull shape2 = 0; repn(xmir,2) { repn(ymir, 2) { repn(swp, 2) { int xsiz = shape.x.x; int ysiz = shape.x.y; if (swp) { int tmp = xsiz; xsiz = ysiz; ysiz = tmp; } repn(i, shape.x.x) { repn(j, shape.x.y) { int xcord = xmir?shape.x.x-1-i:i; int ycord = ymir?shape.x.y-1-j:j; if (swp) { int tmp = xcord; xcord = ycord; ycord = tmp; } sd(shape2, xcord*ysiz+ycord, gd(shape.y,i*shape.x.y+j)); } } dp[mp(mp(xsiz,ysiz), shape2)] = minmex; } } } return minmex; } int main() { /* while(1) { int n; int m; int v; cin >> n >> m >> v; cout << get(mp(mp(n,m), 0ULL),0,v) << endl; }*/ int lim = 42; while (1) { rep(i,1,lim) { rep (j, 1, lim) { if (i*j>lim) { cout << "- "; } else { cout << get(mp(mp(i,j), 0ULL)) << " "; } } cout << endl; } decor(40); cout << endl; ull go; cin >> go; lim+=go; } } 
•  » » » » 5 months ago, # ^ |   +4 I did the same mistake, misread the statement
•  » » » » » 5 months ago, # ^ |   0 me too!!!
•  » » » » 5 months ago, # ^ |   +3 I also assumed the same , and could not solve the problem A due to that .
•  » » » » 5 months ago, # ^ |   +1 me too
•  » » » » 5 months ago, # ^ |   0 I also did the same
•  » » » 5 months ago, # ^ |   0 I just ORed each row and column anc got count of 0's in each Now if mincount of 0's among those two is odd then Ashish wins otherwise Vivek
•  » » » 5 months ago, # ^ |   +6 I too solved B, C and D and wasn't able to solve A :(
•  » » » 5 months ago, # ^ |   0 It wasn't that hard, you just had to determine the number of totally unassigned rows and columns. Take the minimum of them. Ans by checking the number even of odd.
•  » » » » 5 months ago, # ^ |   0 Thanks for easy explanation...
•  » » » » » 5 months ago, # ^ |   0 Welcome
•  » » » » 5 months ago, # ^ |   0 What if both unassigned rows and columns are equal?how to find min of them
•  » » » » » 5 months ago, # ^ |   +1 Then take any of them
•  » » » » » » 5 months ago, # ^ |   0 There is a brute force O(n^3) solution too. Whenever you find zeros, traverse that particular row and column to check if there are no ones. In that case, increase the counter and set that particular a[i][j] to 1. At the end, if the counter is odd Ashish wins, else Vivek wins
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 yeah, I thought that the question was talking about boundary of claimed cells
•  » » » 5 months ago, # ^ |   +1 same here buddy
•  » » 5 months ago, # ^ |   -27
 » 5 months ago, # |   +30 Wow, that was fast.
•  » » 5 months ago, # ^ |   +186 Next Time, editorials before contest!
 » 5 months ago, # | ← Rev. 2 →   +20 Good round! Thanks for fast editorial
 » 5 months ago, # |   +25 Amazing contest! Had fun solving the problems ^_^
 » 5 months ago, # |   +53 FastestFinger fastest editorial <3
•  » » 5 months ago, # ^ |   0 He is FastestEditorial
 » 5 months ago, # | ← Rev. 2 →   +6 It says tutorial is not available. Anyone else having same problem ?UPD : It's working now
•  » » 5 months ago, # ^ |   +2 Yes
•  » » 5 months ago, # ^ |   0 Maybe come later
•  » » 5 months ago, # ^ |   -10 The tutorial isn't out yet I guess. Only the solutions are available at the moment.
 » 5 months ago, # |   0 One of the fastest editorial I'd say :-)
 » 5 months ago, # |   +32 Hardest A ever seen.
•  » » 5 months ago, # ^ |   +8 You should look at round 646 A. So many corner cases!
•  » » » 5 months ago, # ^ |   -7 is it in russian?
•  » » » » 5 months ago, # ^ |   +15 I was so tired and sleepy that I read it as is it rated?
 » 5 months ago, # |   +34 Had 15min left for round so didn't try E and now I see this
•  » » 5 months ago, # ^ |   +2 Ah!! I thought I am the only one who missed E thinking won't be able to solve and code it in 15 min.
•  » » » 5 months ago, # ^ |   0 How is the solution to E is easier than the problem itself?
•  » » 5 months ago, # ^ |   0 You understand me bro !!
•  » » 5 months ago, # ^ |   0 i had 28 mins :( as i have never solved E in contest i just went to sleep
•  » » 5 months ago, # ^ |   0 Can't believe an O(n^3) solution with n = 500 gets AC with Python. Just didn't attempt thinking it'll get a TLE.
•  » » » 5 months ago, # ^ |   0 Yeah, it's nearly on edge, it took 1591ms !
 » 5 months ago, # | ← Rev. 2 →   -16 .
•  » » 5 months ago, # ^ |   +28 i am no better than you. but we all have bad days and also good days. just don't give up!
•  » » 5 months ago, # ^ |   +17 It's fine. I also couldn't solve A,B,C during contest time. Be happy that, in this editorial you can learn something new more than those contest where you could solve more problems.
•  » » » 5 months ago, # ^ |   +8 Exaxtly.we are not supposed to give up.
•  » » » 5 months ago, # ^ |   0 I also can't solve any question in the contest. Some times its looks like I don't know anything. But it ok to take time to learn new concept. Coding needs much practice. Worst part of coding is to find your error in your code.
•  » » 5 months ago, # ^ |   0 Never loose hope. One day you will.
•  » » 5 months ago, # ^ |   +5 And hence as a result, always stay beginners.
 » 5 months ago, # |   +18 I feel so stupid after reading the editorial for problem B
•  » » 5 months ago, # ^ |   -13 This is the best code I've seen for B so far.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Fortunately, I did the exact same thing for B :)
•  » » 5 months ago, # ^ |   +20 I have the same feelings but for E
•  » » 5 months ago, # ^ |   0 Me too bro
•  » » 5 months ago, # ^ |   0 Didn't know that type is attached to the index and not to the value. Was swapping type also with the elements.
 » 5 months ago, # |   +6 those were some really interesting problems tbh rather than pure bash it's observation only (except D but that was fun too)
 » 5 months ago, # |   +2 For C, isn't the time complexity still O(n) if you use a HashMap?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8 Since we only need to consider shifts by 0,...,n-1, I think we should even be able to use an array/vector for the counting (but I used std::map in my solution during the contest).Edit: Yep, works (82880486). But doesn't seem to help much, only makes it run in 514ms instead of 608ms.
•  » » » 5 months ago, # ^ |   +8 Here is my solution using map and array, It made a huge difference in my case.Using Map (514 ms)Using Array (139 ms)P.S :- I submitted both accepted solutions during the contest so my previous solution (using map) got skipped
•  » » » » 5 months ago, # ^ |   0 Well your improvement is a lot larger because you had used maps for inverting the permutations as well (mp1 and mp2), whereas I only used one to count the differences. Also, I just did some tests, and it seems like my array-solution was so much slower than yours just because of the missing "ios_base::sync_with_stdio(false);" — guess that's not so useless after all xD
•  » » 5 months ago, # ^ |   0 yes
•  » » 5 months ago, # ^ |   0 Map works for O(logn) It is optimized binary search tree
•  » » » 5 months ago, # ^ |   0 But HashMap (unordered_map in C++) has O(1) time complexity for adding and removing (with a high constant factor though)
 » 5 months ago, # | ← Rev. 2 →   +1 i tried bubble sort in B when condition satissfies that is when A(i) >A(J) AND B(i)!=B(j) then swap it.And at last checked if its sorted or not? why its giving WA
•  » » 5 months ago, # ^ |   0 Link your submission
•  » » 5 months ago, # ^ |   0 Read the question carefully. It is not bubble sort but you can switch any two numbers if their type is different. I made the same mistake.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 4 3 2 1 1 1 1 0 try bubble sort on this
•  » » » 5 months ago, # ^ |   +3 thank you got it
•  » » » » 5 months ago, # ^ |   +3 no problem :)
•  » » » » » 5 months ago, # ^ |   0 Hey giorgitarkh, Can you please help debug my code? I think you will get the logic when you read the code. 82855417Thanks in advance :)
•  » » » » » » 5 months ago, # ^ | ← Rev. 3 →   0 imagine 5 7 41 0 0 with your logic there will never be a swap, your logic implies that only neighbors can be swapped, but in the problem if two indexes have different b, you can swap them, so your solution won't check the case when you can swap 5 with 4, swapping b would work if you had swapped 5 with 4, then the state would become 4 7 50 0 1 and then you would've swapped 7 with 5, but I think that kind of solution would be n^3 or maybe n^2 if optimized with some algorithm not sure
•  » » » » » » » 5 months ago, # ^ |   +3 oh yeah! got it , thanks a lot
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Try132 1 10 1 0
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 try this test case:133 1 20 1 0ans should be "YES". :)
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 because that doesn’t work. Check this input: 41 3 5 40 1 1 1Your solution will result in No. But it can be sorted
•  » » » 5 months ago, # ^ |   0 can you explain this example , How it can be sorted?
•  » » » » 5 months ago, # ^ |   0 Sure. First swap 4 with 1 Then it will look like this 4 3 5 1 Then 1 with 5 4 3 1 5 Then 4 with 1 1 3 4 5
•  » » 5 months ago, # ^ |   0 Because you can't be sure that in single bubble sort you get the answer. I mean it is possible that when you are applying bubble sort and then checking whether the array is sorted or not and it gives not sorted, then also it is possible that if you apply bubble sort again by the method which you specified, it becomes sorted So exactly dont know how many times you have to apply bubble sort. That,s why you require some other approach for solving this
 » 5 months ago, # |   +5 For wrong answer on E, try this -> 2 12 6 . I got it after the contest :(
•  » » 5 months ago, # ^ |   0 Can you please find out the error in my code : https://codeforces.com/contest/1365/submission/82866772 I tried greedily since picking the max set bit would always be useful. I set k to the cnt of numbers having the max bit set. Now I went through all bit positions and checked if there cnt was more than max(1,k-2). If yes I added (1<
 » 5 months ago, # |   0 I thought we could only switch adjacent numbers in B..
•  » » 5 months ago, # ^ |   0 wasted my 1 try thinking this.then read the statement carefully xD
 » 5 months ago, # |   +6 Damn I feel so stupid after seeing E's solution
 » 5 months ago, # |   0 What is __builtin_popcount?
•  » » 5 months ago, # ^ |   +2 This gives total number of set bit in binary representation of number
•  » » 5 months ago, # ^ |   0 it is an in built function which is used to count setbits
 » 5 months ago, # |   +14 Nice contest! Didn't quite get understand the proof for E while doing the contest, but proof by example and proof by AC is good enough for me :)
•  » » 4 months ago, # ^ |   0 Can you explain the proof you got?
•  » » » 4 months ago, # ^ |   0 Proof by example means I just came up with examples I solved manually. This is not a rigorous way to prove things.Proof by AC means I coded a solution I think might work and tried to see if CodeForces would accept it. This is actually not a real way to test if your code works.
 » 5 months ago, # |   +12 Where are the memes
 » 5 months ago, # | ← Rev. 2 →   0 To me A was harder than B. Don't read stroyI skipped A and solved B quite easily. Again read C, skipped and tried D. Couldn't prove the idea (same as editorial), and again focused on A. I again tried to prove D. When 14-15 min was left I coded D without proving. Finished 20 sec after the contest. Anyways, I don't know why I am commenting...
 » 5 months ago, # |   0 Thanks for nice problems. Though I couldn't solve A,B,C during contest time, I am still happy. Cause Now I know what I should know that I don't know.
 » 5 months ago, # |   +13 D was fun to solve.
•  » » 5 months ago, # ^ |   0 I am getting a RTE in problem D. My logic is the same as that used in the editorial. Can someone please help me in debugging: Link : https://codeforces.com/contest/1365/submission/82791264
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 You must check for every index to be valid i.e, after you do this--> int xx = i + x[k]; int yy = j + y[k]; you must check xx>=1 && xx<=n && yy>=1 && yy<=m Also you have provided the wrong link for the solution ;p
•  » » » » 5 months ago, # ^ |   0 Hey, Thanks for the help, but it did not work Link : https://codeforces.com/contest/1365/submission/83055198 Because anyways i'm using 1 based indexing and the remaining cells are always filled by walls(the ones outside m*n matrix) so this condition xx>=1 && xx<=n && yy>=1 && yy<=m anyways gets checked in the base case of the check(dfs) function!
•  » » » » » 5 months ago, # ^ |   0 Your check function is in infinite loop. Try this case:1 2 3 BBB GG.
•  » » » » » » 5 months ago, # ^ |   0 Thanks!! I figured out the problem.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Hey, I am having some trouble understanding why my solution is not working ! (problem D ) https://codeforces.com/contest/1365/submission/94191073Can someone please point out what I'm doing wrong? Thanks in advance! :DEDIT: My approach is this - Initially, bool yes=1; 1. If no good cell, yes=0; 2. If a bad cell is adjacent to a good cell, yes=0; 3. If a bad cell is adjacent to {n-1,m-1}, yes=0; 4. For each bad cell, block all its neighbors that are blank. 5. Now for each good cell, check if {n-1,m-1} is reachable from that cell If for any good cell, {n-1,m-1} is not reachable, yes=0; 6. if(yes) print("yes") else print("no"); What am I missing here?
 » 5 months ago, # |   +85 No relevant memes this time? We need TheOneYouWant as Co-Author from next time ig.
•  » » 5 months ago, # ^ |   +1 Did you mean TheMemeYouWant?
 » 5 months ago, # |   0 can any one explain problem (E. Maximum Subsequence Value not the solution just the statments.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Here, if we OR the elements, then we'll get all the set bits, but we need to get the bits that are in at least k-2 elements in a subseq of size k(k>3 else 1) so when we go throught the binary repr of the numbers, we find out that not all bits are contributing towards max (cases with dense set bits is exception to this obsv) but when we decrease the size of the array (ie get a subseq), our k-2 decreases and narrowing down to large numbers while also aiming to make it denser(ie in [1,2,4,8,10], 10,1,4 cover all bits), our value increases. So, how long do we need to decrease this subseq size, that goes down to that atleast max(1,k-2) must be set, therefore for k<=3, we have that any set bit contributes and at k=3 our subseq size is max.example: [2,4,8,16,32,64] => [16,32,64] 112 [1,2,4,8,10] => [10,1,4] 15
•  » » » 5 months ago, # ^ |   0 Thank you so much
 » 5 months ago, # |   +3 Can someone tell me why my E fails? Feels like I've done the same thingCode
•  » » 5 months ago, # ^ |   +6 what if biggest number shouldn't be in the solution, for example 11000000 is the biggest, but it would be better to use 10011111, you always use the biggest number in your solution.
•  » » » 5 months ago, # ^ |   +6 Thanks, I feel extremely stupid rn
•  » » » » 5 months ago, # ^ |   +1 no problem.
•  » » 5 months ago, # ^ |   +12 You are doing a greedy solution. It's not always correct to select in this way. For example, consider the following test case (all numbers in binary) 100010 100001 010010 001000 The optimal solution selects rows 2, 3, 4. Yours selects row 1, 3 and 4.
 » 5 months ago, # |   -16 This was completely Mathforces!
•  » » 5 months ago, # ^ |   0 I wish!
•  » » 5 months ago, # ^ |   +141 Felt more like Thinkforces than Mathforces, nice easy implementations after you get the logic, but not that much Math.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +5 Thinking is mathematics. Olympiad combinatorics is mainly "thinkforces". Also, problem F was finding a strong invariant in the process.
 » 5 months ago, # |   +9 Most probably I will be losing my rating in this Contest. But No worries, the questions were too good [Especially the E qn]. I definitely want Ashishgup to host contests more frequently.
 » 5 months ago, # |   0 Great contest with problems that focus on elegant observations. Look forward to more such!
 » 5 months ago, # |   +33 Great contest and hands down the hardest A and B i have seen in a long long time.
 » 5 months ago, # |   0 Has the record for fastest editorial ever been broken?
 » 5 months ago, # |   +6 As a low rated coder I enjoyed it too, thanks!
 » 5 months ago, # | ← Rev. 2 →   0 Can anyone explain why my solution for D failed? First, I checked if any B has G as a neighbor or not. Then, I replaced all empty spots around B as walls. Then I ran a dfs from the right-bottom. https://codeforces.com/contest/1365/submission/82867892 Thanks.
•  » » 5 months ago, # ^ | ← Rev. 4 →   +8 In your dfs code why are you moving left and top only?1 5 5G . . . .G . . . .# # G # .B B # # .B B B # .
 » 5 months ago, # |   +18 I love how you separated the editorial into key idea and solution so people have a second shot at upsolving without looking at the solution
 » 5 months ago, # | ← Rev. 3 →   0 My idea for the solution to D is check if the bad guys can reach the end, if yes, then block all the neighbouring cells. Then check if all good guys can reach the end. Why does this fail on pretest 7?Link to my submission : https://codeforces.com/contest/1365/submission/82872417
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 B and G are next to each other is auto fail, since B can just hop onto whatever path G is on
•  » » » 5 months ago, # ^ |   0 I have included that condition also
•  » » » » 5 months ago, # ^ |   +3 if B and B are next to each other, u can't block off the adj B cellif not that then idk what other edge cases there are
•  » » » » » 5 months ago, # ^ |   0 Yeah, my solution fails for that case. I am blocking off any adjacent cell which is not a wall. Thanks for replying.
•  » » » » » 4 weeks ago, # ^ |   0 Hey, I am having some trouble understanding why my solution is not working ! (problem D ) https://codeforces.com/contest/1365/submission/94191073Can someone please point out what I'm doing wrong? Thanks in advance! :(EDIT: My approach is this - Initially, bool yes=1; 1. If no good cell, yes=0; 2. If a bad cell is adjacent to a good cell, yes=0; 3. If a bad cell is adjacent to {n-1,m-1}, yes=0; 4. For each bad cell, block all its neighbors that are blank. 5. Now for each good cell, check if {n-1,m-1} is reachable from that cell If for any good cell, {n-1,m-1} is not reachable, yes=0; 6. if(yes) print("yes") else print("no"); What am I missing here?
•  » » » » 5 months ago, # ^ |   +3 You have a typo, when you are checking for s[i][j-1]=='G', you are actually checking if i-1>0, and the same typo when checking for '#'
•  » » » » » 5 months ago, # ^ |   0 Thanks for pointing it out. This is the punishment for copy pasting without checking properly
•  » » » » » » 5 months ago, # ^ |   0 Having a row and col array really makes the code a lot less messy and easy to debugCheck out my submission link
•  » » » » » » » 5 months ago, # ^ |   0 Yeah that makes a lot of sense. I'll try to do that from the next time. Thank you!
•  » » » » » » 5 months ago, # ^ |   0 I actually used a similar approach in the contest but I'm getting TLE on test case 16. Here's my code:82884958. Don't know what's wrong in it.
•  » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yeah after correcting the typo, my code also TLE's. So instead of checking if every good guy can reach the end, check if you can reach every good guy from the end. This requires only one traversal whereas the first approach requires one traversal for every good guy.If you want to look at the code: https://codeforces.com/contest/1365/submission/82879263
•  » » » » » » » » 5 months ago, # ^ |   0 Thanks for the help!
•  » » 5 months ago, # ^ |   +4 You have a typing mistake in 1st and 2nd for loops 4th if condition. if(i-1>=0 && s[i][j-1] != '#') is definitely wrong. Other than this it looks ok, Even though you could've optimized your code A LOT. For example, Spoiler You don't "need" to see if bad guys can reach the end, just build walls around them greedily. Building walls don't cost anything. Instead of checking whether all good guys can reach the escape, you may check whether you as an explorer can reach all the good guys starting from the escape position. This will need only 1 traversal instead of doing it everytime.
•  » » » 5 months ago, # ^ |   0 I tried the exact same solution and have put in the exact same conditions, but still, I failed on pretest 4. https://codeforces.com/contest/1365/submission/82867892
•  » » » 5 months ago, # ^ |   0 Yeah, I copy pasted that part without checking properly. And thanks for the tips. I'll keep that in mind from the next time.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 [deleted]
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Why the editorial solution only checks for maze[n][m] == '.' before enqueue? Shouldn't be != '#'?
•  » » » 5 months ago, # ^ |   0 I think it doesn't matter. As long as you have the escape cell empty, you can reach every good guy if it's possible with only one cell in the queue initially.
•  » » » » 5 months ago, # ^ |   0 That's the point. He just adds the scape cell, but only if it is empty. So if there's a good guy on the scape cell, the code doesn't even run the BFS
•  » » » » » 5 months ago, # ^ |   0 It is mentioned in the problem that the escape cell is empty. So unless you build a wall there in which case nobody can escape, the escape cell is empty.
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Thanks, didn't notice!
 » 5 months ago, # | ← Rev. 2 →   +19 The intended solution to problem G is pretty. Unfortunately for me, the solution I found was much uglier, and was a slight modification of the binary search idea.Given two integers $i \neq j$, either there is a bit set in $j$ which is not set in $i$, or $\mathrm{popcnt}(i) > \mathrm{popcnt}(j)$ (where $\mathrm{popcnt}(k)$ is the number of bits set in $k$), in which case there is some bit un-set in $\mathrm{popcnt}(j)$ which is set in $\mathrm{popcnt}(i)$. Applying this directly would require 10 queries that examine values of $i$ with various set bits, and 4 queries that examine values of $i$ with various unset bits in $\mathrm{popcnt}(i)$, which doesn't quite fit within the bounds of the problem. But there are enough 10-bit values of $j$ with $2 \leq \mathrm{popcnt}(j) < 10$ (to enable using only 3 queries based on $\mathrm{popcnt}(j)$) to barely nudge this idea across the finish line by first mapping into that pool of values.EDIT: Now that systests are over, I was able to produce a submission demonstrating this approach. (82885957)
 » 5 months ago, # |   0 After reading the editorials for all problems that I tried solving but could not solve, I am feeling dumb for not thinking the way it is mentioned in the editorial. SMH
 » 5 months ago, # |   +3 Oh my god, I feel so stupid. I got the observation for E, but for some reason I thought n^3 was too slow. I spent almost an hour trying to figure out how you can know which 3 give the largest value. Well, at least I won't make this mistake next time (hopefully).Other than that, I really liked the contest. Fun problems.
•  » » 5 months ago, # ^ |   0 I'm still stuck at the point where I can't reach why a subset of 3 is enough. Can you help with a better explanation?
•  » » » 5 months ago, # ^ |   +3 Let's say we have a subset with more than 3. We can call the numbers in the subset a1, a2, a3, ..., an. The value of the subset is the sum of all the bits present in at least k-2 of the ai. But, if a bit is in k-2 of them, it must be present in at least one of a1, a2, a3. If it wasn't, we'd have at most k-3 ai with that bit. This means: any bit which contributes to the value of a1, a2, ..., an, also contributes to the value of a1, a2, a3. So in fact, the value of a1, a2, a3 is at least as large as the value of the whole subset. Thus you can always reduce the subset to one of size 3.
 » 5 months ago, # |   0 My performance timelapse: Link. Hope you enjoy :)
 » 5 months ago, # |   0 Problem D video editorial: sOlUtiOn
 » 5 months ago, # |   0 We all should appreciate them for this quick editorial
 » 5 months ago, # | ← Rev. 2 →   0 consider for question A, m =5 and n =2 and filled with all 0s. min(m,n) is 2, so as per question Vivek should win. but, actually ashish will win this.first step,ashish,row 1 :1 0 0 0 0,row 2 :0 0 0 0 0second step,vivek,row 1 :1 1 0 0 0,row 2 :0 0 0 0 03rd step ,ashish,row 1 :1 1 1 0 0,row 2 :0 0 0 0 04th step vivek,row 1 :1 1 1 1 0,row 2 :0 0 0 0 05 th step ashish,row 1 :1 1 1 1 0,row 2 :0 0 0 0 1The question said row or column. so, this must be optimum, just a doubt,please clear
•  » » 5 months ago, # ^ |   0 if n = 2 and m = 5, it should look like this 0 0 0 0 0 0 0 0 0 0 Ashish can pick any position '1 0 0 0 0 0 0 0 0 0 ' Now Vivek has the option of picking in the bottom row except the first column. So, '1 0 0 0 0 0 1 0 0 0 ' Now, Ashish has no options. So, Vivek wins.
•  » » 5 months ago, # ^ |   0 Here it's clearly written that no row or column should be picked by anyone if already have 1 in any cell. So your approach is not following the given constraint . Please read it carefully, I think you misinterpret . Anyway I also faced same but got green at last
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 i got my mistake, i misinterpreted the question and wasted 1 hour thinking why i am getting wrong ans.thank you i considered if either row or column is not filled ,u can consider it
 » 5 months ago, # |   0 Can any one explain E ? As i not understand why can not we xor of all element . I think it will automatically fetch all max ? But as here is condition that you need at least k-2 element with bit 1 in binary representation. So any other proof which gives this answer.?
 » 5 months ago, # |   0 Saw E thought it would be much harder and tried D and now I am here crying.
•  » » 5 months ago, # ^ |   0 Really it's looks easy but for that you need one tick which is 3 in mind . Bro don't worry . But if you had solved D then you are awesome. Just Chill.We are on way to learning by making mistakes.
 » 5 months ago, # |   0 I felt like dumb.. even though it's stupid for me to think so but I am glad others found A and B hard..Nice problemset. Anybody else know where can I practice such bit manipulation problems?Ashishgup is the hardest problemsetter for me till date. It's a given now..
 » 5 months ago, # |   +5 I want to know what is the story behind FastestFinger's handle
 » 5 months ago, # |   0 how to solve A if cell having common edge with claimed one are not to be taken ??
 » 5 months ago, # |   +35 Gotta be careful with these maps.
•  » » 5 months ago, # ^ |   0 One map is sufficient.
 » 5 months ago, # |   +48 F is a truly beautiful problem. Love this kind of problems where you don't have to even know some complex data structures or algorithms. Even someone inexperienced with deep insight could solve it and the solution is brilliant. This contest once again reminded me that solutions themselves can sometimes be the simplest (as in E and F).
 » 5 months ago, # | ← Rev. 3 →   +7 Feeling very dumb of me, right now. I got to the intended O(n^3) solution of Problem-E. But, thought, it would give TLE (So dumb of me) and so, tried a greedy approach to solve it, but was't able to pass the pretests! :(Problems were too amazing. You just get the basic approach, and that's it! No heavy implementation. (Except D, but that was fun too).Thanks to the authors.Awaiting more such rounds on CF.
•  » » 5 months ago, # ^ |   0 Feeling sad for E
•  » » 5 months ago, # ^ |   0 Yeah,I'm still wondering how an n^3 solution works for n=500. I thought that 10^6 iterations meant one second of runtime and that this would overshoot it by a lot. Ended up selecting the max everytime and iterating over the other n^2 possible pairs.:(
•  » » » 5 months ago, # ^ |   +7 A good rule of thumb is 4 * 10^8 easy operations (nothing like mods or pows) will take 1 second.
•  » » » 5 months ago, # ^ |   +46 Most CPU can run at 3GHz-4GHz (There's 3e9-4e9 Clock Cycle Time in a second). Different operation will cost different Clock Cycle Time: add, minus, multiply, bitwise operation usually cost 1-3 Clock Cycle Time while divide cost more than 10 Clock Cycle Time. If data is at RAM, read and write will cost about 100 Clock Cycle Time. If data is at CPU cache, read and write will cost only 1-10 Clock Cycle Time. Most CPU have a 4-16Mb L3 cache, so our program which use little consequent memory will run rather quickly, especially DP. And there's many other optimization such like out-of-order execution. For ordered pairs, $C_{500}^3 = 2e7$. Our program use about 500*sizeof(int)=2-4kb memory, this is very small. Our array will be placed at CPU L1/L2 Cache entirely and has a very fast read write speed. Suppose read and write use 3 cycles, bitwise operation use 1 cycle, our program will cost about 2e7*3/4e9 = 0.015s.You can use these rule to evaluate time usage of your code.
•  » » » » 5 months ago, # ^ |   +3 Does the placement of running program in L1/L2/L3 cache or RAM depends entirely on the size of the program or are there any other factors too, as you indicated that the program(2-4kb) is small enough to be placed in L1/L2 cache?
•  » » » » » 5 months ago, # ^ |   +8
 » 5 months ago, # |   0 What should be the difficulty of B?
 » 5 months ago, # | ← Rev. 2 →   0 today i face very unique problem during contest on problem D . I run same code on 3 different ide and i get 3 different output on each ide for first test case. anyone know how it is possible? https://codeforces.com/contest/1365/submission/82870625
•  » » 5 months ago, # ^ |   0 Your use of memset is wrong, the second and third parameter switched. Such things happen much less often if using vector instead of arrays.
•  » » » 5 months ago, # ^ |   0 thanks
 » 5 months ago, # | ← Rev. 2 →   0 can some one tell test case where my solution of problem D fails . I solved for finding the path recursively instead of bfs .submission
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 In your main method, you have a condition j+1 <= m It should've been j+1 < mOk. nvm .You were storing the values from 1 to n instead of 0 to n-1. My bad.
•  » » » 5 months ago, # ^ |   0 I have used 1 based indexing.
•  » » 5 months ago, # ^ |   0 Your code will fail the consecutive Bad guy case. For example, 1 3 3 BB. BG. ... 
 » 5 months ago, # |   +4 https://codeforces.com/problemset/problem/1174/B B was the same problem as above with just a slight change in statement, now i see why practice helps.
 » 5 months ago, # |   0 In B, I considered swapping only adjacent elements with given properties. That was SAD!!!
•  » » 5 months ago, # ^ |   0 I feel you. Spoiled my whole time because of that.
•  » » » 5 months ago, # ^ |   0 sad
 » 5 months ago, # |   0 Can anyone tell me what is wronge with my code Trouble Sort https://codeforces.com/contest/1365/submission/82849016
•  » » 5 months ago, # ^ | ← Rev. 2 →   +2 consider1 3 4 20 1 1 1
•  » » » 5 months ago, # ^ |   0 Thanks for replying Having at least one element of each group is the only condition for above problem?
 » 5 months ago, # |   +22 Tricked me in E. If problem E was placed at C, I would have solved it. Regret missing on such a simple logic.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Yes! I realised that you don't need more than three elements and I noticed that $O(N^3)$ would pass, but somehow I just didn't think of checking all triples...Who knew the correct solution to problem E could be a simple brute force?..
•  » » » 5 months ago, # ^ |   0 Could you help me with my logic, I have posted my doubt below...
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 Haha. Same Happened with me. I was trying to solve E in O(N^2). Finally managed to solve it(after the question). Link to my solution: 82882054
 » 5 months ago, # |   -6 Where are the memes?
 » 5 months ago, # |   +5 Easiest Div2E I have ever seen. For me it was simpler than all other problems in this contest.
 » 5 months ago, # | ← Rev. 2 →   +1 Great editorial !!**I think Every editorial must contain Key Idea.so that we can proceed by ourselves**
 » 5 months ago, # |   +5 this was an unfair contest question F was easier compared to earlier questions
 » 5 months ago, # |   0 Could anybody please explain me why in Div .2 B array can always sorted if 0 type and 1 type is present
•  » » 5 months ago, # ^ |   0 Suppose you want to swap positions i and j where b_i = b_j = 1. Now suppose there is some index k such that b_k = 0. The following sequence of swaps will do the job — (i, k), (i, j), (j, k).
 » 5 months ago, # |   0 I can't think how my E failed , I just grouped and sorted numbers by the last set bit and took the or of three largest numbers in the top 3 bits...should not it be correct
•  » » 5 months ago, # ^ |   0 Try this case.4 34 33 8 14The optimal solution is 59, here (33 | 8 | 14)But, your solution will give 51.
•  » » 5 months ago, # ^ |   0 No. Consider the following case:Array is: [1,2,6,8]According to you, the output should be 8|6|2 = 14.But the answer is: 8|6|1 = 15
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 There are two problems —1) Your code doesn't follow your logic exactly. I think you have made a typo in "sort(all(lb))". It should be "sort(all(lb[i]))".2) Your logic will give wrong answer for the following test case.412 4 2 1According to your logic, you will pick (12, 4, 2) while the optimal choice is (12, 2, 1).
•  » » 5 months ago, # ^ |   0 Consider these 4 numbers11100 1100 100 11Your code will ignore '11' but that's not the optimal solution
 » 5 months ago, # |   +10 Very nice problemset, not as a CP contest, but they are very beautiful indeed.
 » 5 months ago, # |   0 https://codeforces.com/contest/1365/submission/82842665what is the use of function check() and asdasd() in this solution for E.
 » 5 months ago, # |   0 Can someone help me in my code why i am getting runtime error on one particular line https://codeforces.com/contest/1365/submission/82879289
 » 5 months ago, # |   0 fuuuuuuuuuuuuu,.... , this C , damn itttt.
 » 5 months ago, # | ← Rev. 2 →   0 I solved the Problem D using DP. At first I make all the side of bad person("B") to "#"(except if the side has a bad person("B")).After that I will make all the remaining "B" to "#".So I get rid of that "B". Check that if we made the (n,m) cell to "#" then the answer is "No". Otherwise we now backtrack from (n,m) cell to all the possible direction cell we can go.As we can go to same cell many times so we will save that information in an array.If we visit that cell make dp[i][j]= true otherwise false.Beside that If we get a good person("G") through backtracking, we will save that. After backtracking we now check how many good person we get through backtracking.If the number is the same as all the good person then our ans is "Yes" otherwise "No". My code is here:82880358
•  » » 5 months ago, # ^ |   0 thats not dp, thats bfs, i did the same thing as you.
 » 5 months ago, # |   0 If someone can really tell me why is this runtime error on Test Case 28 ! I will be thankfulHERE
 » 5 months ago, # |   +1 If you scored less points for problem d than for c....... Welcome to the club.....
 » 5 months ago, # |   0 Hey guys, I am new at CP. So I am quite confused. The "game" tag for A is it because A is a game theory problem? I solved A using brute force and it passed successfully. But I am in doubt. Is A game theory problem?
•  » » 5 months ago, # ^ |   0 I think it has game tag because the question is who will win or lose.
 » 5 months ago, # |   +22 G is brilliant! Looked impossible at first.Miss the memetorials.
 » 5 months ago, # |   +17 How to solve problem C ,if we have repeated elements in array a and b?
•  » » 2 months ago, # ^ |   0 It isn't supposed to have them be repeated. "Note that a permutation of n elements is a sequence of numbers a1,a2,…,an, in which every number from 1 to n appears exactly once."
 » 5 months ago, # | ← Rev. 2 →   0 In A, Dry running the editorial code should return "Ashish" for this test case, but the answer given is "Vivek". Here mn = min(5-1,10-1) = 4 (which is even, should return "Ashish"), or am I making some mistake? 5 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 
•  » » 5 months ago, # ^ |   0 Hey, if mn is even, then Vivek is the one, who wins the game and not Ashish.
•  » » 5 months ago, # ^ |   0 The answer is "Vivek".
•  » » » 5 months ago, # ^ |   0 sorry, my mistake (sleepy)
 » 5 months ago, # | ← Rev. 3 →   +35 Amazing problems! $G$ is really nice and unique.BTW problem $F$ in OEIS — https://oeis.org/A037223If the given numbers are unique that is, assume $A$ is a $[1..N]$ and $B$ is a permutation of $A$. But it can be easily generalized to something like this: for _ in range(int(input())): q,f=lambda:list(map(int,input().split())),lambda x:sorted(zip(x,x[::-1])) q(),print(['no','yes'][f(q())==f(q())]) 
 » 5 months ago, # |   -7
 » 5 months ago, # |   0 Can someone suggest what changes I can make to my submission D in python (I used pypy compiler), it gives TLE for test 13. I have implemented the same as editorial to my knowledge. https://codeforces.com/contest/1365/submission/82883245
•  » » 5 months ago, # ^ | ← Rev. 2 →   +6 You are applying dfs from every good vertex. worst case it would take >1 second.What you can do is just do a single dfs from n,m and then check if every good vertex is visited and bad isn't like stated in the editorial
 » 5 months ago, # |   0 Why were the constraints for f so low ? Given that we can solve in nlogn ?
•  » » 5 months ago, # ^ |   0 500 Cases
 » 5 months ago, # |   0 Would be awesome if someone can let me know why my same exact idea/concept TLEs when implemented in DFS but somehow passed in BFS :/ https://codeforces.com/contest/1365/submission/82870178 https://codeforces.com/contest/1365/submission/82883583
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 wtf... when I moved the graph/2d array to be a global variable rather then being passed through recursion, it passed :/ Can someone explain why ? :(https://codeforces.com/contest/1365/submission/82884840
•  » » 5 months ago, # ^ | ← Rev. 2 →   +6 Its probably due to the overhead of vector being copied each time your are calling your dfs function. Check the below submission, i changed your code to passing by reference and it got accepted https://codeforces.com/contest/1365/submission/82885046
•  » » » 5 months ago, # ^ |   +6 Always pass constants by reference. Lesson learned. Thank you :)
 » 5 months ago, # | ← Rev. 2 →   +4 Weird constraints. It taught me a lesson though.
 » 5 months ago, # |   0 can anybody tell me why my submission is getting WA 82884730
 » 5 months ago, # |   0 wow! editorial come so early
 » 5 months ago, # | ← Rev. 2 →   0 There is a typing mistake in F code map,int> pairs instead of map pairs 
 » 5 months ago, # |   0 Hey everyone, I am hoping to get some help on why my submission to problem F fails. What am I doing wrong here? Thanks in advance.82883731
•  » » 5 months ago, # ^ |   0 Are you aware of what the count method does?Try this case: 1 5 1 2 2 1 1 1 1 2 1 1 Your code outputs "Yes"
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Apparently not as well as I thought lol Thanks for the comment!
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 Can u please help me why i am getting WA at test 38 for problem F. My logic is same as explained in the tutorial. Link to my submission https://codeforces.com/contest/1365/submission/83329650Thanks in advance for your reply:)
•  » » » » 4 months ago, # ^ |   +1 Try this: 1 11 2 1 1 1 2 2 2 1 1 2 2 2 1 2 2 1 2 1 1 1 2 2 Also, your logic isn't exactly the same, the editorial says "so we only need to check if the multiset of these pairs in $b$ is the same as the multiset of pairs in $a$."
•  » » » » » 4 months ago, # ^ |   0 Thanks for your reply. I got it now, i was using set because of which i was not able to chk the count of same pairs. ;)
 » 5 months ago, # |   0 Can anyone tell why my approach is giving TLE? I first made walls to bock all the B. Then I checked if any B could reach (n, m). If they can reach, ans will be "No". Otherwise, I checked if all the G get to (n, m) or not. Please help. This is my submission.
•  » » 5 months ago, # ^ |   0 if you check separately for each G then it will lead to TLE since worst case lets say there are approximately n*m G's. (can ignore the -1 due to last being '.')Now dfs/bfs from each vertex would take approx n*m*4 steps.so it would lead to net worst case time complexity of t*n*m*n*m*4 which would take >1 second. I had made the same mistake initially. What you can do is just perform dfs/bfs from n,m and then check if each 'G' vertex is visited.
•  » » » 5 months ago, # ^ |   0 Got it thanks!
 » 5 months ago, # |   0 Thanks for nice problems, as well as quick and detailed editorial as well. Couldn't solve much during contest but learned a lot:)
 » 5 months ago, # |   0 There is something wrong with the codes. #include using namespace std; and map, int> pairs; in problem F
 » 5 months ago, # | ← Rev. 2 →   0 In problem C. Now for each shift, we can find the number of matching pairs and take the maximum.Can someone please explain this line and in which step it is happening in editorial code? for(int i = 1; i <= n; i++) { int cur = pos[b[i]] - i; if(cur < 0) cur += n; offset[cur]++; } int ans = 0; for(auto &it:offset) ans = max(ans, it.second); cout << ans; 
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 int ans = 0; for(auto &it:offset) ans = max(ans, it.second); cout << ans; basically 'curr' is obtaining the number of shifts required for element at ith position to match. and then its frequency is being stored. then in the above part of code the maximum frequency is obtained and is the answer.
•  » » » 5 months ago, # ^ |   0 How offset[cur]++ is storing the no. of matching pairs in each shift?
•  » » » 5 months ago, # ^ |   0 thanks
•  » » » 5 months ago, # ^ |   0 how the maximum frequency of shifts is answer?
•  » » » » 5 months ago, # ^ |   0 Because if you shift the array by the amount of positions the result is that much number of positions with same value. Because you want to have the shift with maximum such positions, you choose the one with max freq.
•  » » » » » 5 months ago, # ^ |   0 yeah understood! thanks
•  » » 5 months ago, # ^ |   0 First, you calculate the offset between the positions of $x$ in $a$ and $b$, for all $x$. Let $d$ be the offset that appears more often. Then you shift the sequence $d$ times, and have the maximum number of correct digits. See my code: for (int i = 1; i <= n; ++i) { ++diffs[(digita[i] - digitb[i] + n)%n]; } int maxi = 0; for (int i = 0; i <= n; ++i) maxi = max(maxi, diffs[i]); printf("%d\n", maxi); The offset is (digita[i] — digitb[i] + n)%n, because digita[i] — digitb[i] can be negative.
 » 5 months ago, # |   +27 I'll have to go with antontrygubO_o here. Problem G stands for Problem Genius!
 » 5 months ago, # |   0 Thanks for a fun contest! Well written problem statements — brief, good grammar etc. — to the point and very effective. Thanks for making this about solving the problem, rather than understanding the problem statements.
 » 5 months ago, # |   +8 I liked the way of mentioning the Key Idea in the beginning of the tutorial :)
 » 5 months ago, # | ← Rev. 3 →   0 how can div2E pass n^3 solution? isn't that 10^8 for n=500
•  » » 5 months ago, # ^ |   0 time limit is 2 seconds.(500)^3 = 1.25 * 10^8
•  » » 5 months ago, # ^ |   +2 it can further narrowed down to 500^3/6 bc of permutations
•  » » 5 months ago, # ^ |   +5 $\sum ^{n}_{i=1}\sum ^{n}_{j=i+1}\sum ^{n}_{k=j+1}1=\dfrac 1 6 n^3-\dfrac 1 2 n^2+\dfrac 1 3 n$. Plug in $n=500$ the result is about 2e7.
 » 5 months ago, # |   +33 E is too easy, I think it should just be B or C, or should increase the limit
 » 5 months ago, # |   0 Can someone please explain why this doesn't work? -https://codeforces.com/contest/1365/submission/82893654
 » 5 months ago, # |   0 Why did we choose bfs instead of dfs in D?
•  » » 5 months ago, # ^ |   0 Hey you can choose either of them.
 » 5 months ago, # |   0 My solution for D:Make sure every bad person is surrounded by a grid of walls, something like this ... .#. ... .#. .B. --> #B# or .BG --> .BG ... .#. ... .#. After that, run a DFS from (n,m) and count the number of G's (count_G) and B's (count_B) on your path without crossing any #(wall).  if(count_G == total_G_in_the_matrix && count_B == 0) return YES else return NO  Code/** G R A T I T U D E **/ #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #include using namespace std; #define int long long #define INF 1e18 #define sz(a) (int)((a).size()) #define all(c) c.begin(),c.end() #define present(c,x) (c.find(x) != c.end()) #define endl '\n' #define trace(x) cout << '>' << #x << ':' << (x) << "\n" #define trace2(x,y) cout<< '>' << #x << ':' << (x) << " | " << #y << ':' << (y) << "\n" #define trace3(a,b,c) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n" #define trace4(a,b,c,d) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n" /*-------------------------------------------------------------------------------------------------------------*/ const int MOD = 1e9 + 7; const int N = 1e6 + 10; bool tc = 1; char a[70][70]; bool vis[70][70]; int n,m; int cg , cb; void dfs(int i,int j){ vis[i][j] = 1; if(i > n || j > m || i < 1 || j < 1) return; if(a[i][j] == '#') return; if(a[i][j] == 'G') cg++; else if(a[i][j] == 'B') cb++; if(!vis[i+1][j]) dfs(i+1,j); if(!vis[i-1][j]) dfs(i-1,j); if(!vis[i][j+1]) dfs(i,j+1); if(!vis[i][j-1]) dfs(i,j-1); } void run_case(){ memset(a,0,sizeof a); memset(vis,0,sizeof vis); cg = cb = 0; cin >> n >> m; int g = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> a[i][j]; if(a[i][j] == 'G') g++; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(a[i][j] == 'B'){ if(a[i+1][j] == '.' ) a[i+1][j] = '#'; if(a[i-1][j] == '.' ) a[i-1][j] = '#'; if(a[i][j+1] == '.' ) a[i][j+1] = '#'; if(a[i][j-1] == '.' ) a[i][j-1] = '#'; } } } if(a[n][m] == 'B'){ cout << "NO\n"; return; } dfs(n,m); if(cg == g && cb == 0){ cout << "YES\n"; } else{ cout << "NO\n"; } } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); if(tc) {int t;cin>>t;while(t--) run_case();} else run_case(); return 0; } 
•  » » 5 months ago, # ^ |   0 Thanks bhai
 » 5 months ago, # | ← Rev. 2 →   0 2 2 BG #.can anyone explain how its answer is no please
•  » » 5 months ago, # ^ |   0 You can only block the path of $B$ if you place a wall on the cell $(2,2)$, which would also block the path of $G$. Hence, it is not possible.
•  » » 5 months ago, # ^ |   0 2 2 BG #. in this case, it is not possible to block the bad person to go to the destination cell (2, 2) if the good person can go in the destination cell (2, 2). The bad person will just follow the path of the good person as there is no way to separate them by using some walls. NB. You have to perform the blocking operation before moving any person i.e before the journey starts.
•  » » 5 months ago, # ^ |   0 since you can't put a wall on G's, the B will just be able to go along the path the G would go to.
 » 5 months ago, # |   0 Video Solutions for A to E:https://www.youtube.com/watch?v=1s0bDFWTArY
 » 5 months ago, # | ← Rev. 2 →   0 assign the masks in such a way that no two masks assigned to two indices are submasks of each other. Anyone please explain. Problem G
 » 5 months ago, # |   0 Problem setters need to understand one thing that the questions difficulty must be maintained in increasing order because in last to last contest also, problem A was difficult to solve than as compared to B and C. Who else agrees with the fact?
 » 5 months ago, # |   0 FastestFinger In the code section of problem F "map, int> pairs; " should be "map pairs;" I think.
 » 5 months ago, # | ← Rev. 3 →   0 Problem An=2, m=30 0 00 1 0For this test case, shouldn't the answer be Vivek? Correct me if I have understood it wrong.
•  » » 5 months ago, # ^ |   0 Ashish can claim either cell (1, 1) or (1, 3) (since he goes first); then Vivek won't have any cell to choose (since the cell chosen by Ashish will make any other cell on line 1 unable to be chosen, and the other cells also can't be chosen), thus according to the statement of the problem, Vivek will lose and Ashish will win.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Oh so it is entire row then. I understood it as a row border/column border. So I thought after Ashish make a choice0 0 10 1 0Vivek can choose (1,1). And then Ashish has no choice. So he loses. My bad.Thanks though!
•  » » 5 months ago, # ^ |   0 2 3 0 0 0 0 1 0 initially, there are only 2 possible moves for Ashish, either choose the cell(1, 1) or cell(1, 3). After one of these two moves, the grid will be looked like 1 0 0 0 1 0 or 0 0 1 0 1 0 After this, there is no way to choose a cell following the criteria described in the statement. Hence the result is "Ashish" .
 » 5 months ago, # |   +21 Test cases for F is not strong enough.I believed I hacked some AC submissions using this data set. Obviously the right answer is No, but they all returned Yes.1 3 8 9 8 9 8 9Submissions:
•  » » 5 months ago, # ^ |   +8 Uphacking on that problem caused an unexpected verdict.It seems that the validator(or checker) crashed :(fastestfinger Please try to fix this, thanks.
 » 5 months ago, # |   +6 Is it just me or does anyone else also feel that problem C is the new B and Problem D is the new C in the recent rounds?
 » 5 months ago, # |   0 Can anyone explain why my solution for D failed? I used dfs and marked visited all the G whenever I encounter B then I return back and after the dfs is completely executed, I checked whether there is any G left to be unvisited. I also checked for the condition whether there is any G adjacent to B. Please help!Link to my solution: https://codeforces.com/contest/1365/submission/82868517
 » 5 months ago, # |   0 I am getting memory limit exceeded in test case 4 of problem D. The link to my solution is https://codeforces.com/contest/1365/submission/82901871. Can anyone help me in knowing where I am going wrong.
 » 5 months ago, # |   0 can anyone help me figure out what i am doing wrong in div2-D? 82900500
 » 5 months ago, # |   0 Can anyone please explain this for DIV2B question, By swapping any two elements at indices i and j, their b[i] and b[j] are also swapped? Or only element values are swapped at indices i and j not b[i] and b[j].
•  » » 5 months ago, # ^ |   0 Yes both the value as well as b[i] and b[j] will get swapped Consider each value-key pair as one unbreakable unit.
 » 5 months ago, # |   +7 For problem E , Why maximum element isn't always considered in finding or?
•  » » 5 months ago, # ^ |   +3 Consider a[] sorted max element first, descending. Let $b(x)$ be the set of bits in x. If $b(a_1)=b(a_2 + a_3)$ then it is always better to not choose $a_1$, because all bits of it a covered by the other two elements. And we can add $a_4$ instead of $a_1$ to getter a better result.
 » 5 months ago, # |   0 i was wondering if it was possible to use a comparator function in B. If someone has done it, please share the solution.
 » 5 months ago, # | ← Rev. 2 →   0 Can we solve $E$ using $DP$? I tried solving using $DP$ in the contest time but got $wa$ on pretest $6$. My $DP$ idea was pretty simple. codetypedef long long ll; typedef long double ld; typedef pair pii; typedef pair pll; //mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll ara[505]; ll dp[505][505]; int n; ll f(int now,int nisi,vector&vec) { if(now>n) { ll ans=0; for(int i=0;i<61;i++) { if(vec[i]>=max(1,nisi-2)) ans+=(1LL<temp(vec.begin(),vec.end()); for(int i=0;i<61;i++) if(ara[now]&(1LL<>n; for(int i=1;i<=n;i++) cin>>ara[i]; memset(dp,-1,sizeof dp); vectorvec(61,0); cout<
•  » » 5 months ago, # ^ |   0 Consider input 4 6 4 2 1 The bits of second and third element of the array equals the first one. If you start adding from left to right, you would need to find that 6 is covered by 4 and 2, so you can remove it to add 1 instead.
 » 5 months ago, # |   0 In solution of E:"Let i be any number such that the i-th bit is set in at least k−2 elements of s"What does it mean by "let i be any number" ? the ith element from the sequence ?
•  » » 4 months ago, # ^ |   0 nope referring to the bit
 » 5 months ago, # |   0 could someone help me debug my solution for D
 » 5 months ago, # |   0 Can someone please find out the error in my code : https://codeforces.com/contest/1365/submission/82866772 I tried greedily since picking the max set bit would always be useful. I set k to the cnt of numbers having the max bit set. Now I went through all bit positions and checked if there cnt was more than max(1,k-2). If yes I added (1<
•  » » 5 months ago, # ^ |   0 same here
•  » » 4 months ago, # ^ |   0 Your idea is wrong, try with this case: 7 8 8 4 4 2 2 1 Ans should be 14.The reason is that if you pick the two 8s, your code would check if it could pick one 4, then if it could pick one 2... but if you pick 4 numbers then the 4 and the 2 won't be taken into account, as there isn't at least 2 of each type.
 » 5 months ago, # |   0 what was the point of making so small constraints for F when expected solution was O(n*logn)?
•  » » 5 months ago, # ^ |   0 To trick someone that solution is not that easy as it is. Check the ashishgup’s last contest’s C question. No point there also of giving such low constraints even the solution just have linear time complexity.
•  » » 5 months ago, # ^ |   0 In this case, notice that the sum of $n$ over all test cases is unbounded, i.e. there can be test files where $t=500$ and $n=500$, for each $t$. Hence, you'll have to account for number of test cases while computing time complexity (in this case, the intended solution has complexity $O(t*n*logn)$ for each test 'file', which is reasonable for 2 seconds).I think it was set this way to increase the number of possible test cases on which the solution runs (expected answer was simply a "Yes/No", so you'll require more test cases to verify solution's corr