### Supermagzzz's blog

By Supermagzzz, 6 weeks ago, translation,

1520A - Do Not Be Distracted!

Authors: MikeMirzayanov

Tutorial
Solution

1520B - Ordinary Numbers

Authors: MikeMirzayanov

Tutorial
Solution

1520C - Not Adjacent Matrix

Authors: MikeMirzayanov

Tutorial
Solution

1520D - Same Differences

Authors: MikeMirzayanov

Tutorial
Solution

1520E - Arranging The Sheep

Authors: Supermagzzz, Stepavly

Tutorial
Solution

1520F1 - Guess the K-th Zero (Easy version)

Authors: Supermagzzz, Stepavly

Tutorial
Solution

1520F2 - Guess the K-th Zero (Hard version)

Authors: MikeMirzayanov

Tutorial
Solution

1520G - To Go Or Not To Go?

Authors: Supermagzzz, Stepavly, Aris_244_

Tutorial
Solution

• +125

 » 6 weeks ago, # | ← Rev. 2 →   -26 Finally getting specialist!...Thanks for the round! :)
 » 6 weeks ago, # |   +7 There is some issue with the editorials. Supermagzzz pls check.
 » 6 weeks ago, # |   -44 Editorial is not perfect. please look into it and upload all c++ solutions with proper explanations.
 » 6 weeks ago, # |   0 What happened to the editorial?
 » 6 weeks ago, # | ← Rev. 2 →   -29 Why are people upvoting this blog?? The tutorial is not visible and for c++ code, you can check the submission of any lgm
 » 6 weeks ago, # |   +4 The tutorials aren't visible.
 » 6 weeks ago, # |   +3 You can read this article to read editorials now.Write a new blog on CF (you don't have to post it), add a line [tutorial: ] (e.g. [tutorial: 1336A]), and preview it.
•  » » 6 weeks ago, # ^ |   +14 this is so pog
•  » » » 6 weeks ago, # ^ |   -8 you are so pog
 » 6 weeks ago, # |   +10 My solution to problem G:The main observation is that we don't ever need to use more than 2 teleportations (because going from point $a -> b$ and then from $b -> c$ is strictly worse than going directly from $a -> c$). Therefore, we can calculate for each portal the cost required to use it as the first one, which is $dist(start, portal) * w + a[i][j]$ and in similar way the cost to go from a portal to the end as $dist(portal, end) * w + a[i][j]$ (by using bfs). The solution is either $dist[start][end] * w$ or the smallest cost to access a portal from the start plus the smallest cost to go from a portal to the end.Code : https://codeforces.com/contest/1520/submission/115344755.
•  » » 6 weeks ago, # ^ |   0 Sorry cuz I'm not really familier with C++, I read your code but haven't got it. I have a question is How you ensure the nearest portal from start and the nearest portal from end is not the same one?
•  » » » 6 weeks ago, # ^ |   +1 You don't need to check for that case because going from $(1, 1)$ to $(n, m)$ without using any portal will be strictly cheaper than using the same portal twice.
 » 6 weeks ago, # |   0 Can we solve E with ternary search?
•  » » 6 weeks ago, # ^ |   0 Yeah, we can.
•  » » 6 weeks ago, # ^ |   +1 don't know about ternary but did with binary search after long thinking (ofc i m grey) but i should work more to think like how the solution in editorial is posted here is my submission 115389196
•  » » 6 weeks ago, # ^ |   0 Here is my ternery search soluton
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Yes, it also can be solved using binary search, look at my submission if you are interested: submission
•  » » » 6 weeks ago, # ^ |   0 it's kind of ternary search.
•  » » » » 6 weeks ago, # ^ |   0 parveen1981 I don't know if I should call it ternary search.Ternary search splits the graph into three segments. In my submission the second mid $mid2 = mid1 + 1$ is just to determine where the "binary" search should go. The graph is similar to $y = abs(x)$ and I am searching on the minimum point. if $moves2 > moves1$ then I know I am on the right of the minimum point then I should go to the left and if $moves2 < moves1$ then I know I am on the left of the minimum point then I should go to the right.
•  » » » » » 6 weeks ago, # ^ |   0 You are checking for two points in each iteration. In ternary search also, we check for two points. That's why I said. But your approach is slightly efficient. Thanks. From now on, I will apply same binary search as you did.
•  » » » 6 weeks ago, # ^ |   0 Hey, could you please explain your solution?
•  » » » » 6 weeks ago, # ^ | ← Rev. 3 →   +3 Observation 1: First if we want to make the sheeps in one row then the length of that row has to be the number of sheeps in the given string.Now let's call the number of sheeps in the string to be k.Observation 2: If we want to move the sheeps into a subsegment of length $k$ , then the first sheep that appears in the string has to be in the first position of the subsegment and the second sheep that appears in the position has to be in the second position of the subsegment and so on until we put all the sheeps in the string in the row.Now to calculate the number of moves that we need to put the sheeps in a row for a subsegment consider a subsegment of length $k$ , that starts at position $x$ and let's call the position of the first sheeps in the string to be $s_1 , s_2 , s_3 ... s_k$ then the number of moves is $abs(s_1 - x) + abs(s_2 - (x + 1)) + abs(s_3 - (x + 2)) ... abs(s_k - (x + k - 1))$.Finally, we have to calculate the minimum of that function you can use ternary search or binary search. Here is My SubmissionIt worth mentioning that there is a problem on Atcoder called Linear Approximation which is strongly related to this problem. When I put the equation of the number of moves I remembered this question then I copied my old code for it and edited a few lines and it got accepted. If anything is not clear feel free to tell me I will explain more.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Yes,we can.I did this with ternary search.You can see my sol if interested.Your text to link here...
 » 6 weeks ago, # |   0 $F2$ and $G$ has the same codes.
 » 6 weeks ago, # |   +8 Problem E has issues in solution code.
 » 6 weeks ago, # |   +4 problem D was directly available here
