Блог пользователя shaanknight

Автор shaanknight, история, 4 года назад, По-английски

Hello Codeforces!

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

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

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

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

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

Wish you luck and hope you like the problems !!

UPD 1:

Score-Distribution

500-1000-1500-1750-2250-2500

UPD 2:

Congratulations to the winners of the round.

Div 1

  1. tmwilliamlin168
  2. 244mhq
  3. natsugiri
  4. Golovanov399
  5. Egor

Div 2

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

UPD 3:

Editorial

  • Проголосовать: нравится
  • +432
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +98 Проголосовать: не нравится

Please make strong pretests this time.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -16 Проголосовать: не нравится

    Is it rated?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -21 Проголосовать: не нравится

    IMO pretests are sometimes too strong these days (especially with multitest), rendering hacking virtually impossible. I'd actually prefer to see a contest where it can pay off to search the room for hacks. As for now, sadly, this feature, once a funny part of Codeforces contests, is becoming less and less usable.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +39 Проголосовать: не нравится

      Hacking was never funny nor was it usable, it was always just a swarm of edge cases on div2 B and a rush to grab hacks among the participants in the room. It's unfair and giving points for hacks should be disabled.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +20 Проголосовать: не нравится

      It is true that the ratio of system failure has decreased on average compared to a few years ago. However, we must consider that the number of participants has greatly soared, which means that hacks have become more effective.

      I do not claim that the points from hacks is improper. Hacks are fun! Nevertheless, severely weak pretests might cause disruptive scoreboards, since hacking structure usually follows a-few-winner-takes-it-all.

      The main source of points should be the accepted solutions, not the hacks.

»
4 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Is preet_t's problem really pretty?

»
4 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

Why div2 only?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    It is what it is.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +104 Проголосовать: не нравится

    Honestly, we intended to make a Div 1 + Div 2 round when we started, but we just had 2 problem ideas for the Div1 exclusive problems , which didn't seem to be interesting enough , hence we left the plan of combined round and rather focused on arranging a good Div-2 only round . We hope people find the current set of problems interesting .

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      Good idea. Better to make a round the way you can than to force difficulty up with something boring just so it can be div1.

»
4 года назад, # |
  Проголосовать: нравится +209 Проголосовать: не нравится

Codecraft-17 : Hackforces

Codecraft-18 : More Hackforces

CodeCraft-19 : Terrible Hackforces

There was room like this :

Codecraft-20 : ??

»
4 года назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +51 Проголосовать: не нравится

    Sorry to disappoint, we didn't have sufficient interesting ideas for Div 1 exclusive problems.

»
4 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Excited for this contest!

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Interesting problems with strong pretests

hoping for a good round and rating increas

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Indian Round after long time :)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Click the "Felicity, IIIT Hyderabad" link in this announcement above.

And then, in this website, click the icon located at the top-right corner of the page.

And then......

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +61 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Loaded for rocket launch.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

OMG,i am afraid of attending this round now

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -20 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

stronger pretests this time pls

»
4 года назад, # |
  Проголосовать: нравится -52 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

I hope CodeCraft is as good as Minecraft

»
4 года назад, # |
  Проголосовать: нравится +197 Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Oh my gosh another codeforeces round, It's so exciting, can't wait but honestly when will be round for slower and disabled contestants? (where all the problems are easy and time is not so decisive factor, and you really guys are reading all that math equations so easly?) Anyway good luck guys!

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

Deleted

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

I am (and not only I am, honestly) participant "in competition" with rating greater than 2099 now. Should I re-register to participate out of competition?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Text of tasks in English?

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

![ ]()

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

thanks for one more good mathforces round!!!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Leaving this round 35mins before yay!!! XDXD

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -51 Проголосовать: не нравится

