By awoo, history, 2 months ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

• +272

 » 2 months ago, # |   0 Best of Luck Everyone.
•  » » 2 months ago, # ^ |   +2 where ever i go,i see your comments
•  » » 2 months ago, # ^ |   +70 .
•  » » 2 months ago, # ^ |   -15 ScreenCast for A-D.
 » 2 months ago, # |   0 Thank you awoo for this educational Round. Can't wait to begin ! Good luck to all contestants!!!
 » 2 months ago, # |   0 Good luck broooo❤️
•  » » 2 months ago, # ^ |   0 good luck brooo!! without take part this contest!!
 » 2 months ago, # |   0 Ladies and Gentlemen I hope you all will get positive delta.
 » 2 months ago, # |   0 Good luck!
 » 2 months ago, # |   0 orz
 » 2 months ago, # |   0 After such a difficult contest yesterday, I hope to get a positive delta today :)Wishing good luck to everyone!
 » 2 months ago, # | ← Rev. 2 →   -11 I am looking forward to the problems of this contest, hoping to surprise me.
 » 2 months ago, # | ← Rev. 2 →   +14 After difficult contest yesterday, I hope to change color of nickname
 » 2 months ago, # |   -7 I am sb.
 » 2 months ago, # |   -7 DON_F do you want to participate?
 » 2 months ago, # | ← Rev. 2 →   0 THANKS awoo!
 » 2 months ago, # |   +40
•  » » 2 months ago, # ^ |   +16 you have gained more contribution than me by using my meme.
•  » » 2 months ago, # ^ |   0 Too relatable
 » 2 months ago, # |   +8 sometimes less expectations give fruitful results.
•  » » 2 months ago, # ^ |   +29 This itself is an expectation
•  » » » 2 months ago, # ^ |   0 lol
•  » » » 2 months ago, # ^ |   +4 surely
 » 2 months ago, # |   +25 Currently the standings seem to be showing both Div.1 and Div.2 participants regardless of whether the "show unofficial" checkbox is checked. This isn't too much an inconvenience, but still it makes us hard to see the actual standing based on the division. Can this be fixed ASAP?
 » 2 months ago, # |   0 read-the-problem-statement-carefully forces
 » 2 months ago, # |   +3 Why using Sieve for D to generate list of primes of each number up to 10^7 TLE?
•  » » 2 months ago, # ^ |   0 Send code? I got it through even with Rust: fn sieve(n: usize, lpf: &mut Vec, primes: &mut Vec) { lpf.resize(n + 1, 0); for x in 2..=n { if lpf[x] == 0 { lpf[x] = x; primes.push(x); } for i in 0..primes.len() { let p = primes[i]; if x * p > n { break; } lpf[x * p] = p; if x % p == 0 { break; } } } } let lpf = &mut Vec::new(); let primes = &mut Vec::new(); sieve(10_000_000, lpf, primes); Should be easy to translate to C++
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 184970170 here's mine using sieve get TLE, also probably because i use "not good" sieve
•  » » » » 2 months ago, # ^ |   +3 I think your problem is in IO... your sieve is fast enough (should be around 2-3 seconds), but iostream is slow.
•  » » » » » 2 months ago, # ^ |   +3 sorry im new, what do you mean with iostream ? because endl?
•  » » » » » » 2 months ago, # ^ |   +4 Short Answer: Add ios_base::sync_with_stdio(false); to the start of your code if you want to continue using cin and cout. In that case, do not use scanf or printf. Also add cin.tie(NULL); to the start of your code. Do not use endl, but print \n instead. Note that if you test your program interactively like this, then you will not see any output until termination (i.e., all of the output comes in at once at the end) Long Answer: By default, cin and cout takes some extra time to synchronize with stdout (scanf and printf), e.g. to make sure cin doesn't read something that was already read by a previous scanf. To bypass this, you can either stop using cin/cout, or you can turn off the synchronization (ios_base::sync_with_stdio(false);) and be careful not to use scanf or printf.The other issue is only relevant if you are printing a lot of output (shouldn't be an issue for D here). Each time you use endl or cin, the output is flushed (i.e., whatever you were supposed to display from previous cout are gonna get displayed). Each flush takes some time. We can cut down the time by only invoking one flush at program termination. This requires never using endl and to ensure that cin does not invoke a flush (achieved by setting cin.tie (NULL))
•  » » » » » » » 2 months ago, # ^ |   0 thx i dont get TLE anymore ,but now i got WA ;)
•  » » » 2 months ago, # ^ | ← Rev. 4 →   0 ll MX = 1000*10000; int mx = 0; vector> p; void prep() { p.clear(); p.resize(MX); vector pr(MX, true); for (int i = 2; i < MX; i++) { if (p[i].size()) continue; if (!pr[i]) continue; for (int j = i; j < MX; j += i) { p[j].push_back(i); pr[j] = false; } } } Your code here... ~~~~~~~~~~
•  » » » » 2 months ago, # ^ | ← Rev. 6 →   0 The second for is better done like this: // i is prime number div[i] = i; for (long long j = (long long)i * i; j < MX; j += i) { div[j] = i; pr[j] = false; } Firstly, we will iterate $j$ from $i^2$. Secondly, we will save only the minimum prime divisor for each number. This algorithm works for $O(C log(log(C)))$, but written by you $O(Clog(C))$.Now, all divisors of a number $n$ are searched like this: while (n > 1) { // check answer for div[n] n /= div[n]; } 
•  » » 2 months ago, # ^ |   0 I think generating primes till root(10^7) is sufficient for the problem.
•  » » 2 months ago, # ^ |   +1 You dont need to generate prime numbers up to 10^7. Generating till sqrt(10^7) is sufficient.
•  » » » 2 months ago, # ^ |   0 why?
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   +14 Sieve Factorization. Set a sieve of size $10^7$ where $sieve[i]$ is initialized to $i$. Then find all prime numbers up to $\sqrt{10^7}$ and use them to "mark" all composites up to $10^7$, i.e., set $sieve[i]$ to a prime factor of $i$. You don't need to generate the prime numbers after $\sqrt{10^7}$. We can still factorize all numbers after $\sqrt{10^7}$ this way, since all composites would be marked, and prime numbers are initially marked by themselves anyway.My submission: 184943623. Since we don't need the largest prime factor, we could improve this further by letting the $j$-loop start from $i^2$ instead of $3i$.
•  » » » » » 2 months ago, # ^ |   0 So I tried a solution to generate all primes factor for all numbers up to 10^7. which should take N log log(N) ~100mil operations.Each number has another max 8 different prime factors, so the time to solve 10^6 cases is ~10^7. Why does this solution TLE?I know there's a better way to generate up only root(10^7) numbers but why does this solution TLE at 4 second ?
•  » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 The number of operations in a sieve is not $N \log \log N$, but rather, it is in $O(N \log \log N)$. The constant factor depends on the details of the sieve design, like whether you check even numbers or whether you generate primes beyond $\sqrt{N}$ or not. Your code seems to have none of these improvements, so the constant becomes pretty big. In general, a standard C++ code can comfortably perform $O(X)$ operations in 1 second when $X$ is of the order $10^7$. There are still exceptions where the constant factor is too big, but this is the general case for standard CP algorithms. However, when $X$ is of the order $10^8$, the constant factor matters immensely, and the finer details need to be sufficiently optimized to pass. For your approach, I expect $N = 10^5$ to run within 1 second comfortably, while $N = 10^6$ might fail 1 second but should be safe under 4 seconds, while $N = 10^7$ would definitely fail 4 seconds, and I doubt it would even pass 10 seconds, except maybe just barely. I might be wrong on these estimations, but that's what I would guess from experience. My suggestion would be to run your program to run only the sieve part (without reading any inputs or doing anything else) and check the time it takes to get a good estimation of whether it would work.
•  » » » » » 2 months ago, # ^ |   +6 Thank you, I learnt something new today — Sieve Factorization
•  » » » 2 months ago, # ^ |   0 generating primes up to 10^7 is much more convenient as you can easily do that with linear sieve. Besides, given the number of test cases, traversing all the prime numbers up to sqrt(num) is a bit risky
•  » » » » 2 months ago, # ^ |   0 Well it may be convenient but it is not time efficient. There are around 500 primes in less than sqrt(1e7), but there are 664579 primes in the range 1-1e7
•  » » » » » 2 months ago, # ^ |   +3 With the whole sieve built with linear sieve, you can easily compute each query in LOG(n), I am not sure what you mean by time inefficient. Can you explain?
•  » » 2 months ago, # ^ |   0 I ised linear sieve of erastothenes and it didn't led me to tle !
 » 2 months ago, # |   +11 Enough of these prime number questions...
 » 2 months ago, # | ← Rev. 3 →   +8 guys how did u fix wa16 in E??
