cry's blog

Invitation to Codeforces Round 887 (Div. 1, Div. 2)
By cry, 3 years 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), fast-fourier-transfem, 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. EvenImage

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 (221)
| Write comment?
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it +189 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
»
3 years ago, hide # |
 
Vote: I like it +47 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

I'm afraid to participate cz of your handle.

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

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

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

Problems are high quality. Definitely try to participate!

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

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

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

i hope to be blue this time

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

Very rare to see this many colors in the author list

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -21 Vote: I do not like it

Hoping for a good div2 round.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

OMG!! Benq is the writer. Sounds Good!

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it -9 Vote: I do not like it

As a participant i recommend you to participate.

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

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Is div.2 also 2.5 hours?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +52 Vote: I do not like it

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

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

As a pupil,hope to become newbie.

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

Benq!This round would be very interesting

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

hope I can be a candidate master.

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

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

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

Excited to see tourist in round prepared by Benq

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

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

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +36 Vote: I do not like it

The panda looks like Firefox)

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope for color change!

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

Are you saying Div1 has easier problems?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hoping to become a green , also good luck for everyone

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

you fool me, i fool you！ Good luck

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

Red panda is so cute!

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i hope to be blue this time

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

Feeling excited to give this contest.

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

good luck for all

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it -6 Vote: I do not like it

QaQ

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Imagine 1434ing us

1434 stands for
→ Reply
»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

to my cyan color, i will miss you

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

C>>>>>>>A,B

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

Disgusting problem b and c

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

Nightmarish for me..atleast

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

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

ty guys for the another speedforces round

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +32 Vote: I do not like it

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

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

Yes, We are cry ing :(

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

thank you codeforces for realising me that cp is not for me

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    can you explain how you did div2 B please

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← 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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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 \gt 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 \gt = 0$$$ then we add $$$+1$$$ to our counter.

      → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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 \lt = b)$$$. Now we can easily count all $$$(a,b)$$$. Sorry for my bad English.

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
»
3 years ago, hide # |
← Rev. 5  
Vote: I like it 0 Vote: I do not like it

My approach for getting strong idea for C:

Spoiler
→ Reply
»
3 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

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

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

Div1C

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it +35 Vote: I do not like it

How to solve div1C?

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

Wow I like Constructive and MathForces so much!!!

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it +60 Vote: I do not like it

First time solving d1ABC!

great problems d1C&D!

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

mathforces

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

I think this contest is not for div 2 coders

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

hardest Div2C I've ever seen

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -33 Vote: I do not like it

Don't make contests just to Show-off.

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← 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 \gt = f_1$$$ since we need a non decreasing sequence.

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

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

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

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Very unbalanced contest C was very annoying

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

2*Div 1

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

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

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

Hardforces for div2

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

:

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← 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 \lt = x \lt = 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 \gt = 0$$$ otherwise if $$$N$$$ become negative, the assumed fibo sequence is inValid.

      → Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

very nice problems

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Nice finally some quality stuff!

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

Just realized after the contest that B could be solved by brute force bcoz Fibonacci series is exponential , great contest overall!

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

Binary search is really a great thing

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

Congrats to all the top-participants!

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it +37 Vote: I do not like it

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

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

Happy for becoming pupil :)

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

disappointed , couldn't solve C

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

should've swapped c and d in div2

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

B was actually pretty hard 4 a normal div2 B.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can anyone explain the solution of div2 c question?

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

Rating of Problem D ?

→ Reply