Hello Codeforces!

On Dec/12/2022 17:35 (Moscow time) Educational Codeforces Round 139 (Rated for Div. 2) will start.

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

Best of Luck Everyone.

where ever i go,i see your comments

ScreenCast for A-D.

Thank you awoo for this educational Round. Can't wait to begin ! Good luck to all contestants!!!

Good luck broooo❤️

good luck brooo!! without take part this contest!!

Ladies and Gentlemen I hope you all will get positive delta.

Good luck!

orz

After such a difficult contest yesterday, I hope to get a positive delta today :)

Wishing good luck to everyone!

I am looking forward to the problems of this contest, hoping to surprise me.

After difficult contest yesterday, I hope to change color of nickname

I am sb.

DON_F do you want to participate?

THANKS awoo!

you have gained more contribution than me by using my meme.

Too relatable

sometimes less expectations give fruitful results.

This itself is an expectation

lol

surely

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?

read-the-problem-statement-carefully forces

Why using Sieve for D to generate list of primes of each number up to 10^7 TLE?

Send code? I got it through even with Rust:

Should be easy to translate to C++

184970170 here's mine using sieve get TLE, also probably because i use "not good" sieve

I think your problem is in IO... your sieve is fast enough (should be around 2-3 seconds), but iostream is slow.

sorry im new, what do you mean with iostream ? because endl?

Short Answer:

`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`

.`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)`

)thx i dont get TLE anymore ,but now i got WA ;)

Your code here... ~~~~~

~~~~~

The second for is better done like this:

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:

I think generating primes till root(10^7) is sufficient for the problem.

You dont need to generate prime numbers up to 10^7. Generating till sqrt(10^7) is sufficient.

why?

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

generatethe 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$$$.

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 ?

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.

Thank you, I learnt something new today — Sieve Factorization

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

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

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?

I ised linear sieve of erastothenes and it didn't led me to tle !

Enough of these prime number questions...

guys how did u fix wa16 in E??

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),

oh, I see. thanks!

Just before failing on WA16 my states:

I passed it with states:

States represent the order of relevant stacks. Some duplicates should be allowed as 3 could consume the first duplicate.

Can you explain your approach to E? Like how we are using these valid states.

Can someone please give a test case for which my code for B is failing?

https://codeforces.com/contest/1766/submission/184942949

try "aaaa"

It's giving YES as output. That's what it's supposed to give right?

"aaaab" should output "YES"

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

1 5 aaaab should give Yes

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)

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.

How did you factorized ? If you used seive, then I don't think it would have given you TLE!

Got TLE with seive.

$$$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)

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

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.

Spoiler184984459

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.

use sieve only for sqrt(1e7) and then factorize y — x by iterating all 447 primes in [2, sqrt(1e7)]

O(447n)

Did that.

I got TL with this solution. Can you show your code?

184943905

I did the same and also got TLE

I changed endl to '\n' and it worked.

I factorized $$$y - x$$$ and did not get TLE: 184943623

Note: 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)

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.

Need to save not min but any factor actually. This solution works faster than mine. Thanks for sharing it helped

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.

i got TLE i change endl to \n and add

no TLE anymore but WA ;)

before 184970170 after 184985603

please tell me there's a better solution for D aside factoring $$$|y - x|$$$. That was very painful.

I don't think so, but looking at your submission, it can be optimised by using a linear sieve instead.

I see, thanks. The observation was quite obvious, but getting my factoring to pass was very difficult.

How avoid WA16 in E?

Waiting for a reply to the same question! xd!!

One of my WA submissions fails on

5

1 2 3 2 1

Edit: Okay, your latest submission fails on this case too

what's answer for this case?

23

Thanks, I thought the maximum length of the list(without 0) can be 2 but it can be 3 also.

https://codeforces.com/blog/entry/109994?#comment-979536

Okay, i understood my mistake, thanks

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?

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:

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.

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.

ez solution:my comment no nested loops and only one if statement

only disadvantage: not understandable at all

how to solve problem C anybody ? any hints

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".

Think about the distance between each adjacent W's. And what happens when it is even or odd.

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.

Hint for D?

$$$\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.

Thanks, got it.

Hint 1$$$gcd(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.

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?

if any composite factor is the gcd then any of the prime divisors of that factor will also divide both numbers

184979418

My code for d keeps giving different output in sublime and different output when i submit it on cf

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.

what case

Even I couldn't figure other cases of infinite length while solving.

can someone pls explain how to solve e .

thanks in advance.

Am i the only one who wasted time by writing a stupid dp solution for C?

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.

Me, too, wasted some of my time by thinking in the direction of DP ;)

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.

lol i also did a dp solution haha new learning for me

Can someone help me out in c? code: 185047353

I 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.

Hint for D ?

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

WonderFull explanation dude

Can you please explain how you implemented the factorization part in your code?

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.

what will happen if i generate all prime till 10e7 and linearly calculate the list of primes of y-x?

why its giving tle ?

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.

Gotcha

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

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!

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."?

chiralcentre Here is some simple Python code for it:

Preparing the SieveFactorizing an integerThe 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.

Thank you for the reply! I understand better now haha

Problem A's harder version.

Digit dp?

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!

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...

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$$$).

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.

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

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$$$.