•  » » 2 months ago, # ^ |   +27 Here is a test case that might help:$\texttt{6}$$\texttt{2 1 3 1 1 2}For me this was wrong: it is possible to have a sequence of size 3 (excluding 0's), •  » » » 2 months ago, # ^ | +8 oh, I see. thanks! •  » » 2 months ago, # ^ | +11 Just before failing on WA16 my states: vector st[Maxs] = {{}, {1}, {2}, {1, 2}, {2, 1}, {3}, {3, 1}, {3, 2}, {3, 1, 2}, {3, 2, 1}}; I passed it with states: vector st[Maxs] = {{}, {1}, {2}, {1, 2}, {2, 1}, {1, 1}, {1, 1, 2}, {1, 2, 1}, {2, 2}, {2, 1, 2}, {2, 2, 1}, {3}, {3, 1}, {3, 2}, {3, 1, 2}, {3, 2, 1}}; States represent the order of relevant stacks. Some duplicates should be allowed as 3 could consume the first duplicate. •  » » » 2 months ago, # ^ | 0 Can you explain your approach to E? Like how we are using these valid states.  » 2 months ago, # | 0 Can someone please give a test case for which my code for B is failing?https://codeforces.com/contest/1766/submission/184942949 •  » » 2 months ago, # ^ | 0 try "aaaa" •  » » » 2 months ago, # ^ | 0 It's giving YES as output. That's what it's supposed to give right? •  » » 2 months ago, # ^ | 0 "aaaab" should output "YES" •  » » 2 months ago, # ^ | 0 i checked ur code, it's giving no for bbaaaa, but the answer is yes, since we can write it in 5 i.e . less than 6 steps •  » » 2 months ago, # ^ | 0 1 5 aaaab should give Yes  » 2 months ago, # | ← Rev. 3 → 0 In 1766D I factorized |y-x| and got TLE... is there any solution without factorization?Update:got AC(1762ms) by using sieve and java.lang.StringBuilder(System.out.println() TLE'd) •  » » 2 months ago, # ^ | +3 Precompute the factorisation, or more specifically only the smallest prime factor. This can be done with a linear sieve (there's a cf blog on it). I posted my code 4 comments above. •  » » 2 months ago, # ^ | 0 How did you factorized ? If you used seive, then I don't think it would have given you TLE! •  » » » 2 months ago, # ^ | 0 Got TLE with seive. •  » » 2 months ago, # ^ | -6 O(\sqrt{n}) will clearly TLE. Instead you can use O(\log n) factorization using eratosthenes' sieve (or you may be able to squeeze pollard's rho in TL but I think it would be hacked afterwards) •  » » » 2 months ago, # ^ | +8 UPD: "you may be able to squeeze pollard's rho in TL but I think it would be hacked afterwards"Yes it did get hacked •  » » » » 2 months ago, # ^ | ← Rev. 4 → 0 I use this method to factorial but due to some mistack not able to done during contest even after 4 TLE and 4 RE + 1WA. Spoiler#define MAXN 1000051 ll spf[MAXN]; void sieve() { spf[1] = 1; for (ll i=2; i getFactorization(ll x) { vector ret; while (x != 1) { ret.push_back(spf[x]); x = x / spf[x]; } return ret; } 184984459 •  » » 2 months ago, # ^ | 0 Same here. I have seen a lot of solutions that passed that way. It is either we have missed something in the implementation or most of the solutions that passed that way will be hacked. •  » » » 2 months ago, # ^ | 0 use sieve only for sqrt(1e7) and then factorize y — x by iterating all 447 primes in [2, sqrt(1e7)]O(447n) •  » » » » 2 months ago, # ^ | 0 Did that. •  » » » » 2 months ago, # ^ | 0 I got TL with this solution. Can you show your code? •  » » » » » 2 months ago, # ^ | +3 •  » » » » 2 months ago, # ^ | 0 I did the same and also got TLE •  » » » 2 months ago, # ^ | 0 I changed endl to '\n' and it worked. •  » » 2 months ago, # ^ | 0 I factorized y - x and did not get TLE: 184943623Note: I used a sieve to generate the largest prime factor for each odd number from 3 to 10^7. I could have just used any prime factor (by letting the j-loop start from i^2), which would've been faster. If you TLE'd, my guess is that your sieve might not have been a very good one (e.g., outer loop running till 10^7 instead of its square root) •  » » 2 months ago, # ^ | +4 Need factorized |y-x| carefully.We can save the min factor of any number less than 10^7. Now for factorizing |y-x|, we can remove its min factor, and do it again, until all of factor found. •  » » » 2 months ago, # ^ | 0 Need to save not min but any factor actually. This solution works faster than mine. Thanks for sharing it helped •  » » 2 months ago, # ^ | +4 My issue (and I suspect a lot of other getting TLE on D) turned out to be using "<< endl" instead of "<< \n". 1e6 instead of usual 1e5 output lines turns out to be the magic threshold where output speed matters, and even such small issue can kill you. •  » » » 2 months ago, # ^ | ← Rev. 2 → 0 i got TLE i change endl to \n and add ios_base::sync_with_stdio(false); cin.tie(NULL); no TLE anymore but WA ;)before 184970170 after 184985603  » 2 months ago, # | ← Rev. 2 → 0 please tell me there's a better solution for D aside factoring |y - x|. That was very painful. •  » » 2 months ago, # ^ | +1 I don't think so, but looking at your submission, it can be optimised by using a linear sieve instead. •  » » » 2 months ago, # ^ | 0 I see, thanks. The observation was quite obvious, but getting my factoring to pass was very difficult.  » 2 months ago, # | +3 How avoid WA16 in E? •  » » 2 months ago, # ^ | 0 Waiting for a reply to the same question! xd!! •  » » 2 months ago, # ^ | ← Rev. 3 → +8 One of my WA submissions fails on51 2 3 2 1Edit: Okay, your latest submission fails on this case too •  » » » 2 months ago, # ^ | 0 what's answer for this case? •  » » » » 2 months ago, # ^ | 0 23 •  » » » » » 2 months ago, # ^ | +3 Thanks, I thought the maximum length of the list(without 0) can be 2 but it can be 3 also. •  » » 2 months ago, # ^ | 0 •  » » 2 months ago, # ^ | 0 Okay, i understood my mistake, thanks  » 2 months ago, # | +1 Successfully solved D for the first time, E seems like a tough one, I can only think that 2 followed by a 1 with any number of 0s in between will create an extra subsequences and obviously 0s will also create extra subsequences, I tried to count that in how many sub-arrays a 0 will contribute an extra subsequence and similarly for [2...1] but didn't get the right answers, any similar ideas? •  » » 2 months ago, # ^ | 0 My idea (didn't write up a complete solution btw, so take this with a grain of salt):The number of non-zero subsequences is at most 3. We can try to count how many subsegments will generate each possible number of subsequences. No non-zero subsequences -> The subsegment contains only 0s. We can easily count how many there are. Exactly one non-zero subsequence -> If we look at the non-zero values of the subsegment, we must not have a 2 followed by a 1 or a 1 followed by a 2 (so there is always a 3 in between) Exactly two non-zero subsequences -> This seems to be the hardest, so I was planning to find this by subtracting the others off of the total. Exactly three non-zero subsequences -> There are two sub-cases: Second non-zero subsequence ends with 1: Subsegment contains a 2 followed by a 1 (ignoring 0s in between). Later, after some 3, we get a 1 (so both non-zero subsequences end with 1) and then a 2 (which must form a third non-zero subsequence). Ignore all 0s in between. Second non-zero subsequence ends with 2: Symmetric to the other case The challenge I faced with these counts is on the 0s. It's not enough to just find some segment that fulfills a condition, because a group of 0s can merge easily with whatever fulfills the left side and also whatever fulfills its right side, and I couldn't figure out how to deal with this effectively. •  » » » 2 months ago, # ^ | 0 Yea the in between zeros will make it hard, the implementation would be huge, at least for me, there must be an easier solution, thanks for sharing this one, lets wait for the editorial. •  » » » » 2 months ago, # ^ | ← Rev. 2 → 0 ez solution:my comment no nested loops and only one if statementonly disadvantage: not understandable at all  » 2 months ago, # | ← Rev. 2 → 0 how to solve problem C anybody ? any hints •  » » 2 months ago, # ^ | 0 Think about simulating the process and about the possible movements you can do when at a certain position.Also keep in mind the given constraints that each column has at least one "B". •  » » 2 months ago, # ^ | 0 Think about the distance between each adjacent W's. And what happens when it is even or odd. •  » » 2 months ago, # ^ | 0 Simulating the process might lead to TLE.Hint : make a vector pair of the number of whites and sort it. Now for each white (say i,j) and its the next nearest white (say i1,j1) see that the answer is NO if (i1-i)%2 == (j1-j)%2 and YES if the before condition doesn't hold for all whites.  » 2 months ago, # | 0 Hint for D? •  » » 2 months ago, # ^ | ← Rev. 2 → +4 \gcd(a + k, b + k) = \gcd(a + k, b - a), so for it to not be 1, we want p \mid a + k where p is a prime factor of b - a. Therefore, we generate all prime factors of b - a, which is precomputed by sieving. Then, p \mid a + k means k = (-a) \mod p. Take the minimum over all prime factors. •  » » » 2 months ago, # ^ | 0 Thanks, got it. •  » » 2 months ago, # ^ | +1 Hint 1gcd(a,b)=gcd(a,b-a). So basically if gcd(a,b) is not 1, it will be a divisor of b-a. Hint 2If that divisor is not a prime factor, it will clearly take longer to get that value as the gcd than the prime factors will. •  » » » 2 months ago, # ^ | 0 I did D in the contest by taking my intuition to check for only prime factors of (b-a). Can you please why shouldn't I take composite factors? •  » » » » 2 months ago, # ^ | 0 if any composite factor is the gcd then any of the prime divisors of that factor will also divide both numbers  » 2 months ago, # | 0 184979418My code for d keeps giving different output in sublime and different output when i submit it on cf •  » » 2 months ago, # ^ | 0 In your code, you are giving -1 output for 1 case only, but there are different cases possible when there will be -1 as output. You might be running given test case in sublime, but when another test cases would have be checked, then your code gave TLE. •  » » » 2 months ago, # ^ | 0 what case •  » » » » 2 months ago, # ^ | 0 Even I couldn't figure other cases of infinite length while solving.  » 2 months ago, # | +3 can someone pls explain how to solve e .thanks in advance.  » 2 months ago, # | +1 Am i the only one who wasted time by writing a stupid dp solution for C? •  » » 2 months ago, # ^ | 0 DP was also my first instinct, but then I realized that the path was simply forced to go up/down if the other cell was also Black, and from then on the only possible continuation was going to the right, and repeat. •  » » 2 months ago, # ^ | 0 Me, too, wasted some of my time by thinking in the direction of DP ;) •  » » » 2 months ago, # ^ | 0 I did a 2*n dp table where dp[i][j] is true if you can finish painting the jth column in the ith cell. •  » » 2 months ago, # ^ | 0 lol i also did a dp solution haha new learning for me •  » » » 2 months ago, # ^ | 0 Can someone help me out in c? code: 185047353I did it by traversing both strings and comparing the positions of the white color. but it is failing on 2nd test case ;( i don't know exactly where it's failing. thanks in advance.  » 2 months ago, # | 0 Hint for D ? •  » » 2 months ago, # ^ | ← Rev. 3 → +19 Depends on how far you thought ahead. Hint 1Instead of considering the GCD of two values that change, try to express the GCD such that one number is fixed (and the other number can change). Hint 2If A + B = C, any number that divides two of A, B, and C must also divide the third. Hint 3Factorize the fixed number. Brief OverviewBasically, we need to output the smallest \ell such that gcd (x + \ell, y + \ell) \neq 1. A value \ell satisfies gcd (x + \ell, y + \ell) \neq 1 if and only if it satisfies gcd (x + \ell, y - x) \neq 1. We can then factorize y - x and for each prime factor p, we find the minimum \ell' such that p divides x + \ell'. This is simply \ell' = p - (x \% p). The answer is the minimum of all \ell'.My Submission: 184943623 •  » » » 2 months ago, # ^ | 0 WonderFull explanation dude •  » » » 2 months ago, # ^ | 0 Can you please explain how you implemented the factorization part in your code? •  » » » » 2 months ago, # ^ | +3 Are you familiar with the Sieve of Eratosthenes? The basic idea is that we prepare an array sieve of size 10^7 such that the value of sieve[i] should be any prime factor of i. Initially, we set sieve[i] = i for all i, with the intention of changing this later only for composite values. Now, for each i in increasing order, check if sieve[i] is still equal to i (i.e., it never changed). If yes, then i is prime. For each multiple of i, e.g., ai, we set sieve[ai] = i. Therefore, every composite number i will eventually have sieve[i] as one of its prime factors. (This can be improved in several ways. We can skip all even numbers, because it's easy to check evenness and deal with it separately without needing to utilize a sieve. When we check each i in increasing order in order to find prime numbers and their multiples, we can stop when i > \sqrt{10^7} since every composite number up to 10^7 will have at least one prime factor \leq \sqrt{10^7}, so its sieve value would be set to some prime factor. Also, when finding multiples of i, we can start with i^2 since all the earlier multiples would've been covered by an earlier prime)After setting up the sieve, we can now factorize numbers efficiently. To factorize x, we read sieve[x] to get one prime factor. We then divide x by this factor, i.e., x' = x/sieve[x]. Now we can read sieve[x'] to get another prime factor. Repeat until x is reduced to 1 in order to construct the complete prime factorization. •  » » » » » 2 months ago, # ^ | 0 what will happen if i generate all prime till 10e7 and linearly calculate the list of primes of y-x?why its giving tle ? •  » » » » » » 2 months ago, # ^ | 0 Because it's slow. There are a lot of primes up to 10^7. Even just generating those prime numbers will likely cause TLE, even before you try factorizing y - x. On the other hand, the efficient sieve factorization which I described that requires finding only the primes up to \sqrt{10^7} is significantly faster, comfortably passing the time limit. •  » » » » » » » 2 months ago, # ^ | 0 Gotcha •  » » » » » » » 2 months ago, # ^ | 0 hi just to add on my approach is very similar to the one here, but I keep getting TLE. Does anyone know how I can optimise my code to pass D?My code: Code •  » » » » » » » » 2 months ago, # ^ | ← Rev. 3 → +3 You're using a Boolean Sieve, which works great for checking if a given number is prime, but is not very efficient for actually factorizing many numbers. For each number you wish to factorize, you might have to check over 3000 prime numbers in the worst-case. With 10^6 numbers to factorize, this would not pass the time limit.For Sieve Factorization, you need to make a small change to your sieve function. Instead of making the value False for a composite, make the value p instead (the prime number whose multiples you're marking). There is no need to generate a list of primes. Now, to factorize a number x, you can read the value p from the sieve list to get one factor, then divide x/p, read the corresponding value from the sieve list to get another factor, and so on. This way, the time taken to factorize a single number is proportional to the number of prime factors it decomposes into, which is at most \log_2 (10^7) < 25, much better than iterating over 3000 steps! •  » » » » » » » » » 2 months ago, # ^ | 0 Hi thank you for the response! I can understand the first paragraph, but I am not sure of what you mean in the second paragraph, and how that will result in a shorter runtime. Do you happen to have any pseudocode to illustrate what you mean by "Now, to factorize a number x, you can read the value p from the sieve list to get one factor, then divide x/p, read the corresponding value from the sieve list to get another factor, and so on."? •  » » » » » » » » » 2 months ago, # ^ | ← Rev. 2 → 0 chiralcentre Here is some simple Python code for it: Preparing the SieveSIZE = 10000005 # initially, sieve[i] = i sieve = list (range (SIZE)) for i in range (3, SIZE, 2): if i * i > SIZE: break if sieve[i] == i: for j in range (i * i, SIZE, 2 * i): sieve[j] = i  Factorizing an integerdef factorize (x): lst = [] while x % 2 == 0: lst.append (2) x //= 2 while x > 1: fctr = sieve[x] while x % fctr == 0: lst.append (fctr) x //= fctr return lst The second block is a function that returns the list of prime factors to convey the general idea, but you can, of course, modify it accordingly to what you need.You can also improve the sieve by not even allocating space for the even values, e.g., sieve[i] represents 2i + 1, but that hurts readability, so I didn't do that here.Let me know if you have any questions. •  » » » » » » » » » 2 months ago, # ^ | 0 Thank you for the reply! I understand better now haha  » 2 months ago, # | 0 Problem A's harder version. •  » » 2 months ago, # ^ | 0 Digit dp?  » 2 months ago, # | 0 Although I only solved up to C, this set was good!. After seeing other submissions on D I realized rather than looping through primes until sqrt(1e+7) (which is about 700 prime numbers) it's better to factorize the difference!  » 2 months ago, # | 0 The feeling when you screw up C for more than half an hour because you forgot how c++ grid coords work... again. And then I got late for 2-3 damn seconds. Hate myself...  » 2 months ago, # | ← Rev. 9 → +8 Solution for E:First,calculate the contribution of 0 separately.Next, enumerate the left endpoint L=1,2,..., n .(Next we ignore 0)We find that the answer is always no more than 3.Ans=2 : a[L,R]= ... 1,2 ... , or ... 2,1 ...$$Ans=3$ : $a[L,R]=$ $... [1,2] ... [3 ... 3 2 ... 2 1] ...$ , or $a[L,R]=$ $... [2,1] ... [3 ... 3 1 ... 1 2] ...$If there is no above condition, $ANS=1$ or $ANS=0$ (all elements are $0$).
•  » » 2 months ago, # ^ |   0 I think my solution is the same. I split the array into subarrays whenever we encounter a 3, and then for each subarray, we store the occurrences of $[1, 2]$ and $[2, 1]$. Note that only the first occurrences of the subarray will contribute to the answer.
 » 2 months ago, # | ← Rev. 2 →   +4 i think E is just case work. (correct me if i'm wrong) if you ignore all the 0, it can be proven that the maximum number subsequence will be <= 3
