By awoo, history, 9 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 Roman Roms Glazov, 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!

Our friends at Harbour.Space also have a message for you:

Hey Codeforces!

A couple of weeks ago, we had the pleasure of hosting a webinar featuring Sergey Gordeichik, CIO of the Inception Institute of Artificial Intelligence and Director of the University’s Cybersecurity Programme.

In his talk, Sergey shared his expertise and insights on how AI is being used both positively and negatively during the COVID-19 global pandemic. He touched on topics such as the ethics of using this technology, and how it was implemented during each phase of the pandemic.

We know not everyone had the chance to tune in during the webinar, so we thought you’d be interested in having a look at the slide deck of his presentation.

You can check it out here.

If this was interesting for you, let us know in the comments, and we’ll do our best to try and provide more content like this. Keep an eye out for the final two talks in our webinar series — they might be of interest to you :)

Finally, don’t forget that this July, Sergey is teaching a course on the Cybersecurity of Cloud, Big Data, and AI. The course will be 100% online, so be sure to check it out on our website if you’re interested. Here’s the link.

That’s all from us!

Good luck in the round, and we’ll see you soon!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 ksun48 7 188
2 saketh 7 264
3 hank55663 7 320
4 kefaa2 6 109

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Hakiobo 70
2 napgod_pk 67:-12
3 Zaher 71:-21
5 BohdanPastuschak 62:-26

1115 successful hacks and 2003 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A neal 0:00
B neal 0:02
C ksun48 0:05
D BohdanPastuschak 0:05
E ksun48 0:15
F kort0n 0:51
G rainboy 0:25

UPD: Editorial is out

• +510

 » 9 months ago, # | ← Rev. 5 →   +14 Is something wrong ?? why there are no comments.
•  » » 9 months ago, # ^ |   -30 I hope there are no ugly geometry problems(like in Educational Round 87).BTW glhf xD
•  » » » 9 months ago, # ^ | ← Rev. 3 →   -57 is it rated for unrated??
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   -27 .
•  » » » 9 months ago, # ^ |   +1 read the comment in L's voice
•  » » 9 months ago, # ^ |   +41
•  » » 9 months ago, # ^ | ← Rev. 2 →   +11 Hey MikeMirzayanov, I have got TLE on D whereas i have used O(NlogN) Solution. When i resubmitted it after final standing it got accepted. Solution from contest — https://codeforces.com/contest/1366/submission/83442824 Solution After contest -https://codeforces.com/contest/1366/submission/83505708 They both are same solution.. Kindly look at the issue and try to resolve if possible
•  » » 9 months ago, # ^ |   0
•  » » » 9 months ago, # ^ |   +3 i understood everything..... keep posting Div2.D regularly
 » 9 months ago, # |   +3 Were are the meme squad ??
•  » » 9 months ago, # ^ |   +89 A sad meme :)
•  » » » 9 months ago, # ^ |   +6 This is suicidal.
•  » » » 9 months ago, # ^ |   +2 My D failed system tests duo to TLE, costs me 100+ rating points.
•  » » » » 9 months ago, # ^ |   0 Same here bro,my D also failed :( I feel that the max_test(TLE test) should be included in the pretests. I may be biased because my solution failed, but I think once something passes pretests and it is on the edge of time complexity ==> maybe something like around 1e9 operations whereas maybe only 5 * 1e8 operations are normally allowed... then when it passes pretests, it is very hard for a person to question that maybe the solution might TLE. (I mean how can a person say whether it passed because it was just under time limit , or actually it wasn't supposed to pass?)Therefore I think the max_test is a basic test which should be included. But yeah, maybe they intentionally left it out as it was an Educational Round.
•  » » » » » 9 months ago, # ^ |   0 We both could be master if not failed D!!!
 » 9 months ago, # | ← Rev. 2 →   -27 I enjoy Codeforces comment section more than Facebook. But what's happened today!! Almost 3 hours past and only 2 comments.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +3 I think the announcement was not there on the Home page earlier.
 » 9 months ago, # |   -50 Though I enjoy everytime.. Here are the meme squad bro :v
•  » » 9 months ago, # ^ |   0 everytime everywhere
 » 9 months ago, # | ← Rev. 2 →   +4 Hey sorry for asking if this is discussed before but how come all the Educational Rounds are made by the same authors awoo, vovuh, adedalic, BledDest, Roms, Neon. PS: I love their contests it's just I'm pleasantly surprised.
•  » » 9 months ago, # ^ | ← Rev. 6 →   -64 I quit .
•  » » » 9 months ago, # ^ |   +8 I really worship awoo. I am just trying to know why they make all Educational Rounds
•  » » » » 9 months ago, # ^ |   0 Can you tell what's the difference between educational div-2 round and regular div-2 round on codeforces. I'm new in codeforces.
•  » » 9 months ago, # ^ |   +40 I'm guessing Harbour.Space University signed a contract with Mike for publicity. As part of the contract, 2 contests per month must be held sporting the uni's name. Since this is a long term contract, Mike needed a reliable team of people to hold these (easier than finding a new team for each contest).
•  » » 9 months ago, # ^ |   +1 And one more thing they all are from same institution Saratov state U.
 » 9 months ago, # |   +147 Afraid of WrongAnswerOnTest2 :(
•  » » 9 months ago, # ^ |   0 Afraid of timelimited on 2 3 4 5 6 7 8 9 10.。。
 » 9 months ago, # |   -29 I don't know but why I feel like this blog and the round are feeling bored. Weird!
•  » » 9 months ago, # ^ |   +9 It had only been 50 minutes since the blog was made public. Wait for few hours, I know my true redditers won't let you feel bored
•  » » » 9 months ago, # ^ |   +9 I am not bored. I said if the blog and the round were a person then they seem bored. XD
 » 9 months ago, # |   -78 Coding is Love ♥ Contest is the best option to judge yourself.. Thanks authors for all efforts . ♥
 » 9 months ago, # |   -38 Waiting for testers' validation comment ;)
 » 9 months ago, # |   +298 Educational round exist:
•  » » 9 months ago, # ^ |   0 :) will be CodeGuy
 » 9 months ago, # |   +19 What do we say to Educational Div2 C? Not Today.
 » 9 months ago, # |   +50
 » 9 months ago, # |   +45
•  » » 9 months ago, # ^ |   +130 But every time the codeforces community writes a div2-only contest, somewhere in the world 3000 people with a rating of 2100+ are sad :)
•  » » » 9 months ago, # ^ |   0 ha ha ha
 » 9 months ago, # |   +33 why Ashishgup has so much contribution by making only 5 contest,while pikemike and other authors of educational round has very less contribution?although respect to authors of educational contest,They are really doing great great great job.
•  » » 9 months ago, # ^ |   +14 Because Asishgup got a huge amount of upvote in his blogs while posting about contests.
•  » » 9 months ago, # ^ |   +60 Because Ashishgup is Indian.
•  » » 9 months ago, # ^ |   0 Your text to link here... Have a look at this. Contribution is moreover dynamic and not static.
 » 9 months ago, # |   -25 I hope this one is gonna be great. GL everyone
 » 9 months ago, # |   -41 Hope no more TLE VERDICT
 » 9 months ago, # | ← Rev. 2 →   -26 GL everyone!
 » 9 months ago, # |   -31 I fear to comment anything on codeforces comment section because community just gives big dislike. Maybe this comment gets even more and this is the reason this is my last comment ever on codeforces.
