cry's blog

Invitation to Codeforces Round 887 (Div. 1, Div. 2)
By cry, 18 months ago, In English

Hello Codeforcers!

I am pleased to invite y'all to participate in Codeforces Round 887 (Div. 1) and Codeforces Round 887 (Div. 2), which will start on Jul/23/2023 17:35 (Moscow time). In both divisions, you will be given $$$6$$$ problems and $$$2.5$$$ hours to solve them. The Div. $$$2 $$$ round will be rated for participants with rating below $$$1900$$$, while the Div. $$$1$$$ round will be rated for participants with ratings which are at least $$$1900$$$.

This round was authored and prepared by Benq, emorgan, omeganot, US3RN4M3, me (cry), Ina, nsqrtlog, buffering, ntarsis30, and ArielShehter.

We want to thank the following people for their contributions:

UPD 1: Score Distribution

Div. $$$2$$$: $$$500 - 1000 - 1500 - 2000 - 2500 - 3500$$$

Div. $$$1$$$: $$$500 - 750 - 1250 - 2000 - 2250 - 3000$$$

UPD 2: Editorial has been posted here

UPD 3: Congratulations to the winners!

Div.1

  1. jiangly

  2. Rebelz

  3. Radewoosh

  4. tourist

  5. jqdai0815

Div. 2

  1. dmaksym1177

  2. Tmath_OneLove

  3. onufryw

  4. i_nevergive_up

  5. clonegrandmaster

Good luck! Red panda wishes you all rating inflation!

Art credit to xiaossr

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

Comments Comments (216)
| Write comment?
»
16 months ago, # |
  Vote: I like it +37 Vote: I do not like it

As a problemsetter, I can certify that I did not test in any shape or form

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

    Hello, are you interested in my approach to question c in div2? I feel that the solution to this problem is not quite the same.https://mirror.codeforces.com/contest/1853/submission/215254923

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

would be funny if tourist regains no 1 in a Benq round

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

    I believe that with Benq as the questioner, the "quality" of this contests will not be poor. :D

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

    That's why this will be one of the most beautiful rounds ever

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

      indeed it was beautiful ,as a result i just watched those questions for 2 hrs straight

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

As a tester, I can confirm that this is a great contest and has great problems, much like another amazing contest by the name of CerealCodes :D

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

    As a tester, I can confirm that I will neither be able to teamsforces or codecode on this round.

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

      As a tester, I can confirm that willy is a god at rinbot and therefore codeforces.

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

As a problemsetter, I hope you all enjoy the problems (especially mine).

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

As a tester, I have enjoyed the round and I hope you also enjoy it.

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

As a tester, I can confirm that this contest is truly one of the contests of all time

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

    He speaks not the truth. He isn't a tester; he is actually a VIP tester.

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

      As a VIP tester, I can confirm the validity of this statement

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

it has been scientifically proven that if you play genshin impact you will gain rating on this round!!!

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

Time to enjoy -167 delta in a div.1 round!

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

"The Div. 2 round will be rated for participants with rating below 1900 , while the Div. 1 round will be rated for participants with ratings which are at least 1900"

Does this mean that I, as a purple, am forced to participate in Div1 round?

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

Scared for my first div1 round. Hopefully I can actually solve 2 problems and avoid instant demotion to blue.

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

As a tester, I hope u enjoy the round as much as I did

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

I'm afraid to participate cz of your handle.

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

Hoping to become purple. ( Please make this my most memorable contest ever! )

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

Problems are high quality. Definitely try to participate!

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

As a tester I can confirm that this round is just as good as Oshi no Ko chapter 123.

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

As a problemsetter, I can confirm at least one of the problems will feature Ninomae Ina'nis from hololive-EN Myth!

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

    wah

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

      Wah!

      こんぺこ、こんぺこ、こんぺこ！ホロライブ３期生の兎田ぺこらぺこ！どうも、どうも！

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

As a tester, I can confirm the problems will be problems.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i hope to be blue this time

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

Very rare to see this many colors in the author list

→ Reply
»
16 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Hoping for a good div2 round.

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

as a problemsetter who didnt problemset, i can assure you that this will be a great contest :D

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG!! Benq is the writer. Sounds Good!

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -34 Vote: I do not like it

As the president of CerealCodes and a contest organizer, I can assure you that the problems are of high quality (just like CerealCodes problems).

→ Reply
»
16 months ago, # |
  Vote: I like it -9 Vote: I do not like it

As a participant i recommend you to participate.

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