•  » » 2 months ago, # ^ | ← Rev. 3 →   +16 I have a solution without any casework.let ignore sequence with single $0$ first since we can calculate its contribution to answer easily, then we can find that $3$ can only be at the first sequence, and there will be at most one extra sequence which only have $1$, and at most one extra sequence only have $2$.So we can just do $dp[\text{n}][\text{the last element of first sequence}][\text{flag1}][\text{flag2}]$ where $\text{flag1/flag2}$ represent whether we have a extra sequence with $1/2$.
 » 2 months ago, # |   +1 In problem $B$, am I the only one who thought that the number of operations may be less than (n-1) ? :(
 » 2 months ago, # |   +7 nice contest
 » 2 months ago, # | ← Rev. 4 →   0 Can someone explain problem C ? I did a dfs + visited hashset but it kept giving me TLE. https://codeforces.com/contest/1766/submission/184980253
•  » » 2 months ago, # ^ |   0 simulation
•  » » » 2 months ago, # ^ |   0 I think I did the simulation but it kept giving me TLE.
•  » » 2 months ago, # ^ |   -8 I dont know if a dfs passes, but could be done by a simple observation that each time a sequential BB occurs, I am attaching my code #include using namespace std; #define pb push_back #define mp make_pair #define S second #define F first #define pu push #define po pop #define oo 99349092 #define fast_IO ios_base::sync_with_stdio(false); #define null cin.tie(nullptr); #define lenn .size() #define ret return 0; void solve() { int n; cin>>n; string A, B; cin>>A; cin>>B; int p = 0; bool dp0 = 1, dp1 = 1; for(int i=0; i>t; while(t--) { solve(); } } 
•  » » » 2 months ago, # ^ |   0 Thanks.... this makes sense. Thanks a ton
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Hint : make a vector pair of the number of whites and sort it. Now for each white (say i,j) and its the next nearest white (say i1,j1) see that the answer is NO if (i1-i)%2 == (j1-j)%2 and YES if the before condition doesn't hold for all whites.
•  » » 2 months ago, # ^ |   0 huh , that's strange , I solved it using DFS :|
•  » » » 2 months ago, # ^ |   0 I think it maybe bcoz u did in C++ and I did in Python(not sure tho). Anyways, I have figured out another way thanks to @WarriorOfLiberation. Thanks for trying to help though.
 » 2 months ago, # |   0 Hints for B ,Please ?