I dont know if the difficulty of problem C is proper for div.2 C . Seemingly it requires some math knowledge that only students major in Maths learn. And it is my 1st time to fail at div.2 C after I became 'Master'.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -33 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +129 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The logic is Hell Simple.

    It might not have clicked to you, then.

    But, yeah, the problem seems suitable for Div.2 C Problem.

    In fact, many people were able to do "C" before "B".

»
4 года назад, # |
  Проголосовать: нравится -39 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Like how the hell does nationality come in? If it's a bad contest, it's a bad contest. A mathy one, then it's a mathy one. Blame the problem setters. Downvote the announcement. But why the hell are you pulling their nationality into the picture??

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

AB-Forces

»
4 года назад, # |
Rev. 3   Проголосовать: нравится -35 Проголосовать: не нравится

AB Forces!

»
4 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve C?

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Observe that each term of the resultant polynomial is a sum of product of some terms taken from polynomial a and polynomial b, for ex — x^3 can be x^3.c or x^2.x.For the term to be divisible by p all the sums must be divisible by p. Find a term from x not divisible by p and same from y when you multiply them you get degree t(x)+t(y) and it is sure to be not divisible by p.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I couldn't understand

      "For the term to be divisible by p all the sums must be divisible by p" Why this is correct?

      p = 5, a = 2, b = 3

      a and b are not divisible by p but a + b is divisible by p. Am I missing any part of your comment?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        Well yeah, you need the lowest degree terms that are not divisible from both polynomials as when you take lowest degree terms you ensure that any other terms will be that would be formed will be divisible by p because to make t(x) + t(y) if you take a term greater than t(x) from x then you will have to lower t(y) which will ensure it is divisible by p, vice versa also being true.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Well, wait my solution also passes because the highest degree also has a similar proof wherein the terms greater than t(x) ensure that the other sums are divisible by p.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      How can it be proved that the sum is not divisible by p. Say, we get the individual sum as x and p-x , which are not divisible by p. But their sum is divisible by p.

      Or,Is this case not possible at all?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        p --->number is divisible by p.

        np -->number is not divisible by p.

        A=[p,p,p,p,p,np]

        B=[p,p,p,p,p,p,p,p,p,np]

        Say the first index in array A having np is i,and first index in array B having np is j. We claim that answer is i+j.

        Let's pick a element which has index greater than i and not divisible by p from Array A, now, we are forced to pick a element having index less than j of Array B ,in order to get the sum equals to i+j. Now, A[i]*B[j] will be divisible by p,since B[j] is divisible by p. Therefore we can't pick two elements , both of them who are not divisible by p,and the sum of indices being i+j.

        I hope ,this is the logic behind the soln.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Transform each coefficient to $$$1$$$ if it is not divisible by p, and $$$0$$$ if it is. There will be $$$a_i$$$, $$$b_j$$$ such that $$$a_i = b_i = 1$$$. The answer is $$$i+j$$$.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Here is my solution : https://codeforces.com/contest/1316/submission/72456579 Find an element in A not divisible by p and same in B. Ans will be the sum of index of those elements.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      A=[1,3,1] B=[1,3,1] p = 11 3 % 11 = 3 Therefore your answer would output 2,

      But actually (1 + 3x + x^2) * (1+3x+x^2) = 1 + 3x + x^2 + 3x + 9x^2 + 3x^3 + x^2 + 3x^3 + x^4 = 1 + 6x + 11x^2 + 6x^3 + x^4 And 11 is divisible by 11.

      How come your soluton is correct?

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

How to solve E ? I had following idea — Sort by 'a' and then do dp[i][mask] = maximum score till i'th index such that 'mask' position of players are selected. Add it to audience if possible. This gave WA-16.

Edit — Caught the error.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whats pretest 7 in C problem?

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Any hints on how to approach C? Hitting TLE on pretest 7.

I am not able to simplify the question further. I can't find the relation between GCD(, ..., ) = 1 and prime p. Does prime p have any significance in the logic or solution behind this question? Also, does GCD() = 1 has any importance in the solution?