•  » » 9 months ago, # ^ |   +7 It's interesting that people downvoted this comment, including me.
•  » » » 9 months ago, # ^ |   +2 Thank you for pointing out this interesting fact.
•  » » » » 9 months ago, # ^ |   +3 The fact that you found it interesting is interesting.
•  » » 9 months ago, # ^ | ← Rev. 3 →   -35 Deleted.
 » 9 months ago, # |   -29 It would be really surprising and strange if it didn't say "Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.".
 » 9 months ago, # |   +15 why are these rounds called educational?
•  » » 9 months ago, # ^ |   +41 because they promote some particular university every time
•  » » » 9 months ago, # ^ |   +3 Ah. So there is no actual difference between the normal contests?
•  » » » » 9 months ago, # ^ |   +13 unlike other contests, the problems you solve don't matter, solving E is the same as A, the difference between 2 participants with the same number of problems solved is the difference in submission times.
•  » » » » » 9 months ago, # ^ |   0 Thanks!
•  » » » » 9 months ago, # ^ |   +5 the difference is that in the official rank list, div 1 participants are also included although their rating remains unchanged.
•  » » » » » 9 months ago, # ^ |   +6 There should be some kind of tutorial that explains all this..
 » 9 months ago, # |   +21 hi i m new to Codeforces, Today will be my second contest but was just curious to ask why cant we register from 0 to 5 min before contest. Due to this i missed previous contest.
•  » » 9 months ago, # ^ |   0
 » 9 months ago, # |   -24 I know this comment will only get downvotes....But I will say it.. The contests by Ashishgup has another level of craze... The contributions of Ashishgup is evidence of the fact...
•  » » 9 months ago, # ^ |   +5 I think the contests were Ashishgup were great, but saying they are just on another level is too much. Today's contest was great too, I loved C today. And other problems were great too.
 » 9 months ago, # |   0 Get ready for a rating drop.
 » 9 months ago, # | ← Rev. 2 →   -45
 » 9 months ago, # | ← Rev. 2 →   +37 Wrong answer on test 2Wrong answer on test 2 Wrong answer on test 2Wrong answer on test 2
•  » » 9 months ago, # ^ |   +2
•  » » » 9 months ago, # ^ |   +5 Adequate profile picture for the situation
 » 9 months ago, # |   +14
•  » » 9 months ago, # ^ |   -15 This meme is previously posted by Nieb_Hasan_077 here
•  » » 9 months ago, # ^ |   0 Just so apt :P
•  » » 9 months ago, # ^ |   0 relatable !!
•  » » 9 months ago, # ^ |   0 So true :)
 » 9 months ago, # |   -41 PS: I miss you SupaHotFire
•  » » 9 months ago, # ^ |   +20 I'll comeback soon don't worry
 » 9 months ago, # |   -9 My first time ever participating in a code-forces competition. Good luck everyone, may you all fail your test cases like i will.
 » 9 months ago, # |   -32
 » 9 months ago, # | ← Rev. 2 →   -13 Educational Round Exist !
•  » » 9 months ago, # ^ |   +7 I can hear this meme.
•  » » 9 months ago, # ^ |   0 Educational = MultipleTestForces
 » 9 months ago, # |   -14 meme are too good i like it
 » 9 months ago, # |   +56
 » 9 months ago, # |   0 Hello. I am new to codeforces. When they say that the rules are the extended ICPC rules, does anybody know where these can be found. Also, are you allowed to use the internet for APIs and finding other information?
•  » » 9 months ago, # ^ |   0 Yes, just submit working solutions, then everthing will be fine. But do not talk to anybody while contest about the problems.
 » 9 months ago, # |   +171
•  » » 9 months ago, # ^ |   +1 lol it looks like it's actually more efficient. Pigeoncopter
 » 9 months ago, # | ← Rev. 2 →   -69 BledDest should seriously stop making A/B problems in these rounds, they are usually uninteresting, lengthy and their solution mostly just have 4-5 if-else statements. I mean no offence here, and I do enjoy solving your harder problems.
•  » » 9 months ago, # ^ |   +48 Any examples?
•  » » » 9 months ago, # ^ | ← Rev. 2 →   -43 .
•  » » » » 9 months ago, # ^ |   +67 Well, I can agree with the fact that ER87 A contains some cases, but the model solution for ER88 A contains zero if/else statements.
•  » » » » » 9 months ago, # ^ |   -19 Keep doing the good work having simple brute force questions as A and B are not interesting and doesn't add anything to the contest.
•  » » 9 months ago, # ^ |   +3 But there were almost no if-else and casework in today's A and B.
 » 9 months ago, # |   +33 Guys please stop posting shit tier memes just to increase your contribution.
 » 9 months ago, # |   +53 Increase in codeforces traffic.. kudos to the community
•  » » 9 months ago, # ^ |   0 which website?
 » 9 months ago, # |   +4 This is the first time when small statements are troubling me!! (Sed Lyf)
 » 9 months ago, # | ← Rev. 3 →   -23 Trying to understand the statement of problem B for fucking half an hour.. Still don't understand what does this line means ? " Calculate the number of indices k such that it is possible to choose the operations so that ak=1 in the end."
•  » » 9 months ago, # ^ |   -21 However, at the last moment I have passed by assumption
 » 9 months ago, # |   -11 The statement for B was confusing af!
 » 9 months ago, # |   +10 How to solve D?