•  » » 2 months ago, # ^ |   0 if 'x' letter precedes a letter 'y', then when 'y' letter occurs again in the string check if there is a preceding 'x'. If there is a preceding 'x' to the second occurence of 'y', then it is guarenteed that answer is less than n
•  » » 2 months ago, # ^ |   0 HINTThink in terms of copying Contiguous Subsequnece of length 2 .
 » 2 months ago, # |   +8 Problems were good , was a good contest
 » 2 months ago, # |   +4 Speedforces :(
 » 2 months ago, # | ← Rev. 2 →   +3 Is it possible to use Möbius inversion and binary search to solve D? Search the k and check the sum of [gcd(x+i,y+i)==1](0<=i<=k) is whether equals to (k + 1) in time limit. I spent a lot of time trying it but failed.
 » 2 months ago, # |   0 Another approach for C: Store the positions of W, in increasing order of column number. The following condition should be satisfied for the answer to exist : For any 2 consecutive position of W, if they were in the same row, then the difference between their position must be ODD, or else it should be EVEN. 184980206
 » 2 months ago, # |   +7 Here are video Solutions for A-D, in case someone is interested.
 » 2 months ago, # |   0 Do we get or lose points for hacking in this round?
•  » » 2 months ago, # ^ |   +1 Nope
•  » » » 2 months ago, # ^ |   0 Okay, thanks. But I notice my rank is still increasing, is it because of virtual particpants?
•  » » » » 2 months ago, # ^ |   0 yes, due to virtual participants. Also, it could decrease if someone previously above you got solution hacked for some problem.
 » 2 months ago, # |   0 Nice E, hope to get to Master!
 » 2 months ago, # |   +1 complete codeimport java.util.*; import java.io.*; public class Problem1766E2 { //magic numbers static int[] next1=new int[] {1,1,5,1,4,5,4,9,11,9,10,11, 10,15,14,15}; static int[] next2=new int[] {2,4,2,2,4,5,8,5,8,10,10,11, 14,11,14,15}; static int[] next3=new int[] {3,3,3,3,6,7,6,7,6,7,12,13, 12,13,12,13}; static long[] state=new long[16]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.valueOf(br.readLine()); long ans=0; for (int i = 1; i <= n; i++) { int t = readInt(br); if(t==0) { ans+=((long)i)*(n+1-i); }else { transit(t); } state[t]++; //System.out.println(subSequenceCount(state)); ans+=subSequenceCount(state); } System.out.println(ans); } static long subSequenceCount(long[] a) { long sum=0; for(int i=1;i<=3;i++) sum+=a[i]; for(int i=4;i<=9;i++) sum+=2*a[i]; for(int i=10;i<=15;i++) sum+=3*a[i]; return sum; } static void transit(int i) { int[] next=(i==1)?next1:(i==2?next2:next3); long[] newState=new long[16]; for(int j=0;j<=15;j++) { newState[next[j]]+=state[j]; } state=newState; } public static int readInt(BufferedReader br) { int input = 0; int c; try { while ((c = br.read()) > 32) { input *= 10; input += (c - 48); } } catch (IOException e) { e.printStackTrace(); } return input; } } part of my code for 1766E //magic numbers static int[] next1=new int[] {1,1,5,1,4,5,4,9,11,9,10,11, 10,15,14,15}; static int[] next2=new int[] {2,4,2,2,4,5,8,5,8,10,10,11, 14,11,14,15}; static int[] next3=new int[] {3,3,3,3,6,7,6,7,6,7,12,13, 12,13,12,13}; wish I've come up with this idea before the contest ended