•  » » 4 days ago, # ^ |   0 lol :-D
 » 6 weeks ago, # |   +10 My DP solution for E: we can find all pref[i] values where pref[i] shows how many moves we need to move all sheep to the left from i to i. If a sheep doesn't stay at i position, then pref[i] = pref[i — 1] + was ( was is an amount of sheep to the left from i), else pref[i] = pref[i — 1]. Same operations we can do for suff (we go from n to 1). Then we can simply check for every i: ans = min(ans, pref[i] + suff[i + 1]).
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +5 A similar approach: we can move each '.' either left of all left sheeps or right of all right sheeps. We just need to maintain sheeps till now and total sheeps.
 » 6 weeks ago, # |   0 Can someone hack the F2 solutions which are very nearer to time limit 4000 ms. Even my upsolved solution is very close to 4 sec.
•  » » 6 weeks ago, # ^ |   0 Amazing huangxiaohua !!
 » 6 weeks ago, # |   0 Why does my solution to 1520E - Arranging The Sheep gives WA? I did it like this: SpoilerFor the ith sheep, the number of moves so that all sheep to the right of it and all sheep to the left of it are aligned is:Moves[i] = MovesLeft[i] + MovesRight[i].With MovesLeft and MovesRight being the number of moves to align all the sheep from the left and right respectively. To calculate MovesLeft and MovesRight, one can simply do:MovesRight[0] = 0 (There's no one to the right of the 0th sheep)MovesRight[1] = MovesRight[0] + (Distance from 0 to 1) * 1MovesRight[2] = MovesRight[1] + (Distance from 1 to 2) * 2....MovesRight[i] = MovesRight[i-1] + (Distance from i to i-1) * iSimilarly to the Left Moves.Then at the end simply take the minimum of all Moves[i].Since we do only linear loops, the complexity should be around O(N), fitting the constraints.Thanks if someone had the goodwill to read :)
•  » » 6 weeks ago, # ^ |   0 U dont have to push them all to the left or all to the right to get the answer
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 daviyan You made just one mistake..You initialized the value of ans as n,but in reality ans can be greater than that.So just initialize it with some higher value(say n*n) and it will work..
•  » » » 6 weeks ago, # ^ |   +1 Indeed! It only worked with ans initialized as LLONG_MAX. Kinda sad that the error was only this little detail. Thanks a lot!
•  » » » » 5 weeks ago, # ^ |   0 lol, I used the same approach and did the exact same mistake
•  » » 3 weeks ago, # ^ |   0 why this solution works???
 » 6 weeks ago, # |   +5 In C, I just printed odd numbers first and then the even numbers row-wise, I thought this would be the intended solution.
•  » » 6 weeks ago, # ^ |   +2 For the last few contests, the topic bicoloring has been used in many problems on cf, so this solution comes naturally to people who are regularly solving cf problems.
•  » » 12 days ago, # ^ |   0 Exactly! This solution is easier to understand and implement.
 » 6 weeks ago, # | ← Rev. 2 →   0 Submission 115253830Could someone give a proof (or hint) about the correctness of this simple problem E solution? I solved it during contest based on intuition, but struggle to give a formal reasoning. The solution differs from the one given by the editoral. Any help is appreciated.Idea: discard all leading and trailing empty spaces initialise $ans=0$ for each remaining empty space at position $i$, increment $ans$ by $min(sheeps_l, sheeps_r)$ where $sheeps_l$ is the number of sheeps appears before position $i$, $sheeps_r$ is the number of sheeps appears after position $i$
