atoiz's blog

Codeforces Round #666
By atoiz, history, 4 years ago, In English

(Translation: Hello)

We are very happy to invite you to take part in our contest, Codeforces Round 666 (Div. 1) and Codeforces Round 666 (Div. 2). The contest starts on Aug/30/2020 17:35 (Moscow time) and lasts 2 hours. In both divisions, there will be 5 problems for you to solve.

The problems were authored and prepared by JettyOller, DatVu, MofK, and me.

We are very grateful and would like to sincerely thank the following people for their assistance in preparing the round:

Finally, we would like to thank all of you for participating in the contest!

We have spent many months to brainstorm ideas, ended up discarding most of them, and finally chosen our best ideas to compose together this contest, so we hope you will enjoy our round! (and hope the Devil's Number won't haunt our round XD)

Good luck, have fun!

The score distribution will be announced later.

UPD1: Here is the score distribution:

Div. 1: 500 — 1000 — 1750 — 2250 — 2500

Div. 2: 500 — 1000 — 1250 — 1750 — 2500

Hope the long queue disappears soon :'(.

UPD2: Congratulations to the winners:

Div.1

  1. tourist
  2. Radewoosh
  3. aid
  4. ksun48
  5. Um_nik

Div.2

  1. chokottodake
  2. The_Noble_Brahman_Bison
  3. mickey639
  4. matt64
  5. Kai29

We apologize for the late editorial. Anyway, here it is: Editorial

  • Vote: I like it
  • +1146
  • Vote: I do not like it

Comments Comments (493)
| Write comment?
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Auto comment: topic has been updated by JettyOller (previous revision, new revision, compare).

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

    how do you edit others post?

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

      I'm coauthor

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

        I was not aware of this feature, but indeed you can now add co-authors of the blog post. Thanks

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

        The question levels jumped a lot from 1st to 2nd. 2 Div.

        Hoping gradual increase next time.

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

        Do co-authors receive upvote contribution?

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

          Good question! But the answer is no. I also hope cf will have this feature.

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

            But there are many problems with that. For example, someone may write a blog post and put all his friends as co-authors and they all get free contribution.

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

              The total contribution should be divided among the author and co-authors in some ratio, that will solve the problem :3

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

    https://codeforces.net/contest/1397/submission/91390761 This is my submission of question div2 B, and it returned the wrong answer in the eighth test case. I changed the compiler to VS C++ 2017, and the result was ACCEPTED! Can this question be judged again?At least, can you tell me where is my mistake? thank you very much. UPD:I changed the compiler to GNU C++14 and GNU C++17, and the results are accepted.

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

      There is one abs() outside namespace std and that abs() doesn’t support long long as argument. Change your code to std::abs() and it should work fine. 91432176

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

        Finally I know where the problem is,It took 421 ms on test case 5, and I finally know why. thank you very much.

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

        hey i have the doubt ,during contest my submission 91394398 got passed through pretest and i got the points of the 2nd question but after the contest ended it says your code fails at test case 27 and the points of 2nd question were removed . So the problem is that if during contest it didn't shows that code is wrong and pretests are passed then how would i able to correct it.

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

          There are pretests(which are tested during contest) and system test (real test, which are tested after contest is over). Pretest passed does not guarantee solution being accepted(= accepted in system test), since latter has larger test set.

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

      my code I get a strange bug in my code: In for loop,I wrote "if(temp<=0)break" to avoid overflow, but it doesn't work. Hope someone can give me explanation,thanks in advance.

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

        Signed integer overflow is undefined behaviour in the c++ specification. This lets the compiler prove that for all defined behaviour that if statement is true (as both temp and p are always >= 1) and optimises the check away (as either the values are small enough to be defined behaviour or it's undefined and the compiler can do whatever it wants).

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

As a Maripium fan, I want to start an orz chain.

Maripium orz.

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

Will this contest be Lucifer themed?

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

I tested this round when I was blue!!! xD

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

    After this round I will be blue!!! xD

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

      666 is the devils number, you will become orange :XD

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

      How good it'll be if you and me will have the same colour after this round.

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

        Almost impossible! As max rating change for him as per his current performances will be in rang almost -200 to +200 . Same applies to you as well Thus you were close to make that change , for you to reach blue and for him to reach blue there is a sufficient gap of 40 to 50 points. Anyways good luck to you for a big delta change !

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

    I tested this round when I was blue (well I still am).

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

    I am curious that how different country people conduct around together! As you are an Indian, the coordinator is from Canada, and the other guy belongs to a different country too!

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

      Well, there are specific Discord servers set up for co-ordination.

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

      its because we people have a wonderful sleep schedule :)

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +136 Vote: I do not like it

As an author of Round 666, I just want to say that right now I have exactly 666 friends on Codeforces!

Edit: Wow, it lasted a whole 3 minutes! Now I have 667...

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

    Plot Twist: This was a plan to get more friends using reverse psychology

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

OMG!!!! 666 round, so scared!! OMG

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

♫ 666 the Number of the Beast
Sacrifice is going on tonight ♫

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

WOW! palindrome round.

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

What’s devil’s number?

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

    666 is the devil's number or also referred to as 'number of the beast'

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

300iq seems like having an Asia tour on Internet and now he is arriving at Vietnam.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

Others: " I know coding "
LGMs: " Coding knows me "

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

→ Reply
»
4 years ago, # |
  Vote: I like it +76 Vote: I do not like it
  1. $$$666 = \sum\limits_{i=1} ^ {36} i$$$
  2. $$$666\times 69$$$ is a palindrome.
  3. Look at my profile picture. I also recorded a video of it happening.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    Also, 666 is the sum of squares of first seven primes

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

    One more, 666 is the sum of the first 144 decimals of π.

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

    Also 666 is the smallest positive number to have 3 sixes.

    Also, rotating 666 by 180 degrees clockwise/counterclockwise gives us 999 which is the smallest positive number to have 3 nines.

    And also , (180 degrees rotated 666)-(666) gives us 333 , which is the smallest positive number to have 3 threes.

    And also, ((180 degrees rotated 666)-(666))*666/(180 degrees rotated 666) gives us 222 which is the smallest positive number to have 3 twos.

    Okay,Now I'm tired. Basically we can generate all smallest numbers having 3 same digits using 666 and it's rotation. :P

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

    left-handed? cringe

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

    You use the mouse with your left hand, on the right side of the keyboard???

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

    Hexakosioihexekontahexaphobia is the fear of the number "666."

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

      Hippopotomonstrosesquippedaliophobia is the fear of long words

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

5 problems and div.1 & div.2 looks like round is going to be tough.

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

hope pretests passed => main tests passed

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

    It is almost impossible to do that unless you have pretests=tests and 0 hacks or the problem was solved by a very small number of people. For example, look at Codeforces Global Round 9. Here are the FST rates:

    A: 24/7357

    B: 10/6890

    C: 81/5225

    D: 35/2046

    E: 0/352(pretests=tests)

    F: 3/263

    G: 1/97

    H: 0/7(7 is a very small sample size)

    I: 0/0(duh)

    Overall, it makes sense to wish for strong pretests(but don't do it in a cf comment unless you want downvotes), but pretests passed -> main tests passed has almost no chance of happening.

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

      Does all hack-Cases are included in main tests or it depends on setter committee to decide which tests to include for system tests?

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

        One of the contest managers needs to press a button to add a hack into the system tests, but I don't think there's any case where that button wasn't pressed.

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

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

rip Devil

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

six six six

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

six six six, nice round, :) from VietNam with love <3

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

    nice round :) from LeToan Fan Club <3

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

How many languages does 300iq plan to master?

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

atoiz orz

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

