### shaanknight's blog

By shaanknight, history, 19 months ago,

Hello Codeforces!

We are thrilled to invite you to CodeCraft-20 (Div. 2), which is to take place on Mar/04/2020 17:35 (Moscow time). The contest is rated for all participants with ratings under 2100.

The contest comes under the wing of Threads '20, the annual technical fest, a part of Felicity, IIIT Hyderabad .

Participants will be asked to solve 6 problems in 2 hours . Scoring will be announced just before the contest .

The problems were created by gaurav172, lazyneuron, preet_t and shaanknight .

We want to thank all the people for making this contest possible .

Wish you luck and hope you like the problems !!

UPD 1:

Score-Distribution

500-1000-1500-1750-2250-2500

UPD 2:

Congratulations to the winners of the round.

Div 1

Div 2

UPD 3:

Editorial

Announcement of CodeCraft-20 (Div. 2)

• +432

 » 19 months ago, # |   +98 Please make strong pretests this time.
•  » » 19 months ago, # ^ |   -16 Is it rated?
•  » » » 19 months ago, # ^ |   0 yes its rated
•  » » 19 months ago, # ^ |   -21 IMO pretests are sometimes too strong these days (especially with multitest), rendering hacking virtually impossible. I'd actually prefer to see a contest where it can pay off to search the room for hacks. As for now, sadly, this feature, once a funny part of Codeforces contests, is becoming less and less usable.
•  » » » 19 months ago, # ^ |   +39 Hacking was never funny nor was it usable, it was always just a swarm of edge cases on div2 B and a rush to grab hacks among the participants in the room. It's unfair and giving points for hacks should be disabled.
•  » » » 19 months ago, # ^ |   +20 It is true that the ratio of system failure has decreased on average compared to a few years ago. However, we must consider that the number of participants has greatly soared, which means that hacks have become more effective.I do not claim that the points from hacks is improper. Hacks are fun! Nevertheless, severely weak pretests might cause disruptive scoreboards, since hacking structure usually follows a-few-winner-takes-it-all.The main source of points should be the accepted solutions, not the hacks.
 » 19 months ago, # |   +34 Is preet_t's problem really pretty?
•  » » 19 months ago, # ^ |   +120
•  » » » 19 months ago, # ^ |   +16 wana waun waun wana waun waun wana waun
 » 19 months ago, # |   +28
•  » » 19 months ago, # ^ |   +9 Knock knock modafaka
 » 19 months ago, # |   +56 Why div2 only?
•  » » 19 months ago, # ^ |   +8 It is what it is.
•  » » 19 months ago, # ^ |   +104 Honestly, we intended to make a Div 1 + Div 2 round when we started, but we just had 2 problem ideas for the Div1 exclusive problems , which didn't seem to be interesting enough , hence we left the plan of combined round and rather focused on arranging a good Div-2 only round . We hope people find the current set of problems interesting .
•  » » » 19 months ago, # ^ |   +21 Good idea. Better to make a round the way you can than to force difficulty up with something boring just so it can be div1.
 » 19 months ago, # |   +209 Codecraft-17 : Hackforces Codecraft-18 : More Hackforces CodeCraft-19 : Terrible Hackforces There was room like this : Codecraft-20 : ??
•  » » 19 months ago, # ^ |   +15 Why is it bad?
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Incredible Database XO
•  » » 19 months ago, # ^ |   +2 Thanks for the info. I should probably skip this contest or attempt A,B,C very cautiously. But I seriously hope they learnt their lesson and this time pretests are stronger.
•  » » 19 months ago, # ^ |   +26 Whelp, not hackforces this time
•  » » » 19 months ago, # ^ |   +13 I agree, it's not hackforces.
•  » » 19 months ago, # ^ | ← Rev. 2 →   -28 .
•  » » 19 months ago, # ^ |   0 Hackforces eh m8?
 » 19 months ago, # |   +52 2 years ago CodeCraft was combined round! Why did it downgrade to div2 only?
•  » » 19 months ago, # ^ |   +51 Sorry to disappoint, we didn't have sufficient interesting ideas for Div 1 exclusive problems.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   -64 ......
 » 19 months ago, # |   +21 make strong pretests so that we do not feel bad.hoping a nice contest and thanks to codeforces.
•  » » 19 months ago, # ^ |   +80 We have tried our best to make sure pretests are strong enough.
•  » » » 19 months ago, # ^ |   +5 Alhamdulillah the contest was good
 » 19 months ago, # |   +54 Indian round cool... Hope to learn new things...
 » 19 months ago, # |   +23 Excited for this contest!
 » 19 months ago, # |   +16 Interesting problems with strong pretestshoping for a good round and rating increas
 » 19 months ago, # |   +14 Indian Round after long time :)
 » 19 months ago, # | ← Rev. 2 →   +2 Click the "Felicity, IIIT Hyderabad" link in this announcement above.And then, in this website, click the icon located at the top-right corner of the page.And then......
 » 19 months ago, # | ← Rev. 2 →   0 IIIT Hyderabad is diamond of india in coding.my Respect.
•  » » 19 months ago, # ^ |   +61 IIT Hyderabad may be the one, but just clarifying in case you are mistaken, we are IIIT Hyderabad.
 » 19 months ago, # |   0 Loaded for rocket launch.
 » 19 months ago, # |   +10 OMG,i am afraid of attending this round now
•  » » 19 months ago, # ^ |   -20 As this is an Indian round, the correct way to say would be:"OMG, i am afraid of giving this round now"
 » 19 months ago, # |   0 Codeforces $\times$Hackforces $\surd$stronger pretests this time pls
 » 19 months ago, # |   -52 This contest won't be rated bc of bad pretests :P
 » 19 months ago, # |   0 I hope the round won't be like the HackCraft round before...Also the order of the problems...
 » 19 months ago, # |   -19 Anybody explain please, difference between rated and unrated contest? Thanks in advance.
