Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### ReD_AwHiLe's blog

By ReD_AwHiLe, 7 weeks ago, ,

I hope you liked problems!

Sorry for incorrect placement of problems. I had to do swap(E, F).

Solution C++
Solution C++
Solution C++
Solution C++
Solution C++
Solution C++

• +149

 » 7 weeks ago, # |   +10 Auto comment: topic has been updated by ReD_AwHiLe (previous revision, new revision, compare).
 » 7 weeks ago, # |   +14 Finally !! thanks for the editorial.
 » 7 weeks ago, # |   0 Can anyone help why i am getting wrong answer on testcase 7 -76004123
•  » » 7 weeks ago, # ^ | ← Rev. 4 →   +4 Read the checker's comment. It is said in the question to print those indices where heads will turn from R to L.Check this Testcase: 6 6 RLRLRL
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I did few changes(but dont know whats the difference between this and previous code) but still not able to pass testcase 7-76027745
•  » » » » 7 weeks ago, # ^ |   0 I got my error. Thanks a lot !!
•  » » » » » 7 weeks ago, # ^ |   0 Hi, I've the same problem in my code as well, after taking few hints from this discussion, I made some changes, only to get a different error. Could you help me with this?
 » 7 weeks ago, # | ← Rev. 2 →   +76 I guess many people print something like chess-board on the problem A, so do I lolAnyway, the editorial of the problem A is really amazing!
•  » » 7 weeks ago, # ^ |   +15 i did the same like chess...,but figured out the correct answer after the contest(same as editorial)..baaah!!.
•  » » » 7 weeks ago, # ^ |   +20 Your answer is correct too :)
•  » » » » 7 weeks ago, # ^ |   0 may be the case B=W+1,made us think like that,rather than the simple way,where we can simply cancel out.
•  » » » » » 7 weeks ago, # ^ |   0 I am still not getting about B=W+1. What is mean by B=W+1 in problem div2 A. It made me totally confusing!!
•  » » » » » » 7 weeks ago, # ^ |   0 the difference between no of blacks with atleast 1 adjacent white and no of white with at least 1 black as adjacrent is 1.
•  » » » » 7 weeks ago, # ^ |   0 if the chess board is correct, then why it was showing wrong answer.
•  » » » » » 7 weeks ago, # ^ |   0 like chess board, but a little difference.
•  » » » » » » 7 weeks ago, # ^ |   0 What I did is if n*m is even then make a chess board wont statisfy b=w+1 so I put B in last in place of white to satisfy the condition. if odd, then just put BWBW..... till last. I wonder where I am wrong.
•  » » 7 weeks ago, # ^ |   -7 I think the question should be like B>=W+1 not B=W+1.
•  » » » 7 weeks ago, # ^ |   0 This looks like actual question
•  » » » 7 weeks ago, # ^ |   0 no coz B means number of black boxes who have white neighbors not all the blacks
•  » » 6 weeks ago, # ^ |   0 But his Note for 1st test case is also confusing. where Black = 4 and white = 2. But he said B=3,W=2.
•  » » » 5 weeks ago, # ^ |   0 Just because there are 4 black squares in the example doesn't mean that B=4. If you read the question carefully you'll find that B is the number of black squares that border at least one white square, not the total number of black squares, and thus you can see that B=3 as the bottom right black square doesn't border any white squares.
 » 7 weeks ago, # | ← Rev. 2 →   -36 Another way to explain F is GCD will be 1 when all the numbers are prime. So let x be the number of primes till n. Therefore for each i in [2, x] answer will be 1. After that one can observe we should include the smallest composite number every time.Proof: If we include y before x such that y > x. Let pf(k) denotes the maximum prime factor of number k. So since we know that all prime numbers are included in the set, this condition will simply hold pf(y)>=pf(x). So it is optimal to select x before y to minimize imperfection.