•  » » 6 weeks ago, # ^ |   0 this is the same as claiming that the middle sheep will not move
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +8 Could you elaborate on how the two approaches relate to each other?UPD: I got it now.
•  » » » » 6 weeks ago, # ^ |   0 Can you tell how they relate to each other?
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +8 As we iterate through the array from left to right. We have $min(s_l,s_r) = s_l$ before the middle sheep. Hence, it is best to move the spaces that appear before the middle sheep to the left. This is equivalent to moving the sheeps that appear before the middle sheep to the right, until they meet with the middle sheep. The middle sheep does not move.Similarly, we have $min(s_l,s_r) = s_r$ after the middle sheep, so we can apply the same insight.Example: SpoilerSay after trimming leading and trailing spaces, we have $**..\underline{*}..*.*$The underlined sheep is the middle sheep. The editoral is wrong about the middle sheep number. It is not always $m=⌈\frac{n}{2}⌉$.Now let's consider spaces before the middle sheep, $**\underline{.}.\underline{*}..*.*$Obviously, 2 steps to the left. Now we have $.**\underline{.}\underline{*}..*.*$Also 2 steps to the left. $..**\underline{*}..*.*$Great, now let's consider spaces after the middle sheep. $..**\underline{*}..*\underline{.}*$Yes, 1 step to the right. $..**\underline{*}.\underline{.}**.$2 steps to the right. $..**\underline{*}\underline{.}**..$2 steps to the right. $..**\underline{*}**...$Finally, all sheeps are happily staying together.
•  » » 6 weeks ago, # ^ |   0 I solved it using the same approach. I don't have any proof too but it makes sense when you look from the empty-spaces' point of view. You want to move the empty spaces out of the sheep so you either move them right or left.
•  » » » 6 weeks ago, # ^ |   +3 Ah yes, for cases with consecutive sheeps on both left and right like $***\underline{.}**$, it is clear to move the space 2 steps to the right.Originally, my suscipion arises for cases such as $***\underline{.}*..*$. Instead of considering the optimal position for sheeps (as in editoral), we can consider the optimal position of empty spaces. For this case, the optimal position for the space is 2 to the right.Thanks, I think I grasped the concept.
•  » » 6 weeks ago, # ^ |   0 you made more sense than the tutorial thanks
•  » » 6 weeks ago, # ^ |   0 can we like find the position of the sheep which will give min frequency diff from both left and right side and then taking that position as i move all the sheeps accordingly that would be more intuitive I guess rather than just saying middle sheep wont move.
 » 6 weeks ago, # |   0 interactive problem in cf == Binary Search
•  » » 6 weeks ago, # ^ |   0 No.Interactive problem in CF >= Binary Search Because F2 = Binary Search + Fenwick Tree (or Segment Tree)
•  » » » 6 weeks ago, # ^ |   +2 F1: direct binary search. F2: binary search but with extra steps (no need fenwick tree)
 » 6 weeks ago, # |   0 Finally i'll get 1600+ rating :)
•  » » 6 weeks ago, # ^ |   0 is it unrated?
 » 6 weeks ago, # |   0 Weird solution for "1520A — Do Not Be Distracted!" in Editorial.Isn't this solution much faster and simpler? const set = new Set(); let flag = true; for (let i=0; i
•  » » 6 weeks ago, # ^ |   0 This idea is simple to write, and maybe I would suggest writing this variant in the contest.But set takes O(NlogN) time complexity, and we can remove the logN component by using a map(or vector counter(26, 0)) to store the previous occurrence. This way the time complexity is reduced to O(26*N) which is more optimized :)
•  » » » 6 weeks ago, # ^ |   0 Yep!
•  » » » » 6 weeks ago, # ^ | ← Rev. 3 →   0 t0t_samij_lv3n0k your solution is actually O(nlogn) too its the same as using the set as you are using the count in map instead u can just check if t[s(i)] snd it will beocme O(n)
 » 6 weeks ago, # |   +1 Let's understand what the maximum number of vertices can be in the tree. We will consider each level separately. If the level number x is less than logt≤14, then we can spend no more than x of vertices (since there are simply no more vertices). If the level number is from 15 to 18, then we can spend no more than t vertices, so each request uses only one vertex per level. By limiting the number of vertices in this way, we get that there are no more than 214−1+4⋅104=56383, which fits into the constraints.Can anyone explain these lines from the last paragraph of Tutorial of F2 more clearly?
•  » » 6 weeks ago, # ^ |   +16 It means that, after building the binary tree, suppose1). You visit all the vertices if their level is less than 14, (such kind of total vertices are (2^14-1) )2). Also, for every query we will descend the binary tree and we will only travel one vertex at each level at most so, for levels 15 to 18, there are 4 such vertices, hence the total vertices visited would be, 4*(# of queries) = 4*10000. total visited nodes: (2^14-1)+40000.
•  » » » 6 weeks ago, # ^ |   +39 There is also another way to solve F2, which I found nicer and easy to prove. We can divide the complete array length n into blocks of size m (for ex. m = 32 ). If for every testcase we can find in which block the answer would lie then we can just binary search on that block and it will cost at max 5 queries (if m = 32).Now, to find the required block. We can find the number of zeroes in each block during the 1st test case. After that, we can just traverse on blocks and see in which block kth zero will lie. And, finally decreases the count of zero from that block before moving to the next testcase.To get no. of zeroes in each block, we will require. n/(block size) no. of queries. This is well within the constraints. Here is the link of my submission:https://codeforces.com/contest/1520/submission/115301904The above code can be optimized using some sort of data structure to find the required block, but given the TL of 4 sec, it will pass.
•  » » » 6 weeks ago, # ^ |   0 Thanks! I get it now.
•  » » » 6 weeks ago, # ^ |   +1 What about 14-th level?
•  » » » » 6 weeks ago, # ^ |   +6 Sorry, I meant 1st case for levels less that equal to 14 instead of just less than 14.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +1 then won't there be 2^15-1 vertices?
•  » » » » » » 6 weeks ago, # ^ |   +6 Levels starting from 1, (2^0+2^1+....2^13)these are the 14 levels.
•  » » » » » » » 6 weeks ago, # ^ |   0 1). You visit all the vertices if their level is less than 14, Actually, why will we visit all the vertex level till 14? logt<=14 -- is said in the tutorial. But still now, I am confused why should I visit all the vertex till this level? Can you plz explain details in this point?
•  » » » » » » » » 5 weeks ago, # ^ |   0 We are just showing the worst possible case, ofcourse it is not necessary to visit all the vertices if the 1st condition holds but in that queries total queries would be less than derived for the worst case.
•  » » » » » » » » 4 weeks ago, # ^ |   0 The thing you have to basically realize is that you can't query the entire tree (you don't have to either) such that it becomes full, as that would require 2^18 — 1 queries which is greater than the limit. Now lets try to find an upper bound on the number of queries you might have to make such that its under the limit and you can answer every single query. Assuming that you query every single node before the 14th level that would require 2^14 — 1 queries, and now there are only 4 levels left for which we don't have the nodes for, so for each query we do 4 more get queries. All in all we do 2^14 — 1 + 4*10^4 = 56383, which is under the limit & you answer every single query correctly. This just a way to show an upper bound for the number of queries using this method, you don't have to program in such a way, it's just to show that this method works for the given constraints.
 » 6 weeks ago, # | ← Rev. 2 →   +24 In editorial of F2 it should be $2^{14}$ instead of $2^14$.To correct it the editorialist should put 14 between {}, thats how the syntax works
 » 6 weeks ago, # | ← Rev. 2 →   0
 » 6 weeks ago, # |   +4 G can be solved with dp?