•  » » 19 months ago, # ^ |   +8 If contest is unrated you can't get any point/you can't rank up...
•  » » 19 months ago, # ^ |   0 If contest is rated your rating changes but not the same in unrated where rating doesn't change.
 » 19 months ago, # |   -11 I hope CodeCraft is as good as Minecraft
 » 19 months ago, # |   +197
 » 19 months ago, # |   +9 Oh my gosh another codeforeces round, It's so exciting, can't wait but honestly when will be round for slower and disabled contestants? (where all the problems are easy and time is not so decisive factor, and you really guys are reading all that math equations so easly?) Anyway good luck guys!
 » 19 months ago, # | ← Rev. 2 →   -6 Deleted
 » 19 months ago, # |   0 Hope for no accidents...Hacking is too terrible!!! QAQ
 » 19 months ago, # |   +31
 » 19 months ago, # | ← Rev. 2 →   +1 I am (and not only I am, honestly) participant "in competition" with rating greater than 2099 now. Should I re-register to participate out of competition?
 » 19 months ago, # |   -20 I hope the problemsettters are not fake IRS workers.
 » 19 months ago, # |   0 Text of tasks in English?
•  » » 19 months ago, # ^ |   0 True
 » 19 months ago, # |   +4 I will not able to participate in this contest due to my exams ... feels so bad
•  » » 19 months ago, # ^ |   -22 you are so lucky!
 » 19 months ago, # |   +73 ![ ]()
 » 19 months ago, # |   +10 thanks for one more good mathforces round!!!
 » 19 months ago, # |   0 Is C really this tough! or I'm the stupid one!!Leaving this round 35mins before yay!!! XDXD
•  » » 19 months ago, # ^ |   +1 I am stuck in B but C was easier than I thought but I did terrible mistake beforehand.
 » 19 months ago, # |   -51 I dont know if the difficulty of problem C is proper for div.2 C . Seemingly it requires some math knowledge that only students major in Maths learn. And it is my 1st time to fail at div.2 C after I became 'Master'.
•  » » 19 months ago, # ^ |   -33 Luckily I am out of competition so that my rating will not decrease.
•  » » 19 months ago, # ^ |   +129 I'm glad to know that there are at least 1525 math majors doing contest right now.
•  » » 19 months ago, # ^ |   0 The logic is Hell Simple.It might not have clicked to you, then. But, yeah, the problem seems suitable for Div.2 C Problem.In fact, many people were able to do "C" before "B".
 » 19 months ago, # |   -39 Thank you very much for proving once again why Indians should never be trusted with contests in a prestigious platform like this.
•  » » 19 months ago, # ^ |   +10 Like how the hell does nationality come in? If it's a bad contest, it's a bad contest. A mathy one, then it's a mathy one. Blame the problem setters. Downvote the announcement. But why the hell are you pulling their nationality into the picture??
 » 19 months ago, # |   +6 AB-Forces
 » 19 months ago, # | ← Rev. 3 →   -35 AB Forces!
•  » » 19 months ago, # ^ |   +11 I don't see it bad IMO.Could you explain your opinion?
 » 19 months ago, # |   +45 Weird bug — My handle changed to swust5120175180 in the standings!?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +5 I fell confident now (no offense) that I was able to do Problem C. Link : https://codeforces.com/contest/1316/submission/72456579
•  » » » 19 months ago, # ^ |   +10 Cool. I was trying to pass FFT (I am stupid, wtf was I thinking) before giving up and moving to E.
•  » » » » 19 months ago, # ^ |   0 Same, but then I saw constrains, and there is no way that FFT works in this constrains
•  » » » » » 19 months ago, # ^ |   +33 You just aren't using a fast enough FFT :^)https://codeforces.com/contest/1316/submission/72455655
•  » » » » » » 19 months ago, # ^ |   0 Hii, I am new to FFT BTW,\n why this fft is fast??\n (because using complex no doest require a lot of mod operation as in Ntt)???\n
•  » » » 19 months ago, # ^ |   +1 This could be even easier: just track two coefficients that are not a multiple of $p$.
•  » » » » 19 months ago, # ^ |   0 I dont get this solution. The test: 2 3 4 2 3 2 4 1 seems valid, because both gcd = 1.Just tracking two coefficients that are not a multiple of p gives 0 as one possible answer, but its wrong. What am I missing?
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   +5 Does your test look like this? :2 3 42 3 2 4 1If is, it's not a valid test case since 4 is not a prime.
•  » » » » » » 19 months ago, # ^ |   0 You're right, thx.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 -
•  » » » » » 19 months ago, # ^ |   0
 » 19 months ago, # | ← Rev. 2 →   -12 ;)
 » 19 months ago, # |   +2 How to solve C?
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 Observe that each term of the resultant polynomial is a sum of product of some terms taken from polynomial a and polynomial b, for ex — x^3 can be x^3.c or x^2.x.For the term to be divisible by p all the sums must be divisible by p. Find a term from x not divisible by p and same from y when you multiply them you get degree t(x)+t(y) and it is sure to be not divisible by p.
•  » » » 19 months ago, # ^ |   0 I couldn't understand"For the term to be divisible by p all the sums must be divisible by p" Why this is correct?p = 5, a = 2, b = 3 a and b are not divisible by p but a + b is divisible by p. Am I missing any part of your comment?
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +5 Well yeah, you need the lowest degree terms that are not divisible from both polynomials as when you take lowest degree terms you ensure that any other terms will be that would be formed will be divisible by p because to make t(x) + t(y) if you take a term greater than t(x) from x then you will have to lower t(y) which will ensure it is divisible by p, vice versa also being true.
•  » » » » 19 months ago, # ^ |   +5 Well, wait my solution also passes because the highest degree also has a similar proof wherein the terms greater than t(x) ensure that the other sums are divisible by p.
•  » » » 19 months ago, # ^ |   +4 How can it be proved that the sum is not divisible by p. Say, we get the individual sum as x and p-x , which are not divisible by p. But their sum is divisible by p.Or,Is this case not possible at all?
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +6 p --->number is divisible by p.np -->number is not divisible by p.A=[p,p,p,p,p,np]B=[p,p,p,p,p,p,p,p,p,np]Say the first index in array A having np is i,and first index in array B having np is j. We claim that answer is i+j. Let's pick a element which has index greater than i and not divisible by p from Array A, now, we are forced to pick a element having index less than j of Array B ,in order to get the sum equals to i+j. Now, A[i]*B[j] will be divisible by p,since B[j] is divisible by p. Therefore we can't pick two elements , both of them who are not divisible by p,and the sum of indices being i+j.I hope ,this is the logic behind the soln.
•  » » » 19 months ago, # ^ |   0 suppose a[] is 2 2 b[] is 2 32 * 3 = 6 and 2 * 2 = 4 now if p is 5 then what do you want to say here, since 6 and 4 are not divisible by 5 but their summation is divisible by 5
•  » » » » 19 months ago, # ^ |   0 a cant be 2 and 2 as their gcd will not be 1.
•  » » » » » 19 months ago, # ^ |   0 Yes! I got it!
•  » » 19 months ago, # ^ |   +3 Transform each coefficient to $1$ if it is not divisible by p, and $0$ if it is. There will be $a_i$, $b_j$ such that $a_i = b_i = 1$. The answer is $i+j$.
•  » » 19 months ago, # ^ |   0 Here is my solution : https://codeforces.com/contest/1316/submission/72456579 Find an element in A not divisible by p and same in B. Ans will be the sum of index of those elements.
•  » » » 19 months ago, # ^ |   0 A=[1,3,1] B=[1,3,1] p = 11 3 % 11 = 3 Therefore your answer would output 2,But actually (1 + 3x + x^2) * (1+3x+x^2) = 1 + 3x + x^2 + 3x + 9x^2 + 3x^3 + x^2 + 3x^3 + x^4 = 1 + 6x + 11x^2 + 6x^3 + x^4 And 11 is divisible by 11. How come your soluton is correct?
•  » » » » 19 months ago, # ^ |   0 Sorry pls ignore my reply, I understood your solution now...
 » 19 months ago, # | ← Rev. 3 →   +1 How to solve E ? I had following idea — Sort by 'a' and then do dp[i][mask] = maximum score till i'th index such that 'mask' position of players are selected. Add it to audience if possible. This gave WA-16. Edit — Caught the error.
 » 19 months ago, # |   0 Whats pretest 7 in C problem?
 » 19 months ago, # |   +2 Any hints on how to approach C? Hitting TLE on pretest 7.I am not able to simplify the question further. I can't find the relation between GCD(, ..., ) = 1 and prime p. Does prime p have any significance in the logic or solution behind this question? Also, does GCD() = 1 has any importance in the solution?p.s. Not able to solve Div2C after a long, long time. It hit me so hard!