•  » » 2 months ago, # ^ |   0 Complete code ? Thank you, here's the meme for you.Why would you paste code without a link ? Improve your manners
•  » » 2 months ago, # ^ | ← Rev. 13 →   0 Explaination: In a subsequence only the last element matters. We count answer by counting 0s and non-zero sequences. For 0 at position i it contributes i*(n+1-i). We construct a FSM for another part of the anwser, where its states are represented by the last element of each non-zero sequence. By compute with brute force we can show that there are only 16 possible states: (none),1,2,3,12,21,32,31,22,11,112,221,312,321,212,121. Then we can number these states and make the state transition table manually. Remaining work is trivial.
 » 2 months ago, # |   0 can anyone tell me why my solution getting tle for problem d? https://codeforces.com/contest/1766/submission/184998801thanks in advance.
 » 2 months ago, # |   0 Japan or2
 » 2 months ago, # |   0 Could anyone explain to me how this solution works? (I am skimming through various solutions for problem A and this one is interesting.) string s; cin >> s; int l = (int)s.size(); cout << 9*(l — 1) + s[0] — '0' << '\n';
•  » » 2 months ago, # ^ | ← Rev. 5 →   0 one-digit number -> 1-9: {1,2,3,4,5,6,7,8,9} = 9two-digit number -> 10-90: {10,20,30,40,50,60,70,80,90} = 9three-digit number -> 100-900: {100,200,300,400,500,600,700,800,900} = 9...six-digit number -> 100000-900000: {100000,200000,300000,400000,500000,600000,700000,800000,900000} = 9 Thus in every n-digit has 9 numbers having interval is 10^n-1 for each only one non-zero digitso the ans will be : 9*(LenthOfTheNumber-1) + firstDigitOfTheNumberfor example: n = 201length of n = 3 first digit of n = 2=> 9*(3-1) + 2 => 18 + 2 = 20
•  » » » 2 months ago, # ^ |   0 Thanks for explanation!
 » 2 months ago, # | ← Rev. 4 →   +8 Solution for D: We want $gcd(x+k, y+k) = d , (d > 1)$ then$x+k \equiv y+k \equiv 0 \mod{d} $$x+k \equiv y+k \mod{d}$$ x \equiv y \mod{d} $$x-y \equiv 0 \mod{d} to make x-y divisible by d, d must divide x-yso we will get prime factors of x-ysuppose that prime factors of x-y is p_1, p_2, p_3,...,p_mif we return to our first equation x+k \equiv y+k \equiv 0 \mod{d} substitute d= p_i$$x+k \equiv y+k \equiv 0 \mod{p_i}$we have $x-y \equiv 0 \mod{p_i}$then $x \equiv r \mod{p_i} \;\;\;, y \equiv r \mod{p_i}$after subsititution of x and y$r+k \equiv r+k \equiv 0 \mod{p_i}$ so k must be $p_i-r$I get Wa on the contest because I forget to get the min for all p_iMysumbission TIME (810 ms) 
 » 2 months ago, # | ← Rev. 3 →   -18 1766A - Extremely RoundMy submission -> 185002843Can anyone please explain why I am getting TLE on test case two of the following code? #include using namespace std; int main() { int t; cin>>t; while(t--) { long long n,s1=0,s2=0,s3=0,s4=0; cin>>n; for(long long i=1;i<=n;i++) { if(i<10) s1=i+0; else if(i==10||i==20||i==30||i==40||i==50||i==60||i==70||i==80||i==90||i==100) s2 = i/10; else if(i==200||i==300||i==400||i==500||i==600||i==700||i==800||i==900||i==1000) s3 =i/100-1; else if(i==2000||i==3000||i==4000||i==5000||i==6000||i==7000||i==8000||i==9000||i==10000) s4 = i/1000-1; else if(i==20000||i==30000||i==40000||i==50000||i==60000||i==70000||i==80000||i==90000||i==100000) s4 = i/10000-1; } cout<<(s1+s2+s3+s4)<