•  » » 6 weeks ago, # ^ |   +16 if bfs is dp yes
 » 6 weeks ago, # |   0 weak test cases in d
•  » » 6 weeks ago, # ^ |   0 Actually your solution was totally wrong with this line $if(a[i]-i>0)$.
•  » » » 6 weeks ago, # ^ |   0 I know that but it passed every system test case if it had failed during contest i could have found my mistake
•  » » » » 6 weeks ago, # ^ |   0 Yeah.. that's true no one can say that the pretests were good.
•  » » 6 weeks ago, # ^ |   0 so sad, there should be atleast some pretest for (a[i] — i) < 0
•  » » » 6 weeks ago, # ^ |   0 "Will i get over it,No!...But life goes on..."-Dwight Schrute
 » 6 weeks ago, # |   0 Can I use Dijkstra to solve G?
•  » » 6 weeks ago, # ^ |   0 no that gets MLE
•  » » 6 weeks ago, # ^ |   0 I tried this but it's giving WA for some reason.
•  » » 6 weeks ago, # ^ |   0 Yes, 115309192
•  » » » 6 weeks ago, # ^ |   0 Thank you!
•  » » » 6 weeks ago, # ^ |   0 Time limit exceeded on test 134
•  » » » » 6 weeks ago, # ^ |   +1 So sad
•  » » » » » 5 weeks ago, # ^ |   0 dori is just geniosity
•  » » 5 weeks ago, # ^ |   0 I managed to get it but very very tight. https://codeforces.com/contest/1520/submission/116037918
 » 6 weeks ago, # |   +1 There is a LaTeX problem in the tutorial for F2, $2^{14}$ is mistyped as $2^1 4$ and confused me a bit at first.
 » 6 weeks ago, # | ← Rev. 7 →   -21 1520G - To Go Or Not To Go? solution using Dijkstra's is giving WA on test 2; PLEASE HELP Spoiler#include using namespace std; #define int long long #define deb(x) cout << #x << " = "<< x << endl #define pb push_back //===================== using pii = pair>; using pi = pair; const int MAXX = 1e18; void solve() // simple dijktra's Algorithm { int n,m, w; cin >> n >> m >> w; vector> a(n, vector(n)); // stores original matrix for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> a[i][j]; } } vector>> adj(n, vector>(n,std::vector(n))); // adjacency matrix vector> d(n,vector(n,MAXX)); // distance vector vector>> v; //stores all portals vector> neighbours = {{0,1}, {1,0}, {0,-1}, {-1,0}}; d[0][0] = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if(a[i][j] == 0) { for(auto nbr : neighbours) { int x = i + nbr[0]; int y = j + nbr[1]; if (x >= n || y >= m || x < 0 || y < 0 || a[x][y] == -1) { continue; } adj[i][j].pb({w,{x,y}}); } } else if(a[i][j] != -1) { for(auto nbr : neighbours) { int x = i + nbr[0]; int y = j + nbr[1]; if (x >= n || y >= m || x < 0 || y < 0 || a[x][y] == -1) { continue; } adj[i][j].pb({w,{x,y}}); } v.pb({a[i][j], {i,j}}); } } } for (int i = 0; i < v.size(); ++i) { for (int j = 0; j < v.size(); ++j) { if(j != i ) { pair temp1 = v[i].second; int weight1 = v[i].first; pair temp2 = v[j].second; int weight2 = v[j].first; adj[temp1.first][temp1.second].pb({weight2 + weight1, {temp2.first, temp2.second}}); } } } priority_queue, greater> q; q.push({0,{0,0}}); while(!q.empty()) { int v_x = q.top().second.first; int v_y = q.top().second.second; int d_v = q.top().first; q.pop(); if(d_v != d[v_x][v_y]) continue; for(auto ad : adj[v_x][v_y]) { int to_x = ad.second.first; int to_y = ad.second.second; int len = ad.first; if(d[v_x][v_y] + len < d[to_x][to_y]) { d[to_x][to_y] = d[v_x][v_y] + len; q.push({d[to_x][to_y], ad.second}); } } } if(d[m-1][n-1] == MAXX) { cout << -1 << endl; return; } cout << d[m-1][n-1] << endl; } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); return 0; } 
 » 6 weeks ago, # |   0 Is the solution only given in C++ ? If no, when will Java solutions be uploaded ?
