shaanknight's blog

CodeCraft-20 (Div. 2)
By shaanknight, history, 5 years 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, 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

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

Comments Comments (262)
| Write comment?
»
5 years ago, # |
  Vote: I like it +98 Vote: I do not like it

Please make strong pretests this time.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    Is it rated?

    → Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Is preet_t's problem really pretty?

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Why div2 only?

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

    It is what it is.

    → Reply
  • »
    »
    5 years 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 .

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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 : ??

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

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

    → Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it +54 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Excited for this contest!

→ Reply
»
5 years 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

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Indian Round after long time :)

→ Reply
»
5 years 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......

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Loaded for rocket launch.

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

OMG,i am afraid of attending this round now

→ Reply
  • »
    »
    5 years 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"

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

stronger pretests this time pls

→ Reply
»
5 years ago, # |
  Vote: I like it -52 Vote: I do not like it

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

→ Reply
»
5 years 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...

→ Reply
»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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...

    → Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I hope CodeCraft is as good as Minecraft

→ Reply
»
5 years ago, # |
  Vote: I like it +197 Vote: I do not like it

→ Reply
»
5 years 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!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Deleted

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

→ Reply
»
5 years 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?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Text of tasks in English?

→ Reply
»
5 years 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

→ Reply
»
5 years ago, # |
  Vote: I like it +73 Vote: I do not like it

![ ]()

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

thanks for one more good mathforces round!!!

→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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'.

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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".

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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??

    → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

AB-Forces

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -35 Vote: I do not like it

AB Forces!

→ Reply
»
5 years ago, # |
  Vote: I like it +45 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
    • »
      »
      »
      5 years 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

      → Reply
  • »
    »
    5 years 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$$$.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is my solution : https://codeforces.net/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.

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats pretest 7 in C problem?

→ Reply
»
5 years 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!

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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).

      → Reply
      • »
        »
        »
        »
        5 years 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?

        → Reply
        • »
          »
          »
          »
          »
          5 years 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

          → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years 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$$$

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you for the detailed explanation.

            → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Great explanation.

            → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      As simple as that??

      Does there exist any correctness proof for this?

      → Reply
      • »
        »
        »
        »
        5 years 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$$$).

        → Reply
        • »
          »
          »
          »
          »
          5 years 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 :'(

          → Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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).

      → Reply
    • »
      »
      »
      5 years 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$$$

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
  • »
    »
    5 years 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

    → Reply
  • »
    »
    5 years 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;

    → Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Screencast

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years ago, # |
← Rev. 5   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)

→ Reply
»
5 years 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.

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      5 years 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!

      → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve E?

→ Reply
»
5 years 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.net/contest/1316/submission/72455182

→ Reply
»
5 years 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)$$$?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

    → Reply
»
5 years 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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1316/submission/72454944

Why n^2 give tle in B

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years 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?

    → Reply
»
5 years 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

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

why was there a D just why

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

To me it's ABodeforces...

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Counterexample
    One possible answer is
    → Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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)

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
»
5 years ago, # |
  Vote: I like it -28 Vote: I do not like it

what a shitty day, IRS scamming at its finest

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve F?

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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..

    → Reply
    • »
      »
      »
      5 years 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!

      → Reply
  • »
    »
    5 years 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

    → Reply
  • »
    »
    5 years 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.net/contest/1305/submission/72330015

    → Reply
»
5 years 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...

→ Reply
»
5 years 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.?

→ Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
      • »
        »
        »
        »
        5 years 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."

        → Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        will this include loop for test cases also..?

        → Reply
      • »
        »
        »
        »
        5 years 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$$$

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Then why this code timed out? Here

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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)$$$

            → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain it thoroughly?

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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

        → Reply
        • »
          »
          »
          »
          »
          5 years 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).

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years 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
              :^)

              → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No fft isn't the desired solution.

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years 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 .

        → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Why you google every time during the contest ?!!

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    Well, you can make a theorem about anything. Any observation for an ad-hoc problem could be called "theorem".

    → Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem B?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Construct new string for every $$$k$$$, take minimal

    → Reply
»
5 years 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

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

    No need to sort, just take minimum

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just take first minimum. I solved without sorting

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ohhhhhhhhhhhh,how stupid I am

      thx a lot TUT

      → Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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)

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem B?

→ Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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]) ?

      → Reply
»
5 years 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 :)

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is actually Gauss's lemma

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

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

        → Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

          → Reply
»
5 years 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.

→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice, my also was hacked)

    → Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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.net/contest/1316/submission/72433203

    → Reply
    • »
      »
      »
      5 years 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.net/contest/1316/submission/72450457

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

when the scoring will be announced??

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

https://codeforces.net/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

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Screencast with commentary

→ Reply
»
5 years 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!

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

When the editorials will be available?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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 .

    → Reply
    • »
      »
      »
      5 years 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!

      → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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 .

    → Reply
»
5 years 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?

→ Reply