•  » » 19 months ago, # ^ |   0 Same thought, What was the logic to solve it?
•  » » 19 months ago, # ^ |   +5 smallest i such that ai%p!=0, smallest j such that bj%p!=0, answer is i+j.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +3 observe the c(i+j), it will be (ai*bj + some other number which is divisible by p).
•  » » » » 19 months ago, # ^ |   0 How can we be sure that the sum of other numbers is divisible by p?
•  » » » » » 19 months ago, # ^ |   +12 power will be (i+j) for x^(i+j) you will be chossing either one or more value less than i from first polynomial or one or more value less than j. since i & j are smallest non-divisible, rest all terms will be divisible. Hence their sum will not be divisible
•  » » » » » 19 months ago, # ^ |   0 Expand c(i+j) in terms of coefficient of a, b, there is only one term not divisible by p.
•  » » » » » 19 months ago, # ^ |   0 c(i+j) = ap * bq, if (pj and all ap are multiple of p. If qi and all bq are multiple of p.
•  » » » » 19 months ago, # ^ |   0 Is there any proof?
•  » » » » 19 months ago, # ^ |   0 any proof, that the some other number will be divisible by p?
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   +24 let minimum index of some number not divisible by $P$ in set $A$ $= i$let minimum index of some number not divisible by $P$ in set $B = j$$c(i+j) = (A[i] * B[j]) + (A[i-1] * B[j+1]) + (A[i+1] * B[j-1]) + (A[i-2] * B[j+2]) + ....$notice how all terms except for $A[i] * B[j]$ (let's call any term of which $A[X] , B[Y]$) have ($X > i$ and $Y < j$) or ($X < i$ and $Y > j$)case $X > i$ and $Y < j$: since $Y < j$, then $B[Y]$ is divisible by $P$, hence $A[X] * B[Y]$ is divisible by $P$case $X < i$ and $Y > j$: since $X < i$ then $A[X]$ is divisible by $P$ and $A[X] * B[Y]$ is divisible by $P$conclusion: $A[i] * B[j]$ is the only term NOT divisible by $P$ if we pick minimum $i$ , $j$ for which $A[i]$ isn't divisible by $P$ and $B[j]$ isn't divisible by $P$
•  » » » » » » 19 months ago, # ^ |   0 Thank you for the detailed explanation.
•  » » » » » » 19 months ago, # ^ |   0 Great explanation.
•  » » » 19 months ago, # ^ |   0 As simple as that??Does there exist any correctness proof for this?
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +8 Yes, it is very easy to prove. Write the summation out modulo p for $x^{i+j}$ and you'll see that all terms except one of them are 0 (due to one of the factors being divisible by $p$).
•  » » » » » 19 months ago, # ^ |   0 I don't know where my mind was during the contest. 5 mins later I look in my notebook and I realise I was going in the same direction but I don't know why i left this idea :'(
•  » » 19 months ago, # ^ |   0 gcd = 1 means they're all co-prime. But I didn't know how to use that to solve the problem.
•  » » » 19 months ago, # ^ |   +1 It means that there is no prime that divides all coefficients of f(x) and g(x).
•  » » » 19 months ago, # ^ |   0 What you mean by all co-prime? It doesn't mean that for any i and j $gcd(a_i, a_j) = 1$
•  » » » » 19 months ago, # ^ |   0 I will calculate gcd of constant term and coefficient of x, let the answer be g, then i will calculate gcd(g, coefficient of $x^2$) and set it to g and move on in this manner. gcd is calculated in this manner and the final g you get is 1 in both cases.
•  » » » 19 months ago, # ^ |   0 Let's break it down, if $GCD = 1$ for a set of elements, then there is no prime number that is a common divisor among all elements of this set, because all primes are $> 1$ (otherwise the GCD would be equal to that prime number), In other words, for any prime number $P$ if we try to divide all elements of this set by $P$ we are sure that there exists some element $X$ that isn't divisible by $P$.
•  » » 19 months ago, # ^ |   +31 Hint: gcd = 1 ensures that there is at least one coefficient not divisible by p in each polynomial
•  » » 19 months ago, # ^ | ← Rev. 2 →   +3 The question is based on Gauss Lemma for Polynomials. https://en.wikipedia.org/wiki/Gauss%27s_lemma_(polynomial) You need to find two numbers each from ai and bj such that ai%p!=0 and bj%p!=0, ans is i+j;
•  » » 19 months ago, # ^ | ← Rev. 4 →   +2 If you are having TLE then you might want to check if you are using fast IO method or not. Thought process and proof of C : think about how c[0], c[1], c[2]... these are formed, c[0] = a[0]*b[0], c[1] = a[0]*a[1] + b[0]*b[1], c[2] = a[0]*b[2] + a[1]*b[1] + a[2]*b[0] ... c[n] = a[0]*b[n] + a[1]*b[n-1] + a[2]*b[n-2]...+a[n-1]*b[1] + a[n]*b[0]. You need to find ct which is not divisible by p, means ct = p*x + y, where x can be any integer and y % p != 0. So we find the very first coeffcient of f(x) and g(x) that is not divisible by p, let's call them a[i] and b[j] respectively. We know a[1],a[2]...a[i-1] and b[1],b[2]...b[j-1] all are divisible by p. If I choose ct to be the coefficient of x^(i+j) then ct = a[0]*b[i+j] + a[1]*b[i+j-1] ... a[i+j]*b[0]. Here every term has some part of a[0] to a[i-1] or b[0] to b[j-1] except for exactly one term that is a[i]*b[j] and neither a[i] or b[j] is divisible by p. And as p is a prime number and we are just multiplicating two numbers a[i]*b[j], hence it is not divisible by p. So ct can be written as ct = p*x + y. So coefficient of x^(i+j) is indeed our answer.
•  » » 19 months ago, # ^ |   0 GCD 1 makes it sure that at least one element is there which is not divisible by the given prime. So, the answer always exists.
 » 19 months ago, # |   0 Can someone tell me why my code in B times out?
•  » » 19 months ago, # ^ |   0 your code has complexity n^3. You are running a loop of size n, then inside there is a call to the function that is running another loop of size n, and inside there is reverse function that itself is of O(n) complexity.
 » 19 months ago, # |   +30
•  » » 19 months ago, # ^ |   0 Please upload your video in higher quality, its max is 360p only.
•  » » » 19 months ago, # ^ |   0 The 1080p is available now.
•  » » » 19 months ago, # ^ |   +16 Youtube takes some time before videos become HD.
 » 19 months ago, # |   0 How to solve E? I couldn't deal with the necessity of keeping sets/vectors of all elements chosen as audience while trying to take i-th citizen as a member of the audience.
•  » » 19 months ago, # ^ |   +32 sort the people by A in decreasing order dp(i, msk) = max try to take person i for each non taken position and iff (i — popcnt(msk)) < k then you can use him for support
•  » » » 19 months ago, # ^ |   +5 Sorting — so simple, yet so effective
 » 19 months ago, # | ← Rev. 5 →   +27 I googled for C 2 minutes before ending and got AC. (https://imgur.com/a/NXx553s)
•  » » 19 months ago, # ^ |   0 What is the solution of C?
•  » » » 19 months ago, # ^ |   0
•  » » 19 months ago, # ^ |   0 What did you googled?
 » 19 months ago, # |   0 C even did not understand the question. It is a math riddle, I am sure there are people happy with that. Not me.
 » 19 months ago, # | ← Rev. 4 →   +5 Problem D: go in two phases: the first phase make the connected component of sink point to the sink. In the second phase, do the similar with {-1,-1}'s, except make a "sink" be the circuit of size 2.Is this a correct strategy?
•  » » 19 months ago, # ^ | ← Rev. 6 →   +1 T-shaped tetris is possible!! for example -RDLXUXthat was I missing.
•  » » » 19 months ago, # ^ |   +5 Good point, edited. It seems that we only need eventually periodic.
•  » » » 19 months ago, # ^ |   0 I think you can connect 2 adjacent cells whenever you can (so that they form a loop) and if some single cells remain, you can connect them to an existing adjacent loop. In such a way, as soon as it starts from that cell, on the first move it will go to the loop and after that, it will run infinitely!For example, if we had something like that:...-.- (where — are occupied cells and . are infinite ones)You can connect the (1, 1) and (1, 2) squares to form a loop and the remaining could be directed on this loop, like this:LRL-U-We are 100% certain that this method will always work!
•  » » 19 months ago, # ^ |   +9 For any {-1,-1}, it's enough to point it to a neighouring {-1,-1}. If there is none, no solution exists.Unfortunately, I got TLE because of an extremely dumb mistake (re-initialising the NxN visit matrix every iteration...), but I think this should work.
 » 19 months ago, # |   +8 How to solve E?
 » 19 months ago, # |   0 Can somebody tell a counter case for my code of D. It failed at pretest 9. https://codeforces.com/contest/1316/submission/72455182
 » 19 months ago, # |   0 Is it possible to solve E faster than $O(p^2\cdot 2^p\cdot n)$?
•  » » 19 months ago, # ^ |   +3 $O(nlogn+p\times 2^{p}\times n)$ with SoS DP?
•  » » 19 months ago, # ^ |   +12 O(n * 2 ^ p * p) with standard dp
 » 19 months ago, # |   0 So bad,My fft don't solve div2 C!!! I think it maybe overflow
•  » » 19 months ago, # ^ |   0 https://codeforces.com/blog/entry/74432?#comment-585757. No need of fft
•  » » » 19 months ago, # ^ |   0 thanks,but FFT also get ac
 » 19 months ago, # |   0 https://codeforces.com/contest/1316/submission/72454944Why n^2 give tle in B
•  » » 19 months ago, # ^ |   0 probably because you are not using '+=' for the string concatenation
•  » » 19 months ago, # ^ |   0 I also got a tle. Optimized a bit (still n^2) and pretests were passed. Don't know why?
 » 19 months ago, # |   +53 LOL, B was much harder than it should've been, I solved E faster than B! XD
•  » » 19 months ago, # ^ |   +5 Can you explain how did you solve E?
 » 19 months ago, # |   +8 why was there a D just why
 » 19 months ago, # |   +27 C was actually quite interesting to me. If anyone still doesn't know how to solve, it is sufficient to take the first coefficient in both A and B that isn't divisible by $P$ and output the sum of their powers, call it $X$ (this is guaranteed to exists because of the gcd condition). To understand why this works, consider the summations of coefficients mod p. For every term in the summation besides the coefficients that we have taken, at least one term in the product will be divisible by $P$, thus all terms that contribute to the $X th$ power will evaluate to 0 except for the two that we have chosen which cannot be divisible by $P$, thus the coefficient in the multiplied polynomial will not be zero.
•  » » 19 months ago, # ^ |   0 Nice! I need this kind of intuition in min time. Maybe gotta do some projecteuler questions.
 » 19 months ago, # |   +9 To me it's ABodeforces...
 » 19 months ago, # |   0 Can anyone give me a counter example to my code on D? https://ideone.com/OgTmuL What I'm doing is: find all 'X's and branch off them by reversing the given instructions For the (-1, -1)'s, I group them in groups of two adjacent if possible and make them "look" at each other (For example: RL) Also how to solve B?
•  » » 19 months ago, # ^ |   0 Counterexample3 -1 -1 -1 -1 -1 -1 2 2 2 2 2 2 2 2 2 2 2 2  One possible answer isRLL RXL ULL 
 » 19 months ago, # |   -11 Just why ? Why give such braindead heavy implementing problem like D.
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 It's really hard to implement it precisely, even though the code "only" around 180 lines.(well at least for me)
 » 19 months ago, # |   0 How to solve D?
 » 19 months ago, # |   -28 what a shitty day, IRS scamming at its finest
•  » » 19 months ago, # ^ |   +45 What is IRS?
•  » » » 19 months ago, # ^ |   -8
 » 19 months ago, # |   +10 How to solve F?
 » 19 months ago, # |   +1 I don't believe I'm asking this, how to solve B?
•  » » 19 months ago, # ^ |   +8 Apparently finding all possible solutions and sorting them got past the pretests....... the hard part was finding the trick to find the solution without n^2. for me i just failed to realize that this solution wouldnt get tle..
•  » » » 19 months ago, # ^ | ← Rev. 3 →   0 I just realized that if you apply the K reverse operation on some string s all you have to do to is to compute s as s = s[k .. N] + s[1 ... k — 1] (the latter eventually reversed). Anyway, thank you!
•  » » 19 months ago, # ^ |   0 For B, I think violence will time out, so I turned to finding the rule. After writing a few, I found that when I value K, the composition of strings after operation is like this. First, it is from a [k] to a [len]Then judge whether the parity of K and Len is the same, and then continue from a [1] to a [k-1]The difference is from a [k-1] to a [1]. I hope my approach can help you
•  » » 19 months ago, # ^ |   0 You need to find a way to quicken the loop over reversing all substrings.It is to rotate the whole string, and reverse the last k-1 chars if parity is odd. See solution codes https://codeforces.com/contest/1305/submission/72330015
 » 19 months ago, # |   +3 In problem C, could somebody tell me if multiplying polynomials using divide and conquer method would get AC? I'm not sure of the complexity of this algo, but I couldn't implement it anyway...
•  » » 19 months ago, # ^ | ← Rev. 2 →   +2 No, it should not pass.
•  » » » 19 months ago, # ^ |   0 It would depends on his divide-and-conquer method. For example, some of my friends considered resorting to fft on problem C.
•  » » » 19 months ago, # ^ |   0 have a look at this. link to another comment
 » 19 months ago, # |   0 In B, O(n^2) solution will have 10^9 operations while time limit is 1 seconds only, why it is not giving tle.?
•  » » 19 months ago, # ^ |   +1 N is max bounded by 5000 . So max operations won't be 10^9
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 there will be a loop for test cases outside n^2 and max bound of t is also 5000
•  » » » » 19 months ago, # ^ |   +2 "It is guaranteed that the sum of n over all test cases does not exceed 5000."
•  » » » » » 19 months ago, # ^ |   0 Oh..Thanks.!
•  » » 19 months ago, # ^ |   +9 Why will $O(n^2)$ have $10^9$ operations? $n$ is up to 5000
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +1 5000 * 5000 = 2.5 * 10^7 ..... So I guess time is sufficient. Also it is guaranteed that the sum of n over all test cases does not exceed 5000.
•  » » » » 19 months ago, # ^ |   0 will this include loop for test cases also..?
•  » » » » 19 months ago, # ^ |   +1 Yep, I asked him to prove he was wrong, of course I see $5000^2$ is about $10^7$
•  » » » » » 19 months ago, # ^ |   +1 It is guaranteed that the sum of n over all test cases does not exceed 5000. So the upper bound is t = 1, n = 5000.
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 Then why this code timed out? Here
•  » » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 Look at your make_string complexity. It's bigger than $O(n)$ since reverse() is $O(n)$
 » 19 months ago, # |   0 I don't know why people are complaining so much about C being mathforces.I think it just required little bit of observation and a basic fact that: k*p + a is never divisible by p.Where, k is some integer, p is a prime, a is not divisible by p.
•  » » 19 months ago, # ^ |   0 Can you explain it thoroughly?
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +11 let's say notations p — divisible by p; np — not-divisible by p. Now let the polynomials' coefficients look like this:a: p p p np p np p p p p ....b: p p p p p np p p p p .... Now you can see if you take the first occurrence of np in 'a' and first occurrence of np in 'b', in our case it is 3 and 5 respectively (0- indexing) .The term formed will be x^(3+5) = x^8.And the coefficient of this term in the resultant polynomial will be of the form: k*p + awhich is never divisible by p.Where, k is some integer, p is a prime, a is not divisible by p.
•  » » » » 19 months ago, # ^ |   0 Here's an example where this doesn't seem to work. What am I missing?Given: f(x): 5x^4 + 5x^3 + [2x^2] + [3x] + 10 g(x): 5x^4 + 5x^3 + [2x^2] + [2x] + 15 p: 5 The expressions in [brackets] are not divisible by p. Specifically [2x] and [3x] are the first occurrences that are not divisible by 5. h(x) = f(x) * g(x), which will end up having (2x^2 * 2x) + (2x^2 * 3x) = 10x^3, which is divisible by p
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   +1 let h(x)=summation_from_0_to_n+m-2(cr*x^r) \ncalculate c2. \nc2=15*2*x^2 + 10*2*x^2 + 3*x*2*x. \nc2=56*x^2; \nhence the ans is 2:^)) \nif you didn't understand try calculating every term of h(x).
•  » » » » » » 19 months ago, # ^ | ← Rev. 2 →   +1 Thanks. So it seems that the key here is to take the first powers of x that are not divisible by p for both. Every other equivalent power of x is already a multiple of p, and hence won't impact. Any later coefficients that are not divisible by p are irrelevant, as their multiplication results in a higher power of x, which does not impact our answer.
•  » » » » » » » 19 months ago, # ^ |   +1 i think first power which is not divisible by p is important. \nif we take any index from first poly which is not divisive by p and any index from second poly which is not divisible by p, \nand calculate its corresponding coefficient, it may give WA, because they may be add up to a factor of p. \n so if we take first power, it will not gonna impact out and, \n:^)
 » 19 months ago, # |   0 Do we need FFT for polynomial multiplication in C?I was thinking of solving C but didn't know FFT implementation.
