shaanknight's blog

By shaanknight, history, 8 months ago, In English

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

  1. tmwilliamlin168
  2. kefaa2
  3. natsugiri
  4. Golovanov399
  5. Egor

Div 2

  1. Kazusa
  2. Zetro
  3. I-Love-Islam
  4. DraqonLore
  5. ix35

UPD 3:

Editorial

Announcement of CodeCraft-20 (Div. 2)
 
 
 
 
  • Vote: I like it
  • +432
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +98 Vote: I do not like it

Please make strong pretests this time.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    Is it rated?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +39 Vote: I do not like it

      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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      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.

»
8 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Is preet_t's problem really pretty?

»
8 months ago, # |
  Vote: I like it +28 Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +56 Vote: I do not like it

Why div2 only?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It is what it is.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +104 Vote: I do not like it

    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 .

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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.

»
8 months ago, # |
  Vote: I like it +209 Vote: I do not like it

Codecraft-17 : Hackforces

Codecraft-18 : More Hackforces

CodeCraft-19 : Terrible Hackforces

There was room like this :

Codecraft-20 : ??

»
8 months ago, # |
  Vote: I like it +52 Vote: I do not like it

2 years ago CodeCraft was combined round! Why did it downgrade to div2 only?

»
8 months ago, # |
  Vote: I like it +21 Vote: I do not like it

make strong pretests so that we do not feel bad.hoping a nice contest and thanks to codeforces.

»
8 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Indian round cool... Hope to learn new things...

»
8 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Excited for this contest!

»
8 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Interesting problems with strong pretests

hoping for a good round and rating increas

»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Indian Round after long time :)

»
8 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

IIIT Hyderabad is diamond of india in coding.my Respect.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    IIT Hyderabad may be the one, but just clarifying in case you are mistaken, we are IIIT Hyderabad.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Loaded for rocket launch.

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

OMG,i am afraid of attending this round now

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    As this is an Indian round, the correct way to say would be:
    "OMG, i am afraid of giving this round now"

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces $$$\times$$$
Hackforces $$$\surd$$$

stronger pretests this time pls

»
8 months ago, # |
  Vote: I like it -52 Vote: I do not like it

This contest won't be rated bc of bad pretests :P

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the round won't be like the HackCraft round before...
Also the order of the problems...

»
8 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Anybody explain please, difference between rated and unrated contest? Thanks in advance.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    If contest is unrated you can't get any point/you can't rank up...

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If contest is rated your rating changes but not the same in unrated where rating doesn't change.

»
8 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I hope CodeCraft is as good as Minecraft

»
8 months ago, # |
  Vote: I like it +197 Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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!

»
8 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Deleted

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope for no accidents...Hacking is too terrible!!! QAQ

»
8 months ago, # |
  Vote: I like it +31 Vote: I do not like it

»
8 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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?

»
8 months ago, # |
  Vote: I like it -20 Vote: I do not like it

I hope the problemsettters are not fake IRS workers.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Text of tasks in English?

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I will not able to participate in this contest due to my exams ... feels so bad

»
8 months ago, # |
  Vote: I like it +73 Vote: I do not like it

![ ]()

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

thanks for one more good mathforces round!!!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is C really this tough! or I'm the stupid one!!

Leaving this round 35mins before yay!!! XDXD

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I am stuck in B but C was easier than I thought but I did terrible mistake beforehand.

»
8 months ago, # |
  Vote: I like it -51 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -33 Vote: I do not like it

    Luckily I am out of competition so that my rating will not decrease.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +129 Vote: I do not like it

    I'm glad to know that there are at least 1525 math majors doing contest right now.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it -39 Vote: I do not like it

Thank you very much for proving once again why Indians should never be trusted with contests in a prestigious platform like this.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

AB-Forces

»
8 months ago, # |
Rev. 3   Vote: I like it -35 Vote: I do not like it

AB Forces!

»
8 months ago, # |
  Vote: I like it +45 Vote: I do not like it

Weird bug — My handle changed to swust5120175180 in the standings!?

»
8 months ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

;)

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve C?

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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?

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like 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$$$.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry pls ignore my reply, I understood your solution now...

»
8 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats pretest 7 in C problem?

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same thought, What was the logic to solve it?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    smallest i such that ai%p!=0, smallest j such that bj%p!=0, answer is i+j.

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      observe the c(i+j), it will be (ai*bj + some other number which is divisible by p).

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How can we be sure that the sum of other numbers is divisible by p?

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +12 Vote: I do not like it

          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

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Expand c(i+j) in terms of coefficient of a, b, there is only one term not divisible by p.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is there any proof?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        any proof, that the some other number will be divisible by p?

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it +24 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you for the detailed explanation.

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Great explanation.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      As simple as that??

      Does there exist any correctness proof for this?

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    gcd = 1 means they're all co-prime. But I didn't know how to use that to solve the problem.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      It means that there is no prime that divides all coefficients of f(x) and g(x).

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What you mean by all co-prime? It doesn't mean that for any i and j $$$gcd(a_i, a_j) = 1$$$

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Hint: gcd = 1 ensures that there is at least one coefficient not divisible by p in each polynomial

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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;

  • »
    »
    8 months ago, # ^ |
    Rev. 4   Vote: I like it +2 Vote: I do not like it

    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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why my code in B times out?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it +30 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    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

»
8 months ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

