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 .
- Our Coordinator antontrygubO_o for the immense help and guidance.
- All the testers of the round : codelegend, aryanc403, _overrated_, Little_Bunny, nvmdava, Rahul, sigma_g, pllk, vivace_jr, hoke_t, pajenegod, Arpanet, suzaku_kuru, heisenberg97, TselmegKh, swetanjal, MohamedMagdy.
- coder_h, riz_1_, night_fury208, firebolt, Altitude, matcoder for help in the problem preparation.
- AnimeshSinha1309, madlad, pk1210 for contributing to the initital set of ideas for the problems .
- Ashishgup for pushing our contest in front of the Codeforces coordinators .
- And finally, MikeMirzayanov for the great platforms, Codeforces and Polygon.
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:
Please make strong pretests this time.
Is it rated?
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.
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.
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.
Is preet_t's problem really pretty?
wana waun waun wana waun waun wana waun
Knock knock modafaka
Why div2 only?
It is what it is.
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 .
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.
Codecraft-17 : Hackforces
Codecraft-18 : More Hackforces
CodeCraft-19 : Terrible Hackforces
There was room like this :
Codecraft-20 : ??
Why is it bad?
Incredible Database XO
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.
Whelp, not hackforces this time
I agree, it's not hackforces.
.
Hackforces eh m8?
2 years ago CodeCraft was combined round! Why did it downgrade to div2 only?
Sorry to disappoint, we didn't have sufficient interesting ideas for Div 1 exclusive problems.
make strong pretests so that we do not feel bad.hoping a nice contest and thanks to codeforces.
We have tried our best to make sure pretests are strong enough.
Alhamdulillah the contest was good
Indian round cool... Hope to learn new things...
Excited for this contest!
Interesting problems with strong pretests
hoping for a good round and rating increas
Indian Round after long time :)
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......
IIIT Hyderabad is diamond of india in coding.my Respect.
IIT Hyderabad may be the one, but just clarifying in case you are mistaken, we are IIIT Hyderabad.
Loaded for rocket launch.
OMG,i am afraid of attending this round now
As this is an Indian round, the correct way to say would be:
"OMG, i am afraid of giving this round now"
Codeforces $$$\times$$$
Hackforces $$$\surd$$$
stronger pretests this time pls
This contest won't be rated bc of bad pretests :P
I hope the round won't be like the HackCraft round before...
Also the order of the problems...
Anybody explain please, difference between rated and unrated contest? Thanks in advance.
If contest is unrated you can't get any point/you can't rank up...
I hope CodeCraft is as good as Minecraft
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!
Deleted
Hope for no accidents...Hacking is too terrible!!! QAQ
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?
Text of tasks in English?
True
I will not able to participate in this contest due to my exams ... feels so bad
you are so lucky!
)
thanks for one more good mathforces round!!!
Is C really this tough! or I'm the stupid one!!
Leaving this round 35mins before yay!!! XDXD
I am stuck in B but C was easier than I thought but I did terrible mistake beforehand.
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'.
Luckily I am out of competition so that my rating will not decrease.
I'm glad to know that there are at least 1525 math majors doing contest right now.
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".
Thank you very much for proving once again why Indians should never be trusted with contests in a prestigious platform like this.
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??
AB-Forces
AB Forces!
I don't see it bad IMO.
Could you explain your opinion?
Weird bug — My handle changed to swust5120175180 in the standings!?
I fell confident now (no offense) that I was able to do Problem C. Link : https://mirror.codeforces.com/contest/1316/submission/72456579
Cool. I was trying to pass FFT (I am stupid, wtf was I thinking) before giving up and moving to E.
Same, but then I saw constrains, and there is no way that FFT works in this constrains
You just aren't using a fast enough FFT :^)
https://mirror.codeforces.com/contest/1316/submission/72455655
from https://github.com/kth-competitive-programming/kactl/blob/master/content/numerical/FastFourierTransformMod.h
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
This could be even easier: just track two coefficients that are not a multiple of $$$p$$$.
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?
Does your test look like this? :
2 3 4
2 3
2 4 1
If is, it's not a valid test case since 4 is not a prime.
You're right, thx.
-
https://mirror.codeforces.com/blog/entry/74432?#comment-585904
How to solve C?
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.
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?
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.
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.
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?
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.
suppose a[] is 2 2 b[] is 2 3
2 * 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
a cant be 2 and 2 as their gcd will not be 1.
Yes! I got it!
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$$$.
Here is my solution : https://mirror.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.
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?
Sorry pls ignore my reply, I understood your solution now...
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.
Whats pretest 7 in C problem?
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!
smallest i such that ai%p!=0, smallest j such that bj%p!=0, answer is i+j.
observe the c(i+j), it will be (ai*bj + some other number which is divisible by p).
How can we be sure that the sum of other numbers is divisible by p?
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
Expand c(i+j) in terms of coefficient of a, b, there is only one term not divisible by p.
c(i+j) = ap * bq, if (p<i) then q>j and all ap are multiple of p. If qi and all bq are multiple of p.
any proof, that the some other number will be divisible by p?
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 \gt i$$$ and $$$Y \lt j$$$) or ($$$X \lt i$$$ and $$$Y \gt j$$$)
case $$$X \gt i$$$ and $$$Y \lt j$$$: since $$$Y \lt j$$$, then $$$B[Y]$$$ is divisible by $$$P$$$, hence $$$A[X] * B[Y]$$$ is divisible by $$$P$$$
case $$$X \lt i$$$ and $$$Y \gt j$$$: since $$$X \lt 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$$$
Thank you for the detailed explanation.
Great explanation.
As simple as that??
Does there exist any correctness proof for this?
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$$$).
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 :'(
gcd = 1 means they're all co-prime. But I didn't know how to use that to solve the problem.
It means that there is no prime that divides all coefficients of f(x) and g(x).
What you mean by all co-prime? It doesn't mean that for any i and j $$$gcd(a_i, a_j) = 1$$$
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.
Hint: gcd = 1 ensures that there is at least one coefficient not divisible by p in each polynomial
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;
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.
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.
Can someone tell me why my code in B times out?
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.
Screencast
Please upload your video in higher quality, its max is 360p only.
The 1080p is available now.
Youtube takes some time before videos become HD.
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.
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
Sorting — so simple, yet so effective
I googled for C 2 minutes before ending and got AC. (https://imgur.com/a/NXx553s)
What is the solution of C?
https://mirror.codeforces.com/blog/entry/74432?#comment-585757
What did you googled?
C even did not understand the question. It is a math riddle, I am sure there are people happy with that. Not me.
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?
T-shaped tetris is possible!! for example -
RDL
XUX
that was I missing.
Good point, edited. It seems that we only need eventually periodic.
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!
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.
How to solve E?
Can somebody tell a counter case for my code of D. It failed at pretest 9. https://mirror.codeforces.com/contest/1316/submission/72455182
Is it possible to solve E faster than $$$O(p^2\cdot 2^p\cdot n)$$$?
$$$O(nlogn+p\times 2^{p}\times n)$$$ with SoS DP?
O(n * 2 ^ p * p) with standard dp
So bad,My fft don't solve div2 C!!! I think it maybe overflow
https://mirror.codeforces.com/blog/entry/74432?#comment-585757. No need of fft
thanks,but FFT also get ac
https://mirror.codeforces.com/contest/1316/submission/72454944
Why n^2 give tle in B
probably because you are not using '+=' for the string concatenation
I also got a tle. Optimized a bit (still n^2) and pretests were passed. Don't know why?
LOL, B was much harder than it should've been, I solved E faster than B! XD
Can you explain how did you solve E?
why was there a D just why
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.
To me it's ABodeforces...
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?
Just why ? Why give such braindead heavy implementing problem like D.
It's really hard to implement it precisely, even though the code "only" around 180 lines.
(well at least for me)
How to solve D?
what a shitty day, IRS scamming at its finest
What is IRS?
How to solve F?
I don't believe I'm asking this, how to solve B?
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..
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!
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
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://mirror.codeforces.com/contest/1305/submission/72330015
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...
No, it should not pass.
It would depends on his divide-and-conquer method. For example, some of my friends considered resorting to fft on problem C.
have a look at this. link to another comment
In B, O(n^2) solution will have 10^9 operations while time limit is 1 seconds only, why it is not giving tle.?
N is max bounded by 5000 . So max operations won't be 10^9
there will be a loop for test cases outside n^2 and max bound of t is also 5000
"It is guaranteed that the sum of n over all test cases does not exceed 5000."
Oh..Thanks.!
Why will $$$O(n^2)$$$ have $$$10^9$$$ operations? $$$n$$$ is up to 5000
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.
will this include loop for test cases also..?
Yep, I asked him to prove he was wrong, of course I see $$$5000^2$$$ is about $$$10^7$$$
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.
Then why this code timed out? Here
Look at your make_string complexity. It's bigger than $$$O(n)$$$ since reverse() is $$$O(n)$$$
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.
Can you explain it thoroughly?
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 + a
which is never divisible by p.
Where, k is some integer, p is a prime, a is not divisible by p.
Here's an example where this doesn't seem to work. What am I missing?
Given:
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
let h(x)=summation_from_0_to_n+m-2(cr*x^r) \n
calculate c2. \n
c2=15*2*x^2 + 10*2*x^2 + 3*x*2*x. \n
c2=56*x^2; \n
hence the ans is 2:^)) \n
if you didn't understand try calculating every term of h(x).
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.
i think first power which is not divisible by p is important. \n
if 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, \n
and 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
:^)
Do we need FFT for polynomial multiplication in C?
I was thinking of solving C but didn't know FFT implementation.
No fft isn't the desired solution.
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?
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 .
Why do you take theoroms and make questions out of them . Stupid C really. https://imgur.com/a/NXx553s
Why you google every time during the contest ?!!
I did not. I got this link after contest.
Then it's fine !!
Well, you can make a theorem about anything. Any observation for an ad-hoc problem could be called "theorem".
Am I the only one who left A and B first and solved C then moved to A and don't even saw B.
How to solve problem B?
Construct new string for every $$$k$$$, take minimal
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
No need to sort, just take minimum
You will have to sort, I think, if there are equals Strings we would only save the ones with smaller k value.
Just take first minimum. I solved without sorting
ohhhhhhhhhhhh,how stupid I am
thx a lot TUT
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_r
where,
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.
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 yourbestSringand update it whengeneratedString < bestString. Complexity will be O(N^2)Yeah true, but still my solution passed in just
46 ms. Maybe the test cases were pretty chill.How to solve Problem B?
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
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]) ?
72449591 You can look this. I hope this can help you
Is it intended to counter Treap's stuff in F? It is even harder than offline solution :)
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.
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.
task C is great enough to look for some stable and fast fft model xD
btw, really enjoy these tasks! thanks for that
I don't get the comments above criticising problem C. It was a brilliant observation/ad-hoc problem.
it is actually Gauss's lemma
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.
yeah, and thats exactly how this lemma was proved :D
Its a math student jerk off thing. For me not a programming problem, but a math riddle, the main concern is understanding the question.
Math is very much a part of competitive programming. Combinatorics and Number Theory questions, involving no other algorithms, are frequently asked in contests.
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.
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.
I think problem C is a good ad-hoc problem. Beside, it actually asked us to prove Gauss's lemma.
My randomized C solution will fail on this case:
Thanks I saved my ratings
Can you please tell me your approach? It looks interesting but I don't get it.
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.
Nice, my also was hacked)
System testing even took more time than the total duration of contest :)
How to solve B in O(n^2)?
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.
My solution https://mirror.codeforces.com/contest/1316/submission/72433203
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://mirror.codeforces.com/contest/1316/submission/72450457
You had to give the smallest value of k, you never consider that.
I wonder what should be constraint so FFT solution passes on C...
If n,m <= 1e5, I think O(nlogn) FFT solution should pass.
i dont think so. constrains should be lower for O(nlogn) to work
when the scoring will be announced??
Yay! I solved three problems in Div2 for the first time!!! :D
https://mirror.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
See this loop from your submission:
You add the indices of every $$$a_i$$$ where $$$p$$$ doesn't divide $$$a_i$$$, instead of only adding the first index.
wow thanks, I'm an idiot.
Screencast with commentary
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters and update them again!
Thank You :)
Btw I found you a cheater, I think.
https://mirror.codeforces.com/contest/1316/submission/72434554
The hack looks rather intentional.
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.
Deleted
When the editorials will be available?
https://mirror.codeforces.com/contest/1316/submission/72475791
I am getting wrong answer on testcase 157 by submitting the code mentioned in the link. Can anyone please tell me why is it so?
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 .
it is written in the question you could pick any coefficient though which is not divisible by p!.Not just the first one!
In question C, why is the sum of other numbers not an integral multiple of P?
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.
I see. Thank you very much.
Can anyone please explain problem "B"???I couldn't even understand the tutorial.
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.
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 .
There is a little mistake in case of k=4...Here the string will be BA'...Whatever I understand...Thank you so much.
Right
Nice.
Why does simply doing FFT give me a wrong answer on test 7 of C? Anyone else submitted using FFT?
May because long long integer overflow by using FFT，you can have a try with NTT.
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
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.