•  » » 6 weeks ago, # ^ |   +1 The solution will most likely not given in all languages. However it doesn't matter. The best approach(to learn, And get high rating in long run) is-Step1: try problems yourself(maybe you have done this while the contest is running)Step 2: view tutorial(just explanation, and only upto some lines after which you can solve it)Step 3: if you are unable to understand ask someone, or ask through a blog.Step 4: implement solution yourself.(important)
•  » » » 6 weeks ago, # ^ |   0 Thanks buddy
 » 6 weeks ago, # | ← Rev. 2 →   0 Does the round became unrated or what?
 » 6 weeks ago, # | ← Rev. 3 →   0 Nice
 » 6 weeks ago, # |   0 Can anyone tell why this code is giving TLE on test 125?
•  » » 6 weeks ago, # ^ |   0 It has complexity $O(portals^2)$, which is too slow.
•  » » » 6 weeks ago, # ^ |   0 Would this work?first sort all the portals by minimum distance of getting their from $(1,1) + a[i][j]$(value of portal) put them in list-1 say.then in list-2 sort all the portals by minimum distance of getting their from $(n,m) + a[i][j]$(value of portal)then we can pick the first item from both the list (if they are not same portal otherwise we will take 1st item from 1st list and 2nd item from 2nd list or 1st item from second list and 2nd item from 1st list and select whichever gives the minimum answer)Can you help?
•  » » » » 6 weeks ago, # ^ |   0 You don't actually need to store the distances in a separate array and then sort it later. You can keep track of the current minimum distance and update it accordingly.You also don't have to check whether you picked the same portal twice as the cost from $(1, 1)$ to $(n, m)$ without using any portal will be strictly cheaper.115297135
 » 6 weeks ago, # |   0 For C, my approach was to print consecutive numbers in alternate boxes. I am not sure why this fails, I tried testing my approach by verifying that no 2 adjacent squares have adjacent numbers too.Here's the code: 115288339
•  » » 6 weeks ago, # ^ |   0 Your code fails for n=3. Just check all the trivial cases.
 » 6 weeks ago, # | ← Rev. 2 →   0 Can someone please explain Guess the K'th zero solution hard version using binary search.I understood if i internally initially check the positions of last zero then second last zero and so on upto 1st zero then i can know the all initial positions of all zeros and map the positions e.g. first zero at 2 index and 5th at 9th indexBut after giving the answer for first query how to modify the answer of other queries without using segment tree or BIT.
 » 6 weeks ago, # | ← Rev. 2 →   +1 In problem E: Note that in the optimal solution the sheep with the number $m = \lceil\frac{n}{2}\rceil$ will not make moves. Shouldn't $m = \lceil\frac{k}{2}\rceil$?
•  » » 6 weeks ago, # ^ |   0 Or $m = \lfloor\frac{k}{2}\rfloor$ according to the solution code?
•  » » » 6 weeks ago, # ^ |   0 The explanation counts the sheep starting from $1$ ($x_1, x_2, \dots$), while the code counts the sheep starting from $0$ (the variable cur).
•  » » » » 6 weeks ago, # ^ |   0 I see. I'm wondering whether the author intends that the explanation and the code are not consistent...
 » 6 weeks ago, # |   0 for problem C , i have different approach, (accepted)https://codeforces.com/contest/1520/submission/115286972i am filling cells diagonal wise. first main diagonal then alternate diagnol
 » 6 weeks ago, # |   0 Problem D Video Tutorial link : https://youtu.be/7IRsFvqgWlw
 » 6 weeks ago, # |   0 The option to submit file is not showing. I want to solve those probems which i couldn't do yesterday. When will that option be back? anyone knows it?
•  » » 6 weeks ago, # ^ |   0 you'll be able to submit the code after the system test for this contest is over
•  » » » 6 weeks ago, # ^ |   0 Thanks. It has started showing again.
 » 6 weeks ago, # | ← Rev. 2 →   +18 Wanna share my miserable experience during the contest...During the last 30 min, the queue is too long, I submitted G, but knew the result after the contest ended, so I don't have chance to debug and resubmit!What a pity:<
 » 6 weeks ago, # |   0 In F2 many people have used ordered_set, order_of_key.Can someone tell the functionality of this, or some source maybe. Thanks.
•  » » 6 weeks ago, # ^ |   +10 Ordered_set basically a set but with 2 extra functionality: We can find the kth element in the set and find the number of elements less than k. You can read about how to use it here
 » 6 weeks ago, # | ← Rev. 3 →   +1 My solution for C was, if n != 2, print in appropriate way all odd numbers from 1 to n^2 and afterwards all even numbers.More easy to implement & understand, I think.
 » 6 weeks ago, # |   0 where is my points???
•  » » 6 weeks ago, # ^ |   0 You mean rating change? Please wait for a hour or so (or maybe a few hours), there is always delay between round end and rating change.
•  » » » 6 weeks ago, # ^ |   0 okay thank you!
 » 6 weeks ago, # |   0 Please can anyone can explain problem e?Thanks in advance.