Wow Rated contest after a long gap,Contest is seems to be very Interesting...

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

Hope for strong pretests.

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

This is the last contest I can play before school starts. (T_T)

Then I will become Candidate Master!

QQ图片20200829125713.gif

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

me when i see the image: chrome translate can translate image ???? :D ???? what is going on ????

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

Ya, From VietNam with Love. Good luck to the contest and for all

→ Reply
»
4 years ago, # |
← Rev. 12   Vote: I like it -42 Vote: I do not like it

excited for vietnamese contest

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

    vietnamese nha bro :))

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

      ok fine :)

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

      u'll get many downvotes because of speaking vietnamese here bro :v

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

        I didn't think that it's that big of a problem, based on this situation that they can easily find out that I was pointing out his spelling mistake :(

        I won't make that mistake again :))

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

húuuuuuuuu!!!!!!!!

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

If this round isn't DOOM themed I will lose all hope in humanity.

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

What is codeforces Round X? is it a new type of round?

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

    I think it implies that the date is decided for the contest but they still don't know if there will be additional rounds before that round, hence they have just named it Round X for the moment. If you see there is 18 days gap between Round 669 and Round X and most probably more rounds will be added in those 18 days gap, hence the name X.

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

      It is 2.5 hr long, so it is most probably a different type of round.

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

I hope to get the 666th place :)

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

Here it is! +666

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

Why score distributions are announced later? I don't know the reason. Can anyone tell me?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Again,the long queue issue ..Waiting my solution to be executed...[user:MkeMirzayanov] Please look into it

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

Is the codeforces queue long just to make it feel like a bad omen?

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

Hope your first contest will not be ruined by the long queue issue. I have submitted a solution one hour ago and still, it's in the queue. Hope it will be solved before the contest.

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

Looks like problems from hell.

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

Auto comment: topic has been updated by atoiz (previous revision, new revision, compare).

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

The queue disappeared!

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

Score distribution looks very scary.
B and C have difference of 250 points only
This indicates two types of round
1. Speed-forces
2. The hard one or unbalanced
Fingers crossed....

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

round-666 will be my 66 contest :D

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

Queue disappeared :) All the best everyone for the round.

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

To do well in this contest you have to listen to Iron Maiden not TWICE :P

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

Hakuna Matata!!

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

I had already got a correct answer in B at 34 minutes , I resubmitted now and it also passed but my timing has been updated according to present timing. PLease look into this

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

    you'd be judged based on your last submission time for any problem. it's part of the rules

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

      Why this rule? It just screwed my contest.

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

        Why did you resubmit?

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

        It makes sense in ICPC style contests where you get your submission's final verdict instantly to make your submissions past the AC submission irrelevant.

        Here, the final verdict is supposed to be kind of hidden until the end of the contest (you might get pretests passed on a wrong solution). Only last submission counts rule is to stop the abuse of submitting multiple solutions hoping one of them would pass.

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

    Meanwhile I cant even solve B

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

Is there a way to find the number of pretests in a problem?

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

Reading E is so fun. haha

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

This really is a cursed round

Upd: I had insane skill-issue at the time. My bad : )

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

After this round, I hate 666.

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

finally some interesting problems i love it!!

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

We have spent many months to brainstorm ideas, so we hope you will enjoy our round!

Duh

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

    ques2: 2 test case:: if c is 31625 then answer is 1999827749 (10^9-1+10^9-31625^1+10^9-31625^2)

    (it is less than given one and it also fulfill all condition)

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