Why didn't PurpleCrayon test when Purple Cry is an author?

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

    ofc we asked, but he wanted to participate officially instead.

    PurpleCrayon will win IOI 2023!!!

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

As a tester, I can confirm that this round will not only give you lots of rating but ginormous muscles too :D

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is div.2 also 2.5 hours?

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

    It'll be fixed so that both rounds last the same amount of time.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only one who noticed this announcement was made 7 weeks ago?

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +89 Vote: I do not like it

Hi everyone,

We would also like to mention this round was mostly made possible by problemsetters from the CerealCodes initiative!

What is CerealCodes?
→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm trying to register to CerealCodes but I can't find my country (Turkmenistan) in countries. :(

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

      Hi, the issue should be fixed :)

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

As a tester, I can confirm that problemsetting might have happened.

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

Benq!This round would be very interesting

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope I can be a candidate master.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

as a cyan participant, i hope to be blue after this contest

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

Excited to see tourist in round prepared by Benq

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

Do you mean that you will make us cry in this contest :(

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

will be fun to see if tourist takes back rank 1 in a Benq round

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

    Looks like someone copy paste the same line (⁠•⁠‿⁠•⁠)

    → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

The panda looks like Firefox)

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

As a participant I hope I'll get over this damn pain this round T_T

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope for color change!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you saying Div1 has easier problems?

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

    Based on the score distribution? No, Div1A is the same problem as Div2C, Div1B is the same problem as Div2D etc., the problems are harder. These problems just give less score in Div.1 because the scoring is relative to other problems and usually scoring is started from $$$500$$$ points.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello Benq. This is a fellow United States of America Computing Olympaid competitor, and wishes for you to not write any problems in the USACO 2023 December Gold contest. If this is possible, I will certainly be elated. Please consider others emotions before problem setting for the USACO 2023 December Gold contest.

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

    Skill issue

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

      Shut yo skill issue ahh up you spedialist

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

        Shut yo novice starter learner student trainee apprentice probationer recruit newcomer fledging anti-orz ahh up you unrated newbie in the insanely big world of cp.

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

          Upvoted. Thank you, fellow specialist

          → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to become a green , also good luck for everyone

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

I LOVE YOU CRY :) MY BEST FRIEND, THANK YOU FOR PREPARING A CONTEST <3, good luck to all!!!!.

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

you fool me, i fool you！ Good luck

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

Red panda is so cute!

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

It's even a little insulting — authors have all possible colours except green...

Anyway, why there is such a variety — is it some university project or so on?

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i hope to be blue this time

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

Feeling excited to give this contest.

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

good luck for all

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

I have a question, why the problems of Div.2 have higher score than the problems of Div.1?

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

QaQ

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

Whoever came up with div2 problems B and C I hope that for the rest of their life they would only get pairs of integers as their birthday presents.

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

    That joke was amazing. Div 2 B was did feel kind of out of place for a Div 2 B though. But the C was a really good problem for its position. But its a common and really frequently used fact that certain sequences grow really fast, at some point youll have to get used to it.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Imagine 1434ing us

1434 stands for
→ Reply
»
16 months ago, # |
  Vote: I like it +7 Vote: I do not like it

to my cyan color, i will miss you

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

C>>>>>>>A,B

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

Disgusting problem b and c

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

Nightmarish for me..atleast

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

very strange and hardest contest I have never seen ever...

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

Don't know what this round's authors were thinking, but I feel like there is a huge gap between A and B. As a div 2 participant I feel like this round would have been a nice round if B would have been C and C would have been D.

→ Reply
»
16 months ago, # |
  Vote: I like it -16 Vote: I do not like it

ty guys for the another speedforces round

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

    As a wise man once said, "go solve some problems and learn to use binary search'

    → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

div2 c>>b and b>>a. Doesn't feel like this is a well balanced contest :(

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

    Both Div 2 B and C, you had to spot very commonly used ideas. It was your fault you dont have the experience. As a wise man once said, "go solve some problems and learn to use binary search'

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

does the problem ratings depend only on the ratings of the people who solved it or it also depend on the position of problem ??

like consider same problem in div2C and div4H, then comparitivley div2C will have higher solves than div4H

so, if only the ratings of the problem solvers is considered then div4H will have higher rating than div2C.

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