•  » » 19 months ago, # ^ |   0 No fft isn't the desired solution.
•  » » » 19 months ago, # ^ |   +3 Can you explain me why using FFT leads to TLE. imo the constraints should have passed in the given TL. Or am I missing something?
•  » » » » 19 months ago, # ^ |   +6 Writing an optimal version of fft might even get you an AC on the problem , but since a lot of mod operations are involved , though O(N log N) a general fft code without optimisations takes slightly more time than 1.5 seconds to pass .
 » 19 months ago, # |   -13 Why do you take theoroms and make questions out of them . Stupid C really. https://imgur.com/a/NXx553s
•  » » 19 months ago, # ^ |   +16 Why you google every time during the contest ?!!
•  » » » 19 months ago, # ^ |   0 I did not. I got this link after contest.
•  » » » » 19 months ago, # ^ |   0 Then it's fine !!
•  » » 19 months ago, # ^ | ← Rev. 2 →   +16 Well, you can make a theorem about anything. Any observation for an ad-hoc problem could be called "theorem".
•  » » » 19 months ago, # ^ |   -11 ok
 » 19 months ago, # |   0 Am I the only one who left A and B first and solved C then moved to A and don't even saw B.
 » 19 months ago, # |   0 How to solve problem B?
•  » » 19 months ago, # ^ |   0 It's constructive.
•  » » » 19 months ago, # ^ |   0 would please explain it
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 72451317 What is wrong with my approach
•  » » 19 months ago, # ^ |   0 Construct new string for every $k$, take minimal
•  » » 19 months ago, # ^ |   0 Observe: for any string S, if you pick any valid k, the resultant string isR = S[k : n] + (S[0 : k-1] if n-k is odd) OR (S[k-1 : 0] if n-k is even)72440479
 » 19 months ago, # |   -28 Not only annoying B but annoying C this time :(A understandable solution for problem B is to calculate all the possible strings for every k and sort them.But the complexity seems a bit dangerous...NO FST PLZ XD