•  » » 9 months ago, # ^ | ← Rev. 3 →   +9 test every prime factor (if the prime fac divides multiple times go mult all of them in p^n) and its reciprocal, one of them should always work if there is a solution. i'm not sure if you can do that for every single prime factor (and thus auto break the loop saving time) but i didnt want to take any chances. reason this works is because one number will have all the prime factors and one number will have none, if the 2nd is 100% coprime then when u add the second to first theres absolutely 0 chance of it being mod p, however its possible that its mod a different prime so thats why i tested every prime (it ran within the time constrants since primes under sqrt(10^7) was like 400 or something)
•  » » 9 months ago, # ^ |   +18 First observation is that d1 and d2 are co-prime (or else (d1, d2) would divide a). Second observation is that if (d1 + d2, a) = x then x divides a (obviously). So, there shoudln't be any divisor x of a such that x|d1 and x|d2. From here it's obvious how to solve: get number x2 = a / x1 so that (x1, x2)=1 and if there are no such solutions, then there is no solution
•  » » » 9 months ago, # ^ |   +4 Why d1 and d2 are or must be coprime?
•  » » » » 9 months ago, # ^ |   0 If they have a common factor, it will remain in (d1 + d2). Which will turn out to be a part of the gcd of (d1 + d2) with a. Hence the gcd will be greater than 1.
•  » » » » » 9 months ago, # ^ |   -8 Of course I believe it if you say so. But still, if d1 and d2 have a common factor, a has it, too? Why this?
•  » » » » 9 months ago, # ^ | ← Rev. 4 →   +15 If $gcd(d_1,d_2) = x$ then $d_1 + d_2 = x \cdot (d_1/x +d_2/x)$.Also, $x$ must divide $d_1$. Then, $d_1 = x\cdot y$ for some $y$. Therefore, $a = d_1 \cdot z = (x \cdot y) \cdot z = x \cdot(y \cdot z)$ for some $z$. Then, $x$ divides $a$.Finally, we have that $gcd(d_1+d_2,a)$ must be at least equal to $x$.
•  » » » » » 9 months ago, # ^ |   0 I understand, thanks!
•  » » » » » » 9 months ago, # ^ | ← Rev. 3 →   +2 There was a mistake, if $d_1$ divides $a$ and $d_2$ divides $a$ does not imply that $d_1 \cdot d_2$ divides $a$, but $lcm(d_1,d_2)$ divides $a$.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Hey, I implemented this approach but this is giving me TLE, Could you send me the link to your submission if you have solved it??My submission: https://codeforces.com/contest/1366/submission/83499523
•  » » » » 9 months ago, # ^ |   0 First of all, u can't do that while reading the numbers, because the complexity becomes O(n * sqrt(VAL_MAX)) which is quite big. So, you might think of precalculating something. That something is the smallest prime factor or every number <= VAL_MAX. This can be done with a sieve and the time complexity is very small. Check this out (https://codeforces.com/contest/1366/submission/83421836)
•  » » » » » 9 months ago, # ^ |   0 Thanks, that optimisation solved the problem :)
•  » » 9 months ago, # ^ | ← Rev. 2 →   +17 if ai have only 1 prime divisor, then -1if a[i]%2=0 then a[i]=2^k * x, so pair (x,2) alway trueif a[i]%2=1 then a[i]=p1^x1*p2^x2*.... which (pi
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 case of even is obvious, any idea/hint on proving the other case?
•  » » » » 9 months ago, # ^ | ← Rev. 4 →   +11 case of oddcall p1+p2=2^x*k of course because p1 and p2 oddso if gcd(ai,p1+p2) != 1 mean gcd(ai,2^x*k) != 1->gcd(ai,k) != 1 because gcd(ai,2^x)=1(*) we have p1 < k < p2 and gcd(k,p1) = 1 because p1+p2 % p1 != 0 (similar with p1)to have gcd(ai,k) != 1 so k must be a prime or product of some prime whicH ai divisor. It is impossible case k is a prime: p1 and p2 are two smallest prime that ai divisor so there isn't any prime between p1 and p2 case k is product of some prime: because k
•  » » 9 months ago, # ^ |   +35 Using seive you can find the spf(smallest prime factor) array for all numbers till 10^7.Then to query a number num, divide num by spf[num] till num isn't divisible by spf[num].if num==1 answer doesn't exist, otherwise answer is (spf[num], num)
•  » » » 9 months ago, # ^ |   0 Can you prove this approach?
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   +1 Yea, So the trick which i used is to basically find 2 coprime numbers d1 and d2 such that both are divisible by the number and the product of both is the number.If d1 and d2 are not coprime, they will have a common divisor which will also be divisible aiThere may be many ways to find such 2 numbers d1 and d2, I just used one of them
•  » » » » » 9 months ago, # ^ |   +7 Will any 2 co-prime numbers work? I think not. If A[i]=30, gcd(2+3,30)!=1. So they must be some particular coprime. I intend to know the thought process behind it.
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 I missed d1 and d2 need to multiply to the number in my reply. I didn't try to prove this mathematically but with intuition this came out to be true for every numberEdit: So consider 4 prime numbers a,b,c,d (with relevant powers) with a as spf.For a+b*c*d to be divisible by the number ai, a+b*c*d needs to be divisible by either a,b,c,d but you can clearly see this isn't possible since none of these 4 numbers can be taken common from the sum. So ai can never be divisible by it.
•  » » » » » » » 9 months ago, # ^ |   0 But, then if I take d1 and d2 as 2 distinct primes then still they can't take a common factor out of these. Like for 30, I've 2, 3 which don't have any common factor among themselves but even then their sum=5 have the common factor which divides 30. Can I get the reason why this doesn't happen when we take all primes with relevant powers?
•  » » » » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 Ok, I got the reason that 5 is another prime factor of 30 which still divides the sum of d1 and d2. So, I need to take all the factors into consideration for d1 and d2 and not leave any, this is to ensure that d1+d2 doesn't have any prime common with a, and that can only be done if I cover all the primes by d1 and d2.
•  » » » » » » 9 months ago, # ^ | ← Rev. 4 →   +6 Actually it can be proved like this:Let, x = A[i].Addition of 2 no.s be say z. Now possible gcds of x & z are multiples of one of the prime factors of x. Without any loss of generality, lets say multiple is 1, and gcd be 'p'.Sum of 2 no.s is divisible by primes which are present in both summands. If one of the two does not have 'p', then 'p' can't be a divisor of their addition. But since we are using spf and the rest of the product, we ensure all primes are present in either of the 2, still no prime lies in both summands. Hence the proof follows.
•  » » » » » » » 9 months ago, # ^ |   +1 Spf may work I don't know the proof for it, but two summands being greater than p and not divisible p can also result in gcd being p. Consider case of 3&5
•  » » » » » » » » 9 months ago, # ^ |   0 Thanks, I have updated my proof.
•  » » » » » » » 9 months ago, # ^ |   0 Nice proof , Made my day buddy!
•  » » » » » » » 9 months ago, # ^ |   +1 "Sum of 2 no.s is only divisible by primes which are present in both summands." This statement seems wrong. Take case of 2 and 3. Their sum is 5 which is a new prime and sum is divisible by it and not by primes of summands.
•  » » » » 9 months ago, # ^ |   +18 See Here how I am able to understand the approach. Suppose a=(p1^x1)*(p2^x2)*(p3^x3)*...(pn*xn) where p1,p2..pn are primes. Now let's take spf=p1 so after dividing we are left with x=(p2^x2)*(p3^x3)*...(pn*xn).Now x+spf=p1+(p2^x2)*(p3^x3)*...(pn*xn).So you can see there is no common factor between x+spf and a.Hence they are coprimes and x+spf cannot divide a.
•  » » » » » 9 months ago, # ^ |   0 But the question is why is it necessary that gcd ( (p1^x1)*(p2^x2)*(p3^x3)*...(pn*xn) , p1+(p2^x2)*(p3^x3)*...(pn*xn)) = 1. Am I missing any trivial proof?
•  » » » » » » 9 months ago, # ^ |   0 See my comment.
•  » » » » 9 months ago, # ^ |   +32 This approach is really nice, in contest I was just fooling around with stupid half witted solutions.See If $a_i$ is prime or primes power then it is obvious that the answer is not possible. Lets consider the case where $a_i = \prod_{j=1}^{m}p_j^{k_j}$ and where $m > 1$ and let $p_1$ be smallest prime (which we can easily get using classic sieve). So in this case sharath101 argues that we can use the pair $(d_1, d_2)$ as $(p_1, \prod_{j=2}^{m}p_j^{k_j})$. Indeed $d_1+d_2 = p_1 + \prod_{j=2}^{m}p_j^{k_j}$ is not divisible by any $p_j$ for $j \in [1, m]$ and as a direct consequence $\text{gcd}(d_1 + d_2, a_i) = 1$ $\blacksquare$
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   +16 Yes this the proof because (a+b)%c = (a%c + b%c)%c. If we take (d1+d2)%pi then it is always non zero as in case of p1 first modulo is zero but rest can't be zero as none of the rest pi's are divisible by p1. If we take any other pi then second modulo is zero but first is p1(it's smallest). And d1+d2 can't have anything common with A because we already checked above with all factors of A and none of them divides d1+d2. Sorry for bad formatting I'm typing on phone
•  » » » » » 9 months ago, # ^ |   0 I understand that d_1 + d_2 with this split is not divisible by any p_j. However, why does d_2 need to be the remaining portion? Like why can't we have d_1 = p_1 and d_2 = p_2^k_2 * p_3^k_3 or even d_2 = p_2 * p_3 * ... * p_n? Also, is every number which has at least two distinct primes in its prime factorization valid since we can make the split you mentioned?
•  » » » » » » 9 months ago, # ^ |   0 $d_2$ doesn't need to be remaining portion, its just that his answer is very easy to construct as we directly get smallest prime factor using sieve. And not all divisions into two sets will be valid, the prime factors sets $d_1$ and $d_2$ should not share any prime factor and both together should contain all primes of $a_i$ and only then we can be sure.
•  » » » 9 months ago, # ^ |   0 Bro help me plz in DLet we have N ,Now unique prime factorisation of N = p ,q ,r ,sNow how can we claim that gcd((p + (q*r*s---)) , N ) = 1 , can u please explainFor ex : N = 210then unique prime factors = 2 3 5 7then how gcd((2+(3*5*7)) , 210 ) = gcd(107 , 210 ) = 1 ?
•  » » » » 9 months ago, # ^ |   +3 So consider 4 prime numbers a,b,c,d (with relevant powers) with a as spf.For N to be divisible by a+b*c*d, a+b*c*d needs to be divisible by either a,b,c or d but you can clearly see this isn't possible since none of these 4 numbers can be taken common from the sum. So N can never be divisible by it.
•  » » 9 months ago, # ^ | ← Rev. 2 →   -19 .
•  » » » 9 months ago, # ^ |   +17 Negative: $30 = 2 \cdot 3 \cdot 5$, but $a_1 = 2$ and $a_2 = 3$ are a wrong answer, since $2 + 3 = 5$.
•  » » 9 months ago, # ^ |   +1 A simple solution I came up with was as follows: Consider all primes $p_1, p_2, ..., p_k$ which divide $n$, with $k \ge 2$. Then we consider $a = p_1 + p_2 p_3 ... p_k$. Suppose $gcd(a, n) > 1$. Then at least one prime which divides $n$ also divides $a$, however this is a contradiction (fun fact: note that the same argument can be used in a proof of the infinitude of primes). Now if $k < 2$, note that there is no solution.To implement this, we can do the following: using the sieve of Eratosthenes, find the product of all primes which divide $n$, and call it $f[n]$. Also keep storing the smallest prime divisor of $n$, say $g[n]$, then your answer will be $(g[n], f[n]/g[n])$ if it exists.
•  » » 9 months ago, # ^ |   0 It is clear that gcd(d1, d2) = 1 otherwise gcd(d1+d2, a) !=1 Let p be the smallest prime which divides a. Then, a = XY where Y is the largest number such that Y%p !=0 If Y=1: we are sure that there can't be 2 divisiors>1 such that gcd(d1+d2, a)=1 So in this case answer is (-1, -1) Now we will prove with (d1, d2) = (X, Y) we are done. Proof: Note the following 2 identities 1. gcd(a,b) = gcd(a,a+b) 2. if gcd(a,b)=1 and gcd(a,c) = 1 then gcd(a,bc)= 1 Now note that gcd(X,Y) = 1 This implies gcd(X+Y, X) = gcd(X+Y, Y) = 1 By (2) It is clear that gcd(X+Y, XY) = gcd(X+Y, a). Hence, find p, then find Y by dividing a_i by p until you get a_i%p!=0. X = a_i/ Y If Y = 1 your answer is (- 1, -1) else (X,Y)
•  » » 9 months ago, # ^ | ← Rev. 2 →   +2 Simple ApproachFor an $even$ number, answer will be $($ $2$, Product of remaining odd prime factors $)$For an $odd$ number, answer will be $($ $1st$ Smallest prime factor, $2nd$ Smallest Prime factor $)$And obviously, first, you need to check whether alteast $2$ distinct prime factors for a number exists or not. if not answer will be $($ $-1$, $-1$ $)$ProofFor an $odd$ number, Consider an example $ai$ = $105$ $( 3 * 5 * 7 )$. Ans is $(3, 5)$.$3$ is $1st$ smallest prime factor and $5$ is $2nd$ smallest prime factor of $105$.Let $x = d1 + d2 = 3 + 5 = 8$.$g = gcd(x, 105)$ and obviously $g$ can't be $3$ or $5$. So $g$ should be greater than $5$, which is not possible. (why? Let $x' = g * e$ , $e$ is even number, $e$ must be aleast $2$. You can see $x' > x$ if $g > 5$, which is not possible.So $g$ has to be $1$.For an $even$ number, Consider an example $ai$ = $210$ $( 2 * 3 * 5 * 7 )$. Ans is $(2, 105)$.$105 = 3 * 5 * 7$ (Product of remaining odd prime factors).You can see $d1 = 2$ and $d2 = 105$, now forget about $d1$ and ask a question from yourself. What is the minimum $y$, I should add to $d2$ such that $g = gcd(d2 + y, ai) > 1$. And you will find you need to add smallest prime odd factor, for this case it is $3$ but we are adding just $2$ ($d1 = 2$, hence the answer).
 » 9 months ago, # |   +8 How to solve Question D? Couldn't come up with a strategy.
•  » » 9 months ago, # ^ |   -10 83434115 Consider the cases where the number x is odd or even.If x is even: 1. If x is a power of 2, then no solution exists 2. Otherwise, there exists some odd factor k > 1 and gcd(2+k, x) = 1 If x is odd: Check for every factor k < sqrt(x) if gcd(x/k + k, x) = 1 Motivation: If x/k and k are coprime, then they would be the solution Otherwise, no solution exists
•  » » » 9 months ago, # ^ |   +38 This should give TLE, time for hacking :p, I am sorry dude.
•  » » » » 9 months ago, # ^ |   +8 jesus ur brutal
•  » » 9 months ago, # ^ |   -6 https://codeforces.com/contest/1366/submission/83472749 we just need to find 2 factor which are coprime to each other
•  » » » 9 months ago, # ^ |   0 Let's say we have a number 70 --> 2 * 5 * 7, now according to you we can select d1 = 2 and d2 = 5 as they are co-prime but d1 + d2 = 7 i.e, not co-prime with 70 (gcd(7, 70) = 7)? If you meant something else.. please explain again if possible..? Thanks..
•  » » » » 9 months ago, # ^ |   0 such that d1*d2=a[i]
 » 9 months ago, # |   +6 Did anyone get WA4 in D because the value of mod < 10^9 ?
•  » » 9 months ago, # ^ |   0 I initialized the min as I always do with MOD. And yup, WA4.
 » 9 months ago, # |   0 How to solve F? I figured out that the walk will always be a path (without repeated edges) except at the last edge. So I computed $dp[len][v] = \text{maximum weight ending at v of walk length len}$, for up to $len = 2*n$. for $q >= 2*n$, the weight will increase by a constant term. Got WA on test 12 ? What am I doing wrong?
•  » » 9 months ago, # ^ |   +29 increases by different constants in O(n) ranges. its not same constant always.
•  » » » 9 months ago, # ^ |   0 Does it uses idea of convex hull ?
•  » » » » 9 months ago, # ^ |   +19 Yup
•  » » » 9 months ago, # ^ |   0 Is there no upper bound for the length of path after which we start taking the same edge?
•  » » » » 9 months ago, # ^ |   0 It should be m, by the pidgenhole principle. After m moves, assuming you've seen every edge once, it would be at least (if not more) optimal to have kept going back and forth once you reached the edge with maximum weight.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +14 This might give you the idea where it fails : Input : 4 3 10000000001 2 12 3 1000001 4 99999Here you will be getting maximum answer by repeating the edge 99999. But there comes a time when 100000 will dominate.
•  » » » 9 months ago, # ^ |   0 Can you please tell what should be the output for this input?
•  » » » » 9 months ago, # ^ |   +8 My AC solution gives 2649959.
•  » » 9 months ago, # ^ | ← Rev. 3 →   +22 Let $f[u][k]$ denote the maximum weight path ending at $u$ using exactly $k$ edges. You can compute it for all $1 \leq k \leq m$ via $\mathcal O(nm)$ DP. Consider a long path using $x > m$ edges. It will always arrive at some node $u$ using some $k$ edges and repeatedly traverse the maximum weight edge adjacent to $u$ (let's call it $\text{max}_u$) the rest $x-k$ times. So the answer for $x$ is the maximum of $f[u][k] + (x-k)\text{max}_u = \text{max}_u x + f[u][k]- \text{max}_uk$ over all $1\leq u\leq n$ and $1\leq k \leq m$. Interpret this quantity as a line $y=mx+c$ and compute the lower hull for all of $\mathcal O(n)$ such lines. Now each line can give you the maximum answer for some range $[l,r]$ of values $x$. You can use binary search to find this range and add the contribution using some standard formula.
•  » » » 9 months ago, # ^ |   0 It will always arrive at some node u using some k edges and repeatedly traverse the maximum weight edge adjacent to u (let's call it maxu) the rest x−k times.Why so? I don't really get the intuition behind it.
•  » » » » 9 months ago, # ^ |   0 Suppose we have some path, the maximum weight of an edge is $w$, but in the end, we traverse some other edge having weight less than $w$. Since $w$ is the maximum weight in our path, we can replace the suffix starting with its first occurence with repeated traversal of this edge, and the total weight becomes greater.
•  » » » » » 9 months ago, # ^ |   0 Yeah, I thought this, but what if you still haven't visited the maximum weight edge? You can visit it and then repeat that edge from thereafter. Can't you?
•  » » » » » » 9 months ago, # ^ |   0 This path is handled by dynamic programming — basically, for every possible vertex and every possible number of steps it computes the maximum weight of path to this vertex in exactly that number of steps. That way, we can consider each vertex as the one where we start walking along the maximum edge.
•  » » » » » » » 9 months ago, # ^ |   0 What I am asking is why is it sufficient to only consider m steps and then repeat the last edge? What if, let's say m = 2000, for answer for 1000000000, I start repeating the last edge after 3548 steps, will this always be unoptimal or always considered if we take only m steps? If so, why?
•  » » » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +10 If the length of the path is greater than $n$, then it is not simple — it contains a cycle. Since the last edge is the maximum one, we can delete the whole cycle, since the average weight on it is not greater than the weight of the last edge.
•  » » 9 months ago, # ^ | ← Rev. 3 →   +3 Here's my AC 83474415 submission. First part handles case $k \le n$ (dp) second part handles $n+1 \le k \le q$ (convex hull of $mx_i * (k-n) + dp_i$). Complexity is $O(n*m + n*n) = O(n*m)$ (you could probably solve second part in $O(n*log(n))$).
 » 9 months ago, # |   0 Is D a tricky problem? I couldn't find a way to solve it
•  » » 9 months ago, # ^ |   +1 In my point of view, it's a straightforward application of prime factorization.
 » 9 months ago, # |   0 Video Tutorial for B : https://www.youtube.com/watch?v=kuO_Cfe_i-Y
 » 9 months ago, # |   +9 god damn it I knew C solution after one minute from reading but couldn't code it without mistakes
•  » » 9 months ago, # ^ |   0 Could you please explain your approach?
•  » » » 9 months ago, # ^ |   +3 You have to first notice that if you take a path starting from (1,1) and (N,M) simultaneously, then all the cells on the i-th step must have the same value. This is true since we want our paths to create a palindromic string.Now, we can run a bfs and store the number of cells with value of zero and one on each step.For each step the cost to make every path palindromic is the minimum between the number of cells with value of one(1) on the i-th step and the cells with value of zero(0) on the i-th step.Note: When saying "step" I mean the depth of the bfs search.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 I did the same using dp[i][0] for storing number of 0's till i length form (1,1) Similarly dp[i][1] , and kept getting WA on 1st test itself and lost midway :( Did you mean that the last part has to be done for the complete string or till mid of the string
•  » » » » » 9 months ago, # ^ |   0 Till the mid of the string!In order to stop at the right moment I had a variable that stored the expected number of cells at the i-th step. If the number of zeros and ones at the i-th step did not match that number, then the loop would stop and output the solution.
•  » » » » 9 months ago, # ^ | ← Rev. 6 →   0 I tried to check all diagonals. Is there something wrong with this approach ?1 0 1 1 1 1 10 0 0 0 0 0 01 1 1 1 1 0 1first I check (1,1) and (n,m) then [(1,2),(2,1)] & [(n-1,m),(n,m-1)] and so on always updating my answer as ans+=min(total zeros,total ones)Idk why I always failed at test case 2 ?
•  » » » » » 9 months ago, # ^ |   0 I did the same approach and it worked, you can check out my submission.
•  » » » 9 months ago, # ^ | ← Rev. 5 →   +21 each line from both sides(that has the same color) should be the same so we count how many ones and zeros from each two lines and get the minimum from both and add it to the final answer except the line in the middle we don't need to change it I just couldn't code it with for loops it was hard I should've tried recursive way
•  » » » » 9 months ago, # ^ |   +3 This may be useful for youhttps://codeforces.com/contest/1366/submission/83428525
•  » » » » » 9 months ago, # ^ |   +3 you made me feel more stupid XD
•  » » » » 9 months ago, # ^ |   0 That is basically what I did but implemented it using bfs rather than loops, since, as you said, it would be difficult to code.
•  » » » 9 months ago, # ^ |   0 Take a square, calculate its distance from (1,1) , (n,m) , say d1 and d2. Now use d = min(d1,d2). Put all squares with distance 'd' in array[d]. Do this for d from 0 to (n+m)/2. Then for each array[i], calculate how many elements you need to swap so that all the elements are same. Answer will be sum of swaps for all arrays.
•  » » » 9 months ago, # ^ |   0 observation : pair of cells at the same distance from 1,1 and n,m must have same no.now we just need to implement it and the best way is https://codeforces.com/contest/1366/submission/83470989 (the code is very small so i guess there is no need to explain the implimentation)
•  » » 9 months ago, # ^ |   0 Just in case you require a clean implementation of C, ignore otherwise CODE#include using namespace std; int n,m;bool a[32][32]; void solve(){ cin >> n >> m ; map o,z ; for(int i=0;i> a[i][j] ; o[i+j]+=(a[i][j]); z[i+j]+=(!a[i][j]); } } int ans=0 ; for(int l=0,r=m+n-2;l> t ;while(t--)solve() ; return 0; } 
•  » » » 9 months ago, # ^ |   0 very nice algo ! thanks...
 » 9 months ago, # |   -11 Feeling great. For the first time solved 5 problems in div2 contest. Thanks awoo. Hoping that my solution would pass the system test.
•  » » 9 months ago, # ^ |   0 Oh got hacked in E. Bad luck.
 » 9 months ago, # |   +5 What was in Test case 17 for F? :(
•  » » 9 months ago, # ^ |   +86 puts("2000 1999 1000000000"); forn(i, 999) printf("%d %d %d\n", i + 1, i + 2, 999999); puts("1 1001 1"); forn(i, 998) printf("%d %d %d\n", i + 1001, i + 1002, 1); puts("1999 2000 1000000"); 
 » 9 months ago, # | ← Rev. 2 →   0 What's wrong with this code. Problem B : Your text to link here...
•  » » » 9 months ago, # ^ |   0 Alright so I believe you got the algo wrong, the idea is to find the largest segment of numbers possible, by unioning segments that have an intersection with the current segment (initially the current segment is of size 1, and has value = [x, x]). Here order matters, you can't find the largest union with cur across all the segments [l, r] that they give, you'll have to find the largest union in the order of input. Have a look at my submission for more clarity: Link .
•  » » » » 9 months ago, # ^ |   0 Somebody replied that I am getting wrong if there are no pair[l,r] contain x then the answer is 1, but in your code it's 0 and I did it now and got accepted. I did it during the contest but I have to change the ans with " Max — Min + 1 ". Thank you for reply
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 83464368 — Check this out. Edited your submission a little.Just keep track of range where we can convert a[i] to 1.
•  » » » » 9 months ago, # ^ |   0 I solved it other way but getting wrong on the above code. Thanks for the reply
•  » » 9 months ago, # ^ |   0 if there are no pair[l,r] contain x then the answer is 1, but in your code it's 0
•  » » » 9 months ago, # ^ |   0 Thank you
•  » » 9 months ago, # ^ |   0 15 1 13 4For this case ans should be 1. Your code returns 0...
•  » » » 9 months ago, # ^ |   0 Yeah, I got it. Thank you
•  » » 9 months ago, # ^ |   0 check my submission, it might help here
•  » » 9 months ago, # ^ |   0 Initialise L = x, R = x. Iterate through segments in line. If there is overlap between [l,r],[a,b] update the [l,r] segment to their union.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Initialise x to 1 and in the last if condition replace r-l+1 by r-l..this works fine
•  » » » 9 months ago, # ^ |   0 You can calculate answer in the end as $Ans = R-L+1$
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 But what if that condition is never met : Example : x=1 , l= 2 , r=4 ,m=1,n=5 epsilon_573
•  » » » » » 9 months ago, # ^ |   0 Answer will be 1. Because only x=1 can be 1.
•  » » » » » » 9 months ago, # ^ |   0 I think you should say Ans = max -min +1 instead of r-l+1 just a bit of confusion over there . Hola !!
 » 9 months ago, # |   0 what is the 2nd test case for D? please tell
•  » » 9 months ago, # ^ |   0 maybe A[i] = 156 for some i in array A.
•  » » 9 months ago, # ^ |   +1 i think A[i] = 7817670
•  » » 9 months ago, # ^ |   0 210 is also a good case, expected -1, -1.
•  » » » 9 months ago, # ^ |   +1 Why -1 -1? Why not 2 105?
 » 9 months ago, # |   0 I feel I was/am so close to solving E ... can someone take a look ? 83459283
 » 9 months ago, # |   0 That C. I first implemented a solution to traverse through all diagonals and then realised it isn't the right strategy (because of test case 1, part 2). I should look at the test cases carefully before implementing some crap smh. C turned out to be easier than I thought after making an observation (which you can see in my submission).D was tricky. I don't understand (yet) why my solution fails (also, it's brute force maybe? so it'd TLE anyway). Maybe I need to look through some probable bugs in my code... Any ideas about D? I think I've seen a problem similar to F before but never solved. Any ideas on it too would be good. Thanks. I found the problems really interesting.
•  » » 9 months ago, # ^ |   0 Can you tell about C? I couldnt come up with any idea
•  » » » 9 months ago, # ^ |   0 if you move k steps from (1,1) ,then all the cell (i,j) at k steps will have same value of S = i+j.The value of S will change from 2 (for (1,1) ) to n+m (for (n,m)) and its incremented by 1.(just draw some example on paper). Now store all the value 0s and 1s at s = i+j in cnt array. use two pointer left , right and find minimum changes required so that left and right have same values.then increment left and decrement right.Your text to link here...
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 What observation did you make in C ?? after first reading I thought I had to convert all the strings into a palindrome (if they are not obviously),Moreover the test cases created more confusion.I still can't get the question clearly :( My bad
•  » » » 9 months ago, # ^ |   0 Observe that if you start your journey from the cell (1, 1) and (n, m), the reachable cell after the i'th step have to contain the same number(either 1 or 0). So decide greedily which one will minimize your answer.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 Will our choice at length n-i of string would depend on our choice of i done earlier ?? (Will the value at cell(i,j) change )
•  » » » » » 9 months ago, # ^ |   0 I didn't get your query clearly. can you elaborate on it ?
•  » » » » » » 9 months ago, # ^ |   0 for example if the matrix is [[1,0,0] , [1,1,1] , [0,0,1]] the final matrix will be of which form ??
•  » » » » » » » 9 months ago, # ^ |   0 stunareeb_09 there can be two possible forms we can obtain. they are 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 with the cost of changing the cells (2, 1) and (2, 3) in the 1st possible form and the cells (1, 2) and (3, 2) in the 2nd possible form.
•  » » » » 9 months ago, # ^ |   0 What about the testcase 1 1 0 1 How do you handle cases like these where some paths after i'th step will be completely independent of each other ?
•  » » » » » 9 months ago, # ^ |   0 This is the case when the length of the path is odd. In this case you never have to change any value of the middle cell of the path since they are independent.
•  » » » 9 months ago, # ^ |   0 See that all squares that are equidistant from (1,1) and (n,m) need to equal.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 In test case 1, 3rd subtask we had 2 ones and 2 zeros (101,101,100,100) till 3rd position starting from (1,1) while also we had 2 zeros and 2 ones (101,101,100,100) at 3rd position starting from (n,m) then why the cell at (2,2) was changed to 1, Also in 1st test case 1 subtask this same scenario happened we had one zero and 1 one (10,11) till 2nd postion also we had the same strings from (n,m) till 2nd position then why there were no changes ? Please Correct me if missed something.
•  » » » 9 months ago, # ^ |   0 Working through all the strings will likely give TLE. I thought of it too but rejected it immediately. There are a total of (n + m - 2)! / ((n - 1)! * (m - 1)!) strings, if I'm not wrong. Going through each of them, finding the cost of changing them to palindromes and making updates in each of them having some path common to the currently being parsed string will take a lot of time. It's hard to implement too.My observation is basically this comment by SupaHotFire. You can calculate the cost of changing the i'th diagonal and (n + m - i)'th for all i in O(n + m) time.
•  » » 9 months ago, # ^ | ← Rev. 3 →   -6 Zeus_NoT_Zues In D, you have to observe that if number has only one distinct prime factor than the answer is (-1,-1), otherwise, the number has at least 2 distinct prime factors. If the number is even then it must have an even and an odd prime factor whose sum is an odd number and the result will be (2, any_other_prime_factor). If the number is odd then it's all prime factors ar odd and if you sum up any 2 of them then you will get an even number and the result will be (prime_factor1, prime_factor2).
•  » » » 9 months ago, # ^ |   +13 No gcd of two different parity is not always 1.Eg (6,15)=3
•  » » » » 9 months ago, # ^ |   0 Ops, My bad. Yes, You are right. But the main observation is that since the prime factors are relatively co-prime so the sum of them will be coprime to the number itself. Let's prove it by contradiction. Let the number we are considering be n and the prime factors are f1 and f2 and the gcd of them is g = gcd(f1, f2). So we can write f1 = g * a and f2 = g * b for some positive integers a and b. So f1 + f2 = ga + gb = g(a + b). Since n % f1 == 0 and n % f2 == 0, so n % g == 0. Observe that if g > 1 then f1 and f2 can't be the answer. Since f1 and f2 are coprime so g must be equal to 1. Hence the sum f1 + f2 will be coprime to n.
•  » » » » » 9 months ago, # ^ |   +1 30 = 2*3*5 gcd(2+3,30)!=1
•  » » » » » 9 months ago, # ^ |   0 No, it's not. Suppose n=30, and its prime factors are 2,3 and 5. So sum of 2 and 3 isn't coprime to 30.
•  » » » » » » 9 months ago, # ^ | ← Rev. 3 →   0 Sorry for my poor observation :(. The answer should be (factor1, n/factor1^k). I will come up with the proof later.
•  » » 9 months ago, # ^ |   0 I tried to check all diagonals. Is there something wrong with this approach ?1 0 1 1 1 1 10 0 0 0 0 0 01 1 1 1 1 0 1first I check (1,1) and (n,m) then [(1,2),(2,1)] & [(n-1,m),(n,m-1)] and so on always updating my answer as ans+=min(total zeros,total ones)Idk why I always failed at test case 2 ?
•  » » 9 months ago, # ^ | ← Rev. 3 →   +3 Let the prime factors of a = p1^x * p2^y * ..* pm^z. Take d1 = p1 and d2 = a/p1^x Since both d1 and d2 have no prime factors in common, their sum d1 + d2 has no prime factors in common with a which gives gcd(d1 + d2, a) = 1.Obviously the answer is -1 if any of d1 == 1 || d2 == 1Code of this approach 83482353
•  » » » 9 months ago, # ^ |   0 How to prove that: if d1 and d2 are two coprime factors of a number n, then: s = (d1+d2) is also coprime with n?
•  » » » » 9 months ago, # ^ |   0 If two numbers are co-prime, their sum is coprime to each of the summands LinkThus d1 + d2 has no factors in common with d1 and d2, which implies it has no factors in common with d1 * d2 = n. Thus gcd(d1 + d2, n) = 1
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0 I found a couple of proofs for this in the comments. Here's one: https://codeforces.com/blog/entry/78633?#comment-639993
 » 9 months ago, # |   +8 How to solve G? I couldn't optimize my DP from n^3 to n^2.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +33 Let $f[i][j]$ denote the minimum answer for suffix $s_i$ and $t_j$. If $s_i=t_j$ you can update with $f[i + 1][j + 1]$. Otherwise you have to match $t_j$ with some $k > i$ with $s_k = t_j$ and clean up the stuff between $s_i$ and $s_{k-1}$. Notice that before reaching $s_k$ the character labels don't matter: it's either append a character or delete one. So you essentially have a bracket sequence and you should delete some of the positions to turn it into a correct bracket sequence. Now you can either delete the current character and update by $1 + f[i + 1][j]$, or, you can skip the first balanced portion starting at $s_i$ and update by $f[\text{to}_i + 1][j]$ where $\text{to}_i$ is the right end of the balanced bracket sequence starting at $s_i$. You can precompute $\text{to}_i$ in $\mathcal O(|s|^2)$ and run the DP in $\mathcal O\left(|s||t|\right)$.
•  » » » 9 months ago, # ^ |   0 Addition: $\mathrm{to}_i$ can be found in $\mathcal{O}(|s|)$. Maintain the bracket positions in a stack. (83439327)
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 That assumes that if we don't delete a character or match if some character of t, we'll preserve the bracket sequence starting at that charactet. Why would we always preserve it?
 » 9 months ago, # |   0 When is editorial coming?
•  » » 9 months ago, # ^ |   0 When hacking phase will end.
 » 9 months ago, # |   +32 It took me 47 minutes for A and 6 minutes for B.Life's weird
•  » » 9 months ago, # ^ |   +8 I solved B, C, E and didn't solve A. Life's weird indeed.
•  » » » 9 months ago, # ^ |   +12 Update: Nope. My E got hacked. I guess I'm just stupid today.
•  » » » » 9 months ago, # ^ |   0 Mine too. Just one silly mistake.
 » 9 months ago, # |   -25 Solved A and B fastly in first attempt. After that just saw my rank getting worse and worse. Sed life.
 » 9 months ago, # |   0 Problems B and C were really nice. I didn't manage to solve D during the round, but it was also really nice. I just think that problem A was quite boring... Beside problem A, the contest was really nice!
 » 9 months ago, # | ← Rev. 2 →   0 Can anyone give me testcases where my Solution for B fails?Edit: Nvm got it.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +3 Just change the last line of your code to cout << "1" << endl and see the magic.Because at the end, a[x]=1 is always true. Feel sorry for you tho.Edit: ok
•  » » 9 months ago, # ^ |   0 Answer would be 1 at least. the starting position X
 » 9 months ago, # |   +28 200IQ play be Deathly_Hallows.
•  » » 9 months ago, # ^ |   0 koboshi hacked himself too
 » 9 months ago, # | ← Rev. 3 →   +26 Kind suggestion for the future contests — please be consistent with moduli (is that plural from modulus?) over multiple tasks — there's less gotcha when in every task we deal with the same number.
 » 9 months ago, # | ← Rev. 9 →   +6 Why is A- min((a+b)/3,min(a,b)).
•  » » 9 months ago, # ^ |   +2 after each move, total sum of a and b decreases by 3, so (a + b) / 3 will hold the answer, and min(a, b) because in case min(a, b) * 2 < max(a, b), the logic above wouldn't work, because in the best case you can decrease min(a, b) by min(a, b), case a = 18 b = 2 ans = 2
•  » » 9 months ago, # ^ |   +22 Case 1: If a >= 2 * b or b >= 2 * a, answer is clearly min(a, b). Case 2: Now, let's assume this is not the case. Now, every time we will choose 2 from the larger pile and 1 from the smaller pile. A time will arise when the larger pile will become smaller (else it's Case 1). We observe that after this time arise the difference between the 2 pile sizes is at most 1. So, when we are unable to make any other tool, the remaining items in the piles can be (0, 0), (0, 1), or (1, 1). So, we must have utilised all the remaining items.
 » 9 months ago, # |   +3 The description of B is really confusing and I was stuck at B for an hour. l_i≤c,d≤r_i this statement has two meanings: 1.l_i<=c and d<=r_i 2.l_i<=c<=r_i and l_i<=d<=r_i
 » 9 months ago, # |   +3 is the hacking just for fun and not rewarded with points?
•  » » 9 months ago, # ^ |   0 In Educational and div3,4 rounds, Yes !!
•  » » » 9 months ago, # ^ |   0 Bro help me plz in DLet we have N ,Now unique prime factorisation of N = p ,q ,r ,sNow how can we claim that gcd((p + (q*r*s---)) , N ) = 1 , can u please explainFor ex : N = 210 then unique prime factors = 2 3 5 7then how gcd((2+(3*5*7)) , 210 ) = gcd(107 , 210 ) = 1 ?
•  » » » » 9 months ago, # ^ |   0 This should help you, spf means smallest prime factor.
•  » » 9 months ago, # ^ |   0 Yes
•  » » 9 months ago, # ^ |   0 I you hack somebody which then falls behind you in ranking, you will raise one position. So just hack the ones right in front of you.
•  » » 9 months ago, # ^ |   0 Why so many hacks in D?
•  » » » 9 months ago, # ^ |   0 Because D is the new G
•  » » » 9 months ago, # ^ |   0 because they failed with this case:500000 9999991 9999991 9999991 ....
•  » » » 9 months ago, # ^ |   0 There was no pretest to eliminate solutions with complexity N(sqrtN) whereas required complexity was nlogn :
 » 9 months ago, # |   +21 Educational Rounds always feel like Div 1.5
•  » » 9 months ago, # ^ |   +1 can relate, i'm doing 3 problems in div2 and div3, but in this educational I sucked a lot
 » 9 months ago, # |   0 Is that course duration of the year 2019 or the year 2020?
 » 9 months ago, # |   0 Can anyone tell me what is wrong in my code for problem C?https://codeforces.com/contest/1366/submission/83448870
•  » » 9 months ago, # ^ |   0 I think your solution is failing for test cases where n>m. Let's say n=8 and m=2 then your solution might give Wrong answer.
•  » » » 9 months ago, # ^ |   0 I think you're right, thanks a lot!
 » 9 months ago, # | ← Rev. 2 →   0 One of the best contest till now! But I could not solve the errors in C on time.
 » 9 months ago, # |   +3 Will $O(n*\sqrt{a_i})$ solution for D pass?
•  » » 9 months ago, # ^ |   +3 Nope
•  » » 9 months ago, # ^ |   0 No, I tried.
•  » » » 9 months ago, # ^ |   0 Apparently my solutions passed all tests. :|
•  » » » » 9 months ago, # ^ |   +6 There are a lot of hacks in D ;)
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Your solution is $O(n^{5 / 3}\cdot\sqrt{a_{i}})$
•  » » » » 9 months ago, # ^ |   0 I just got hacked :/
•  » » » » » 9 months ago, # ^ |   +1 What would be the approach for D? I used sieve (pre-computation) for O(N log2 ai) solution, taking all possible pairs of prime factors, but it turns out that for numbers like 210 (mentioned below in a comment), it doesn't work. What would the right process be?
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   0 Shortest Prime Factor sieve gives the desired complexity right?
•  » » 9 months ago, # ^ |   0 I think no.
•  » » 9 months ago, # ^ |   0 My solution passed on pretests but was hacked later.
 » 9 months ago, # |   +14 These both accounts belong to the same person and he's changing his codes a bit to not get caught. He has cheated in previous contest too. MikeMirzayanov
•  » » 9 months ago, # ^ |   0 How does someone be so blatant about cheating? He's literally uploaded a picture of himself in both accounts. Ofcourse, there's always the chance that they're twin brothers or something.
 » 9 months ago, # |   0 Could someone please explain C?.Thank you
•  » » 9 months ago, # ^ |   +1 C is simple. Since all paths are palindrome, we need to have the bits as same at same distance from (0,0) and (n-1,m-1), unless they are equidistant from both(it'll happen only if n+m-1 is odd).For eg, take {{1,1,0},{1,0,0}}. Here n=2,m=3 and n+m-1= even. At distance 0 from (0,0) and (1,2) we have 1 and 0, we need to change any one of them. Similarly at distance 1 from (0,0) and (1,2) we have 1,1,0 and 0, we need to change any 2 of them. So finally the answer for this case is 3.We can ignore the ones that are equi-distant from (0,0) and (n-1,m-1), because the paths would be palindrome anyway. Hope that helps! 83443782
•  » » » 9 months ago, # ^ |   0 Thank you! I have understood.
 » 9 months ago, # | ← Rev. 2 →   0 In problem D, why can't we choose any pair of prime divisors of A[i]?
•  » » 9 months ago, # ^ |   +12 It's possible that their sum will be divisible by some other prime factor. Ex: A[i]=3*5*7, choose 5 and 7.
•  » » 9 months ago, # ^ |   +2 case a[i] = 2 * 3 * 5, if we choose (2, 3), gcd(2 + 3, 2 * 3 * 5) = 5 # 1. A good strategy is choosing (2 * 3, 5)
•  » » 9 months ago, # ^ |   0 Take the example of 30. The prime factors of 30 are 2,3 and 5. Now if we choose 2 and 3 __gcd(2+3=5,30)=5>1.
•  » »