p.s. Not able to solve Div2C after a long, long time. It hit me so hard!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +12 Проголосовать: не нравится

          power will be (i+j) for x^(i+j) you will be chossing either one or more value less than i from first polynomial or one or more value less than j. since i & j are smallest non-divisible, rest all terms will be divisible. Hence their sum will not be divisible

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

          let minimum index of some number not divisible by $$$P$$$ in set $$$A$$$ $$$= i$$$

          let minimum index of some number not divisible by $$$P$$$ in set $$$B = j$$$

          $$$c(i+j) = (A[i] * B[j]) + (A[i-1] * B[j+1]) + (A[i+1] * B[j-1]) + (A[i-2] * B[j+2]) + .... $$$

          notice how all terms except for $$$A[i] * B[j]$$$ (let's call any term of which $$$A[X] , B[Y]$$$) have ($$$X > i$$$ and $$$Y < j$$$) or ($$$X < i$$$ and $$$Y > j$$$)

          case $$$X > i$$$ and $$$Y < j$$$: since $$$Y < j$$$, then $$$B[Y]$$$ is divisible by $$$P$$$, hence $$$A[X] * B[Y]$$$ is divisible by $$$P$$$

          case $$$X < i$$$ and $$$Y > j$$$: since $$$X < i$$$ then $$$A[X]$$$ is divisible by $$$P$$$ and $$$A[X] * B[Y]$$$ is divisible by $$$P$$$

          conclusion: $$$A[i] * B[j]$$$ is the only term NOT divisible by $$$P$$$ if we pick minimum $$$i$$$ , $$$j$$$ for which $$$A[i]$$$ isn't divisible by $$$P$$$ and $$$B[j]$$$ isn't divisible by $$$P$$$

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      As simple as that??

      Does there exist any correctness proof for this?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        Yes, it is very easy to prove. Write the summation out modulo p for $$$x^{i+j}$$$ and you'll see that all terms except one of them are 0 (due to one of the factors being divisible by $$$p$$$).

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I don't know where my mind was during the contest. 5 mins later I look in my notebook and I realise I was going in the same direction but I don't know why i left this idea :'(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I will calculate gcd of constant term and coefficient of x, let the answer be g, then i will calculate gcd(g, coefficient of $$$x^2$$$) and set it to g and move on in this manner. gcd is calculated in this manner and the final g you get is 1 in both cases.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    The question is based on Gauss Lemma for Polynomials. https://en.wikipedia.org/wiki/Gauss%27s_lemma_(polynomial) You need to find two numbers each from ai and bj such that ai%p!=0 and bj%p!=0, ans is i+j;

  • »
    »
    4 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится

    If you are having TLE then you might want to check if you are using fast IO method or not.

    Thought process and proof of C :

    think about how c[0], c[1], c[2]... these are formed, c[0] = a[0]*b[0], c[1] = a[0]*a[1] + b[0]*b[1], c[2] = a[0]*b[2] + a[1]*b[1] + a[2]*b[0] ... c[n] = a[0]*b[n] + a[1]*b[n-1] + a[2]*b[n-2]...+a[n-1]*b[1] + a[n]*b[0]. You need to find ct which is not divisible by p, means ct = p*x + y, where x can be any integer and y % p != 0. So we find the very first coeffcient of f(x) and g(x) that is not divisible by p, let's call them a[i] and b[j] respectively. We know a[1],a[2]...a[i-1] and b[1],b[2]...b[j-1] all are divisible by p. If I choose ct to be the coefficient of x^(i+j) then ct = a[0]*b[i+j] + a[1]*b[i+j-1] ... a[i+j]*b[0]. Here every term has some part of a[0] to a[i-1] or b[0] to b[j-1] except for exactly one term that is a[i]*b[j] and neither a[i] or b[j] is divisible by p. And as p is a prime number and we are just multiplicating two numbers a[i]*b[j], hence it is not divisible by p. So ct can be written as ct = p*x + y. So coefficient of x^(i+j) is indeed our answer.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    GCD 1 makes it sure that at least one element is there which is not divisible by the given prime. So, the answer always exists.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    your code has complexity n^3. You are running a loop of size n, then inside there is a call to the function that is running another loop of size n, and inside there is reverse function that itself is of O(n) complexity.

»
4 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E? I couldn't deal with the necessity of keeping sets/vectors of all elements chosen as audience while trying to take i-th citizen as a member of the audience.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    sort the people by A in decreasing order dp(i, msk) = max try to take person i for each non taken position and iff (i — popcnt(msk)) < k then you can use him for support

»
4 года назад, # |
Rev. 5   Проголосовать: нравится +27 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

Problem D: go in two phases: the first phase make the connected component of sink point to the sink. In the second phase, do the similar with {-1,-1}'s, except make a "sink" be the circuit of size 2.

Is this a correct strategy?

  • »
    »
    4 года назад, # ^ |
    Rev. 6   Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think you can connect 2 adjacent cells whenever you can (so that they form a loop) and if some single cells remain, you can connect them to an existing adjacent loop. In such a way, as soon as it starts from that cell, on the first move it will go to the loop and after that, it will run infinitely!

      For example, if we had something like that:

      ...

      -.- (where — are occupied cells and . are infinite ones)

      You can connect the (1, 1) and (1, 2) squares to form a loop and the remaining could be directed on this loop, like this:

      LRL

      -U-

      We are 100% certain that this method will always work!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    For any {-1,-1}, it's enough to point it to a neighouring {-1,-1}. If there is none, no solution exists.

    Unfortunately, I got TLE because of an extremely dumb mistake (re-initialising the NxN visit matrix every iteration...), but I think this should work.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve E?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

why was there a D just why

»
4 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

C was actually quite interesting to me. If anyone still doesn't know how to solve, it is sufficient to take the first coefficient in both A and B that isn't divisible by $$$P$$$ and output the sum of their powers, call it $$$X$$$ (this is guaranteed to exists because of the gcd condition). To understand why this works, consider the summations of coefficients mod p. For every term in the summation besides the coefficients that we have taken, at least one term in the product will be divisible by $$$P$$$, thus all terms that contribute to the $$$X th$$$ power will evaluate to 0 except for the two that we have chosen which cannot be divisible by $$$P$$$, thus the coefficient in the multiplied polynomial will not be zero.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

To me it's ABodeforces...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone give me a counter example to my code on D? https://ideone.com/OgTmuL What I'm doing is: find all 'X's and branch off them by reversing the given instructions For the (-1, -1)'s, I group them in groups of two adjacent if possible and make them "look" at each other (For example: RL) Also how to solve B?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Counterexample
    One possible answer is
»
4 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    (well at least for me)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

what a shitty day, IRS scamming at its finest

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve F?

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Apparently finding all possible solutions and sorting them got past the pretests....... the hard part was finding the trick to find the solution without n^2. for me i just failed to realize that this solution wouldnt get tle..

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      I just realized that if you apply the K reverse operation on some string s all you have to do to is to compute s as s = s[k .. N] + s[1 ... k — 1] (the latter eventually reversed). Anyway, thank you!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For B, I think violence will time out, so I turned to finding the rule. After writing a few, I found that when I value K, the composition of strings after operation is like this. First, it is from a [k] to a [len]

    Then judge whether the parity of K and Len is the same, and then continue from a [1] to a [k-1]

    The difference is from a [k-1] to a [1]. I hope my approach can help you

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You need to find a way to quicken the loop over reversing all substrings.

    It is to rotate the whole string, and reverse the last k-1 chars if parity is odd. See solution codes https://codeforces.com/contest/1305/submission/72330015

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

In problem C, could somebody tell me if multiplying polynomials using divide and conquer method would get AC? I'm not sure of the complexity of this algo, but I couldn't implement it anyway...

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't know why people are complaining so much about C being mathforces.
I think it just required little bit of observation and a basic fact that: k*p + a is never divisible by p.
Where, k is some integer, p is a prime, a is not divisible by p.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain it thoroughly?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      let's say notations p — divisible by p; np — not-divisible by p.

      Now let the polynomials' coefficients look like this:
      a: p p p np p np p p p p ....
      b: p p p p p np p p p p ....

      Now you can see if you take the first occurrence of np in 'a' and first occurrence of np in 'b', in our case it is 3 and 5 respectively (0- indexing) .
      The term formed will be x^(3+5) = x^8.
      And the coefficient of this term in the resultant polynomial will be of the form: k*p + a
      which is never divisible by p.
      Where, k is some integer, p is a prime, a is not divisible by p.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Here's an example where this doesn't seem to work. What am I missing?

        Given:

        f(x): 5x^4 + 5x^3 + [2x^2] + [3x] + 10
        g(x): 5x^4 + 5x^3 + [2x^2] + [2x] + 15
        p: 5
        

        The expressions in [brackets] are not divisible by p. Specifically [2x] and [3x] are the first occurrences that are not divisible by 5.

        h(x) = f(x) * g(x), which will end up having (2x^2 * 2x) + (2x^2 * 3x) = 10x^3, which is divisible by p

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

            Thanks. So it seems that the key here is to take the first powers of x that are not divisible by p for both. Every other equivalent power of x is already a multiple of p, and hence won't impact.

            Any later coefficients that are not divisible by p are irrelevant, as their multiplication results in a higher power of x, which does not impact our answer.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Do we need FFT for polynomial multiplication in C?

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No fft isn't the desired solution.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Can you explain me why using FFT leads to TLE. imo the constraints should have passed in the given TL. Or am I missing something?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        Writing an optimal version of fft might even get you an AC on the problem , but since a lot of mod operations are involved , though O(N log N) a general fft code without optimisations takes slightly more time than 1.5 seconds to pass .

»
4 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem B?

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

Not only annoying B but annoying C this time :(

A understandable solution for problem B is to calculate all the possible strings for every k and sort them.
But the complexity seems a bit dangerous...

NO FST PLZ XD

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    No need to sort, just take minimum

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

    Just a bit of writing on paper and trying to find the pattern would have helped.
    You will find out for string s of size n and k,
    resultant string will be = (last n-k+1 chars) + string_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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      You don't even need to put them all in map. You can just keep a bestString, initialize it to the given string s. This is what you get if you pick k = 1. Then you just keep increasing k till n and generate the possible strings in the way you mentioned. Just compare your generated string with your bestSring and update it when generatedString < bestString. Complexity will be O(N^2)

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Problem B?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For B, I think violence will time out, so I turned to finding the rule. After writing a few, I found that when I value K, the composition of strings after operation is like this. First, it is from a [k] to a [len]

    Then judge whether the parity of K and Len is the same, and then continue from a [1] to a [k-1]

    The difference is from a [k-1] to a [1]. I hope my approach can help you

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think they raised the limit to allow it, there are treap solutions with 3.5s execution time. The problem is that if you have anything that makes the constant slightly bigger it's a ton of time: I used the problem to test splay tree and got 4.9s by inserting in the first way I thought of, then I optimized the insert after the contest to use one splay operation and it's 4s.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No, we did not intend to fail the treap solution. We had the offline segment tree solution that passes in 1.4 s. We raised the limit to allow certain other slow solutions but with same complexity . As tfg rightly mentioned, it's true if you have any part that's unoptimised it really takes a lot of time to pass.

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

btw, really enjoy these tasks! thanks for that

»
4 года назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    it is actually Gauss's lemma

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Maybe it is a named lemma. But I don't see the need to know the lemma beforehand — it can easily be solved by observing how the coefficient for each power of x is obtained.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -39 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        The question cannot be understood without in-depth knowledge of polynomials. The technical terms used make no sense without the appropriate context.

        This is different with most combinatorics and number theory problems, where concrete examples have to be calculated.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          No, all you need to know is how polynomials are multiplied, and some luck observing how that would help. Luck is always involved in observation-based questions like these. Can't help it.

          Knowing the lemma and proof beforehand, would allow you to quickly submit the solution. But it's not as if without knowing the lemma you are completely helpless. (I didn't even know that there is a lemma for this, until after the contest).

          Now you may claim that making a question completely on a named famous lemma might not be a good idea, and I don't disagree. But this does happen very often, so I wouldn't criticize this round specifically.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My randomized C solution will fail on this case:

n 2 2
1 1 1 1 1 ... 1
1 1

Thanks I saved my ratings

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Gather all indices which $$$a[i] \not \equiv 0 \bmod{p}$$$ and $$$b[j] \not \equiv 0 \bmod{p}$$$ each. Now just run random. In each iteration you will pick any two indices from the first list and the second list. Break if you find the correct answer.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Nice, my also was hacked)

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    There is an observation. If k is 1, then the string remains the same. If k is 2, then first character goes to the end of the string. If k is 3, then first two characters goes to the end of the string. So first k-1 characters will go to the last.

    So if we have ABCDE, then for k = 3, it will become CDEAB. But if we have ABCD, then for k = 3, it will be CDBA.

    Now the only thing to check is if the first k-1 characters that that are going to the last, will be reversed or not.

    They will be reversed if reversing operation is run odd times. So check if the n-k+1 is odd or not.

    My solution https://codeforces.com/contest/1316/submission/72433203

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