•  » » 19 months ago, # ^ |   +8 No need to sort, just take minimum
•  » » » 19 months ago, # ^ |   0 You will have to sort, I think, if there are equals Strings we would only save the ones with smaller k value.
•  » » » » 19 months ago, # ^ |   0 Just take first minimum. I solved without sorting
•  » » » 19 months ago, # ^ |   0 ohhhhhhhhhhhh,how stupid I amthx a lot TUT
•  » » 19 months ago, # ^ | ← Rev. 3 →   +9 Just a bit of writing on paper and trying to find the pattern would have helped.You will find out for string s of size n and k,resultant string will be = (last n-k+1 chars) + string_rwhere,if (n-k+1) is even:- string_r = (first k-1 chars)else- string_r = reverse_of(first k-1 chars) Thus finding the resultant string for each k takes at most O(N) operations. And put them all into a map and find the lexicographically least one.Complexity is: O(N*N*log(N))Check my AC submission for more clarity.
•  » » » 19 months ago, # ^ |   +12 You don't even need to put them all in map. You can just keep a bestString, initialize it to the given string s. This is what you get if you pick k = 1. Then you just keep increasing k till n and generate the possible strings in the way you mentioned. Just compare your generated string with your bestSring and update it when generatedString < bestString. Complexity will be O(N^2)
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 Yeah true, but still my solution passed in just 46 ms. Maybe the test cases were pretty chill.
•  » » 19 months ago, # ^ |   0 It's a theorem https://imgur.com/a/NXx553s
 » 19 months ago, # |   0 How to solve Problem B?