•  » » 2 months ago, # ^ |   0 On this question t can be up to 10000 and n can be up to 999999. On the worst case scenario your code perform 10000 * 999999 operation that's why it is getting TLE verdict. It is better to memorize the answer from 1 to 999999 instead of calculating the result repeatedly.
•  » » » 2 months ago, # ^ |   0 But in this problem we have 3 second per test case. I have only one loop having O(n). It can pass easily!?
•  » » » » 2 months ago, # ^ |   0 3 second for entire test case and for a single test t can be up to 10000.
•  » » » » 2 months ago, # ^ |   0 The time limit is not 3 seconds per test case, but 3 seconds per test.
 » 2 months ago, # |   +47 I have a question for those who solved F (spoiler alert — it is about some part of the solution). SpoilerWhen designing the solution to this problem, I found it kinda difficult to avoid having negative cycles in the flow network. I've eventually figured out how to construct it without negative cycles, and I want your opinion on that. Have you come up with a network design without negative cycles, or have you just used a mincost flow algorithm that handles them? Also, do you think it's reasonable to have mincost flow problems where one of the solutions (but not all of them) relies on having to implement negative cycle handling?
•  » » 2 months ago, # ^ |   +31 Add edges from new_s and edges to new_t with a very negative value, and add edges from t to s with a very positive value, the new graph will not have negative cycles, find the min cost max flow in the new graph and delete new_s, new_t to run min cost flow from s to t.
 » 2 months ago, # | ← Rev. 2 →   +3 For question D:So I tried a solution to generate all primes factor for all numbers up to 10^7. which should take N log log(N) ~100mil operations.Each number has another max 8 different prime factors, so the time to solve 10^6 cases is ~10^7. Why does this solution TLE?I know there's a better way to generate up only root(10^7) numbers but why does this solution TLE at 4 second ?
•  » » 2 months ago, # ^ |   0 probably because push_back is slow
•  » » 2 months ago, # ^ |   0 Same code as yours but with C++20 (185029658) gives MLE. I suspect yours is MLE too.
•  » » » 2 months ago, # ^ |   +3 same idea used but with little extra help 184968390 ,184969180 and 184969946 as you can see the more primes I checked separately the better the time gets
•  » » » » 2 months ago, # ^ |   0 Thanks! Any idea on when it stops helping? If ve.size()==k then maxm*(ln(ln(k))) ops are saved in the sieve but I find it hard to estimate the overhead due to for (int p : ve){...}.
•  » » » » » 2 months ago, # ^ |   +3 I think we can go further from 47 but I don't know till when it will get better
 » 2 months ago, # |   -23 For problem C: Hamiltonian Wall, I was getting the error. Can anyone point out where is the mistake? t=int(input()) for _ in range(t): arr=[] x=int(input()) y=input() z=input() arr.append(list(y)) arr.append(list(z)) b,w=False,False c=0 flag=True for j in range(len(arr[0])): if arr[0][j]=='B' and arr[1][j]=='B': c+=-1 elif arr[0][j]=='W' and arr[1][j]=='B': if w: if c%2: flag=False break else: flag=True elif b: if not c%2: flag=False break else: flag=True c=0 w=True elif arr[0][j]=='B' and arr[1][j]=='W': if b: if c%2: flag=False break else: flag=True elif w: if not c%2: flag=False break else: flag=True c=0 b=True else: flag=False break if not flag: print('NO') else: print('YES') 