•  » » 7 weeks ago, # ^ |   +41 Consider n = 9Of course, we first take all the prime number from 2 to 9 and 1 as well.1 2 3 5 7Hence, for k = 2 to 5, the minimal imperfection is 1 because the gcd is always 1.For k = 6, we pick 4 so minimal imperfection is now 2.For k = 7, we pick 6 so minimal imperfection is now 3.For k = 8, we pick 9 so minimum imperfection is still 3.For k = 9, we pick 8 so minimum imperfection is now 4.In this example, it doesn't hold that we take the smallest composite number every time. Correct me if im wrong.
 » 7 weeks ago, # |   +18 The problems were very good but the tutorial is too damn late bro still you really did a good job thanks!
 » 7 weeks ago, # |   0 Can someone please explain why my solution for problem A is failing. 76024216 Maybe, there's an issue with my declaration of the 2d array, as the output to some of the subcases has 'W' in the top left as well as right corner which is not what I intend to do.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Your array is initially filled with junk values (values that are uninitialised i.e. initialised to whatever junk was present in that memory location previously). So, any particular value may or may not be equal to 1 (or any number as a matter of fact). Make your array declaration global of sufficiently large size (or use a vector and resize it for different input) (or manually assign all values in C-style array to 0 for every input N,M)
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 just declarate array before main and u will get AC.and if u will declarate it before main u not need to initialize array by zero
•  » » » 7 weeks ago, # ^ |   0 And how say Yuki726 "You are using i for iterating tests and rows both."
•  » » » 7 weeks ago, # ^ |   0 That would solve it. But my question is why is my code failing? Isn't declaring the array as int arr[n][m]={0} not the correct way of declaration?
•  » » » » 7 weeks ago, # ^ |   0 That will only make arr[0][0] initialise to 0.... Not all of arr[0...N — 1][0...M — 1] like you expect it to.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 You are using i for iterating tests and rows both.
•  » » » 7 weeks ago, # ^ |   0 Changing variable names didn't help 76026831.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Here, an accepted version of your code...Edit: Like I mention in the comment below (reply to Yuki726), your variable declarations don't cause an issue. Even if they were to, it'd be a compile time error.
•  » » » 7 weeks ago, # ^ |   +6 That wouldn't cause the issue. Even if it does, it should be a compile error. The access to arr[i][j] will use the closest declared 'i' in the scope (similar to how you can shadow a global variable of the same name inside a function).
•  » » 7 weeks ago, # ^ |   +6 ok, my above answer is not correct. initializing array with ={0} is not correct, try initializing with ={} and it passes, 76027021
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 I believe = {0} syntax is only valid for statically allocated arrays. Though I cannot find a reference for this. It doesn't even compile on my GCC.
 » 7 weeks ago, # |   +16 Do anyone know how to prove minimum bound for k in problem.D?
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   +11 Using dynamic programming, you can calculate for each 'R' what the maximum number of moves it will take to get its position in the final array. Formula:dp[cur 'R'] = max(dp[next 'R'] + 1,'L' cnt on [i + 1, ..., n]).It only remains to note that for the strategy in the solution, this estimate is achieved.
•  » » » 7 weeks ago, # ^ |   0 I just spoilered how to calculate this value :(
•  » » » 7 weeks ago, # ^ |   +16 Thanks for the reply. Great contest btw.
•  » » » 7 weeks ago, # ^ |   0 A bit confused about the formula.What about: "LLLRRR" It is obviously that the minimum move is 0.But according to the formula,"dp[next 'R'] + 1" force the value to add at least one for each 'R'. The first 'R' to calculate in dp is the first 'R' which is not on its right position? This makes me confused.
•  » » » » 7 weeks ago, # ^ |   0 Im sorry. Its works only for 'R' after which there are 'L's in the string. We can drop out rightmost 'R's.
•  » » » » » 7 weeks ago, # ^ |   0 OK,got it. Thanks a lot! (*^▽^*)
•  » » » » » 6 weeks ago, # ^ |   0 If LRLRR given then can I take pair like LR and RL consecutive or should I take LR as one pair and next LR will be another pair
•  » » » » » 5 weeks ago, # ^ |   0 Does it mean that for consecutive 'R's, the formula should be: dp[cur 'R'] = max(dp[next 'R'], 'L' cnt on [i+1,...,n])?
 » 7 weeks ago, # |   0 can anyone help me? It says i failed on test2 token 175: 76028180
•  » » 7 weeks ago, # ^ |   0 probem 2*
•  » » 7 weeks ago, # ^ |   0 Your logic is wrong. Sub-testcase-175 of TestCase-2, your code prints "YES" whilst the answer is "NO"
•  » » 7 weeks ago, # ^ |   0 1 2 -1 -1 -1 1 try this case.
•  » » » 7 weeks ago, # ^ |   0 Solved Thanks!
 » 7 weeks ago, # |   0 Is it possile to solve C using segment tree.If yes then please give your code or explain it.
 » 7 weeks ago, # |   +4 Somebody want to explain F? I do not get it at all. What is the question, what is the idea to solve it? There is obviously something with divisors because the imperfection is defined using gcd. And then?