•  » » 6 weeks ago, # ^ |   0 the task was to calculate the minimum steps for which all the * will be adjacent to each other, and at each step either you can move any * forward or backward by one position, so it let's assume the string ..*..***...*..*.... here there are 6 * and we what we want is to make their position consecutive so we have our first * at position 3(one's notation) and last one at 15'th position so can make it like ******............. or .******............ or ..******......... or ...******......... or ....******........ and upto .............****** , we can notice it won't make any sense to start before the first * and * after last * . so we can iterate through all positions from where we can start our * and just calculate the steps for each and store the minimum value.(o(n^2) solution)//optimizing it in the orignal string so, we can just precalculate the steps needed to make all the * from left of any position consecutive and the steps needed to make all * consecutive to right of any index, and we can just iterate through our precalculated values and take min(steps for left + steps for right) for entire precalculated value
 » 6 weeks ago, # |   +2 A relatively easier approach for problem C (Not Adjacent Matrix):At first, we try to fill the array with odd elements starting from 1 till n2, then we fill the remaining cells with even elements starting from 2 till n2. The only exception is when n is 2.For reference, here is the link to my submission.
 » 6 weeks ago, # | ← Rev. 2 →   +2 I think problem C can be easily solved by just simply printing the odd numbers till n*n and then the even numbers. For example, if n=4 1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 16 
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 i think here the only corner case is 3..for 3 i think this is not work..but for all case this will be work..
•  » » » 4 weeks ago, # ^ |   0 If n=3, then it will look like below: 1 3 5 7 9 2 4 6 8 Just simply push all the odd numbers and then the even numbers. After that just print it serially, and just take care of the new line..  int n,i; vector v; cin>>n; for(i=1;i<=n*n;i+=2) v.push_back(i); for(i=2;i<=n*n;i+=2) v.push_back(i); for(i=0;i
 » 6 weeks ago, # |   0 Would anyone mind explaining E tutorial again to me? I've been trying for a while but I still didn't get the formula for the final position of the sheep
•  » » 6 weeks ago, # ^ |   0 first group sheep with contiguous segment like ******...***.**....****** here we have four groups of sheep.now it is optimal to fix a group and full its left groups and right groups towards it and minimize the answer .for clear clear concept see here 115315773
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Easiest solution is greedy. Just move to center (in loop) side sheeps from left or from right (choose lesser group). Example
 » 6 weeks ago, # |   0 Does anyone else thinks editorial for problem F2 has not been explained properly ? Comments have better explanation than that. Could someone explain the editorial of F2 ?
 » 6 weeks ago, # |   0 Nice round ! Thanks for the problems !
 » 6 weeks ago, # | ← Rev. 2 →   +11 Alternate solution for F-hard if anyone is interested:Divide the array into blocks of size $20$. As a preprocess, store the number of zeros in all these blocks. It takes $200000/20==10000$ queries.Now, we can answer each query: find the block where the zero is, and use $\lceil \log 20 \rceil == 5$ per query to binary search this block. In total, we use exactly $60000$ questions in worst case.115436756 code with some comments
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I tried to solve it similar, but size of block = 8. It should take n / 8 + 3 * t = 55000 queries, but I got WA21: 115451217
»
6 weeks ago, # |
0

I can propose a simpler solution for the C (Not Adjacent Matrix) Question

we can just print all the odds or all the even first until they are greater than n^2 . Then after all those are printed we can just print the rest odd or even numbers.

Implementation is as follows:

# include<bits/stdc++.h>

using namespace std; void solve() { int n ; cin>>n;

if(n == 1)
{
cout<<1<<endl;
return;
}
if(n == 2)
{
cout<< -1 <<endl;
return;
}
int odd = 1;
int even = 2 , evenc = 0;

for(int i = 0 ; i < n ;i++)
{
for(int j = 0 ;j<n ;j++)
{
if(evenc<(n*n)/2)
{
cout<<even<<" ";
even+=2;
evenc+=1;
}
else
{
cout<<odd<<" ";
odd+=2;
}
}
cout<<endl;
}

}

int main(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif

ios_base::sync_with_stdio(false);
cin.tie(NULL);
auto start1=high_resolution_clock::now();
//solve();
test(solve);

auto stop1=high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
//cerr<<"Time: "<<duration.count() / 1000.0<<endl;
cout<<endl<<endl<<endl<<"Time: "<<duration.count()/1000.0<<endl;
#endif

}

So if you like the solution then please star this comment.

 » 6 weeks ago, # |   0 Can someone explain why in problem E, not moving the middle sheep and moving other sheep towards it is the optimal solution?
•  » » 6 weeks ago, # ^ |   0 Consider all sheeps have moved. Then there is a position where all sheeps left of it where moved right, and all sheep right of it where moved left. One of both halfs is the bigger one, WLG consider it be left.Then it would be a better solution to move all left sheeps one step less, and all right sheeps one step more.
 » 6 weeks ago, # |   0 Hi, guys! Trying to solve F2 with multiset. I have WA on 9 test. My someone help to find the mistake please? https://codeforces.com/contest/1520/submission/115447429 (Very simple code)