As a div1 contestant, i gave up A after reading it :(

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, We are cry ing :(

→ Reply
»
16 months ago, # |
  Vote: I like it -9 Vote: I do not like it

More then a half div1 contestants gave up after reading Div2C. Sounds like something that shouldn't happen... Hardest div2C... Spent an hour, but still have as few ideas as after i read it for the first time...

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

    can you explain how you did div2 B please

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

      I am author of B. Intended is to brute force over element before N and reconstruct the sequence from the back. Note that Fibonacci grows fast, so sequences must be short (max length is around log(N)).

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

        What was that C, bro?

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

          We actually considered making it C, but since the solution is just brute force, we decided against it.

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

      Since $$$f(i) = f(i - 1) + f(i - 2)$$$ is increasing really fast. If $$$k > 40$$$ (or so) it will be impossible to construct such a sequence.

      Otherwise we know, that $$$a_{k - 3} + a_{k - 2} = n$$$, so we can iterate over all possible values of $$$a_{k - 2}$$$ and $$$a_{k - 3}$$$ will be equal to $$$n - a_{k - 2}$$$, $$$a_{k - 4}$$$ will be equal to $$$a_{k - 2} - a_{k - 3}$$$ and so on. If this sequence is non-decreasing and $$$a_0 >= 0$$$ then we add $$$+1$$$ to our counter.

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

      You can notice that $$$n=F_{k-1}*a+F_{k}*b$$$, with $$$F_k$$$ is the $$$k^{th}$$$ Fibonacii number, and $$$a,b$$$ is first two number of our sequence $$$(a <= b)$$$. Now we can easily count all $$$(a,b)$$$. Sorry for my bad English.

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

        Yeah. This is exactly what i Did. One of the best math problem I had solved in a while. Also C is also very very genius problem. Those who are hating C are the ones low IQ people. Smart ones knows who good the problem is.

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

Just want a honest opinion , Really 7000 plus people were able to solve B , got me into thinking , for a hard time

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

    Yes. It was very easy, If you would have solved around 40 1500 math rated problems. Because in these types of problems generally we fix something. For example --- To build the whole sequence we just need starting A and B right!!!.

    So just bruteforce all the values of A and B.

    There are bunch of problems in 1400-1500 rating.

    The idea is very very well known.

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

      Oh maybe, yeah I haven't done too much problem solving and the first approach I started was to use matrix exponentiation and then use binary search over 1 to n to find a and b possibilities, but were not able to implement properly, thought that O(nlognlogk) solution would be okay, but it was much simpler, tookna long time to realise the constraint of 30 and dp approach. Hope to do well in upcoming contests

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

My approach for getting strong idea for C:

Spoiler
→ Reply
»
16 months ago, # |
  Vote: I like it -12 Vote: I do not like it

I failed to impress Ntarsis moreover i failed to impress myself.

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

Div1C

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

    Hi, we were just made aware during the contest. Tbh, just unlucky, none of us were aware of the problem, including the 40 testers and coordinator

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

How to solve div1C?

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

Wow I like Constructive and MathForces so much!!!

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

IMHO Problem B to me was like you either know it or you don't. Like, I can't get a piece of paper and start working on it and finally get an answer, but 7000+ people solving it really got me questioning my existence.

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

    Very surprising considering we found 5 different solutions for B in testing (intended was just brute force).

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

    You don't need to downgrade yourself by comparing yourself with others!.

    The idea is very well known. Just study about it, so the next time you see this problem make sure you are the first one to solve among your friends!!!

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

First time solving d1ABC!

great problems d1C&D!

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

mathforces

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this contest is not for div 2 coders

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

    why? I mean ppl around 1300-1500 can solve first three problems

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

      why so many downs? I really stupid & nob, but can still solve first three problems ( i mean pretests )

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

        Bro, you able to solve it doesn't mean everyone solve all three problems

        → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hardest Div2C I've ever seen

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

    We actually had a harder version before lmao. Originally, K<=10^9.

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

      and what is the difference now?

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

        Now, more binary search solutions pass and an alternate implementation in O(k) time also passes.

        → Reply
»
16 months ago, # |
  Vote: I like it -33 Vote: I do not like it

Don't make contests just to Show-off.

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

Is there anyone who can give some hint on 1C? I have absolutely no idea.

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

    In this problem, you want to cover an array with intervals such that the $$$i$$$-th octopus is covered by $$$a_i \pmod k$$$ intervals (if $$$a_i = k$$$, set it to $$$0$$$). The idea is that you want to process the array from left to right while opening or closing intervals. Opening an interval has a cost of $$$1$$$ while closing an interval is free.

    Hint 1
    Hint 2
    Spoiler
    → Reply
»
16 months ago, # |
  Vote: I like it +14 Vote: I do not like it

wow. It was really ( i mean really ) interesting contest ( for me, as div2 user). Amazing second & third problems, like, for me, they was hard, but really interesting. Second was on idea mostly ( like not many fibonacchi numbers ) & third was on idea & realization ( as for me i mean )

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

cry (The author of this blog) really made me cry during the contest.

S/He literally gave the spoiler of the full contest in the handle.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div.2(x) Div.1.2(√)

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

Problem B can be easily solved thanks to this post.

So we can iterate over all values of $$$f_1$$$ from $$$0$$$ to $$$n$$$ and check if there exists integer $$$f_2$$$ such that $$$f_2 >= f_1$$$ since we need a non decreasing sequence.

We don't even need to check for $$$k > 30 $$$, as $$$f_{30} > 2 * 10^{5}$$$ . So the answer for all such values of $$$k$$$ will be 0.

Time complexity : $$$O(n)$$$

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

Div2C was so difficult but once you solve it ,it seems easy.

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

    can you give a hint, I just got to the point that

    max element that will be canceled on last day = max_element + (k — 1) * (max_element — number missed in b/w)

    for eg = 1 3 5 7 number missed = (2, 4, 6) = 3 k = 2

    max element that will be canceled on last day = 7 + (k — 1) * (7 — 3) = 7 + 2 * 4 = 15

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

Please somebody tell me how to do div2 C and how you came to this conclusion :(

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

    consider the items the first number deletes every round

    note that it increases by 1 -> i.e. 1, 2, 3, etc until you reach the position of the second number, then it increases by 2, then 3 when you reach the third number, etc

    my code:

    void solve() {
  int n, k; cin >> n >> k;
  vector<int> a(n); for (auto& x : a) cin >> x;
  int cur = 0; int curv = 1;
  for (int cnt = 0; cnt < k; cnt++) {
    curv += cur;
    while (cur < n && curv >= a[cur]) {
      cur++;
      curv++;
    }
  }
  cout << curv << endl;
}
    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Wow, nice observation!! Thanks a lot

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

      reasonings of such patterns?

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

      why are you updating curv and cur when curv>a[cur] ?

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

    My intuition was that answer can be a very big number, so we might be able to use Binary Search on Answer. Then the predicate function clicked immediately.

    f(x) = Count of numbers deleted before 'x' == x-1

    Now how did I calculate f(x) ?

    I observed that once we delete some numbers, the "indices move forward". So for a particular 'x', once an index 'i' crosses 'x', deletion of 'ith' smallest element now doesn't affect f(x).

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2 B, I got that we want number of integers in the interval $$$[nx_{k-1},nx_k]$$$ where

$$$x_k := \frac{f_{k}}{f_{k+1}}$$$

Here $f_i$ is $$$i$$$-th fibonacci number with $$$f_1 = 0, f_2 = 1$$$. It can be shown that

$$$x_n = \frac{1}{1+x_{n-1}}$$$

with $x_1 = 0$.But when I tried to evaluate this, I was getting TLE on pretest 5; is the way to go?

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

While I'm waiting for solution, here is what I wrote in $$$B$$$ and just now noticed, that this is incorrect.

Corner cases: all are $$$0$$$, all are $$$n$$$, there are $$$0$$$ and $$$n$$$.

For simplicity, there is $$$0$$$. It not, do $$$a_i = n - a_i$$$.

Some number are positive, others are negative. Sort all values. Some suffix is positive and has all edges. Let size of suffix be $$$cnt$$$, sum on suffix be $$$s2$$$ and sum on prefix $$$s1$$$. If $$$s2 - s1 = cnt^2$$$, this is correct split position, answer is $$$YES$$$. Now to build it. Look at suffix, let it be $$$a_1, \dots, a_k$$$. Subtract from all of them $$$cnt$$$. Let $$$idx = 1$$$. Take $$$a$$$ values by blocks of same values. For each block put $$$-idx$$$ to front of result vector $$$a_i$$$ times, then put $$$idx+1$$$ to back of result vector size of block times, add $$$idx += 2$$$. At the end append left $$$-n$$$ to front of result vector.

Further steps:

  1. Write stress

  2. See, as it immedeately asserts, investigate test

  3. Cry, write this

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

    About problem $$$A$$$. Well, that looked obvious for me, that I have just to $$$k - 1$$$ times do $$$x = a_x$$$, where $$$a_x$$$ is a vector of non-mentioned numbers.

    Though, I think that $$$a_i \le 10^9$$$ does not make sense, and makes implementation move complex without any reasons (I wrote something like scanline, also thought about set::lower_bound, of binary search).

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

div 2 c Is a good problem to think about for 3 days after contest

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

Problem B and C were good, amazing contest!!!.

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

This was hard. Managed to lose only 21 (according to carrot), i'll get purple in the next context.

Also my brain farted a little on B when i tried using diophantine equations or double for to find the coefficients. Anyways the problems are nice, B is a very cool property of fibonacci-like sequences

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

2*Div 1

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

I got some inspiration from this task to solve D1A/D2C

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

GoodBye my chance to become master :( I really have hard time

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

Hardforces for div2

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

Nice problems!

Solution for B (if anyone needs):

-> Form the Fibonacci Series up to 200005, call it arr

-> For a Fibonacci Series of length k and last term n, it looks like this:

a, b, b + a, 2b + a, 3b + 2a, 5b + 3a, ....., arr[k — 1] b + arr[k — 2] a

-> The equation is arr[k — 1] * b + arr[k — 2] * a = n

-> Fix the values of a from 0 to n and find if there exists an integral solution b for the equation

-> if exists, ans++

-> One edge case: n is only up to 200000, so k can't be > 200000, if so answer is 0

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

:

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

When every problem in the contest seems solvable but you're still not able to solve all :(

→ Reply
»
16 months ago, # |
← Rev. 5   Vote: I like it +9 Vote: I do not like it

I overkilled problem B by doing fast general fibonacci calculation to determine the last element of the sequence in log(k) time by doing fast squaring of matrices for the fibonacci sequence.

Then I bruteforced over all of the first element, binary searching for the second element using my fast_fibo function to see which one is closest to n. If the fast_fibo(i, j, k) == n, then i increase the count

Time complexity: O(n log(n) log(k)) ??? LOL

I was like: "Theres no way this can be a problem B..."

EDIT: Just failed system tests LOL

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

    haha it seems this round has a lot of overkillable problems

    people "solve" problems B and C and say they're implementation hell when theres actually a clean 10 line solution for both of them

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

      Yeah, it turned out there are pretty short implementations for C and B, but coming up with that idea is not easy..

      → Reply
»
16 months ago, # |
← Rev. 4   Vote: I like it +24 Vote: I do not like it

I came up with a pretty easy and intuitive solution for div2 B after about an hour.

Div2 B
→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    can you please tell(maybe briefly) about the intuition...

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

      I have just simulated the whole process according to the question. For a given number $$$N$$$ at $$$k$$$ th position, I am brutally checking if it is possible to have some number $$$x$$$ $$$(0 <= x <= N)$$$ at $$$(k - 1)th$$$ position.

      Check function is really simple, if we just fix $$$(k - 1)th$$$ number and $$$k$$$ th number in a fibo sequence, we can easily determine that $$$(k - 2)th$$$ number will be the difference of $$$k$$$ th number and $$$(k - 1)th$$$ number. With that we can easily determine if the sequence we are getting by fixing those $$$2$$$ numbers is a valid sequence or not by recursively calling the same function with different values of $$$N$$$ and $$$K$$$. Sequence is Valid if $$$k = 0$$$ and $$$N >= 0$$$ otherwise if $$$N$$$ become negative, the assumed fibo sequence is inValid.

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

The problems are so hard that very few people are able to solve CDEF in div.2

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

B felt a little tougher than a usual div2 B, A was perfect

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

Performed really badly! Don't even feel to give cf contests anymore!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2 B I tried hacking with this solution 215216845 with test case: 1 200000 1000000000 but judge gave me unsuccessful hacking verdict. Can anyone explain why the above mentioned solution won't TLE on this test case. Also the solution got FST on test 21 with TLE verdict.

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

    This was already a pretest

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

      Yes but it runs in O(1e9) which should TLE?

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

        1e9 fairly fast operations isn't too surprising

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

          I lost 100 points for 2 unsuccessful hacks. I later realised in last few seconds that I should have used 1 1000000000 for 200000 times. It might have given me 150 points from my room.

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

    Exactly same thing happened with me , I used it 10 tim s but still passed, i'm still not sure how a O(1e10) solution could pass

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved B with just brute force, just like what the problem said: Solution

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

for problem b, the constraints are tricky because the highest Fibonacci term (where in the original Fibonacci sequence the first two terms are min possible ) less than 2 * 10 ^ 5 is the 27th term(0-based) so it's okay to brute force the solution. you know that the last element is n so start from pos n — 1 and try all numbers that you can use from n to 0 and call it x for every x use recursion to build the sequence, if at any pos you can't get a valid value ( positive and less than the next value in sequence ) so this x is invalid

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

very nice problems

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

div1 A is so hard,but div1 B is too easy.There's also a huge gap between problem B and C.

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

    Opposite for me, I took so long to find the correct observations for div1B/div2D meanwhile I solved div1A/div2C quite easily with binary search

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

Nice finally some quality stuff!

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

Binary search is really a great thing

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Congrats to all the top-participants!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I used a mysterious method to pass this problem in C of Div2, with time complexity O(n). Is anyone interested in proving the right thing to do? https://mirror.codeforces.com/contest/1853/submission/215254923

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved Problem C with binary search. I search if we can delete a prefix of numbers 1, 2, 3, ... x using given operations. If we can delete it then we can also delete prefix upto x-1, x-2 and so on.

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

I have a Question about a problem, in problem D in Div 2, or problem B in Div 1, I sent my code which was graded as a RTE in case 18, I simply changed the variables from long long to int, and magically the problem was an AC. The more I try to explain why this happened, the more confused I am, mostly because I only use 4 arrays of size 2x10^5 and a few extra variables.

I'm sending my submission that got an RTE: RTE code

And my submission that got the AC: AC code

I would thank so much to whoever explains me why this occurred.

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

    Take a look at Ticket 17000 from CF Stress for a counter example.

    Ideone Logs

    There's clearly an out of bounds access in your code, you just got lucky with your second submission due to how the memory is mapped for int vs long long. It should be easy to find out the troublesome line using the testcase from the above site. If you're still not able to figure it out, I'll share the exact line number later.

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

Why 256MB ML?

Sometimes people ask this question and the answer is often like "Hmm, we didn't intend to accept or reject your solution. We just didn't recognize such a solution, and used the default ML". Today I got MLE in Div1D and I guess this is yet another example of the above story.

This is certainly my mistake, and I won't complain about it to the authors. However, I'd like to ask why is the default ML 256MB, and I'd be happier if it was 1024MB or something. Is there a particular reason for the current value, or it's just that nobody cares?

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

    hi, i prepared div 1d, and indeed there were a lot of things i could do better, i apologize :(

    It is like you said, we did not consider raising the ML since all testers' solutions had very little trouble passing under the constraints; all of the solutions that AC pass with minimal memory.

    Next time I will try to be more careful, once again, sorry :(. But I do think you raise a good point. A lot of the times blatant MLE can be caught by TLE anyways, and unless the problem is about optimizing memory (which usually isnt fun) there is little point in blocking slightly worse solutions with a valid memory and time complexity. I will try to keep this in mind for the future.

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

Ratings updated preliminary, it will be recalculated after removing the cheaters.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Happy for becoming pupil :)

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

disappointed , couldn't solve C

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

should've swapped c and d in div2

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

215249497 Hmm, I have O(n) solution for problem D. Can somebody give me a counter test?

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

    Well, it is possible to solve D1B/D2D in $$$\mathcal{O}(n)$$$ using counting sort.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B was actually pretty hard 4 a normal div2 B.

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

https://youtu.be/9fNJvvqVTpo

The problems B,C and D of div2 was very good learnt a lot, not able to perform well during contest.

try to explain solutions of Problem A,B, C and D in this video

problem A: try to unsort a[i] and a[i+1] for each i.

problem B: try to reach Ax+By=N; where A is kth no of fibonacci series {f[0]=1,f[1]=0}; where B is kth no of fibonacci seires {f[0]=0, f[1]=1}; and find out the no of integer solution of x and y such that x is less then or equal to y;

problem C:- what is the position of x after first day? and then in how many days x will be removed;

problem D:for every i and j (abs(bi)!=abs(bj)) and try to find out number of positive intergers in imbalanced array, and then fill positive intergers one by one and according to need fill negative integers.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solve Div2 C differently. After some day it falls into a pattern. So our task is to find when it falls upon a pattern. Take a look at my code 215241713

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

    Isn't this very similar to simulating deletions and a solution in this comment. And if by a pattern you mean that after some day we are going to start skipping n consecutive numbers for every single one of the remaining days — yes, using brute force you can see that for any arbitrary inputs at some point the smallest remaining number is going to be increasing by n each time after each round of deletions.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the solution of div2 c question?

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating of Problem D ?

→ Reply