when the scoring will be announced??

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.com/contest/1316/submission/72467933 Why I am getting wrong answer in C testcase 7? Ignore the leftrotate and rightrotate, those were for last question xD

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

When the editorials will be available?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's because you intend to find the first coefficient that is not divisible by p , but you put r as 0 initially , so whenever there's a case when the first coefficient you are looking for is at power 0, you skip that one and pick up the next coefficient that's not divisible by p , as your r is still 0.

    Changing initial r as -1 and putting in the check , if r is -1 , only then assign r = i, the code should work .

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    The solution is you find the first i in first polynomial ( i can be from 0 to n-1 ) such that it's coefficient is not divisible by p. Since all other ak's from k = 0 to i — 1 are divisible by p , the entire thing that you put in initial paranthesis is divisible by p.

    Now we want a find a j in 2nd polynomial, similar to how we found i in first polynomial. Since now all other bk's from k = 0 to j — 1 are divisible by p , the entire thing that you put in second paranthesis is divisible by p .

    Now since ai is not divisible by p and bj is not divisible by p, ai*bj cannot be divisible by p since p is a prime. Hence the entire expression is not divisible by p because ai*bj is not divisible by p and all other terms are.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Consider any string str for modification for a chosen k and let us write str = AB , where A is the prefix of length k-1 and B is the suffix of length n-k+1.

    Now applying the modification, the modified string is either of form BA or BA' ( where A' is the reverse of the string A) based on the parity difference between k and n, i.e., (n-k)%2 .

    Consider str = "malice" . n = length of string = 6.

    • Now using k = 3, A = "ma" & B = "lice", the modified string is BA , i.e., "licema" . Parity difference is 1 here.
    • Now using k = 4, A = "mal" & B = "ice", the modified string is BA' , i.e., "icelam" . Parity difference is 0 here.

    I hope I haven't made any mistake in the example. I suggest taking a string and trying it out for yourself to note the observation. Understanding the way resultant string is obtained after modification in the 2 cases, we can actually obtain the modified string in O(n) for each k rather than O(n*n). Hence we can check for each k and find the lexicographically smallest string .

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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