•  » » 7 weeks ago, # ^ |   +10 The problem: Given the set of integers from $1$ to $n$, $\forall$ $i$ $\epsilon$ $[2..n]$, find a set, $M$ of size $i$ such that max value of $\gcd (p,q)$ $\forall$ $p,q$ $\epsilon$ $M$ is minimized. The solution: Firstly, note that $1$ must always be included in the optimal set. Next, note that if there are $P$ primes from $[2..n]$, then max value of $\gcd (p,q)$ $\forall$ $p,q$ $\epsilon$ $M$ is always $1$. Hence, for the first $P$ numbers, answer will always be $1$. Now from the $p+1$ th number onwards, if we include an integer $x$, the optimal set always contains at least $1$ divisor $d$ $(1\le d #define ll long long int #define pb push_back #define mp make_pair #define F first #define S second #define SZ(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define MS(x,a) memset((x), (a), sizeof(x)) #define F0R(i,n) for(auto (i) = 0; (i) < (n); (i)++) #define FOR(i,a,b) for(auto (i) = (a); (i) <= (b); (i)++) #define ROF(i,a,b) for(auto (i) = (a); (i) >= (b); (i)--) using namespace std; const int INF = 1e9+2; const ll LINF = 1e18+2; const int MX = 2e5+5; const ll MOD = 1e9+7; int lf(int n) { int ans = 1; for(int i = 2; i*i <= n; i++) { if(n%i == 0) { ans = max(ans,i); ans = max(ans,n/i); } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector oof(n); oof[0] = 1; FOR(i,1,n-1) { int n2 = lf(i+1); oof[i] = n2; } sort(all(oof)); FOR(i,1,n-1) cout << oof[i] << " "; }  •  » » » 7 weeks ago, # ^ | 0 why we are adding the greatest divisor in set instead we should add the smallest divisor to minimize perfection?  » 7 weeks ago, # | ← Rev. 2 → 0 In Second problem In this test case may be editorial's answer is wrong in 140 2 4 60 2 8 10I have mad b from a. Like, 3rd element of b is made from 2 time add 2nd element of a, etc. I have also checked others code some of them gave answer as Yes, Other gave No .If I am wrong, please reply me. •  » » 7 weeks ago, # ^ | 0 Array a consists only of {-1, 0, 1} •  » » » 7 weeks ago, # ^ | 0 Thanks •  » » 7 weeks ago, # ^ | 0 array a can contain elements -1,0,1 only so your test case is incorrect •  » » » 7 weeks ago, # ^ | 0 Thanks  » 7 weeks ago, # | ← Rev. 2 → 0 Can someone explain why in problem A, for testcase 2 BWB WBW BWB is not an accepted solutionhttps://codeforces.com/contest/1333/submission/75973141 •  » » 7 weeks ago, # ^ | +11 because in your output: BWB BBB there three B where a W is of them(2 in first row,1 in middle of second row).So B=3 here.Again a W has a adjacent B.So w=1.It doesn't maintain B=W+1. •  » » » 7 weeks ago, # ^ | 0 thanks for pointing out my error •  » » » » 7 weeks ago, # ^ | 0 Welcome.  » 7 weeks ago, # | ← Rev. 6 → +16 Here is how I up-solved D. Spoiler, it is long to be newbie friendly.Note: if you are getting TLE in this problem. Use '\n' instead of endl to enabled output buffering because endl will flush the output. You don't want to flush the output everytime you need to output a newline because that means doing IO. The TL is very tight. SpoilerFirst, we consider the simpler case when the steps are not done simultaneously... I realized that we are just sliding any L to the left. For example,RL becomes LRRRL becomes LRRRRRL becomes LRRR and so on.The reason for this is because, when L is preceded by an R, then they effectively swap.When there are two or more L's, then we just slide them one by one.For example,RRLRRRRL becomes LRRRRRRL then becomes LLRRRRRRNote that this is just one strategy. Of course, we can also start with the rightmost L, then slide it to the previous L.For example,RRLRRRRL becomes RRLLRRRR by sliding the last L to the previous L.Hence, there are multiple strategies of doing it in any order. But the number of operations stay the same becomes the n-th L will move to the n-th position by moving a fixed number of times.Now, the number of moves that we incur when we do this strategy is the highest number of moves . So if the required number of moves k is larger, then the it's impossible to do it. However, if the required number of k is lower, then it's possible to reduce the number of moves by doing some of the swaps simultaneously.You can approach this by simulating doing as many simultaneous swaps in each step. Here's how I implemented it:  deque< vector > indices; // indices[x] is the the list of indices that you can swap at time x int min_moves = 0; int max_moves = 0; while (true) { // should be at most O(N^2) min_moves += 1; // add a new set of moves to perform indices.push_back(vector()); for (int i = 1; i < s.size(); i++) { // find all swaps we can make if (s[i] == 'L' && s[i - 1] == 'R') { indices.back().push_back(i); max_moves += 1; } } if (indices.back().size() == 0) { // we cant do any more swaps indices.pop_back(); min_moves--; break; } // perform the swaps for (int i : indices.back()) { swap(s[i], s[i - 1]); } } After performing the simulation, we now that min_moves is the the minimum number of moves required and we know how to do it as well. So if k is less than this. Then, it's impossible (i.e. the answer is -1).By now, min_moves <= k <= max_moves.If k = min_moves or k = max_moves, then the answer is trivial. So let's consider min_moves < k < max_moves.By intuition, we CAN increase the number of moves from the minimum solution by selecting some swaps and not doing them simultaneously. We basically select k - min_moves of these swaps. Here's how I implemented it:  int adjust = k - min_moves; while (adjust--) { // take one swap, then perform it separately in one move cout << "1 " << indices.front().back() << '\n'; indices.front().pop_back(); if (indices.front().size() == 0) { // we cleared a time step, therefore we should increase "adjust" indices.pop_front(); adjust++; } } // print the remaining steps for (auto v : indices) { cout << v.size() << ' '; for (int i : v) { cout << i << ' '; } cout << '\n'; } Some caveats: If you take a time step with L steps done simultaneously, and then you separate each of these steps in separate times. You might thinking you are ading L seconds, but you actually remove one second from the minimal solution. So, in the end, you are actually only adding L — 1 seconds to the minimum solution. •  » » 7 weeks ago, # ^ | 0 Excellent explanation! •  » » 7 weeks ago, # ^ | 0 Dude... This is giving TLE.. •  » » » 7 weeks ago, # ^ | 0 See my submission. I didnt get TLE. And I checked your submission, it has many differences such that you are performing the swaps right away •  » » » » 7 weeks ago, # ^ | 0 does it matter if we perform the swaps right away. even i am getting TLE •  » » » » » 7 weeks ago, # ^ | ← Rev. 3 → 0 I'm not saying performing swaps right away will (necessarily) cause TLE. I'm just saying there's a lot of differences in my solution to risk_17's. And YES, it would matter.Consider RRLLHow many swaps can you simultaneously in the first step?Answer: 1But if you perform swaps right away:RRLL becomes RLRL then becomes RLLR in one loop. So, first, find all L's preceded by an R. Then only AFTER, swap them. •  » » » » » » 7 weeks ago, # ^ | 0 yes i have taken care of what you are saying but still i get tle •  » » » » » » » 7 weeks ago, # ^ | 0 You are right, it seems weird that you are getting TLE. After checking, using \n instead of endl will get you AC. I think the TL is very tight and the output is huge, so input buffering must be enabled.Here is your solution modified to get AC: https://codeforces.com/contest/1333/submission/76085125 •  » » » » » » » » 7 weeks ago, # ^ | 0 thanks •  » » » » » » 7 weeks ago, # ^ | 0 Please check it.. I had incremented i value if any swaps is there.. •  » » » » » » » 7 weeks ago, # ^ | 0 You are right. You can perform the swaps right away if you increment twice during any given swap :) •  » » » » » » » » 7 weeks ago, # ^ | 0 OK...After changing endl to \n its not giving TLE.. maybe because of the large amount of output  » 7 weeks ago, # | 0 The problem A says that B should be equal to W+1 but in the tutorial number of W is always 1 then how it is a good coloring what am i missing??Please help.. •  » » 7 weeks ago, # ^ | +1 There are 2 black cells with a border to the white one, and the one white one.So B=2, W=1 •  » » » 7 weeks ago, # ^ | 0 oh thanks,got it •  » » 7 weeks ago, # ^ | 0 B is not equal to total number of B. B is equal to total number off such B whice has a adjacent W. I hope you understand.  » 7 weeks ago, # | +3 What is the time complexity of this solution for problem C, by tmwilliamlin168? •  » » 7 weeks ago, # ^ | +6 This solution is similar to the solution at editorial. So nlogn •  » » » 7 weeks ago, # ^ | 0 Thank you for replying so quickly •  » » » 7 weeks ago, # ^ | 0 I am so sorry to bother you again, but could you please tell me how the log(n) part came into the time complexity. Is this some well known algorithm? I have seen such two pointer questions earlier too, but could never understand how it works internally. •  » » » » 7 weeks ago, # ^ | +1 from std::map. std::map::operatop[] cost log(n)  » 7 weeks ago, # | 0 Can anyone help me to understand error in my code for (133C) my code •  » » 7 weeks ago, # ^ | 0 Your code give 3 for this case, but it should give 2. 3 1 0 -1  •  » » » 7 weeks ago, # ^ | 0 Thanks, I forgot to keep the 'st' pointer to rigtmost position  » 7 weeks ago, # | 0 Explain C in simple language and example. •  » » 7 weeks ago, # ^ | ← Rev. 2 → +3 In C we were asked to count number of subarrays that were good (i.e their subarrays must not have zero sum)Now few observations before starting : 1. If a subarry is good that means all of 'its' subarrays are also good. 2. If a subarray is not good then all subarrays which will contain this subarray is also not good. example: 1 -1 3 4 now sum(1 -1) = 0 so it is a bad subarray so if you include (1 -1 3) this is also bad for same reason and so is (1 -1 3 4) now main problem is to find subarrays with 0 sum in efficient manner for which we use idea of prefix sum. what we try to do is find sum of all elements coming before it. for example 1 2 3 4 is the array then it's prefix sum is 1 3 6 10. now we can say that there exist a subarray with 0 sum if : 1. prefix itself is 0. 2. prefix in some index is seen before.let's say 1 2 -3 4 -1 it's prefix sum is 1 3 0 4 3 so there are two cases where subarray is 0 one is (1 2 -3) as prefix index was 0 here and second is (-3 4 -1) as prefix 3 in last index was seen before in 3rd index. we can use maps to find subarray with 0 sum to efficiently. Hope that helps. •  » » » 7 weeks ago, # ^ | 0 prefix in some index is seen before. I can't understand this line...can u pls explain this? •  » » » » 7 weeks ago, # ^ | 0 In simple words: If you have a number let's say 5, I am going to add few arbitrary numbers lets call them x,y,z to 5. Now if I told you that total sum is 5 again what would that mean? x+y+z = 0 !! don't believe me? here's the proof :if 5+x+y+z = 5 => x+y+z = (5-5) ---> 0. •  » » » » » 7 weeks ago, # ^ | 0 Got it...Thank u •  » » » 7 weeks ago, # ^ | 0 If we consider array:[1,2,-3,4,-1] and consider its subarray [1,2,-3,4] which is a good. But if we consider again its subarray [1,2,-3] which is not good. So I think your observation is incorrect that is " 1. If a subarray is good that means all of 'its' subarrays are also good". If it is not the case then make me correct. •  » » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 [1,2,-3,4] is not good because it has a subarray [1,2,-3] which is not good :)by a good subarray we here mean that all "its" subarrays are also good. •  » » » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 Oh I missed that fact while reading your comment.  » 7 weeks ago, # | 0 I'm a bit confused right now. So you advise us to use set/map instead of unordered_map/unordered_set so we don't get TLE, because some "adorable community colleagues" added test cases to make it non-viable.Does this recommendation stand only for this particular problem or we will have to use it from now on? Won't we get TLE on other problems for using an ordered data structure when it isn't generally needed? •  » » 7 weeks ago, # ^ | ← Rev. 2 → +5 Unordered set and unordered map use hashing, so if someone creates anti-hashing testcases ordered data structures are faster. In the worst case data structures that use hashing take O(N) complexity to access a element where N is the number of element in the data structure. Ordered data structures like set and map always have a O(logN) complexity. Use ordered data structures to decrease the risk of getting a TLE.Sorry for my bad english. •  » » » 7 weeks ago, # ^ | 0 What actually concerns me is: could it happen to get TLE using ordered map/set but pass with unordered(in case someone doesn't make anti-hash test cases)?? •  » » » » 7 weeks ago, # ^ | 0 No. Just do not use unordered_set/map without modification of hashing.  » 7 weeks ago, # | +1 I solved C using recursion. 75900316 •  » » 7 weeks ago, # ^ | 0 can u explain your code •  » » » 7 weeks ago, # ^ | ← Rev. 3 → 0 Basically we can't include 2 indices the difference of whose prefix sums is 0. Let's say during the first call of the function we find difference of prefix sum of indices 4 and 11 is 0. So we return f(first_index, 10) + f(5, last_index).So that these two indices are not considered together. Here first_index and last_index are the values for that particular call of the function intially the function is called as f(0, n-1) where n is the length of the string.Note that we also have to substract f(5, 10) as it has been counted twice. The value the function returns is n(n+1)/2 where n is the number of included elements.The code is a bit untidy as I submitted it in a hurry during the contest . Hope this helps :)  » 7 weeks ago, # | 0 The answer to the first problem is like a joke :) Still very clever. This was my first contest in Codeforces and I could only submit this problem and got wrong answer and spent most of the time searching for a test case breaking my code but I couldn't and gave up. And now I noticed that I put a space between Bs and Ws. I also noticed that I can see why the test was not accepted. My question is, could I see that during the contest as well? Thanks.  » 7 weeks ago, # | 0 In this tutorial,for problem C,Isn't the loop is amortize?Why not complexity is O(n+n)? Please anyone explain. » 7 weeks ago, # | 0 # include <bits/stdc++.h> using namespace std; long long n; map<long long,long long> ls; int main() { long long i,k,sm=0,mx=0,z=0; scanf("%lld",&n); ls[0]=1; for(i=1;i<=n;i++) { scanf("%lld",&k); sm+=k; mx=max(mx,ls[sm]); z+=i-mx; ls[sm]=i+1; } printf("%lld\n",z);  } This works for problem C but what I don't understand is why do we have mx=max(mx,ls[sm]); Is this not equivalent to if(ls.find(sm)!=ls.end())mx = ls[sm]; •  » » 7 weeks ago, # ^ | 0 Got it. •  » » 7 weeks ago, # ^ | +1 Code in Spoiler, please?  » 7 weeks ago, # | ← Rev. 2 → 0 In problem C what should be the output of 1 2 0? for me it should be output-> 5 (1),(2),(1,2)(1,2,0),(2,0) but editorial solution gives 3 •  » » 7 weeks ago, # ^ | 0 0's should be excluded, so answer is 3 •  » » » 7 weeks ago, # ^ | 0 Ok got it thanks for reply •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 Firstly, how is {1,0} a sub-array of {1, 2, 0}?Also, {2,0} is incorrect because its sub-array {0} is not valid. So, answer is 3.EDIT: (following your edit) {1,2,0} is also not valid, as its sub-array {0} is invalid. •  » » » 7 weeks ago, # ^ | 0 Ok got it thanks for reply •  » » » 7 weeks ago, # ^ | 0 what should be output for {1,0,2} either 2 or 3 or 5 •  » » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 2 -> {1}, {2}  » 7 weeks ago, # | -17 Plz, write editorial in a more descriptive way. Write by assuming we don't know, not just write by assuming you are revising something, although this is for only last question's editorial. •  » » 7 weeks ago, # ^ | 0 The editorials are already well descriptive. You will cope with understanding them gradually. Keep reading until you understand and seek for help if you need. And be patient.  » 7 weeks ago, # | 0 I tried to implement C before check author's code, but my implementation is wrong, and I don't see difference between my and author's code, can u help me find where is my solution going wrong Codeint n; cin >> n; for ( int i = 1; i <= n; i++ ) cin >> a[i]; for ( int i = 1; i <= n; i++ ) pref[i] = pref[i-1] + a[i]; int ans = 0, j = 0; for ( int i = 0; i <= n; i++ ) { setdup; for ( j; j <= n; j++ ) { if ( dup.count(pref[j]) ) { ans += j-1-i; break; } else dup.insert(pref[j]); } } cout << ans << endl;  •  » » 7 weeks ago, # ^ | ← Rev. 2 → +1 set dup is empty at the start of every iteration by i. Also you need to use long long instead of int. •  » » 7 weeks ago, # ^ | +4 I do some fixes. Check it https://codeforces.com/contest/1333/submission/76047566 •  » » » 7 weeks ago, # ^ | 0 I got it. Thanks a lot!  » 7 weeks ago, # | ← Rev. 2 → 0 Can somebody please help? I'm getting wrong answer on test #8 for problem D — 76047171  » 7 weeks ago, # | 0 Can anyone explain me the editorial's logic for question 2?? •  » » 7 weeks ago, # ^ | 0 Important points 1) array a consists of {-1, 0, 1} 2) pair(i,j) while i < j add ai to aj. 3) to make ai become bi, we need value 1 for ai < bi while value -1 for ai > bi However based on point 2, i < j, mean that we can only consider the value appear before the current index i. For example a = {0, -1, 1} b = {0, 1, -1} at index 2, ai = -1, bi = 1, we can only consider the values of array a that appear before index 2, in this case is 0, hence we cannot make ai become bi as we need value 1 since ai < bi •  » » » 7 weeks ago, # ^ | 0 thnkx bro •  » » » » 7 weeks ago, # ^ | 0 No problem, hope it helps  » 7 weeks ago, # | 0 Hello, I got WA on pretest 9 for problem Div2C. Can anyone please tell me what is pretest 9? My submission. Any help will be greatly appreciated.  » 7 weeks ago, # | 0 Can anyone please explain the editorial of C, specially the first solution with O(n^2 logn) solution.Here it is said that if a subarray with [ai.....aj] is good then [ai....aj-1] is also good, i'm not clear how it works.if i take an array of {1, 2, -3, 1, 0} then a subarray {1, 2, -3, 1} is good but {1, 2, -3(aj-1)} is not good, or i misunderstood ? Plz help anyone •  » » 7 weeks ago, # ^ | 0 here is an explanation, hope it will help you.  » 7 weeks ago, # | 0 Problem D is extension of BINARY MOVEMENTS. I will show how. Let us assume person looking to Right as 0 and Left as 1. We want to swap these values so the they apart to each other, means change all 01 to 10 state.So in the end our array will look like 111...0000. This problem can even be solved in O(n) .If i am wrong please point it out as I am a beginner.According to the editorial of the problem. I will copy the editorial here. Explaination of Problem Setter of the other problemIn Abhinav Jain words: Let’s try to figure out where each zero end up after Q steps. We’ll process them from right to left. Suppose the previously Computed zero stopped at position p .Then if the next zero starts from position q and q + Z \leq p — 2 then that zero will stop at position q+Z . Otherwise, if q + Z > p — 2 ,then it may either stop at p — 2 or p — 1 Now, you may be misleaded in a way that you might think there is a simple greedy solution here to predict which of the two positions this zero will end up at. Like for example looking at the moment the previously Computed zero ended up in position p, or maybe something else like that. But the reality is that the path each zero takes may be very complex and bumpy and not following any ordinary pattern, and in fact, the only way to know where the zero will end up is to know the complete path the previously Computed zero took.So let’s store for each zero a polyline in 2 dimensional-space “time-position”. This polyline will only have two types of segments. Either a horizontal one (time passes, but position doesn’t change) or a diagonal one (time passes and each unit of time the position changes by 1). Actually, the movements are not continuous, so a continuous polyline may not be a perfect representation of the movement of zeroes, but it is much easier for imagination.The final observation is that if we take this line for the previously Computed zero and shift it by 1 in time and in position (add 1 to time, subtract 1 from position), we will receive a polyline of maximum position the zero behind this one may take at any moment in time. The reason is that the zero can only take a position behind another zero one unit of time after the zero that’s ahead took it’s position. The exception is the moment t = 0, because in the beginning a zero can stand right behind another zero.So take the polyline for the previous zero, shift it by 1 in time and position. Then cut out the 1-unit part of it where t in [Q,Q+1] , as it’s not needed. Then append 1-unit part where t \in [0,1] , because it is now missing. Now this polyline represents the maximum position the new zero can be at each moment in time. Consider another polyline where this zero just goes ahead without any bumps for all of the Z steps. If this polyline never intersects the polyline you currently have, then substitute it for this new diagonal polyline. Otherwise substitute just the part before the intersection.Now we can look at the end of the polyline each time we process another zero and this will reveal it’s final position.If we store the points of the polyline as a deque, then cuts, appends and substitutions can be done in an amortized O(n) .  » 7 weeks ago, # | 0 can anyone explain problem A? •  » » 7 weeks ago, # ^ | ← Rev. 2 → +1 Take an NxM board, it is allowed to color a cell as black or white. If a black cell has atleast one adjacent white cell, lets increment variable B. Same holds for W.The task asks to color such that, B = W + 1. Now, the immediate way that strikes is to color like a chess board. This has one corner case to handle: when value of NxM is even, then we have B == W. So, we have to color one more white spot as black, preferably the position: 0,0 [Since I've assumed coloring all odd sum cells as black. My soln. for reference: linkThe editorial provides a much simpler implementation, as in, color only the top-left cell as white and the rest as black. Why is this correct? Well, we have W = 1, since there's only one white cell, also, it has 2 neighboring black cells. We also have B = 2 always, this is because only two cells: (0,1) and (1,0) have neighboring white cell (other blacks only have black neighbors). Thus, the constraint: W = B + 1, always holds. I would recommend visualising/drawing out and seeing. Bonus: As the editorial mentions, the problem gets a little tricky if 1 <= N,M! I realised why only after typing out this explanation.  » 7 weeks ago, # | 0 Can someone explain eugene one. I am unable to get it. I was relating this to count arrays with sum zero and using that approach. and then subtracting n(n+1)/2-count.But I am not able to figure out how to include in count those subarrays of the given array whose subarrays are also not good. •  » » 7 weeks ago, # ^ | 0 You can check my solution here  » 7 weeks ago, # | 0 In Problem C, Understood all before"we need to note that R(i) is monotonous over i. Now we can iterate over i from 0 to n and over j from R(i−1) to n uses a set of prefix sums from the previous iteration"Can anyone help me with this part? An example would be really helpful. •  » » 7 weeks ago, # ^ | 0 Let's say for i, j is the rightmost position for making a good subarray. Then when consider i + 1, (i+1,...j) is also good. Hence we can check j from j + 1  » 7 weeks ago, # | +17 The spiral path idea in E is so nice!!  » 7 weeks ago, # | ← Rev. 3 → +5 For given constraits we do not need a sieve in problem F. We can find smallest prime divisor with naive brute force and get AC, 187 ms •  » » 7 weeks ago, # ^ | 0 Do you know the asymptotics of your solution (without sorting)? Its look like n*e operation so O(n), but I'm not sure. •  » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 It is$O(n \sqrt{n})$UPD. Looks like time complexity is$O\left(\dfrac{n \sqrt{n}}{\log{n}}\right)$•  » » » » 7 weeks ago, # ^ | 0 Why? •  » » » » » 7 weeks ago, # ^ | 0 We can run this function for some$n$and calculate$\dfrac{n \sqrt{n}}{\text{#operations}}$. This is experiment.Looks like time complexity is$O\left(\dfrac{n \sqrt{n}}{\log{n}}\right)\$
•  » » » » » » 7 weeks ago, # ^ |   0 Yes, it's looks like O(n sqrt(n) / log(n)), but it's interesting to find accurate complexity. New challenge!
 » 7 weeks ago, # |   0 In problem D.If I print just only one pair in one move to the start of the process to make time equal to k. what will happen then?