•  » » 6 weeks ago, # ^ |   0 Hello!You binary search should return r instead of l, as you only give ok position to rBut despite that, the interactor's a array changes after you giving you an answer, so there's no need to use multiset.The most serious thing is your solution needs $t \cdot \lceil\log_2 n\rceil$ times to interact, which is much bigger than the limit when $n=200000$
•  » » » 6 weeks ago, # ^ |   0 Thank u so much! It very helps me
 » 6 weeks ago, # |   0 weak pretests in G if you intended to make the dijkstra solution get TLE.
 » 6 weeks ago, # |   0 In problem C, it's enough to randomize the position of each number until a valid matrix is found. There's a small probability of generating an invalid matrix.
 » 6 weeks ago, # |   0 Editorial is awesome and very clear thank you
 » 6 weeks ago, # |   0 There is an block solution for F2.Let $w$ be the block size, it will interact $\frac n w + t\cdot\lceil \log_2 w\rceil$, with $w=8$, it will interact not more than 55000 timesUses BIT for prefix sum between blocks, the time comlecity is $O(n \log n + t \log^2 n)$115414141
 » 6 weeks ago, # |   0 solution using Dijkstra's is Runtime error on test 146 ; PLEASE HELPmy submission : https://codeforces.com/contest/1520/submission/115467140
 » 6 weeks ago, # |   0 Can someone explain me this part of code. Prob : F2 void dec(int pos, int L, int R) { cache[{L, R}]--; if (L != R) { int M = (L + R) / 2; if (pos <= M) dec(pos, L, M); else dec(pos, M + 1, R); } } 
•  » » 4 weeks ago, # ^ |   0 It's been a while, but there is my personal interpretation: *This function recursively updates each interval, this since "cache" stores the number of zeros in such interval [L,R] and each time that there is an answer such queried zero is flipped to one, in this way cache can be re-utilized.
 » 6 weeks ago, # |   0 Problem F-2I can't figure out why it is wrong. It gets wrong at test case 7, can you especially explain that? Because when I try, it seems fine!
•  » » 6 weeks ago, # ^ |   0 Also I realized Jury's Ans != Participant Output but still Verdict is OK.. why is this so?
•  » » » 6 weeks ago, # ^ |   0 It shows the number of queries used and not the answerIf queries will be below 60000 and answers are correct then it will pass it
•  » » » » 6 weeks ago, # ^ |   0 Oh.. I get that part now, thanks! But still can't understand why my solution was wrong..
 » 6 weeks ago, # |   0 In F2, what does "In this task, the interactor is not adaptive. This means that within the same test, the hidden array and the queries do not change." mean? Are we supposed to keep track of the changes in the array ourselves, because the interactor will continue to answer according to old values?
 » 6 weeks ago, # | ← Rev. 2 →   0 My submission for Problem E 115482300Basic approach is:  Count Total Stars  Iterate through string {  if(starsTillNow <= (totalStars / 2)) {  if(c == '*') starsTillNow++;  elsesteps += starsTillNow;  }  else {  if(c == '.') dotsTillNow++;  else steps += dotsTillNow;  }  } 
 » 6 weeks ago, # |   0 In problem G:Here is link to my AC solution.Here is link to my WA on test case 122 solution, it's exactly similar to previous solution, only difference is value of LINF as LONG_MAX.Can anyone explain, why this error is caused????
•  » » 6 weeks ago, # ^ |   0 long max : 2147483647 long min : -2147483648
•  » » » 6 weeks ago, # ^ |   0 Yes, my question is why do I get WA when I use value of LINF as LONG_MAX and AC when I use value of LINF as 1e18.
•  » » » 6 weeks ago, # ^ |   0 Also, that is not correct value of LONG_MAX. The value you have provided is value of INT_MAX.
•  » » » » 6 weeks ago, # ^ |   0
•  » » » » » 6 weeks ago, # ^ |   0 It's compiler issue, you are using an out dated compiler.Check this: https://ideone.com/jFV2pg
•  » » » » » » 6 weeks ago, # ^ |   +1
•  » » » » » » » 6 weeks ago, # ^ |   0 OH MY GOOODDDDWhat the hell is this. :(
 » 6 weeks ago, # |   0 Can someone please clarify, that in (QUESTION E) are we assuming that the count of sheeps will always be odd, then only we can have one middle sheep, or else there will be two. The test cases passed with this assumption but i cannot see anywhere specified that number of '*' is odd. should i have known this just by reading the question or am i missing something.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 ApproachBasically we need to fix the position of middle sheep and then stack all left and right sheep adjacent to the middle sheep. That will be the minimum answer possible.Lets understand with this example. $n = 10$ $s =$ $*.*...*.**$. Here we have total 5 sheeps marked with *. So middle sheep would we the sheep with number $mid = ceil(k/2)$ and lets say its index is $idx$. For above given example $mid = ceil(5/2) = 3$. *.*...$*$.** $idx = 7$ (Highlighted one is the middle sheep that will be fixed)Now we will move our left and right sheeps to stack adjacent with the middle sheep. To move right sheeps towards middle sheep we will need total of $2 steps$. $s =$ *.*... $***..$ now move left sheeps towards middle sheep we can move all sheeps in total of $7 steps$. $s =$ $....*****.$ Hence answer is $9$. My Algorithm Find middle sheep index. $(idx)$ cnt = 0 counter to count the steps Moving left from $idx-1$ to $0{th}$ index. for(curr = idx-1 , prev = curr ; curr >= 0 ; curr--){ if(s[curr] == *) cnt += abs(curr-prev) , swap(s[curr],s[prev]) , prev--; }  Moving right from $idx+1$ to $n-1 th$ index. for(curr = idx+1 , prev = curr ; curr < n ; curr++){ if(s[curr] == *) cnt += abs(curr-prev) , swap(s[curr],s[prev]) , prev++; }  print cnt.
 » 6 weeks ago, # |   0 Please see my solution for E: Arranging The Sheep 115496010  Why is it WA can anybody tell me ? I found the center of mass of all the sheep, on that position will be the center sheep in the final arrangement and accordingly place half sheep to left and half sheep to right. then count number of spaces each sheep is from the center of mass and add them together Is my approach wrong?
 » 6 weeks ago, # |   0 Why the code following cannot accept...Problem B115509456
 » 6 weeks ago, # |   0 I did not get the logic of 4th problem. Can anyone explain?
 » 5 weeks ago, # |   0 Problem F2, Does anyone have any way to show that there are no more than 6*10^4 vertices?