•  » » 19 months ago, # ^ |   0 I solved like this, so suppose k is 2 then first 2 elements will go the end and all others will come in front. if total operations is odd then first 2 will be reversed, else first two will remain same. so using this pattern u can calculate the required string in O(n). And choose min out of all .
•  » » » 19 months ago, # ^ |   0 Isn't it total operations AND length of the string that is supposed to be odd?
•  » » 19 months ago, # ^ |   0 For B, I think violence will time out, so I turned to finding the rule. After writing a few, I found that when I value K, the composition of strings after operation is like this. First, it is from a [k] to a [len]Then judge whether the parity of K and Len is the same, and then continue from a [1] to a [k-1]The difference is from a [k-1] to a [1]. I hope my approach can help you
•  » » » 19 months ago, # ^ |   0 So when K and Len have different parity we would store a[k-1] to a[1] to the right of (a[k] to a[Len]) ?
•  » » » » 19 months ago, # ^ |   0 72449591 You can look this. I hope this can help you
•  » » » » » 19 months ago, # ^ |   0 Yeah Got it.
 » 19 months ago, # | ← Rev. 2 →   +16 Is it intended to counter Treap's stuff in F? It is even harder than offline solution :)
•  » » 19 months ago, # ^ |   0 I think they raised the limit to allow it, there are treap solutions with 3.5s execution time. The problem is that if you have anything that makes the constant slightly bigger it's a ton of time: I used the problem to test splay tree and got 4.9s by inserting in the first way I thought of, then I optimized the insert after the contest to use one splay operation and it's 4s.
•  » » 19 months ago, # ^ |   0 No, we did not intend to fail the treap solution. We had the offline segment tree solution that passes in 1.4 s. We raised the limit to allow certain other slow solutions but with same complexity . As tfg rightly mentioned, it's true if you have any part that's unoptimised it really takes a lot of time to pass.
 » 19 months ago, # |   +2 task C is great enough to look for some stable and fast fft model xDbtw, really enjoy these tasks! thanks for that
 » 19 months ago, # |   +79 I don't get the comments above criticising problem C. It was a brilliant observation/ad-hoc problem.