•  » » 7 weeks ago, # ^ |   0 If the pairs in one move,it has no effect on the final answer.Because in different move,the move in last time maybe effects the move next.Meanwhile ,if you just print one pair,maybe you will get -1.
 » 7 weeks ago, # | ← Rev. 2 →   0 Can anyone help getting WA on test 76 https://codeforces.com/contest/1333/submission/76074501
 » 7 weeks ago, # | ← Rev. 4 →   +3 Just want to suggest that an O(n) solution of problem C is possible.Python solution: http://codeforces.com/contest/1333/submission/76077853
•  » » 7 weeks ago, # ^ |   0 Yes, I also solved for O(n). Here is my C++ solution: https://codeforces.com/contest/1333/submission/75888071
•  » » » 7 weeks ago, # ^ |   0 can u pls explain it
 » 7 weeks ago, # |   0 I cant find the error of this code. 76082322can anyone please give me any testcase?? problem D.
 » 7 weeks ago, # |   0 please explain me the following lines separately, I cant understandvoid solve() { int n, m; cin >> n >> m; string black_row(m, 'B'); vector result(n, black_row); result[0][0] = 'W'; for (int i = 0; i < n; ++i) { cout << result[i] << '\n'; } }
 » 7 weeks ago, # |   0 for the first problem how it satisfy the condition if there is only white cell the left corner , since B=W+1 and for 3,2 then it will be 5=1+1 and also the adjacent side is not of opposite colour