»
5 weeks ago, # |
Rev. 2   0

why this code is giving the wrong answer.

# include<bits/stdc++.h>

using namespace std; bool a[26],res; int main() { int t; cin>>t; while(t--) { int n; string s; cin>>n>>s;

for(int i=0;i<n;i++)
{
a[i]=false;
}
bool res=true;
for( int i=0;i<n;i++)
{
int t=s[i]-'A';
if(!a[t])
{
a[t]=true;

}
else if(s[i]^s[i-1])
{
res=false;

break;
}

}
if(res)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}

}

}

•  » » 5 weeks ago, # ^ |   0 https://codeforces.com/contest/1520/submission/115754029says right there in your submission
•  » » » 5 weeks ago, # ^ |   0 but i created it bool and assigning bool value why is it non valid.
•  » » » 5 weeks ago, # ^ |   0 thanks jt.cheng26_orz I got my mistake. thanks you so much.
 » 5 weeks ago, # |   0 In Problem G, I was facing TLE but adding these line got accepted. ios_base::sync_with_stdio(false); cin.tie(nullptr); All I knew was that these statements optimize I/O performance but I didn't know it would make such a great difference. Can someone please explain (in simple terms if possible) what is happening under the hood? Thanks!
 » 5 weeks ago, # |   0 Can someone explain me the proof of correctness of 1520E?.. I've tried to prove it but I failed.. Help is really appreciated.. In my approach I've used 4*n auxiliary space..it was a DP approach but the solution in the editorial is way easier if we are able to prove that the middle sheep should make zero moves.. Can someone give me the proof for it?
 » 5 weeks ago, # |   0 I have a new way of 1520C. (c++11) #include using namespace std; void solve(int n) { if (n == 2) { cout << -1 << endl; return; } int a = 1, b = ceil(n * n / 2.0) + 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) if ((i + j) % 2) cout << b++ << ' '; else cout << a++ << ' '; cout << endl; } } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif int t; cin >> t; while (t--) { int n; cin >> n; solve(n); } return 0; } 
 » 5 weeks ago, # |   0 Can anyone explain the logic for G. Thanks in advance!!
 » 4 weeks ago, # | ← Rev. 8 →   0 For problem E , will the given code work for the pattern: **.....*** ?the answer will be 15, but the minimum must be 11 ri8?i guess in the for loop if we compare cur with cnt-cnt/2, the solution must be right. please point out if i am going wrong somewhere
 » 4 weeks ago, # |   0 Anybody had different solutions to F2 and G?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 For F2, i think i had a different idea from the one mentioned in the editorial. Basically, the idea is to divide the array in buckets of size $32$. For each bucket, we'll calculate initially the amount of zeros it contains. Then, for each query, we'll find which bucket contains the given $k$ and binary search to find its exact position. The number of queries is $n/32$ for preprocessing and around $50000$ for all the other queries.Code : https://codeforces.com/contest/1520/submission/116861616
•  » » » 4 weeks ago, # ^ |   0 oh yess. I had the same idea, but my bucket size was 16. I implemented it and got WA, though. probably just a logic error.
 » 3 weeks ago, # |   0 The solution to Ordinary Numbers is beautiful.
 » 3 weeks ago, # |   0 I have doubt in Q2. I am getting WA on 2nd test case.Can anyone help me with this, please? #include using namespace std; #define ll long long int main() { ll t; cin>>t; while(t--) { ll n; cin>>n; ll f=0; string s=to_string(n); ll len=s.size(); for(int i=0;i
 » 3 weeks ago, # |   0 For all noobs like me who were having trouble with understanding the tutorial for 1520C,In problem 1520C — Not Adjacent Matrix, the better approach for me was to push all the odd numbers (from 1 to n*n) first in a vector, then push all the even numbers in the same vector. FE,  vector v; v.push_back(1); for (int i = 1; i <= n*n; i+=2) v.push_back(i); for (int i = 2; i <= n*n; i+=2) v.push_back(i); Then print out all the elements in that vector.  for (int i = 1; i <= n*n; i++) { cout << v[i] << " "; if(i%n==0) cout << endl; } (I was having a hard time understanding the tutorial for this problem so I decided to put my own in the comment section.)
 » 9 hours ago, # |   0 B).Time Complexity:-O(N*9),where n is the given number.Maximum value of n is 10^9.See my solution here: 119520328Time Complexity:2*O(K),where k is the no.of digits in n.Also,maximum value of k is 10.