•  » » 19 months ago, # ^ |   0 it is actually Gauss's lemma
•  » » » 19 months ago, # ^ |   +5 Maybe it is a named lemma. But I don't see the need to know the lemma beforehand — it can easily be solved by observing how the coefficient for each power of x is obtained.
•  » » » » 19 months ago, # ^ |   +11 yeah, and thats exactly how this lemma was proved :D
•  » » 19 months ago, # ^ |   -39 Its a math student jerk off thing. For me not a programming problem, but a math riddle, the main concern is understanding the question.
•  » » » 19 months ago, # ^ |   +8 Math is very much a part of competitive programming. Combinatorics and Number Theory questions, involving no other algorithms, are frequently asked in contests.
•  » » » » 19 months ago, # ^ |   -8 The question cannot be understood without in-depth knowledge of polynomials. The technical terms used make no sense without the appropriate context.This is different with most combinatorics and number theory problems, where concrete examples have to be calculated.
•  » » » » » 19 months ago, # ^ |   0 No, all you need to know is how polynomials are multiplied, and some luck observing how that would help. Luck is always involved in observation-based questions like these. Can't help it. Knowing the lemma and proof beforehand, would allow you to quickly submit the solution. But it's not as if without knowing the lemma you are completely helpless. (I didn't even know that there is a lemma for this, until after the contest). Now you may claim that making a question completely on a named famous lemma might not be a good idea, and I don't disagree. But this does happen very often, so I wouldn't criticize this round specifically.
•  » » 19 months ago, # ^ |   0 Yeah it's a lemma https://imgur.com/a/NXx553s
 » 19 months ago, # | ← Rev. 2 →   +44 I think problem C is a good ad-hoc problem. Beside, it actually asked us to prove Gauss's lemma.
 » 19 months ago, # |   0 please provide contest Material(solutions)
 » 19 months ago, # |   0 Can Someone tell me whats wrong with this solution For 'B'? Code- https://codeforces.com/contest/1316/submission/72450457
 » 19 months ago, # |   0 My randomized C solution will fail on this case: n 2 2 1 1 1 1 1 ... 1 1 1 Thanks I saved my ratings
•  » » 19 months ago, # ^ |   0 Can you please tell me your approach? It looks interesting but I don't get it.
•  » » » 19 months ago, # ^ |   +8 Gather all indices which $a[i] \not \equiv 0 \bmod{p}$ and $b[j] \not \equiv 0 \bmod{p}$ each. Now just run random. In each iteration you will pick any two indices from the first list and the second list. Break if you find the correct answer.
•  » » 19 months ago, # ^ |   0 Nice, my also was hacked)
 » 19 months ago, # |   +9 System testing even took more time than the total duration of contest :)
 » 19 months ago, # |   0 How to solve B in O(n^2)?
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 There is an observation. If k is 1, then the string remains the same. If k is 2, then first character goes to the end of the string. If k is 3, then first two characters goes to the end of the string. So first k-1 characters will go to the last.So if we have ABCDE, then for k = 3, it will become CDEAB. But if we have ABCD, then for k = 3, it will be CDBA.Now the only thing to check is if the first k-1 characters that that are going to the last, will be reversed or not.They will be reversed if reversing operation is run odd times. So check if the n-k+1 is odd or not.
•  » » » 19 months ago, # ^ |   0 In my case i was considering a greedy approach with K as index of smallest character in the string. So that the smallest charcter will come in front and after that i just needed to perform the operations as mentioned. But it showed wrong answer in test 2. Can you help where did i go wrong? code- https://codeforces.com/contest/1316/submission/72450457
•  » » » » 19 months ago, # ^ |   0 You had to give the smallest value of k, you never consider that.
•  » » » » » 19 months ago, # ^ |   0 Got where i went wrong.
•  » » 19 months ago, # ^ |   0 Construct new string for every k, take minimal
 » 19 months ago, # |   0 I wonder what should be constraint so FFT solution passes on C...
•  » » 19 months ago, # ^ |   +10 If n,m <= 1e5, I think O(nlogn) FFT solution should pass.
•  » » » 19 months ago, # ^ |   0 i dont think so. constrains should be lower for O(nlogn) to work
•  » » » » 19 months ago, # ^ |   0 FFT will take O(nlogn) which should work for n,m<=1e5 and then you have to iterate over n+m-2 coefficient doing a modulo operation which will be <=2*10^5-2 steps. This should work.
 » 19 months ago, # |   +3 when the scoring will be announced??
 » 19 months ago, # |   +10 Yay! I solved three problems in Div2 for the first time!!! :D
 » 19 months ago, # | ← Rev. 4 →   0 https://codeforces.com/contest/1316/submission/72445522 Can someone help me find the bug? Problem B, can't figured it out myself my stemy steps are the same with the tutorial? wa on test case 133 Edi: nvm i got it
 » 19 months ago, # | ← Rev. 3 →   0 https://codeforces.com/contest/1316/submission/72467933 Why I am getting wrong answer in C testcase 7? Ignore the leftrotate and rightrotate, those were for last question xD