»
7 weeks ago, # |
0

# include <bits/stdc++.h>

typedef long long ll; using namespace std;

int main() { long long n; cin>>n; long long arr[n]; long long prefix=0; for (long long i=0;i<n;i++){ cin>>arr[i]; } long long ans=0; bool flag=true; for(long long i=0;i<n;i++){ if(arr[i]==0)continue; for(long long j=i;j<n;j++){ prefix+=arr[j]; if(arr[i]==0)break; if(prefix==0){ans+=j-i;flag=false;prefix=0;break;} } if(flag)ans+=n-i; flag=true; } cout<<ans<<endl;

}

 » 7 weeks ago, # |   0 Why my code doesn't have n2logn time complexity. I stopping the second loop wherever i am finding the sum of subarray is zero. please help me ?
 » 7 weeks ago, # |   0 I have some problems with E, according to the author's solution for N = 3 case. rook goes through cells: 1 -> 3 -> 2 -> 5 -> 6 -> 4 -> 8 -> (1 vun) -> 7 -> 9 pays 1; Queen goes through cells: 1 -> 2 -> 3 -> 4 -> 6 -> 5 -> 7 -> 9 -> (1 vun) -> 8 pays 1; The cost is equal...... Is there something wrong with my path？
 » 7 weeks ago, # | ← Rev. 3 →   0 ReD_AwHiLe In your solutions for 1333D - Challenges in school №41 there is a small mistake in computing mini(minimum possible k).It's giving wrong answer for the case-6 2RLLRRR