•  » » 2 months ago, # ^ | ← Rev. 2 →   -21 def solveShit(): m = int(input()) s = [getStrs(), getStrs()] cnt =0 cur = 1 flag = False for i in range(m): if s[0][i]==s[1][i]: cur = not cur else: if s[cur][i]!='B': break cnt+=1 if cnt==m: flag = True cur = 0 cnt =0 for i in range(m): if s[0][i] == s[1][i]: cur = not cur else: if s[cur][i] != 'B': break cnt+=1 if cnt==m: flag = True if flag: print("YES") else: print("NO") 
 » 2 months ago, # | ← Rev. 3 →   0 Can someone explain solution of Problem E?Thanks in Advance.
 » 2 months ago, # |   0 Can Anyone Explain Why my Solution For D Gave TLE:(https://codeforces.com/problemset/submission/1766/184955390
•  » » 2 months ago, # ^ |   0 got TLE with input 1,8388609 where diff=8334608=1<<23 and your solution consumed too much time for factorization. In fact answer is 1 when x,y are both odd numbers, so determine it first can save a lot of time
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 also there's no need for push duplicated element to s1
•  » » 2 months ago, # ^ |   0 Just replace endl with '\n' and your solution will pass.I faced the same issue
 » 2 months ago, # | ← Rev. 2 →   +6 I solved problem D offline, but no body hacked me. 184948549
 » 2 months ago, # |   0 (◕︵◕) I will be +99 at this contest but road to expert still so far.
•  » » 2 months ago, # ^ |   +1 Man, just 1 more good contest to go. All the best!
 » 2 months ago, # |   0
 » 2 months ago, # |   +6 My D using neal Pollard's rho code from last contest.https://codeforces.com/contest/1766/submission/184943158Passes under 2.5 seconds
•  » » 2 months ago, # ^ |   0 Is the code based on Brent's improvement on Pollard's Rho? FYI, The constant on the one with Brent's improvement is quite smaller than the vanilla one.
 » 2 months ago, # |   +7 Why is it rejudged twice?
 » 2 months ago, # |   +3 When will the editorial be out?
 » 2 months ago, # |   0 When can l get the rattings why it shows that the contest is unrated in my constets
•  » » 2 months ago, # ^ |   0 do you have any updates? when will the rating be out?
•  » » » 2 months ago, # ^ |   0 NO,and I'm waiting for the results for a long time .Maybe tomorrow the results will be out.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 The results for the educational/div 3/div 4 rounds are coming in the afternoon or in the evening of the next day from the contest so they will be today but i don't know when.
•  » » » » » 2 months ago, # ^ |   0 OK,thanks for your reply.
 » 2 months ago, # |   +22 I participated in the contest. I submitted by code for problem D(184941244) and it got hacked because Time Limit exceeded. After the contest I submitted the same code(185049594) and it got accepted. I want to bring this to the notice of the authors of the contest(awoo, BledDest,Neon, adedalic) and Mike MikeMirzayanov to consider this problem and come up with a solution to this.Thank You
•  » » 2 months ago, # ^ |   0 Use '\n' in place of endl to reduce the time of your soln. My solution got accepted during the hacking phase with the same time as yours, but got TLE during system testing..
 » 2 months ago, # |   0 I participated in the contest. I submitted by code for problem D(184961915) and it got hacked because of Runtime Error. After the contest I submitted the same code(185050448) and it got accepted. I want to bring this to the notice of the authors of the contest(awoo, BledDest,Neon, adedalic) and MikeMirzayanov to consider this problem and come up with a solution to this.Thank You
•  » » 2 months ago, # ^ |   +1 This is also your solution getting TLE on test 3. You probably have an undefined behavior somewhere in your solution. I don't think the contest authors can do anything about that.
 » 2 months ago, # |   -14 I got TLE in 1766D - Lucky Chains after the contest because of the usage of endl instead of \n I think the solution should be considered accepted as the algorithm is fine The TLE solution 184975152 The accepted one 185056871
•  » » 2 months ago, # ^ | ← Rev. 2 →   +18 It's unfortunate that you were unaware of the timing delays caused by endl flushes, but the reality is that the submission did not pass the time limit. There is no subjective judgment on whether a solution should be "considered" accepted or not (just like how a submission that solves 99% of the cases but fails one specific edge case is still not going to be "considered" accepted). Please instead use this as a learning experience to avoid using endl in the future. This is an important component of fast I/O, and I can see that your code already attempts to speed up the I/O.On that note, I would also recommend that you properly learn what your code does, instead of memorizing or preparing a template of code you don't understand. Both submissions had cin.tie (0);, but the purpose of this (prevent early flushing) is basically cancelled out by the use of endl. By the way, cout.tie (0) doesn't do anything.
 » 2 months ago, # |   +7 When will the results be out??
 » 2 months ago, # |   +28 Release the updates :) :), I need to see my shiny new color
•  » » 2 months ago, # ^ |   0 Same BrO :)
 » 2 months ago, # |   +13 contest ratings are not updated yet. why?
 » 2 months ago, # |   0 Where is the editorial?
•  » » 2 months ago, # ^ |   +10 While you wait you can ask here about the problems or see what other people wrote above
 » 2 months ago, # |   +23
 » 2 months ago, # |   0 Where is my new slightly bigger rating???
 » 2 months ago, # |   0 Hello?It said "rated for the participants with rating lower than 2100".But the line chart in my profile shows that this Round is "unrated" for me.Is it a bug?
•  » » 2 months ago, # ^ |   0 It means the round is not rated YET, may not be a bug necessarily.
 » 2 months ago, # |   +1 Change my color
 » 2 months ago, # |   +9 So,what time does the rating change? qwq
 » 2 months ago, # |   +6 How long will cyan have to wait to take over green?
 » 2 months ago, # |   0 Maybe this will be the first div2 contest which everyone got unrated lol
•  » » 2 months ago, # ^ |   0 Educational Codeforces Round 121 (Rated for Div. 2) was unrated because of some technical issues during the contest.
•  » » » 2 months ago, # ^ |   +2 was it announced? i didn't see any announcement regarding that
•  » » » » 2 months ago, # ^ |   +11 For 139? I also didn't see any announcement. I hope it's not unrated :(I was gonna get to CM for the first time :(
 » 2 months ago, # |   0 Is the contest unrated?