Pretests for B :(

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

    Wrong answer on pretest 4 :( As the contest is finished, I tried finding a number such that (num^(n-1))>=(biggest element of the array) using binary search and then using this num as C to calculate the answer. Can anyone help.

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

      I did the same! I also tried for mean and weighted mean. What my friend did was nice. From the constraints it can be seen that ans lies from 1 to 1e6, he just did binary search in the entire range.

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

      Did the same bro, WA on pretest 4, my output comes smaller :D

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

Div1 C was really painful

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

    Agreed, statement was very long.

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

    The statement looked so painful that after solving all the other tasks in div2 I decided to quit without approaching it

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

    Disagree. The first impression was indeed painful, but the seemingly annoying parts disappeared quickly. Code is short and contains no strange special cases.

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

      Hmm, my code doesn't look that short. Maybe I'we just done things in a too complex way

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

      contains no strange special cases

      I'm very curious as to how you solved this problem, because my solution is case whack after case whack.

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

        Are the cases only on paper or in the code too? Now I'm kind of worried that I'll fail system tests.

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

          The cases are in my code, but I'm not sure if they're actually necessary or I'm just being a clown as usual.

          My code (apologies, I don't appear to know what line breaks are)
          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    I dare to disagree with you. I think Div1 C was a beautiful dp problem.

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

what is the pretest 4 of B.. Any guess ???

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

How to solve B?? Should we brute force all possible values of c and then find minimum cost??

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

    Yes

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

      Yeah but how do you set the limit on maximum value of c.My logic gave WA on pretest 4.

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

    Because c^i increases very fast, and the largest value of c is about sqrt(1e9). I brute force all value and exit when the cost is stop decreasing. View submission 91363571

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

How to solve D?

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

    Greedily. Actually I think it was easier than C

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    Passed pretest by always choosing the pile with the biggest value. Let's see if it passes the system test.
    UPD: It passed.

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

      Thanks. Actually constrains confused me a little bit.

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

    If max_value > sum — max_value answer is T, else answer depends on sum % 2.

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

      I also came up with the same observation but forgot to write simple 'else' keyword in one of the conditionals while implementing, this gave WA and I thought this approach is wrong coz I didn't have a proof :(
      Adding up on this, I thought div2D cannot have such an easy solution so I was convinced this is the wrong approach :'(.
      Do you know how to prove it?

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

        its more like, if the sum is odd then its T, else u look at your first condition, because the first player can always take an element from the max pile, if the sum is odd then he definately wins bcs they will either take all the stones or when a single pile is left, he will be the one to take the stone from it, making the second player unable to take from it, and if the sum is even, then if the first player doesnt always take the max element, then the second player is left with odd sum and an option to take maximums, so then the second player wins, so the first one has to take the maximums in every step, so if the maximum pile isnt bigger than the sum of the rest of the piles then the second player wins bcs, else the first player wins, this is roughly it

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

          Thanks, this makes sense. Btw how to prove it mathematically?

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

            well, u can prove this more thoroughly by proving the fact that the first player can always take the max, but i dont know how to bring math in here

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

Approach for B?

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

    Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.

    My submission 91391756

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

Nice problem, like this round

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

Please don't tell me that the constraints in D were so low only to confuse the heck out of me.

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

    there was a solution in O(sum(a)^3)

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

      Seeing the constraints made me think that the solution is dp. But greedy passed the pretests, can you explain the solution in O(sum(a)^3) ?

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

I feel like dumb after i fixed the bug for C that i was missing n = 1, just a minute before the contest. Really painful.

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

What is the logic in Div2 B

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

    for n >= 62(max size of long long) the answer should be sum abs(a[i] — 1) else you just consider the powers of c till a[max](1 / (n — 1)) and calculate the answer

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

      I got it, but can you please help me in finding x^(1/n). I know how to find x^n but never used x^(1/n) (without using inbuilt pow function)

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

        I guess you can use Newton raphson's method or similar iterative approximation techniques

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

    Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.

    My submission 91391756

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

Div2 C was by far one of the most interesting observations used on an ad-hoc problem.

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

    Div2 C was a pretty darn clever problem, ngl

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

      There was a similar one in a global round! Couldn't do it then!

      Upsolving helped :D

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

    I mean... You can't say "by far" and then say "one of the..." xD

    It was a super cool problem!

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

      "By far" was for me... "one of the" for the more experienced people. Didn't want to declare something without allowing public opinion. :p

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

    "It can be proved that the solution is always possible". Imagine if that hint wasn't there!

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

Let's hope the main tests pass :P

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

Could not solve even B this time :( Any idea on how to do it

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

    Could not solve even B this time

    You're Not Alone.

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

      a real relief to find that an expert(not for long time xD) is with me.

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

    Sort the numbers ascending. Now if the list is like really long, like over 50 elements, the only c you have to consider is c=1, even for c=2 the last c**i will be way to big.

    For arrays under 50 elements, one can brute force all possible c numbers up to 10**5 and pick the best one. The search for c can be optimised using stricter upper bound and binary search but with generous time limit its not needed.

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

      I implemented the same n=50 approach. Dont know what went wrong ;/

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

      thanks ! i will try this method.i was trying to reduce the value of c by using value of n.Don't know why it gave WA on pretest 4 though

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

      How can you use binary search?

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

        Lets say the biggest c I have to consider is 10**6.

        I will start with c = 500_000, calculate the absolute difference and then I will check c=499_999 and c=500_001, if c=499_999 is better and c=500_001 is worse then it means I am overshooting, and have to reduce the c.

        Next I take c=250_000, check if I am overshooting or undershooting by checking c=249_999 and c=250_001, if I undershooting next c will be 375_000 etc.

        So like a slightly modified binary search with gradient checking.

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

          Can you prove that the function is increasing (for you to return true or false even with gradient checking)?
          I'm not sure if i'm convinced.

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

    Me too, 3rd problem was clever though!

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

I'm sorry guys, but Div1 C killed this round for me. The idea is straightforward, but dealing with all the details was too hard for me. Besides, I noticed that $$$r_1 \le r_2 \le r_3$$$ only 15 minutes before the end of the contest :(

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

    Wow, didn't even notice it till the end, wrote min statements everywhere to handle cases for that ._.

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

    $$$r_1 \leq r_2 \leq r_3$$$ — what?

    Although the solution without this constraint is too complicated as well.

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

    I just noticed after reading your comment. Thanks.

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

    The key observation for me (which I was missing for an hour) was that there exists an optimal solution that's ever only $$$O(1)$$$ steps to the left from the rightmost position reached. Once I got that, the solution became quite manageable.

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

Div2 B. Im trying to brute force. 1 < i < sqrt(max(list)) But I got TLE on pretest 4

How to approach it?

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

    I used ternary search on $$$c$$$. Passed the pretests.

    EDIT: No it doesn't work that way. My solution failed in the real tests. There could be local minimas too, and I didn't think of that.

    The correct way to solve it is to notice that you can not have a value for $$$c^i$$$ for any number greater than 2e9. (As you can always select $$$c=1$$$). So, if you have $$$n$$$ numbers then you can find the upper limit of the range of values for $$$c$$$. That is,

    $$$up^{(n-1)}<=2e9$$$

    . To be more careful, I selected 1e10 instead of 2e9. So I got up = pow(10,10.0/(n-1)). Now you can go from 1 to up, and keep track of the minimum abs diff.

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

    Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.

    My submission 91391756

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

What was the point of Div1C? It had a really long and complex statement, but once you understood what was actually being asked, it was easy and fairly uninteresting :/

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

    Honestly, I don't see the point of Div2 BCDE either. The difficulty gradient was quite unbalanced.

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

I implemented Div2 C at last moment is this code correct or still it require something else!

https://ideone.com/HJ3kDp

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

    My idea is first we can make any possible number with two numbers whose gcd is 1. thus for each Ai I was trying to make -Ai. IN 2 operations by using n and n-1 length of segment in first 2 operations. In one remaining operation first remaining value was tackled by me separately thus a total of 3 operations!

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Out of curiosity, did anyone manage to get pretests passed on Div 1 C using the +1 / +2 dp and running an exponential brute force at the end instead of handling cases?

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

Div2 C was nice :) took too much time to solve it

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

Looks like solving linear congruences a∗x≡b (mod n) was an overkill for C lol.

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

    Can someone explain how to solve it?

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

      Yep. Actually all you gotta realize is that multiples of consecutive numbers can form any number.

      So step 1: Select 1 to n, and add -1LL*(a[i])*(n)

      Step : Select 1 to n-1 and add 1LL*(a[i])*(n-1)

      Now numbers 1 to n-1 must 0 by now. You can make the nth number 0 by adding (n-1)*a[n-1].

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

        What a clever solution!!!

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

      For C: If we can make all a_i multiple of n then we can make all of them 0 in one step using -a_i.

      Now, a_i+(n-1)*a_i=n*a_i So if we select segment with length n-1 then adding (n-1)*a_i will make all element divisible by n.

      Using this we can make all element divisible by n in two step and finally 0 in last step.

      You should handle overflow issue and n=1 case carefully.

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

Devil fooled me with div2A

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

Someone, please explain B and C. In B I iterate over constant c until power(c,n) <= 1e18, and permutation I choose the sorted one.

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

    For C: If we can make all a_i multiple of n then we can make all of them 0 in one step using -a_i.

    Now, a_i+(n-1)*a_i=n*a_i So if we select segment with length n-1 then adding (n-1)*a_i will make all element divisible by n.

    Using this we can make all element divisible by n in two step and finally 0 in last step.

    You should handle overflow issue and n=1 case carefully.

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

      Thanks, Got it! Can you tell me what's wrong in my B approach...

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

        I will see it once i solve B successfully.

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

    For B : Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.

    My submission 91391756

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

      What was the answer for Test case 2 ? The 10^9 one , I Mean the number they were power of ?

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

        31622 and 31623 are the closest to 10^9 and 31623 will give us a minimum for 31622 2000017493, for 31623 1999982505

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

Problems B and C gave me PTSD.

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

Could someone please tell what is the problem for my soln to B?

https://codeforces.net/contest/1397/submission/91418834

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

How to solve Div2 D ??

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

    On every turn the player should pick the biggest pile, if he can't, try the next pile, if he still can't the other player wins. you can just simulate the process.

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

Some people complained that the pony round had long problem statements

Ha-ha.

Look at Monster Invader. That is how you write long statements

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

For correct solution, the timing is updated ,for incorrect it is not updated. Why the rule that the recent solved timing would be considered ?I solved Problem B nearly 30 min from the contest and then at last just to conform ,it resubmitted it with a small change so that it does not fail system test and it updated my timing. Why not make it something like If the first correct attempt fails, then the next one is considered. Also for who are new to codeforces at least the link of the rules could be included in the contest posts.

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

    Link to the rules is there when you register.

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

      I actually register just 5 minutes before the contest seeing whether I could give that round or not

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

    You make changes so that it does not fail system test. So your first solution is potentially not correct. So I surely agree to the rules.

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

      And if someone makes wrong submission then is he not doing changes.

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

    Why not make it something like If the first correct attempt fails, then the next one is considered

    Then everyone will submit multiple solutions to 'secure' AC.

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

      You can then also charge him for his previous wrong submissions.

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

    If you do not want you do not have to submit twice.

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

    "Why not make it something like If the first correct attempt fails, then the next one is considered"

    Yeah. And if this one fails too, let's move on to the next one. Let's give participants infinite number of attempts to bypass system testing in case they're uncertain.

    "And if someone makes wrong submission then is he not doing changes."

    If someone makes wrong submission then this solution is definitely not a candidate for system testing. And I believe in most of the cases it is a mistaken submission of a completely different task

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

      If the test cases are strong then obviously only correct solution will pass which don't pass can be skipped in system tests.

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

        Thinking that strong pretests cover all possible cases and give you absolute guarantee is a plain bullshit and naivety

        One hacked solution does not mean pretests are necessary bad. It just means that the solution is hacked. No more, no less. Similarly with system tests.

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

I've written a fairly straight-forward brute for B.

Could someone tell, if i'm missing something? Solution Failing on TC3

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

    [deleted]

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

      I have put a break condition in case the c^i overflows. also, since the biggest c is 10^5, a negative check for overflow should have done the job.

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

      Found the mistake! The negative check is wrong! It'd overflow multiple times

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

Was I the only one to not attempt Div-1 C seriously initially considering its low number of submissions in the beginning?

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

Who else skips a heart beat when you go to the Dashboard during system tests and you see RED on your problems? (and 1 second later realize/remember it's just the bad attempts).

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

Although I couldn't solve C, looking at its solution, I can say it's a pretty cool ad-hoc problem.

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

problem C: Help Dora to find all the ways to beat the level

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

I misunderstood Problem B and tried solving it taking into consideration a different c for each a[i]...

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

Please, A quick editorial

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

Weak pretests = Many hacks = (Actually not super) long systest queue($$$3$$$ pretests, $$$60$$$ systest for $$$A$$$...)

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

Anyone interested in hacking my code, Here's the testcase : 3 1 1 1

Weak Pretests guys :(

→ Reply
»
4 years ago, # |
← Rev. 9   Vote: I like it +123 Vote: I do not like it
D2A
D2B
D2C/D1A
D2D/D1B
D2E/D1C
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    IN div2 B I calculated (n-1)th root of largest element ad tried from 1 to that value plus 2.whats wrong with that. I also sorted the array to calculate the cost.

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

      It is possible for the largest element at the end of the process to be much, much larger than the largest element at the beginning. See my comment above.

      In addition, be careful about overflows.

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

      For B : Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.

      My submission 91391756

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

    For D2C/D1A we can also use one operation of length n, subtracting n*a[i] from all elements for 1 <= i < n and adding 0 to the last one. Then one operation of length n-1, adding (n-1)*a[i] (initial value of a[i]) to all elements for 1 <= i < n. The last operation will be of length 1, applied to the last element, subtracting it from itself. (And the case with n=1 should be treated separately with any approach. For example subtract the only element from itself in one operation, then add 0 in the subsequent two operations.)

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

tourist exorcised the devil.

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

Am I the only one really bothered by Div1 C statement?

If Ziota damages the boss but does not kill it immediately, **he** is forced to move out of the current level to an arbitrary adjacent level [...]. Ziota **can also** choose to move to an adjacent level

At first, I thought "he" referred to the boss, who would flee if not killed. This was enforced by the next sentence (the boss is forced to do something. Ziota can also choose to do it).

The wording in the sample is also unhelpful:

forced to move to either stage four or two, here we move to stage four

We? Ziota was in third person singular throughout the problem statement, why use "we" now? Ziota and the boss?

The statement is "correct", but these things get hard to read if you're not a native speaker and are reading in a hurry during the contest. Why not use the character name?

After re-reading the problem many times I submitted a suggestion the change the use of "he" for the character name, which got "No comments". I wished it could have been updated, so at least others wouldn't spend time figuring this out.

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

    Well I only read the problem and I did not read it your way. I think it's about computer games logic, and that's why it passed through all the testers... For some reason you assumed in your head that Ziota is the feared, all powerful being, but that's usually the boss.
    If you are playing a game and you reach a super strong boss that kills you with ONE SHOT, and you miss a shot (or hit but not kill), who runs away afraid? you or the boss?
    Usually all you do is run and dodge while the boss attacks...

    (I literally imagined teleporting between worlds making a single shot and continuing to teleport. I have a clear vision of this computer game in my head LOL)

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

      Having a 1 HP boss run behind other small enemies isn't that unreasonable. And again, during the contest it's easy to misinterpret the statement if it's a bit ambiguous and you're not a native speaker. I don't see why they wouldn't change it

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

what is meant by reorder in question B??????

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

    You can reorder a[]

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

    That means you can swap any pair of elements and sort the whole array for convenience.

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

My solution to Div2 C was to just simulate every player choosing pile with max number of stones (among available ones).

I'm still not 100% convinced, but it passed pretests (soon I will see if it passes the main tests).

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

    I used this solution as well. Looking at others' solutions, it seems that another approach is to say that player 1 wins if there is a pile with size at least all other piles combined, otherwise determine the winner by the parity of the total amount of stones. I believe it can be shown that the two approaches are equivalent.

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

    I think the idea is that a player can claim "ownership" of a pile because if the only take from that pile, the other player can never take from it due to the rules. So, if a player takes from the non-largest pile, it could lead to a situation where the largest pile > sum of the other piles.

    So if a pile > sum of the other piles (this must be the max pile), take from that pile. The other player can never take from that pile. Otherwise, never make it so that the max pile > sum of the other piles, which you can do by always taking the max pile. Then it just comes down to parity.

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

      But how to prove that if sum of the max pile is less or equal to other piles combined "HL" will always win?

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

        HL won't always win, it depends on the parity, you can prove it by induction.

        Suppose we have $$$x$$$ stones for some even $$$x$$$ and that the max pile is not bigger than all the others combined. If $$$x = 0$$$, the proposition holds trivially. Assume, by induction, the proposition is true for all arrangements with $$$x - 2$$$ stones. Then, no matter which pile T chooses, HL can always choose another one such that the (possibly new) max pile is not bigger than all others combined. Moreover, after this we'll have $$$x - 2$$$ stones. By the induction hypothesis, HL wins.

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

What is the approch for div 2 B

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

    We can simply try all possible numbers for C.

    This is possible since if n is big, there are only very small numbers for c possible, and if n is small we can actually try all possible C. (max sqrt(1e9), ie 1e5)

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

      Can you please explain the intuition behind max sqrt(1e9) ?

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

        If n==1 and n==2 the solution is trivial, if n==3 the max possible value for c is "a little bit more" than sqrt(1e9), because 1e9 that is the max value a[2] can have. For bigger values of n the max value of c is smaller.

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

    Find (n-1)th root of the maximum value in the array. This will be double type value so you have to add 0.5 and then take the floor of that so that value gets rounded off properly. This value is c for our array then calculate the sum of the absolute difference of a[i] and c^i for all.

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

      I should sort the array first right bfore calculating abs difference

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

        yes

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

          I tried calculating the (n-1) th root of largest element and than looped c from 1 to that value+2 and tried minimum cost. But i got test case 4 wrong. Can it be becouse of some overflow. I was using long long

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

    Start by calculating the score for c=1, it is the one that will certainly not overflow long long in any case. Then, taking larger values of c, the score may first decrease (this may be the case for small values of n), then increase forever after passing the minimum, or it can immediately increase (for large n even powers of 2 will already overflow), the score for c=1 being optimal. So iterate over c values starting from 2, continuing while getting answers smaller than the current optimum, and in the first instance when the current optimum is exceeded interrupt the search, we are past the turning point.

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

      I think that too might cause overflow. I came up woth a formulaa to find the upper limit upto which i should consider c. double x=pow((double)(arr[n-1]),(1.0/(double)(n-1))); ll st=floor(x+0.5); ll ans=LLONG_MAX; ll c=floor(pow(10.0,17.0/(double)(n-1))); for(ll i=1;i<=min(st+2,c);i++) { ... }

      this worked for me

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

        When calculating a given next candidate score, interrupt immediately after getting a (possibly intermediate) value larger than the current optimum, no need to calculate the full score, if it is already too large. In this case it should not overflow. Code for reference

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

      Suppose the previous_optimal is x and we are in the process of finding the current_optimal and current_optimal current value is < x. How can we be sure that the next value(candidate) added to the current_optimal will not overflow current optimal as if it will overflow current_optimal then current_optimal can be < prev_optimal after all the overflows.

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

I Think Div-2-B was pretty hard for newbi contestant like as me ☹️

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

Mastering puzzles is really necessary to be good at CP? Is it?

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

Anyone else solve Div 1C/2E without realizing r1<=r2<=r3?

OOPS

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

    I think I've seen this during the contest, but my solution ended up not caring about it)

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

I wouldn't say this round is bad by itself, but I really expected something special prepared for #666

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

Found out that my A failed system tests because I wrote for(int i = 1... when I was supposed to write for(int i = 0.... Almost 500 points blown away for nothing :P

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

I know, for interview preparation, there is leetcode. But sometimes I wonder, will the problems in Div 2, like A,B,C, will they really help me in interviews, as they are just some tricks. You understand the trick, you get AC, else not. More of a mind game type. Can someone answer this?

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

    Let's just say it's not the most optimal way to prepare for interviews.

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

(a + x * b) % n = 0 can anyone tell me what will be value of x (here b is prime) ??

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

Problem set was really good. Div2(C) was tricky and one of the best one.

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

How did you solve Task B?

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

    Sort whole input array.

    Find (n-1)th root of the maximum value in the array.

    This will be double type value so you have to add 0.5 and then take the floor of that so that value gets rounded off properly.

    This value is c for our array then calculate the sum of the absolute difference of a[i] and c^i for all.

    Formula to calculate kth root of n : pow(k, (1.0 / k) * (log(n) / log(k)))

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

      What is the intution behind this?

      Any resources for this concept?

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

      how do you prove that that's the best C . edit : you failed main tests, F

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

    A brute force solution works. Store the best seen cost so far. For each power from 1 to 33000, you can stop the evaluation when the cost becomes worse than the best so far: https://codeforces.net/contest/1397/submission/91374026

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

    For B : Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.

    My submission 91391756

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

How to avoid long queues? Answer: write a problem like B with like 5 pretests and run the contest

(yes I'm frustrated :p nice contest otherwise imo)

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

I felt humiliated by Div2 C

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

    Haha same. My code worked after a minor fix when a number is 0.I could've gotten it in contest had I remembered that 0 is not a multiple of n!

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

      0 as a multiple works. It was part of the clarifications.

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

        You cannot add 0 I thought. I changed just that (and removed unnecessary base cases) and it worked. 91407141 91423874

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

          It seems your error was not printing endl in every line when n == 2.

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

            Thank you! I see now. Very sad about that problem now :(.

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

Anyone else who lost motivation to solve Div2 E just by seeing the size of problem statement?

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

Is #667 (Div. 3) going be rated?

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

Were pretests really weak today? Can't believe both A and B failed system tests.

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

Great contest..

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

Was it only me or n=1 troubled many in problem C ?

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

Great contest, problem setters! A question though.. Do you folks intentionally make weak pretests (for A in my case)? I'm asking this because, I made a substantial blunder in A, and somehow the pretests still passed for me(and then, it failed in system tests).

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +15 Vote: I do not like it

I have a wrong solution for Problem D. And it has got Accepted after system testing. 91418247

WA case:

1

2

1 15

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

For div2 B, how do you prove that simply sorting gives the best permutation?

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

    like consider the GP as 1,c,c2,c3 and the sorted araay be a0,a1,a2,a3.....an you will make ai-->ci else if difference of a(i+1) and ci is less than that of ai and ci then you have to transform ai to a much larger no. which will not be optimum. this was what i used and am not sure whether is correct or not.

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

    let's say you want to make your array to exist on a number line

    <------c^0---c^1----c^2--------c^(n-1)--> This is required array for a particular value of chosen c. Cool.

    Now lets say your array contains a1, a2......an-1. on a number line. Now the mapping we chose is to map minimum value in a to minimum value in c , and so on. lets say our array is sorted a0<=a1<=a2.....Now we will prove why we chose the sorted order as follows. Say at any point ai> ai+1. By contradiction and you matched ai to say c2 and say ai+1 to c3. lets say ai+1< c2 <c3<ai. And if we tried matching ai+1 to c3 and ai to c2. then see the segment between c2 and c3 is included twice which is not optimal.

    >>>>>>>>>>>

    | |

    ai+1.....c2----c3----ai.

    |           | 

      >>>>>>>>>>>>

    Hence it is always it is viable to map with nearest value.

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

    Exchange argument should work. If our target values are $$$x$$$ and $$$y$$$, $$$x < y$$$, and we have two value $$$a$$$ and $$$b$$$, $$$a < b$$$, matching them in sorted order will cost us $$$abs(x-a) + abs(y-b)$$$. If instead we match $$$x$$$ with $$$b$$$ and $$$a$$$ with $$$y$$$, we need to prove that the cost can't get any less

    Case 1: $$$b$$$ < $$$x$$$ or $$$a$$$ > $$$y$$$
    Then the total cost doesn't change. One will cost less by $$$b - a$$$, and the other will cost more also by $$$b - a$$$.

    Case 2: $$$a < x < y < b$$$ or $$$a < x < b < y$$$ (similar case if $$$x < a$$$)
    You can draw the four values in a line and it should be clear that matching $$$b$$$ with $$$x$$$ is going to result in more cost.

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

    We can prove a more general statement.

    Given two sequences $$$a$$$ and $$$b$$$ with the same length $$$n$$$ and $$$b$$$ strictly increasing find a permutation $$$c$$$ of $$$a$$$ such that $$$\sum \lvert c_i - b_i \rvert$$$ is minimal.

    We claim that the optimal permutation is non-decreasing.

    It is easy to prove it for $$$n = 2$$$ by considering a few different general cases. For $$$n > 2$$$, assuming that $$$c$$$ is not sorted, we can improve the sum over any two elements that are not in order (and the total sum) by swapping them. Repeat until c is sorted.

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

My B , failed in main test cases :(((

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +74 Vote: I do not like it

the contest must have been cursed

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

BINOD.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

https://codeforces.net/contest/1397/submission/91390761 This is my submission of question div2 B, and it returned the wrong answer in the eighth test case. But the result I run locally is indeed 912788665, what's the problem? I changed the compiler to VS C++ 2017, and the result was ACCEPTED! Can this question be judged again? And I'm curious where is the mistake?

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

    It could be undefined behavior, but I have no idea where it is...

    Changing the language to C++17 solves the problem.

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

      Thank you very much, I am still trying to find the problem, I changed the compiler to GNU C++14 and GNU C++17, and the results are accepted.

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

    If you change your abs() calls to std::abs() it'll pass. The abs() that is available outside of std is the c version (which means no overloads) and takes int arguments so your values get truncated. This has been changed in newer compilers to include the overloads outside of std as well but you are choosing an old compiler.

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

      Finally I know where the problem is,It took 421 ms on test case 5, and I finally know why. thank you very much.

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

div2D/div1B defeated me... I still don't have an intuition for it... but I should have just tried it anyways.

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

My B and C both failed on system testing
vary sad contest for me....

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

Teach me to read pls(

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

Can anyone please tell me why is this wrong for Div2 A?

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string s;
        unordered_map<char, int> m;
        while(n--){
            cin>>s;
            for(int i=0; i<s.size(); i++){
                m[s[i]]++;
            }
        }
        int flag=0;
        for(auto it: m){
            if((it.second%n !=0){
                flag=1;
                cout<<"NO"<<"\n";
                break;
            }
        }
        if(!flag) cout<<"YES"<<"\n";
    }
    return 0;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this won't even pass the example case. You used while(n--) so at last n will be zero, so mod n is always zero therefore the output would always be all YES (I think?).

    Use for(int i=0; i<n; i++) instead

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

    You are decrementing variable 'n' in while loop . Then using the same variable to check if else conditions , it's not going to work . Use a 'for — loop'.

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

Anyone else who solved 2C using extended Euclidean algorithms like me? :(

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

Looking forward to seeing the proof for the solution of Div2 D...

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

man problem C was so fucking beautiful, Sometime i just don't get it ,why I can't catch these problems, fuck ups after fuck ups. Man cp can really hurt dumb fucks like me.

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

    This is not CP . These are off the charts tricky ad hoc "you are lucky if you guessed it right in the first few minutes" problems.

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

      ((n*k)-k)%(n-1)==0 ,how can say it just guessing ? it was a really good problem.

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

      Lol thats not how cp works. Observation is key in cp

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

      Uhh more like trying one thing after some other thing after some other thing until something works.

      The better one is at keeping a problem in his / her brain, the faster they can solve some problem.

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

What wrong with my 91425950 for problem C in div2

Checker Log wrong answer Integer -1 violates the range [1, 4]

thus for the sample, why the following is wrong answer atoiz

1 4 
0 0 -8 -4
1
-1
2 4
-3 6 0
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Output two integers as range for each operation, even it only contains one element.

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

Question C in Div 2 — Multiples of length.91406408 On system Testing it got Time Limit Exceeded (on TestCase 70(last test case) ) verdict but now on running its displaying AC Verdict. What to do?Can anyone help?

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

    atoiz[user:atoiz] Help needed with this.

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

      Your solution passed with 998ms out of 1000, probably with internal retries. It is perfectly normal that problems have some fluctuations of the execution time. And it is certainly not a reason for rejudgement.

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

    Your practice submission used $$$998ms$$$, which is too close to the time limit.

    It's normal that the time your program used is different for each time.

    Codeforces rejudges submission which got TL for several times, and sadly your solution failed on all of them :(

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

3 times WA is huge demotivation. I was like, ratings can go to hell, I am not solving it :D

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

Please make the round unrated

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

    Yes, the test cases weren't great but that doesn't justify making it unrated. It is the contestant's job to ensure that his/her solution is correct.

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

![ ](

)
→ Reply
»
4 years ago, # |
  Vote: I like it +71 Vote: I do not like it

My approach for problem E:

First we decide for each edge how many times it is passed through, then we could easily construct a matching using bottom-up.

It is easy to see, that a sequence of numbers (of times an edge is passed through) corresponds to a perfect matching if and only if : for every node $$$u$$$ (suppose its adjacent edges have numbers $$$a_1,a_2,\ldots,a_d$$$), the conditions $$$(\sum a_i)\bmod 2=1$$$ and $$$2\max\{a_i\}\le (\sum a_i)+1$$$ hold.

Starting from $$$a(u,v)=\min\{size_u,size_v\}$$$, each time we decrease the maximum value by $$$2$$$. It's obvious that the conditions above always hold (until some $$$a(u,v)<0$$$). We want the sum of $$$a(u,v)$$$ equals to $$$k$$$, so we can use binary search to find the final sequence.

The overall complexity is $$$O(n\log n)$$$.

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

I don't know why this solution is giving Runtime error : Wrong Answer!! whereas the same code with if-else condition is accepted : Accepted

Someone please explain it!! As I am losing 50 points because of this.

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

    You should always return 0.Returning different from 0 means the program exited due to error or anomaly.

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

      This is strange and disgusting!! I compiled it on my system and it was showing correct output.

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

        This is not strange at all. Program returning 0 signals the program runs properly. Other return values signals the program not working properly due to incorrect input, memory issues, etc.

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

          Thanks!! I learned something new and will try not to repeat the same mistake again!

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

Hexakosioihexekontahexaphobia is the fear of the number "666" .

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

I declared 25 size array for 26 characters.

I deserve weak pretest.

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

DIV1 B and DIV2 B should have been swapped

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

    Not sure about that, div2B seemed straight forward to me. I solved div2D/div1B without being sure about its correctness. Sometimes correctness of greedy algorithms is hard to prove.

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

      can you explain the logic for div2 B?

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

        Sort the array $$$a$$$ and calculate cost for $$$c = 1,2,3,4,5,......$$$
        Stop iteration when the cost for current $$$c$$$ becomes greater than the current minimum cost. Because current $$$c$$$ and any greater $$$c$$$ won't give a cost less than the current minimum.

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

Why did my first submission 91409058 printed some random negative number? I just replaced printf with cout (91412283) and it worked correctly. atoiz

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

    You use %lld to output an integer. You should either store n as long long or output it using %d. Also, don't use cin mixed with printf. Use printf and scanf / cin and cout.

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

      The output was displaying correct on Codechef IDE.

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

        Your code might work in some ide because it is undefined behaviour. Anything (e.g. crash, output the thing you want, or in this case, output the wrong answer) can happen if undefined behaviour exists in your program.

        c99 Standard: 7.19.6.1: para 9:

        If a conversion specification is invalid, the behavior is undefined.225) If any argument is not the correct type for the corresponding coversion specification, the behavior is undefined.

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

          Thanks man. When you mentioned that para 9 thing, it felt like a verse mention from Holy Bible :D

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

The problems are tricky but they are good.

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

Why this submission 91375766 gives runtime error on test 3 I ran the code on my machine and it gave me the correct answer

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

I used INT_MAX to set limit for long long int type data.Press F for me. Got WA in div2 B

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

When will rating be updated

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

Can someone please explain to me the exact score decline function for problems? And how a wrong submission penalty affects it?
I can't find it anywhere and I would really love to know the gravity of every passing minute or wrong pretest submission.

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

DIV2 B solution without using log to calculate upper bound : 91433534

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

Can someone prove the correctness when using greedy to solve the DIV1B? THX~

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

I just realized how ironic it is that today of all days I started to watch Lucifer on netflix... it's ok. I'm a little scared it's just another crime show.

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

Genuine question: if the problems take months of preparing, with lots of time spent writing/testing and scheduling, why aren't the editorials immediately ready after the contest? Isn't there plenty of time to write it between conception of the problem and the contest date?

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

Rating Update!!!

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

why is there no change in my rating after participating in 666 div 2?? I solved one problem but there is not even +1 or -1 , exactly same ..have the ratings not updated?

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

    Yes indeed, the ratings aren't updated yet. Wait for it and it will update soon.

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

      quite strange...they always got updated after the system check..anyways thank you!

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

        No that's normal don't worry. It happened before many times. Usually I check rating changes the next day haha xD
        If you really want to know a prediction of your rating changes, you can install "CF-Predictor" it's an extension for web browsers that predicts your rating changes. it's quite accurate.
        Here's the link for the extension for chrome link
        install it and then check the standing page you'll see an additional column that contains the rating change.

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

          That's so cool!! Thank you so much for the suggestion, I'll surely try it ;)

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

I faced this issue of signed integer overflow, where I can easily see passing the same code for test case 17 in my machine but failing here. I am using G++17 latest on my machine. I couldn't find any solution that what is different with codeforces C++17 compiler. My submission link

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

When will rating be updated?

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

Can this comment reach 666 upvotes?

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

[problem:B — Power Sequence] [contest:Codeforces Round #666 (Div. 2)]

Mistake by CodeForces Judges!!!!!!!!!

In Problem B under test case no. 56:

**CASE 1:**
if the resulting power sequence will be : 1  1^2  1^3  1^4  1^5  1^6  1^7  1^8   ..... 1^32 
	then cost will be 4073741790  (_marked as correct by judges_)

**CASE 2:**
if the resulting power sequence will be : 1  2^2  2^3  2^4  2^5  2^6  2^7  2^8   ..... 2^32 
	then cost will be 2368709120  (_less than that of previous case_)

**CONCLUSION:** 
The maximum possible range of a[n-1]  for a perfect power sequence is not mentioned anywhere. And so, CASE 2 must be the correct answer for this problem.

p.s : I have used this headline just for attention on my doubt.. No offense on headline please. Thanku for ur replies.

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

    Can't see TC 56

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

    your int is overflowing which is giving a random value, if you change it with long long , it will come out to be greater than the judges' answer. Please read the c++ diagnostics on ur submission ... smh

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

    You are incorrect. I tested it locally, if c is 2 then cost will be 4516192768. Also check twice before making such a huge statement

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

    According to my calculation, the cost for the 2nd case is coming as 4516192768, which is greater than 4073741790. Kindly, check your calculation.

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

can someone give an explanation to why the Div2 D depends only in the parity if there is not a pile bigger then the sum?

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

    I didn't participate officially in the competition yesterday (12:35am for me), but read the questions and my solution sketch for Div2D/1B is as follows:

    Let S represent the sum of the piles of stones and let M be the max number of stones in one pile. Let R = S-M be the remainder — the number of stones in the other piles.

    If M > R (2M > S) then the first player wins: they repeatedly take from the M pile. The second player is forced to take one of the R stones from another pile. After 2R moves, there is only one pile remaining with M-R > 0 stones; the first player takes from this pile and then wins.

    Otherwise, if M <= R, we take two cases depending on the parity of S.

    Let's first look at S odd; let S = 2P+1. Firstly, the first player should take from pile M. Then there are S-1 stones remaining. We can create (S-1)/2 = P pairs of stones such that each pair comes from two different piles. This can always be done by creating a pair between the two piles of greatest size. By doing this pairing, no matter what move player 2 does, player 1 can always pick the other stone in its corresponding pair. Since player 1 always has a move/response to player 2, they will win.

    On the other hand, if S is even, then player 2 does this pairing strategy immediately; they have an answer to any move that player 1 does, so since player 2 can always move, they will win.

    We can see why this pairing strategy doesn't work if M > R (like in the first case) — we're not able to create all the pairs because the pile with max stones has too many stones in it; if the remainder is R (R = S-M), then you can create at most R pairs.

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

      How will we maintain the constraint M<=S/2 when we remove a pair from smallest 2 piles? Then, only S reduces and not mx.

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

Thank for the contest but I want to ask a problem happen with me: I submitted it 6 times in problem B. The 6th time I was accepted, but when I reviewed the results, no results for my 6th submission and no grade for it. I want to ask why is that? I submit when time have 50 minute left. Have someone know this problem?

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

    Your code could've passed the pretests, but probably didn't pass system tests, which happens once the test is over.

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

hey guys. i have a problem about 1397B - Power Sequence that i dont understand, hope someone can help me :)

this submission 91447181 is wrong at test 44 , because variable "power" is int and overflow happens. when i change variable "power" from int to long long , which is this submission 91446926, its wrong at test 4 and i dont know why.

sorry for my poor English by the way.

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

    We cannot go above the required c as it will always result in overflow For eg as in test case 4 N=100 so the appropriate c is 1 but in your code, you are also computing it for c=2 also and then comparing, for c=2 it will always have overflow(2^100 is large).By using power as int you were lucky as it resulted in greater value(at c=2 after overflow)than previous. Whereas for long long you got smaller value(again after overflow).So we cannot go to 1 higher value of c. My code for reference https://codeforces.net/contest/1397/submission/91450164

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

I like this contest. :)

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

In problem D of div2 can anyone help that for pile 2 1 3 2 how they are going....

according to me,

1st player chooses 3 in 1st turn and removes only 1 from this

2nd player chooses 2 in his 1st turn and removes only 1 from this

1st player chooses 2(new) in his 2nd turn without making empty the 1st pile he chooses of 3

2nd player chooses 1(new) in his 2nd turn without making empty the 1st pile he chooses of 2

then player 1 empty his pile from 3,2 one by one and similarly player 2 from 2,1 pile and player 1 has more number of the pile to remove so player 1 wins

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

    Since they are playing optimally

    2nd player chooses 1 in his 1st turn then u will get Player 2 wins always

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

      Can you explain more?

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

        I think you assumed that a pile chosen by player 1 in any of the previous turns can't be picked.

        But according to the question the pile chosen in the most recent turn can't be picked all others can.

        So, according to the moves mentioned. 1 2 2 3 --> 1 2 2 2(P1) --> 1 2 1(P2) 2 --> 1 1(P1) 1 2 --> 0(P2) 1 1 2 --> 0 0(P1) 1 2 --> 0 0 1 1(P2) --> 0 0 0(P1) 1 --> 0 0 0 0(P2)

        So P1 has no piles left to choose.

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

          Oh only pile chosen in the last round can not be picked

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

I saw many people pass 1B with a O(n) solution.I just know O(sum log sum) where sum = $$$\sum a_i$$$.Can somebody explains it?

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

due to a small doubt i resubmitted my solution for question A , but during system testing my first solution was skippped , though it was compeltly correct.Can i get any help regarding this.After the contest i checked my previous submission , it was also an accepted solution.Please help . Link for resubmitted solution: https://codeforces.net/contest/1397/submission/91394792 Link of skipped solution: https://codeforces.net/contest/1397/submission/91357472 Link of skipped solution which was also an accepted solution : https://codeforces.net/contest/1397/submission/91424283 please help with this, i got -106 due to this blunder.

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

I am still eagerly waiting for that UPD : Editorial is published !!! Anyone Else still waiting ?

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

oh god where is the tutorial?

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

submission:(http://)https://codeforces.net/contest/1397/submission/91449160

why it is showing signed integer overflow on the line 43 thank u

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

    in your binpow, if the value of b is very large, like around 1000 and even if your a is as small as 2, the values will overflow.

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

      then what is the solution sir

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

        I think inside your second for loop after calculating ans just check if ans<0 then assign ans= +infinity and break the loop. Your code will work fine

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

div2D's easy solution

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

    can you please give your proof? mx part was easy but I can't think of the sum&1 part

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

      If $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}$$$ is even, then we can pair all the stones on the table into pairs so that each pair contains stones from two different stacks. (We can do it e.g. by repeatedly removing two stones from two highest stacks and pairing them together; we can prove that the conditions $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}\%2=0$$$ are satisfied throughout the process.) Then, the second player has a winning strategy -- whenever the first player picks some stone, the second player removes the other stone from the pair.

      On the other hand, if $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}$$$ is odd, then the first player removes a stone from the highest stack. Then we can convince ourselves that we now have that $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}$$$ is even, but now the second player is to move. Hence, the first player wins.

      It appears that this part of the solution is arbitrary:

      [...] we can pair all the stones on the table into pairs so that each pair contains stones from two different stacks.

      But it is nice to remember that this condition holds if and only if $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}\%2=0$$$; this is quite useful e.g. in game theory or some optimization problems.

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

      We can consider each stone as a vertex, and each pair of stones from two different piles are connected by an edge. The first player chooses an arbitrary vertex, and in each turn a player chooses a vertex that wasn't chosen before and is connected with the vertex chosen in the previous turn. It's the well-known theorem that the first player loses if and only if the graph has a perfect matching.

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

My solution with explanation for problem E: https://codeforces.net/blog/entry/82130

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

Since the editorial is taking so long, would anyone who solved Div1D share how they solved it?

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

    Brief editorial: For every x,we enumerate y from 0 to L.Suppose the left-bottom vertex of matrix is $$$(x,y)$$$ .We maintain an array $$$a_{x \dots L}$$$ ,means $$$(i,y_2)(y_2 \ge a_i)$$$ is an legal right-top vertex.We may erase some candy during enumerating y,so there will be some events like $$$(l,r,y')$$$ ,means for $$$l \le i \le r$$$ ,$$$a_i=\max(a_i,y')$$$ .We can enumerate y from L to 0 and maintain a set for every color to get the events.The total events number is $$$O(n)$$$ .Use segment tree to maintain $$$a$$$ ,time complexity is $$$O(n^2 \log n)$$$ .

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

Hello everyone. I had a submission 91458515 which fails on the problem B but a similar submission 91458087 passed. The only difference between the two is — in one I assign the initial answer as 'LONG_MAX' and for the other, it is '1e15'. This should not break the solution to my knowledge. I may be missing something. If someone can point out the reason it would be very helpful to me.

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

    Use LLONG_MAX instead of LONG_MAX. Accepted Solution 91464270. Value of LONG_MAX is 2147483647 and total cost can be greater than the value of LONG_MAX.

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

Annotation-2020-08-31-130026

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

when will we get editorials

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

I thought I would reach Violet(1900) this time :(

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

    You have at least better luck than me! ![ ](rating.png)

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

      haha. lets see who reaches 1900 first.

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

        Challenge Accepted!! By the Way, Whyn't play a little longer, lets see who reaches 2400 first!!!

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Video explanation Div 2 a,b,c,d
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Hope the long wait for EDITORIAL disappears soon :'(.

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

Hi

My submission for Problem B Div.2 is failing in the cf compiler at test case 44. While running the same test case in my local compiler it seems to be giving the right answer.

https://codeforces.net/contest/1397/submission/91479829

Can someone help me with the same.

Thanks!

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

In Div.2 B , firstly I sorted the array and then took (n-1)th root of last number , say it came to be 6.4 , then I took 6 and 7 , calculated answer in both cases and found minimum of that , still WA at pretest 4 . Is my logic wrong or I did mistake in implementation part ? My code : https://codeforces.net/contest/1397/submission/91376042

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

    You need to implement power function for long long int, the inbuilt pow(x,y) function runs in overflow.

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

      Can you tell me the exact pow function required as I'm getting WA by this pow func. long long int Pow(long long int x,long long int y) { if(x==0) return 0; if(y==0) return 1; long long int p=Pow(x,y/2); p*=p; if(y&1) p*=x; return p; }

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

        You can use powl(x,y) for long long values from library.

        You can check my submission here : 91391745

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

          It's still WA , can you tell me the error ? My code : https://codeforces.net/contest/1397/submission/91514571

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

            Point 1 : when you are incrementing cc variable make sure to get the condition greater than zero then you will pass test 3 but not test 4 and after that.

            Point 2 : In your case, if you will have n greater than 64 then the powl(x,y) will overflow the long long integers and the function will return garbage value.In test 4 m + 1 = 2 and n — 1 = 99 , so powl(2,99) will be way beyond the limit of the long long int.

            Actual Solution : For larger values of n (n > 50) your answer will be to make the sequence all 1s. In that case only you will get minimum cost.

            if(n > 50) {
	    long long int ans = 0;
	    for(int i =0;i<n;i++) ans += abs(V[i] - 1);
	    cout << ans << endl;
	}
else{
      // your original code here from sort line. You will definitely past the tests``
}

            Thanks me later

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

              thanks dude for understanding my newbie code and finding mistakes :))

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

when editorials will be published?

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

    Sorry for the long delay. We are really busy and trying to publish editorials as fast as possible.

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

Is the editorial not released due to the long queue?

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

    Long queue disappeared long before contest started

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

For div 2 problem C -

Can some1 explain what is the proof for k1 * n + k2 * (n — 1) = 0, in other words some multiples of coprimes can produce any number we want?

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

    Since gcd(n, n — 1) == 1, we can use Bezout's identity to get a, b such that a * n + b * (n — 1) == 1 and then multiply both sides by the number you need, to get a * x * n + b * x * (n — 1) == x

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

For div 2 problem D what should be the output for 1 2 1 3 According to me, it should be T but the accepted code says its HL. Explanation- first, T picks 3 one now it piles are 1,2 now HL has to pick 1 so now piles are 0,2 now T has to pick 2 so new piles are 0,1 now HL can,t pick either so T should win. UPD: I got it Sorry actually max>rest_sum so it is T

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

In division 2 question 2, in the following test case, why is the answer to this test case 1999982505 ? With c = 31623 we can get even smaller value 1999954247. TEST CASE: 3 1000000000 1000000000 1000000000

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

Since I joined Codeforces Community, this is the slowest editorial among all of the contest!

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

Hurry up with the tutorial, Please!!

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

In stoned Game problem , according to me there can be multiple answer, as it depands on "T" and "HL" which pile they choose. can anyone help ,

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

    This is a misunderstanding of the concept. It is stated that both play "optimally".

    Which means that the one losing the game would have made at least one other move that he did, if that would have helped to not be the loser. But he didn't, which means that no such move is possible.

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

Here are my solution to Div2 probE.91547269

In each level of the game, we have two plans to kill all monsters:

  1. Using Pistol to kill all normal monsters and then use awp kill boss immediately.
  2. Using Pistol to kill all monsters (include boss), or using Laser gun kill all normal monsters and deals 1 hp damage to boss and then use Pistol to kill it.

The difference between two plans is that boss will not be killed immediately if using plan 2, so we have to move to adjacent levels twice and spend $$$ 2d $$$ time (assume that we stay in current level after kill all monsters).

Let $$$ \text{once}[i] $$$ be the time we kill all monsters in level $$$ i $$$ by plan 1 , and $$$ \text{twice}[i] $$$ be the time we kill all monsters in level $$$ i $$$ by plan 2. At the beginning, we start the game at level $$$1$$$, and at a certain time, we are at level $$$i$$$, where all monsters in level less than $$$i$$$ were killed and all others are alive. This just same as we start the game at level $$$i$$$. So we using dynamic programming and let $$$dp[i]$$$ be the minimum time to finish the game if we start the game at level $$$i$$$.

Normally, we kill all monsters in current level, then move to next level. So we have $$$dp[i]=\min(dp[i],min(\text{once}[i],\text{twice}[i])+d+dp[i+1])$$$. And let's consider if we use plan 2 in level $$$i$$$, after deals 1 hp damage to boss we are forced to move to next level. If we use plan 2 again in level $$$i+1$$$, then we will move back to level $$$i$$$, we now kill the level $$$i$$$ boss, back to level $$$i+1$$$, and kill the boss too. Now we are at level $$$i+1$$$, where all monsters in level $$$i$$$ and $$$i+1$$$ were killed. We have moved to adjacenct level three times, if we move to level $$$i+2$$$ next, then the total time we spend on this two level is $$$\text{twice}[i]+\text{twice}[i+1]$$$. So we also have $$$dp[i]=\min(dp[i],\text{twice}[i]+\text{twice}[i+1])+dp[i+2])$$$.

And there is also a corner case. Let's consider $$$dp[n-1]$$$, if we use plan 2 in level $$$n-1$$$, then we will finish the game at level $$$n-1$$$. So we have $$$dp[n-1]=\min(dp[n-1],min(\text{twice}[n-1]+\text{once}[n],\text{twice}[n-1]+\text{twice}[n]-d))$$$.

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

Any idea till when will the Tutorial be uploaded? I am stuck on the last question, Div 2.

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

Where is the tutorial?

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

How to summon the editorial

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

Auto comment: topic has been updated by DatVu (previous revision, new revision, compare).

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

For the problem 1396A - Multiples of Length, Do I have to select different segments in each step?

→ Reply