•  » » 7 weeks ago, # ^ |   0 hey ajay.07, may you help me to know how can we determine min and max numbers of operations
•  » » 7 weeks ago, # ^ |   0 Thank you! Fixed.
 » 7 weeks ago, # |   0 May anyone explain how did she find min and max value in problem D?
 » 7 weeks ago, # |   0 Auto comment: topic has been updated by ReD_AwHiLe (previous revision, new revision, compare).
 » 7 weeks ago, # |   0 Hello, Can someone please explain C question duplicate prefix sum part of the tutorial? I didn't understand why that should be true?Thanks in advance!
•  » » 7 weeks ago, # ^ |   0 just a simple thing you have to maintain prefix array and then if any value repeats that show that the sum of elements including this indices is zero than you can easily calculate how much subarrays contains this subarrays after counting all subarrays which contain subarray with sum=0 subtract it from total number of subarrays that can be found by n*(n+1)/2
•  » » » 7 weeks ago, # ^ |   0 Thanks for the explanation, but can you explain why duplicates in a range (as mentioned in the tutorial) will create problem?
 » 7 weeks ago, # | ← Rev. 4 →   0 can anyone help me please, actually I think my code doesn't have a mistake but it fails on the test case 3 how can I improve this code https://codeforces.com/contest/1333/submission/76197328