I googled for C 2 minutes before ending and got AC. (https://imgur.com/a/NXx553s)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C even did not understand the question. It is a math riddle, I am sure there are people happy with that. Not me.

»
8 months ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it

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?

  • »
    »
    8 months ago, # ^ |
    Rev. 6   Vote: I like it +1 Vote: I do not like it

    T-shaped tetris is possible!! for example -
    RDL
    XUX
    that was I missing.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Good point, edited. It seems that we only need eventually periodic.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve E?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody tell a counter case for my code of D. It failed at pretest 9. https://codeforces.com/contest/1316/submission/72455182

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve E faster than $$$O(p^2\cdot 2^p\cdot n)$$$?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    $$$O(nlogn+p\times 2^{p}\times n)$$$ with SoS DP?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    O(n * 2 ^ p * p) with standard dp

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So bad,My fft don't solve div2 C!!! I think it maybe overflow

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    probably because you are not using '+=' for the string concatenation

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also got a tle. Optimized a bit (still n^2) and pretests were passed. Don't know why?

»
8 months ago, # |
  Vote: I like it +53 Vote: I do not like it

LOL, B was much harder than it should've been, I solved E faster than B! XD

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

why was there a D just why

»
8 months ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice! I need this kind of intuition in min time. Maybe gotta do some projecteuler questions.

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

To me it's ABodeforces...

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Counterexample
    One possible answer is
»
8 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Just why ? Why give such braindead heavy implementing problem like D.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It's really hard to implement it precisely, even though the code "only" around 180 lines.

    (well at least for me)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

»
8 months ago, # |
  Vote: I like it -28 Vote: I do not like it

what a shitty day, IRS scamming at its finest

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve F?

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I don't believe I'm asking this, how to solve B?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In B, O(n^2) solution will have 10^9 operations while time limit is 1 seconds only, why it is not giving tle.?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    N is max bounded by 5000 . So max operations won't be 10^9

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      there will be a loop for test cases outside n^2 and max bound of t is also 5000

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        "It is guaranteed that the sum of n over all test cases does not exceed 5000."

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Why will $$$O(n^2)$$$ have $$$10^9$$$ operations? $$$n$$$ is up to 5000

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        will this include loop for test cases also..?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yep, I asked him to prove he was wrong, of course I see $$$5000^2$$$ is about $$$10^7$$$

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Then why this code timed out? Here

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Look at your make_string complexity. It's bigger than $$$O(n)$$$ since reverse() is $$$O(n)$$$

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain it thoroughly?

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
            Rev. 2   Vote: I like it +1 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do we need FFT for polynomial multiplication in C?

I was thinking of solving C but didn't know FFT implementation.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No fft isn't the desired solution.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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 .

»
8 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Why do you take theoroms and make questions out of them . Stupid C really. https://imgur.com/a/NXx553s

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only one who left A and B first and solved C then moved to A and don't even saw B.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem B?

»
8 months ago, # |
  Vote: I like it -28 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    No need to sort, just take minimum

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You will have to sort, I think, if there are equals Strings we would only save the ones with smaller k value.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just take first minimum. I solved without sorting

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ohhhhhhhhhhhh,how stupid I am

      thx a lot TUT

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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)

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yeah true, but still my solution passed in just 46 ms. Maybe the test cases were pretty chill.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem B?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't it total operations AND length of the string that is supposed to be odd?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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]) ?

»
8 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Is it intended to counter Treap's stuff in F? It is even harder than offline solution :)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

task C is great enough to look for some stable and fast fft model xD

btw, really enjoy these tasks! thanks for that

»
8 months ago, # |
  Vote: I like it +79 Vote: I do not like it

I don't get the comments above criticising problem C. It was a brilliant observation/ad-hoc problem.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is actually Gauss's lemma

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        yeah, and thats exactly how this lemma was proved :D

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -39 Vote: I do not like it

    Its a math student jerk off thing. For me not a programming problem, but a math riddle, the main concern is understanding the question.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Math is very much a part of competitive programming. Combinatorics and Number Theory questions, involving no other algorithms, are frequently asked in contests.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah it's a lemma https://imgur.com/a/NXx553s

»
8 months ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

I think problem C is a good ad-hoc problem. Beside, it actually asked us to prove Gauss's lemma.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please provide contest Material(solutions)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone tell me whats wrong with this solution For 'B'? Code- https://codeforces.com/contest/1316/submission/72450457

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please tell me your approach? It looks interesting but I don't get it.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice, my also was hacked)

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

System testing even took more time than the total duration of contest :)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B in O(n^2)?

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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://codeforces.com/contest/1316/submission/72433203

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You had to give the smallest value of k, you never consider that.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Construct new string for every k, take minimal

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder what should be constraint so FFT solution passes on C...

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    If n,m <= 1e5, I think O(nlogn) FFT solution should pass.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i dont think so. constrains should be lower for O(nlogn) to work

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

when the scoring will be announced??

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Yay! I solved three problems in Div2 for the first time!!! :D

»
8 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See this loop from your submission:

    for(ll i=0;i<n;i++){
        cin>>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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wow thanks, I'm an idiot. I wonder how it passed 6 test cases though

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
8 months ago, # |
  Vote: I like it +23 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it +26 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters and update them again!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank You :)

    Btw I found you a cheater, I think.

    https://codeforces.com/contest/1316/submission/72434554

    The hack looks rather intentional.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

  • »
    »
    8 months ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it

    Deleted

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

When the editorials will be available?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it is written in the question you could pick any coefficient though which is not divisible by p!.Not just the first one!

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In question C, why is the sum of other numbers not an integral multiple of P?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain problem "B"???I couldn't even understand the tutorial.

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 .

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is a little mistake in case of k=4...Here the string will be BA'...Whatever I understand...Thank you so much.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does simply doing FFT give me a wrong answer on test 7 of C? Anyone else submitted using FFT?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the Editorial on time.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did my rating got deducted even after submitting the right code?