•  » » 19 months ago, # ^ |   0 See this loop from your submission: for(ll i=0;i>a[i]; if(a[i]%p!=0) ans+=i; } You add the indices of every $a_i$ where $p$ doesn't divide $a_i$, instead of only adding the first index.
•  » » » 19 months ago, # ^ | ← Rev. 3 →   0 wow thanks, I'm an idiot.
 » 19 months ago, # |   0 My python solution for C works but fails to read inputs quickly. from sys import stdin n, m, p = map(int, stdin.readline().split()) f_coeff = list(map(int, stdin.readline().split())) g_coeff = list(map(int, stdin.readline().split())) # find the coefficient with highest degree that is not divisible by p # then all the coefficients before it are divisible by p for i in range(n - 1, -1, -1): if f_coeff[i] % p != 0: break for j in range(m - 1, -1, -1): if g_coeff[j] % p != 0: break # i, j are the degrees print (i + j) Submitting this in PyPy3 gets a TLE but submitting in Python3 gives Accepted. What is causing this difference? Does stdin behave that much differently?
 » 19 months ago, # |   +23
 » 19 months ago, # |   +26 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters and update them again!
•  » » 19 months ago, # ^ |   +8 Thank You :)Btw I found you a cheater, I think.https://codeforces.com/contest/1316/submission/72434554The hack looks rather intentional.
•  » » » 19 months ago, # ^ |   +6 I don't think so. It seems that the attacked solution try to output some debugging information on the sample testcases and forgot to delete them while submitting. And the hacker just found this and made a targeted attack. Since it seems that both accounts has no relationship here.
•  » » 19 months ago, # ^ | ← Rev. 6 →   0 Deleted
 » 19 months ago, # |   +6 When the editorials will be available?
 » 19 months ago, # |   0 https://codeforces.com/contest/1316/submission/72475791I am getting wrong answer on testcase 157 by submitting the code mentioned in the link. Can anyone please tell me why is it so?
•  » » 19 months ago, # ^ |   0 It's because you intend to find the first coefficient that is not divisible by p , but you put r as 0 initially , so whenever there's a case when the first coefficient you are looking for is at power 0, you skip that one and pick up the next coefficient that's not divisible by p , as your r is still 0. Changing initial r as -1 and putting in the check , if r is -1 , only then assign r = i, the code should work .
•  » » » 18 months ago, # ^ |   0 it is written in the question you could pick any coefficient though which is not divisible by p!.Not just the first one!
•  » » » 18 months ago, # ^ |   0 I did the same thing and only then did all the cases pass. My doubt was regarding the instructions given, it is written in the question you can pick any coefficient which is not divisible by p, not just the first one. So that way my answer is an alternatively correct one. Anyways, thank you!
 » 19 months ago, # |   0 In question C, why is the sum of other numbers not an integral multiple of P?
•  » » 19 months ago, # ^ |   +5 The solution is you find the first i in first polynomial ( i can be from 0 to n-1 ) such that it's coefficient is not divisible by p. Since all other ak's from k = 0 to i — 1 are divisible by p , the entire thing that you put in initial paranthesis is divisible by p.Now we want a find a j in 2nd polynomial, similar to how we found i in first polynomial. Since now all other bk's from k = 0 to j — 1 are divisible by p , the entire thing that you put in second paranthesis is divisible by p . Now since ai is not divisible by p and bj is not divisible by p, ai*bj cannot be divisible by p since p is a prime. Hence the entire expression is not divisible by p because ai*bj is not divisible by p and all other terms are.
•  » » » 19 months ago, # ^ |   0 I see. Thank you very much.
 » 19 months ago, # |   0 Can anyone please explain problem "B"???I couldn't even understand the tutorial.
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 Consider any string str for modification for a chosen k and let us write str = AB , where A is the prefix of length k-1 and B is the suffix of length n-k+1.Now applying the modification, the modified string is either of form BA or BA' ( where A' is the reverse of the string A) based on the parity difference between k and n, i.e., (n-k)%2 .Consider str = "malice" . n = length of string = 6. Now using k = 3, A = "ma" & B = "lice", the modified string is BA , i.e., "licema" . Parity difference is 1 here. Now using k = 4, A = "mal" & B = "ice", the modified string is BA' , i.e., "icelam" . Parity difference is 0 here. I hope I haven't made any mistake in the example. I suggest taking a string and trying it out for yourself to note the observation. Understanding the way resultant string is obtained after modification in the 2 cases, we can actually obtain the modified string in O(n) for each k rather than O(n*n). Hence we can check for each k and find the lexicographically smallest string .
•  » » » 18 months ago, # ^ |   0 There is a little mistake in case of k=4...Here the string will be BA'...Whatever I understand...Thank you so much.
•  » » » » 18 months ago, # ^ |   0 Right
•  » » » » » 16 months ago, # ^ |   0 Nice.
 » 19 months ago, # |   0 Why does simply doing FFT give me a wrong answer on test 7 of C? Anyone else submitted using FFT?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +17 May because long long integer overflow by using FFT，you can have a try with NTT.
•  » » » 19 months ago, # ^ |   +8 NTT is annoying to do because it's not using an NTT mod so you need to combine multiple NTT's with CRT.You want to use something called FFTMod: https://github.com/kth-competitive-programming/kactl/blob/master/content/numerical/FastFourierTransformMod.h
•  » » 19 months ago, # ^ |   0 Simply doing an FFT tho has a complexity O(N log N), will actually run a bit slower and take more than 1.5 s because of a lot of mod operations associated . A good optimisation on FFT might fetch you an AC : look at this 72472090 by risujiroh . It seems he got AC by a fft solution. The desired solution was never FFT though.
 » 19 months ago, # |   0 Thanks for the Editorial on time.
 » 18 months ago, # |   0 Why did my rating got deducted even after submitting the right code?