•  » » 7 weeks ago, # ^ |   0 this code can be done in O(n). you don't need to actually change the value in first array you can just check is it possible to make it equal to value at same index in second array
 » 7 weeks ago, # |   0 can anyone identify what is wrong with my logic for div2 problem B- https://codeforces.com/contest/1333/submission/76225752
•  » » 7 weeks ago, # ^ |   0 https://codeforces.com/contest/1333/submission/76229807 I have made some modifications to your code. 1) The first change is this if(a[i]==b[i] || (b[i]>0 && m[1]>0) || (b[i]<0 && m[-1]>0)) Because you want to convert a[i] to b[i], So comparing them is more intuitive. The second change is in for loop for(int i=n-1;i>=0;i--). Hope it helps ;)
•  » » » 7 weeks ago, # ^ |   +1 nadeemshaikh In your second point, your for-loop is running from n-1 to 0 and so does mine. I think it's not a problem.My logix is as follow- if b[i]>0 and if we have at least one 1 in [0, i-1], we can converter a[i](-1, 0, 1) to b[i]. if b[i]<0 and if we have at least one -1 in [0, i-1], we can converter a[i](-1, 0, 1) to b[i]. if b[i]=0 we have following options- (i) if a[i]=0, handled by b[i]==a[i]. (ii) if a[i]=1, we need at least one -1 in [0, i-1]. (iii) if a[i]=1, we need at least one -1 in [0, i-1]. My code is handling 1,2, and 3i only. My updated code for handling 3ii and 3iii- https://codeforces.com/contest/1333/submission/76245364Thanks for reply however.
 » 7 weeks ago, # |   0 Good problems for beginners like me.
 » 7 weeks ago, # |   0 in C problem why are we doing ans+=end-begin instead of ans+=end-begin+1
 » 7 weeks ago, # |   0 Can anyone suggest where can we study and practice the questions like E. Thanks in advance : )
 » 7 weeks ago, # |   0 Can anyone tell me what I am doing wrong in C ? 76439537
 » 7 weeks ago, # |   0 Was it rated?
 » 7 weeks ago, # |   0 How to solve eugen and array ?
 » 6 weeks ago, # |   0 Can Some one explain me in question D how to get the upperbound and lowerbound of k initially (why the algo in the code works)?
 » 6 weeks ago, # |   0 Wonderful implementation of problem B- Kind Anton. Never thought like that!!
 » 6 weeks ago, # |   0 To make the code shorter for 1333E, I filled the spiral differently. https://codeforces.com/contest/1333/submission/77185747
 » 6 weeks ago, # | ← Rev. 2 →   0 I believe this is an O(N^2) solution: submissionBut i'm getting TLE on 1333D - Challenges in school №41 on test case number 10. Can anyone help me?