•  » » 2 months ago, # ^ |   0 :(
•  » » 2 months ago, # ^ |   0 No updates till now....
 » 2 months ago, # |   0 When is the editorial?
•  » » 2 months ago, # ^ |   +1 behind you...
 » 2 months ago, # |   0 I'm a novice. B's first idea about KMP is KMP, but I don't have any idea about KMP. I hope to give some hints
•  » » 2 months ago, # ^ |   +1 think about a substring of length 2
•  » » 2 months ago, # ^ |   +6 I thought about KMP too in tne contest and have wasted a lot of time on this idea, because I didn't notice that $n$ is just the length of the string, rather than an arbitrary number. Otherwise this problem maybe far more difficult.
•  » » » 2 months ago, # ^ |   0 +1
 » 2 months ago, # |   +69 is it really unrated :(
 » 2 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
•  » » 2 months ago, # ^ |   +33 where are the rating changes :(
•  » » 2 months ago, # ^ |   0 i am not doing any cheating in contest ,i had give many contest at default mode of ide, till now i don't know it will be cheated at that ide. so please take my solution its my hard work on that solution i think u take it serious.
•  » » 2 months ago, # ^ |   0 i am not doing any cheating in contest ,i had give many contest at default mode of ide, till now i don't know it will be cheated at that ide. so please take my solution its my hard work on that solution i think u take it serious.
 » 2 months ago, # |   +24 Will we get the rating today? MikeMirzayanov, we, thousands of participants, are eagerly waiting for the rating change.
 » 2 months ago, # |   +4 MikeMirzayanov, awoo. Can we knwo why the rating hasn't changed? We have waited already two days with no information. Is there a problem with the rating system or will we get our rating at all? :/
 » 2 months ago, # |   +11 When will the rating get updated? Is it unrated?
 » 2 months ago, # |   +9 why the rating has not been updated?
 » 2 months ago, # |   +9 when will the ratings be out??
 » 2 months ago, # | ← Rev. 2 →   +8 it's my first contest ㅠ_ㅠ wanna get my rating..,,
 » 2 months ago, # |   +31
 » 2 months ago, # |   +6 Why is the rating not updated?
 » 2 months ago, # |   +6 Is it was not rated?
 » 2 months ago, # |   +9 ratings vro
 » 2 months ago, # |   +9 When will the rating get updated? I was going to get under zero rated for the first time :(
 » 2 months ago, # |   0 No ratings till now.
 » 2 months ago, # |   0 @Codeforces , atleast give update about rating changes
 » 2 months ago, # |   +12 It is deadforces? No ratings updated yet
 » 2 months ago, # |   +18 This has been the longest waiting time before ratings to be updated in almost 2 years.
 » 2 months ago, # |   +8 I'm refreshing the page since yesterday :( ...plz release the ratings fast or atleast give an update
•  » » 2 months ago, # ^ |   +1
•  » » » 2 months ago, # ^ |   +5 me too =D
 » 2 months ago, # |   +5 DeadForces!
•  » » 2 months ago, # ^ |   +8 DeadForces!
 » 2 months ago, # |   +2 Harshly true that awoo wants more comments to announce the rating! source: deadforces
 » 2 months ago, # |   0 Deadforces!
 » 2 months ago, # |   0 when did rates will be updated?
 » 2 months ago, # |   0 why the rating changes are not being updated ?? its been 3 days since contest ..
 » 2 months ago, # |   +12 Hey guys, it has been 3 days since the contest started. Why does it take so long :(?.
 » 2 months ago, # |   +4 My rating!When can I get my rating!TAT
 » 2 months ago, # | ← Rev. 2 →   0 DeadForces! Where’s my rating…=_=
 » 2 months ago, # |   0 deadforces :(
 » 2 months ago, # |   0 Cyan be waiting for too long now.
•  » » 2 months ago, # ^ |   +1 What happened to your rating graph ?
•  » » » 2 months ago, # ^ |   0 Looks like a bug, I'm sure am not the only one.
 » 2 months ago, # |   0 To everyone writing deadforces Glitches happen sometimes. Starting to make fun of such a wonderful platform is not funny. Codeforces is <3
•  » » 2 months ago, # ^ |   +1 That's fine. But atleast they can inform about that.
•  » » 2 months ago, # ^ |   +6 The problem is that so far to my knowledge we've not received any word from MikeMirzayanov or awoo about it. Is it a glitch? Are they working on it? Will we eventually receive our rating? Will the round be unrated? I hope they can at least give any update on this
 » 2 months ago, # |   +1 i am not doing any cheating in contest ,i had give many contest at default mode of ide, till now i don't know it will be cheated at that ide. so please take my solution its my hard work on that solution i think u take it serious.
 » 2 months ago, # |   0 How do I prove that I have not cheated?
•  » » 2 months ago, # ^ |   0 say mother promise!
•  » » » 7 weeks ago, # ^ |   0 what?
 » 2 months ago, # |   0 It would be so much easier to read the comments that discuss solutions if there were not so many people asking about the rating change. What is the problem with waiting? Obviously there is some issue and of course they must be resolving it.
•  » » 2 months ago, # ^ |   +4 Yeah, well y'all should stop making noise now that rating update is out
•  » » » 2 months ago, # ^ |   0 the rating is out?
 » 2 months ago, # |   0 is the rating out?? can anyone confirm?
•  » » 2 months ago, # ^ |   0 yes
•  » » » 2 months ago, # ^ |   0 bruh my rating increased to 757 from 750
•  » » » » 2 months ago, # ^ |   0 see properly it decreased
»
3 weeks ago, # |
0

# Problem C

## Greedy Approach:

We check every corresponding indexes of both the strings; Since we have to travel all B's therefore, whenever the same index characters are BB we switch the row => since if proceed ahead without traveling the B in the other row and move ahead, then we won't be able to come back to the other B. Now when the two chars are BW => then we must be on the first or else we can't paint and then our requirement for B in the next row is a must have on first row. Similarly with WB we must be on second row and we must be able to move ahead on the following second row. If on doing all this we reach last B then we can paint in reqd limits.

Code

## DFS Approach:

First, compute the number of Black cells in the given matrix. Then, if under given constraints we are able to count all black cells then answer will YES else NO. We will try to implement painting from left to right. So to implement traversing with given constraints, we will use visited matrix and apply DFS accordingly. If on 0th row we look down and then right side neighbor, similarly if on 1st row we look up and then right side neighbor. Up and down movement first because we are moving L to R and when the up and down chars are same we must travel it or else we will move ahead and not come back.