In problem $$$B$$$, am I the only one who thought that the number of operations may be less than (n-1) ? :(

nice contest

Can someone explain problem C ? I did a dfs + visited hashset but it kept giving me TLE. https://codeforces.com/contest/1766/submission/184980253

simulation

I think I did the simulation but it kept giving me TLE.

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

Thanks.... this makes sense. Thanks a ton

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.

huh , that's strange , I solved it using DFS :|

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.

Hints for B ,Please ?

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

HINTThink in terms of copying Contiguous Subsequnece of length 2 .

Problems were good , was a good contest

Speedforces :(

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.

`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. 184980206Here are video Solutions for A-D, in case someone is interested.

Do we get or lose points for hacking in this round?

Nope

Okay, thanks. But I notice my rank is still increasing, is it because of virtual particpants?

yes, due to virtual participants. Also, it could decrease if someone previously above you got solution hacked for some problem.

Nice E, hope to get to Master!

complete codepart of my code for 1766E

wish I've come up with this idea before the contest ended

Complete code ? Thank you, here's the meme for you.

Why would you paste code without a link ? Improve your manners

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.

can anyone tell me why my solution getting tle for problem d? https://codeforces.com/contest/1766/submission/184998801

thanks in advance.

Japan or2

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';

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} =9Thus in everyn-digithas 9 numbers havingintervalis10^n-1for each only one non-zero digitso the ans will be :

`9*(LenthOfTheNumber-1) + firstDigitOfTheNumber`

for example:

n = 201`length of n = 3`

`first digit of n = 2`

=> 9*(3-1) + 2

=> 18 + 2 = 20

Thanks for explanation!

`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-y$$$`so we will get prime factors of`

$$$x-y$$$`suppose that prime factors of x-y is`

$$$p_1, p_2, p_3,...,p_m$$$`if 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_i`

Mysumbission

1766A - Extremely Round

My submission -> 185002843

Can anyone please explain why I am getting

TLEon test case two of the following code?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.

But in this problem we have 3 second per test case. I have only one loop having O(n). It can pass easily!?

3 second for entire test case and for a single test t can be up to 10000.

The time limit is not 3 seconds per test case, but 3 seconds

per test.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?

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.

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 ?

probably because

`push_back`

is slowSame code as yours but with C++20 (185029658) gives MLE. I suspect yours is MLE too.

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

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){...}`

.I think we can go further from 47 but I don't know till when it will get better

For problem C: Hamiltonian Wall, I was getting the error. Can anyone point out where is the mistake?

Can someone explain solution of Problem E?

Thanks in Advance.

Can Anyone Explain Why my Solution For D Gave TLE:(

https://codeforces.com/problemset/submission/1766/184955390

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

also there's no need for push duplicated element to s1

Just replace endl with '\n' and your solution will pass.I faced the same issue

I solved problem D offline, but no body hacked me. 184948549

(◕︵◕) I will be +99 at this contest but road to expert still so far.

Man, just 1 more good contest to go. All the best!

Detailed Solution With Explanation Problem D

My D using neal Pollard's rho code from last contest.

https://codeforces.com/contest/1766/submission/184943158

Passes under 2.5 seconds

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.

Why is it rejudged twice?

When will the editorial be out?

When can l get the rattings why it shows that the contest is unrated in my constets

do you have any updates? when will the rating be out?

NO,and I'm waiting for the results for a long time .Maybe tomorrow the results will be out.

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.

OK,thanks for your reply.

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

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..

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

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.

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 185056871It'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.When will the results be out??

Release the updates :) :), I need to see my shiny new color

Same BrO :)

contest ratings are not updated yet. why?

Where is the editorial?

While you wait you can ask here about the problems or see what other people wrote above

Where is my new slightly bigger rating???

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?

It means the round is not rated YET, may not be a bug necessarily.

Change my color

So,what time does the rating change? qwq

How long will cyan have to wait to take over green?

Maybe this will be the first div2 contest which everyone got unrated lol

Educational Codeforces Round 121 (Rated for Div. 2) was unrated because of some technical issues during the contest.

was it announced? i didn't see any announcement regarding that

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 :(

Is the contest unrated?

:(

No updates till now....

When is the editorial?

behind you...

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

think about a substring of length 2

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.

+1

is it really unrated :(

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).where are the rating changes :(

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.

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.

Will we get the rating today? MikeMirzayanov, we, thousands of participants, are eagerly waiting for the rating change.

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? :/

When will the rating get updated? Is it unrated?

why the rating has not been updated?

when will the ratings be out??

it's my first contest ㅠ_ㅠ wanna get my rating..,,

Why is the rating not updated?

Is it was not rated?

ratings vro

When will the rating get updated? I was going to get under zero rated for the first time :(

No ratings till now.

@Codeforces , atleast give update about rating changes

It is deadforces? No ratings updated yet

This has been the longest waiting time before ratings to be updated in almost 2 years.

I'm refreshing the page since yesterday :( ...plz release the ratings fast or atleast give an update

me too =D

DeadForces!

DeadForces!

Harshly true that awoo wants more comments to announce the rating!

source: deadforces

Deadforces!

when did rates will be updated?

why the rating changes are not being updated ?? its been 3 days since contest ..

Hey guys, it has been 3 days since the contest started. Why does it take so long :(?.

My rating!When can I get my rating!TAT

DeadForces! Where’s my rating…=_=

deadforces :(

Cyan be waiting for too long now.

What happened to your rating graph ?

Looks like a bug, I'm sure am not the only one.

To everyone writing deadforces Glitches happen sometimes. Starting to make fun of such a wonderful platform is not funny. Codeforces is <3

That's fine. But atleast they can inform about that.

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

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.

How do I prove that I have not cheated?

say mother promise!

what?

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.

Yeah, well y'all should stop making noise now that rating update is out

the rating is out?

is the rating out?? can anyone confirm?

yes

bruh my rating increased to 757 from 750

see properly it decreased

## 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.

Code