•  » » 6 weeks ago, # ^ |   +1 You have to use "\n" instead of endl.
•  » » » 6 weeks ago, # ^ |   0 Thank you. Now i have got WA on test case number 76. I will try to move forward.
 » 6 weeks ago, # | ← Rev. 2 →   0 My solution 77420751 for problem C uses the idea of two pointers. Broadly we can keep two pointers in the array denoting the start and endpoint of a valid subarray and iterate them to get the number of good subarrays. First, we store prefix sums in an array then we iterate the endpoint from 1 to an index such that the sum hasn't been seen before. The number of segments is end-pt- start-pt+1. Once we encounter an already found sum, we know that sum from startpt+1 to end-pt is 0, and any subarray starting before or equal to startpt+1 and ending after end-pt will contain this subarray. We thus increment our start-pt by 2 and repeat this process till we cover all array. We need to keep care of the fact that start-pt never decreases because this would mean over counting.
•  » » 3 weeks ago, # ^ |   0 hey ... in your submission .... can you pls explain these lines: else { if(ind1ind2) { ma[sum[ind2]]=ind2; ind2++; continue; } ans+=ind2-ind1+1; ma[sum[ind2]]=ind2; } i hope you will answer.... badly in need of that
•  » » » 3 weeks ago, # ^ |   0 Suppose you find a sum at some index j which you have already seen at some index i, this means that sum from i+1 to j (inclusive) is 0. Thus, you need to increase your pointer1 (ind1) (denotes the starting point of subarray in consideration) to i+2, as pointer2 (ind2) is at j and sum from i+1 to j is 0, so we need to go to i+2. The map stores the latest index at which this sum has been obtained. So, if ind1>ind2 by increase, we just assign map[sum[ind2]]=ind2 and continue with our loop. There will be no effect on ans in this case.
 » 5 weeks ago, # |   0 in problem eugene and array, how time complexity comes to be nlogn?
 » 5 weeks ago, # |   0 I am getting TLE in Problem C (testcase 86). Can someone please point out what is wrong in my implementation.. Submission for problem C. Thank you..
•  » » 5 weeks ago, # ^ |   0 Its ok... It got accepted..
 » 5 weeks ago, # |   0 Can someone please tell me why this solution exceeds time limit? 77867414
 » 4 weeks ago, # | ← Rev. 2 →   0 1
 » 4 weeks ago, # | ← Rev. 2 →   0 Can somebody help me out for ques C why this is getting wrong answer on test 8? https://codeforces.com/contest/1333/submission/78603617 is link to my submission. Thanks in advance.
 » 4 weeks ago, # |   0 can anyone explain vector used in code in problem b, specialy good(2,0), as i m new to vectors i have used array in my sol, and it shows time limit exceed at test 72
 » 4 weeks ago, # |   0 I m Getting wrong answer at test 7 of problem D. Link to my submission https://codeforces.com/contest/1333/submission/78657016 Somebody plz tell me my mistake. Thanks in advance.
 » 2 weeks ago, # |   0 In Editorial of Problem DCan anyone just explain this statement ,that we came to the point that we should now flip (U-k+1) pairs Otherwise, we roll back to the previous iteration and use U−k+1 pairs in this move