pakhomovee's blog

By pakhomovee, 15 months ago, In English

Hello, Codeforces!

We are glad to invite everyone to participate in Codeforces Round 893 (Div. 2), which will be held on Aug/15/2023 17:35 (Moscow time).

Please note the unusual start time of the round. This round will be rated for the participants with rating lower than 2100.

Our round is completely set by SIS (Summer Informatics School) students. We did our best to prepare interesting and creative problems. You can check out some of the previous rounds prepared by SIS students: Codeforces Round 816 (Div. 2), Codeforces Round 815 (Div. 2),Codeforces Round #694,Codeforces Round #612,Codeforces Round #530.

Task authors and developers: Daria arbuzick Grekova, Petr green_gold_dog Losev, Yaroslav Kihihihi Semenyuk, Artem ArtAlex Alexeev, Anton NToneE Egorov, Fedor FedShat Shatokhin, Timofey IzhtskiyTimofey Izhitskyi, Egor salyg1n Salygin, Vladimir plagues Gerasikov under the guidance of Evgenii pakhomovee Pakhomov

We are very thankful to

You will have 5 tasks and 2 hours to solve them. We recommend you read all the problems. The contest may contain interactive problems! Make sure to read this post.

The scoring distribution is $$$500-1250-1500-2000-(1750+1000)$$$

Note that the round has been moved one hour later. The contest start time is Aug/15/2023 17:35 (Moscow time)

We hope that you will enjoy our tasks!

Good luck!

UPD: Editorial

UPD 2: Congratulations to the winners!

Div. 2:

  1. dong_liu

  2. yydtq

  3. wk______tzc

  4. qwesda

  5. Van_Dijk

Div. 1:

  1. jiangly

  2. neal

  3. BucketPotato

  4. kotatsugame

  5. YocyCraft

First solves:

A. ball_of_wool

B. ecnerwala

C. nigus

D. jiangly

E1. grass8sheep

E2. yydtq

  • Vote: I like it
  • -62
  • Vote: I do not like it

| Write comment?
»
15 months ago, # |
  Vote: I like it +46 Vote: I do not like it

More authors = better problems (as an author) xd

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +59 Vote: I do not like it

    this didn't age well. to be fair, most of the problems were interesting, but B and C were definitely ordered incorrectly

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +43 Vote: I do not like it

    Problem B should be a literary comprehension problem, not a coding problem.

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

      It just doesn't fit the style of Codeforces problems. Good problems should be hard to solve instead of being hard to understand.

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

        Fully agree. I spent most of time to understanding what to do and then very little time to coding.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldn't reach pupil in the last contest.. I hope I reach pupil this time. Thanks for the contest.

»
15 months ago, # |
  Vote: I like it +11 Vote: I do not like it

If so many people with a high rating came up with tasks, then there is a high probability of high-quality tasks

»
15 months ago, # |
  Vote: I like it +80 Vote: I do not like it

As an author, I love phonk.

»
15 months ago, # |
  Vote: I like it +42 Vote: I do not like it

As a person who reviewed all of the tasks and gave the authors valuable advice, which helped them to improve the contest, I encourage you to participate and enjoy the problems!

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest may contain interactive problems. This statement is enough to make you worried.

»
15 months ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

Good luck!

»
15 months ago, # |
  Vote: I like it +26 Vote: I do not like it

As a tester, I suggest you to read all the problems.

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

    As a not tester I suggest everyone to listen to you.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"In the recent contest, i have noticed a significantly larger number of contestants solving problems A, B, and C compared to previous contests. Are the problems easier, or are the contestants more intelligent in your opinion?"

»
15 months ago, # |
  Vote: I like it -48 Vote: I do not like it

As a regular codeforces user, I will take part in this round!

»
15 months ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

as a tester, i wish you good luck, problems are good

»
15 months ago, # |
  Vote: I like it +4 Vote: I do not like it

omg , independence day contest

»
15 months ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

This time is just right because it’ll start at 21:35 in China and when it ends at 23:35 I’ll just sleep.

UPD: Postponed to 22:35…

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

    Why u guys sleep so early? You can study late night too.

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

    Not anymore :|

»
15 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

this is the best contest that i have done before :vvvvv

»
15 months ago, # |
  Vote: I like it +7 Vote: I do not like it

as a tester, i wish you good luck, problems are good

»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Is it necessary to use faster languages for this contest?

»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

OMG 5 problems with so many authors. That would be a great round :)

»
15 months ago, # |
  Vote: I like it -11 Vote: I do not like it

wssb

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

A very good starting time for us Chinese.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, I hope i cna learn something new in this competition and hope everyone can get good results.

»
15 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Only 5 problems? then 5th one could be 2400+ :( This might lead to other probs being harder than usual too

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Considering that one of the authors of the tasks is green_gold_dog, chinese users are advised to refrain from writing this competition...

»
15 months ago, # |
  Vote: I like it +27 Vote: I do not like it
»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Good luck!

»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Worried about the interactive problem

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Wish to become Master. Just a bit below it :)

»
15 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Scoring distribution?

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully there won't be any down site moments again during the contest :)

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

delayed :l

»
15 months ago, # |
  Vote: I like it +61 Vote: I do not like it

1 refresh cost me 1 hour

»
15 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Please note the usual start time of the round. This round will be rated for the participants with rating lower than 2100.

»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

OMG I will have to sleep one hour later...

»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Why is the contest postponed by an hour, which makes my sleep worrying.

»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Time not unusual now...

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It was probably delayed because the site kept going down.

»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Why u delay an hour? As we can see, CodeForces is going very well.

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

    For we Chinese Coder, we have to stay up for another one hour.

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

      Agree

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

      Oh sorry, I'm sorry to hear that there was a power outage in the city today. Hope a good round!

»
15 months ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

"Please note the unusual start time of the round."

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Huh? What's going on with start time?

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

    Please start some professionalism and if you want to delay the start of the contest, do it earlier than 5-10 minutes before :)

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

delayed?-_-

»
15 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Score distribution not updated yet.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did the contest be postponed?

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I woke up early, just for it to get delayed. rip hopefully it will still be a good contest

»
15 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

pakhomovee thank you

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

    Is this really needed? All you need to do is just solve problems

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

      Scoring distribution gives some idea about problem difficulty (in case you haven't figured this out yet)

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

        Ok but you always see scoring distribution while contest

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

    posted it as soon as I found out that Codeforces is up!

»
15 months ago, # |
  Vote: I like it +12 Vote: I do not like it

"Please note the usual start time of the round."

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

why postponed by 1 hour

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

    From codeforces telegram:

    Unfortunately, there was a power outage in the city today, which caused a disruption in Codeforces' operation. At this moment, Polygon and other services are already operational, and Codeforces is close to being up and running. We estimate that the start will happen in about 15-20 minutes. Considering that the "Codeforces Round 893 (Div. 2)" was expected to start around this time, we have decided to postpone the start of the round by 1 hour. Therefore, the round will begin at 14:35 (UTC) / 17:35 (MSK).

    tldr: site were down for like an hour and started working ~10 mins before contest were about to start so codeforces decided to postpone

»
15 months ago, # |
  Vote: I like it +61 Vote: I do not like it

Unusual time + Unusual delay = Usual time

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For now the start time of the round is usual again xD

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

in the end, it's amusingly held at the usual time again >_<

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

    I never understood why some rounds happen at unusual time in the first place.

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

      Actually, participating in contests at the 'usual time' can be a bit tough for participants from East Asian countries, who might have to stay up late to take part. I think it would be nice to schedule a contest at an 'unusual time' once in a while:) Maybe Codeforces are thinking about this too, considering people from all around the globe

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Note that the round has been moved one hour later.

OK but why? Any explanation for participants maybe?

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

    `

    Spiler

    `

»
15 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Authors: note the unusual time of the contest

(probably) Server issues: Let me fix that for you.

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hmm I guess that the interactive problem will be divided into 2 subtasks :))

»
15 months ago, # |
  Vote: I like it +34 Vote: I do not like it

"Please note the usual start time of the round."

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

    "That's magic! No sooner had I written the previous message than Codeforces started working. Hooray!"

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is it rated for all ??

»
15 months ago, # |
  Vote: I like it +27 Vote: I do not like it

If someone was wondering why the initial start time was unusual, that's because dinner in SIS starts at 18:30 Moscow time :)

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

    If someone was wondering why the contest got postponed, that's because the authors were trying to come up with problems B and C in the last 10 minutes (they have failed miserably).

»
15 months ago, # |
  Vote: I like it +32 Vote: I do not like it

The contest is postponed, probably because Mike has been playing Genshin Impact excessively.

已延丁真,鉴定为:玩原神玩的

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

swap(problem B,Problem C)

»
15 months ago, # |
  Vote: I like it +24 Vote: I do not like it

abomination of a contest

my code for e1 should pass in every way, shape, or form but why mle so low when stuff can be up to 10^6???

»
15 months ago, # |
  Vote: I like it +7 Vote: I do not like it

I don't understand with so many authors no one noticed that they should swap B and C. Current C is an easy B at most

»
15 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

C<B

»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I miss +ve $$$\Delta$$$

»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

A<C<<B . C was easier than B.

»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

The problem statement of B was quite tricky. First, I couldn't notice that I must remove exactly one cookie seller.

»
15 months ago, # |
Rev. 3   Vote: I like it -39 Vote: I do not like it

.

»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to optimize memory in E2?

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

b was very tricky , i loved the problem but according to contest , it doest not fit for B

»
15 months ago, # |
  Vote: I like it +102 Vote: I do not like it

AK'ed in 82min. The memory limit of E2 might be too tight for me.

A: Obviously two players will press buttons which can be pressed by both players if possible. So we can assume the 1st player has a+ceil(c/2) buttons and the 2nd player has b+floor(c/2) buttons.

B: The problem statement is unclear: "the number of cookie sellers, such that..." can be considered as "the index of the optimal seller to be removed" instead of "how many sellers can be removed to minimize the number of cookies". Back to the solution: For 2 adjacent sellers s[i] and s[i+1], petya will eat ceil((s[i+1]-s[i])/d) cookies from position s[i] to s[i+1]-1. Therefore, if we add 2 unremovable sellers s[0]=1 and s[m+1]=n+1, the number of cookies will be sum(1<=i<=m+1)(ceil((s[i+1]-s[i])/d)), then we can brute force for every removable seller.

C: The maximum score is floor(n/2), which means (1, 2, ..., floor(n/2)) can be values of gcd(a[i], a[i+1]), because if t>floor(n/2), then 2*t>n, but if a[i]!=a[i+1] and gcd(a[i], a[i+1])=t, WLOG assume a[i]<a[i+1], then a[i]>=t and a[i+1]>=2*t, which is a contradiction. On the otherside, the permutation (1, 2, 4, 8, ..., 3, 6, 12, ..., 5, 10, ..., 2*k+1, 2*(2*k+1), 4*(2*k+1), ...) can reach this upper bound.

D: We need to find following values:

pre[t][i]: the maximum size of consecutive block of '1' in the substring s[1, i] if we can flip at most t values.

suf[t][i]: the maximum size of consecutive block of '1' in the substring s[i, n] if we can flip at most t values.

They can be found by two pointers (keeping index i, j and make sure that the number of occurence of '0' in the substring s[i, j] is no more than t). Then for every pair (i, j) such that i<=j, we can take s[i, j] as the maximum consecutive block of '0', let cnt = the occurence of '1' in s[i, j], then L0=j-i+1 and L1=max(pre[k-cnt][i-1], suf[k-cnt][j+1]). We can get a valid pair of (L0, L1) for every pair (i, j), but for each L0 we only need to keep the maximum corresponding L1. Then we can get at most (n+1) different functions f(a)=L0*a+L1, then we can evaluate the maximum values on [1, n] by brute force in O(n*2).

E1: At first we create a tree with only a root node and no value, and a stack containing this root node. Then we can translate queries like this:

"+ x": Create a new node with value x, let the node on the stack top be it's parent. Push this new node into the stack.

"- k": Push the k-th ancestor of the node on the stack top into the stack.

"!": Pop the top node from the stack.

"?": Find the number of distinct values on the path from the root to the node on the stack top.

Using binary lifting we can find the k-th ancestor in O(log(k)), then we can build the tree and get the list of queried nodes in O(q*log(q)), and using dfs to find the answer for all nodes. Then we can solve the problem offline.

E2: To solve the problem online, we need to use persistent segment tree to do update and queries on the history version of an array. However, because the low memory limit of this problem, when using 12 bytes (3 int32 variables for value, left child and right child) for a node of segment tree (there can be O(q*log(X_MAX)) = 2e7 nodes in total), I got MLE for several times. But we can make some observation:

--- Once a tree node has been created, the answer corresponding to this node will not change. So we only need to find answers when doing "+ x" operation.

--- If value x is on the path from root to the parent of new node, the answer will be increased by 1, otherwise remain the same. So we only need to check the existence of a single value, instead of checking the sum on any certain range.

Therefore, we only need to keep 2 pointers to left child and right child (we use -1 as null pointer, which means there's no value exists in the subtree), and the space for a single node of segment tree will be 8 bytes, which fit the memory limit.

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

    Wow! Fast Editorial. Thanks

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

    Orz

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

    For E actually there is a kinda simple solution that just uses sets which I ACed after contest. You just need to maintain a records array and a pointer.

    The idea is that everything to the right of ur pointer may not be valid currently, while everything before is accurate. Then, in your records you can store (is this x 'useful' (contribute to distinct count), x, how many 'useful'). Then, to handle -k, you just jump the ptr to k before, to handle ?, just find how many 'useful' ptr is at, and to handle + x, its abit tricky, but you just need to keep track of the indices of useful x, and make sure there is one useful x before the ptr, so u can use another set to do it. Then you override the current record to the new record, (but make sure to store the change to handle rollback). Then rollback can be done with a stack.

    The key is to notice that suppose you delete and then add stuff, you must rollback the added stuff before rollbacking the delete so by doing that and restoring the records after rollbacking add, you are sure that your records are correct before rollbacking the delete.

    Submission: https://codeforces.net/contest/1858/submission/219002981

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Graphical Approach for Problem C

    For problem C, I modelled it using trees with an edge between every number n and its n/spf(smallest possible factor). After making the tree, I ran a normal dfs for the required array.

    Here's my submission: My Contest Submission

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

    Thanks for E1 solution!

»
15 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve B?

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

    Don't

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

    Think of calculating the answer without removing any element for all the prefixes and suffixes. Then you can compute the answer corresponding to the removal of ith element in constant time

»
15 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

i got stuck on B for almost an hour and needed 10' to finish D. spent 15' coding problem B and 40' to try to understand what the problem wants me to output.

why can't the author just cut the bullshit on problem statement? B problem statement is horrendous and confusing and open to different interpretations.

"The number of cookie sellers...." omg, just simplify it next time please.

The problem itself asks to get the count of cookie removals that result in the minimum cookie to be eaten. Just why? this is just to trip on the test case where 1 is in the input.

»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

B number problem are defficult than C

»
15 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

This contest went so well for me! I solved the first 3 problems (my best performance yet). Also, B was harder than C, which was kind of funny

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Balanced...

»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

there's a reason i save my vote till the end :)

»
15 months ago, # |
  Vote: I like it +23 Vote: I do not like it

B is one of those problems that is simple if you have the author's intended implementation in mind and torturous if you don't.

»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is B>C :/

»
15 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Any one got WA on pretest 5 on E1/E2? can you please kindly tell me what went wrong?

upd: i found reason

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

Are you sure you f**king passed English IV?

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Please open the practice as fast as possible, for I failed to submit my code in the last minute due to network jam :(

»
15 months ago, # |
  Vote: I like it +11 Vote: I do not like it

zero balance

»
15 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Statement for problem B was so bad.

»
15 months ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

Thank you so much for making E2 interactive instead of xor lastans.

My online algorithm get TLE on E2 but passed E1, because I thought can not use std::cin and ios::sync_with_stdio(false) in an interactive problem:(

»
15 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Worst Problem B statement I have ever seen.

»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

B is unclear.

»
15 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Had really high hopes.

»
15 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Second and third problem should be swapped. I almost fell asleep while reading the statement. Bad problem for B.

»
15 months ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

I don't understand why none of the testers realized that positions B and C must be changed

»
15 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Anyone else overkill D with CHT?

»
15 months ago, # |
  Vote: I like it +4 Vote: I do not like it

What a shit statement of B. Fully ruin my entire life.

»
15 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I can't understand Problem B. Statements are not clear and a lot of information makes me panic.

»
15 months ago, # |
  Vote: I like it +19 Vote: I do not like it

I just hate problems like B.
Especially if given at position B.
(may be i just dont like A or B having big statements.)

But its completely non obvious why suddenly ask count? I just assumed index and coded already.
And the statement was bit ambiguous too.

»
15 months ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

Why would anybody set strict ML in problem with persistent segment tree?

UPD: My bad, model solution doesn't require it

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What the tight memory limit on E? My submission for E got MLE since it use only 300MB.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

so many authors and testers in this round yet we have B much harder than C with terrible problem statement

»
15 months ago, # |
  Vote: I like it -17 Vote: I do not like it

One of the biggest mistakes of my entire life is upvoted this blog before start of the contest. (:

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

    Don't be dramatic bruh

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it -25 Vote: I do not like it

      How the fu*k is it drama? I was trying to CM hardly. Today I solved A/C too fast. You can't deny that B statement was shit (: also, when I read D in last 30 min, it was clearly solvable for me if I can manage 1 hours. But still if i can't solve D. I didn't get negative at least.

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

        you must be getting negative bro, as b has more than 4k submissions and you are 1870 :/

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

          Hello, sir. My guess ability is too low to understand that near means zero distance.

»
15 months ago, # |
  Vote: I like it +94 Vote: I do not like it

B was just crap problem. Phrasing was very confusing, for example why do you say a seller is "near" a bench instead of at a bench. Can a seller be "near" multiple benches? And in what world does the whole story even make any sense? Why would you eat a cookie where a cookie seller is if you already have unlimited cookies. And why would you even buy a cookie in the first place if you already have unlimited cookies. Why not just say: You eat a cookie at position 1, after walking for $$$d$$$ units without having eaten a cookie and whenever there is a bench, where the benches have positions on the coordinate axis.

Also $$$m$$$ was only bounded by $$$n$$$ (which was fixed after 30min), so you either tried to solve the problem for $$$m \le 10^9$$$ or saw that the sum of $$$m$$$ is bounded by $$$10^5$$$.

»
15 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

are writers just trolled us by B?

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

a < c < d < e < b

:/

»
15 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Sorry, it's my mistake. Please don't click the dislike button again, I'm sorry! (I mistook C as an existing problem)

(Comment before modification) //This game has an existing problem https://www.luogu.com.cn/problem/P9345

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

    It's shameful for the person who wrote the original question

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

    This problem requires finding a permutation with score exactly equals to k, instead of the maximum possible score.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I think it's even easier than the original question

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

      We also had the same problem asking for a permutation with score equal to k but then decided to ask for the max answer.

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the output of the second number in B question, I haven’t understood it yet. :(

»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

It's exactly the same as question C.

https://www.luogu.com.cn/problem/P9345

»
15 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Codeforces Round 893 (Div. 2) Problem C looks the same as Luogu: https://www.luogu.com.cn/problem/P9345. Should th contest be unrated?

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve Problem B

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

    create 2 arrays first array (let's name it a) to store the number of cookies eaten by Petya at seller[i]'s bench second array (let's name it b) to store the number of cookies eaten by Petya at seller[i]'s bench if seller[i-1] was removed a[0] = b[0] = 1 + floor the distance between seller[0] and 1 divided by d for the rest of the array, a[i] = a[i — 1] + floor the distance between s[i] and s[i — 1] divided by d (+ 1 if the distance isn't divisible by n). b[i] = a[i — 2] + floor the distance between s[i] and s[i — 2] divided by d (+ 1 if the distance isn't divisible by n) now you find the max difference between a[i] and b[i] which is the difference resulted by removing s[i — 1] and count how many times did this difference occur. the answer is the difference between the number of cookies eaten if no sellers are removed and the max difference then the count of the max difference. here's how I solved it 219009908

»
15 months ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

A problem which is requires similar observation as problem C but slightly more interesting appeared in RUET IUPC 2022.

Here is the problem statement
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's quite interesting, and I figured out only when min(u,v)==gcd(u,v) can edge(u,v) be useful. So the number of edges is not big.

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

B and C should've been swapped

»
15 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Question about problem B.

Why is the answer for this test case 6, 4 instead of 6, 3?

30 5 8

6 8 15 24 29

Removing cookie sellers at 8 or 24 won't give the minimum, right?

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

    Removing 24 will give minimum as, if we consider the points where petya eats cookies in range [15 ,29]. Before removing 24 will be 15 — 23 — 24 — 29. After removing 24 will be 15 — 23 — 29

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

    You can remove 6, 15, 24, 29 for minimum

»
15 months ago, # |
  Vote: I like it +20 Vote: I do not like it
Problem B
»
15 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

I can not understand the second output in problem B. Can someone help me pls :(

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

    The second output is the count of people that (if he's removed, the least cookies are consumed)

    e.g

    Remove People#1, Cookie Count=3

    Remove People#2, Cookie Count=4

    Remove People#3, Cookie Count=5

    Remove People#4, Cookie Count=3

    And the output should be 3 2

    because there are 2 people that can lead to least cookie counts(people #1,#4)

»
15 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

suggest swap(rate[B],rate[C]) (MAD)

»
15 months ago, # |
  Vote: I like it -42 Vote: I do not like it

C is the same problem from other OJ, and E1&E2 r 2ez and trivial.

I don't think this round should be rated, whether in terms of quality or difficulty.

»
15 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Linear solution for E1 (Edit: Seemingly linear, actually quadratic):

We construct history tree of additions (or persistent linked list if you will) then dfs it, storing how many uniq values we have.

Query processing:
+ Add a node to history tree and move to that node. Store it to history.
- Move to a father k-times, store final node to history. (We can do this, cause we will not move up more times, then we added nodes)
! Load last but one node from history and delete last.
? Mark this node for an answer

Dfs — we store counts of all items in array and total unique ones:
- Add value stored in current node.
- Answer all questions marked here.
- Dfs all sons.
- Remove the value stored in this node.

Seems to me this is O(N) but did not pass (218993624). Did this happen to anyone else?

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    cause we will not move up more times than we added nodes

    Not true with ! queries. Consider adding many values then repeatedly doing - and !.

    Fix to this problem is to do binary jumping.

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

    It's because the queries can repeatedely go back k times and then rollback which goes forward k times. Its pretty easy to see how the number of operations would blow up in that case.

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

What's your explanation of the number of people who passed C is 3 times of who passed B, and why did you use a widely known problem witch had appeared in Chinese as C?

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

    C was kinda easy , B was kinda of a corner cases thing

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

    I think it partly has to do with problem B being very hard to read especially for those whose first language is not english.

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

      Yes! I spent at least 15 minutes to get to know what B tells.

»
15 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone help me with this solution for problem c? Getting WA 218998257. I don't know which case is failing.

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

    Your proposal only has 5 distinct numbers. There is no number six.

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

      Sorry, Didn't get you.

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

        The wrong test case is when n=12. The expected permutation should have 6 different numbers, but yours only have 5

»
15 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

No way you guys have just pulled the contest announcement from the front page. That's just a little bit silly, don't you think?

UPD. It's back, now I am not worried for all of the work that went into this contest

»
15 months ago, # |
Rev. 2   Vote: I like it -27 Vote: I do not like it

UPD 3: The contest will be unrated

»
15 months ago, # |
  Vote: I like it +31 Vote: I do not like it

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please find the solution of problems A and B on the channel: https://www.youtube.com/channel/UCLQtLtFcxXAd7366G3iCadw

Problem A Link: https://youtu.be/fKhvK6TfRXA Problem B Link: https://youtu.be/fZQQedImGNw

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good problems, bad round I guess. But B's problem statement gives me a headache:(

Also, after solving A~C, I saw that E1's score is lower than D, so I thought it would be easier, but in fact it seems like I'm terribly wrong. I solved D in the last 20 minutes, but got penalty on E1 for like 10 times. Maybe I'm just bad at data structures bruh

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why my first submission of problem A was skipped? but it is right.

»
15 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I think problem B can be rephrase into something like :

Given $$$N$$$ points from $$$1, 2, ..., N$$$. There are also $$$M$$$ benches numbered $$$1, 2, ..., M$$$. Bench number $$$i$$$ is located at point $$$s_i$$$

You start at point $$$1$$$ and go all the way up to point $$$N$$$ by moving $$$1$$$ unit per second. Then you start by eating a cookie ay point $$$1$$$. Along the way, you can eat cookie at any integer point $$$p$$$ when at least one of the following condition is fulfilled :

  • There's a bench located at $$$p$$$
  • The last point where you ate the cookie is at least $$$d$$$ unit away from $$$p$$$ (Formally if the last point where you eat the cookie is $$$p'$$$, then you can eat cookie at $$$p$$$ if $$$p - p' ≥ d$$$)

You want to remove exactly one bench so that after the removal of the bench, the number of cookie you eat in the end is minimal

Determine :

  • the minimal number of cookie you eat after the removal of the bench
  • the bench number that needs to be removed
»
15 months ago, # |
  Vote: I like it +9 Vote: I do not like it

15 authors and we have the problem B with more 5000 Accepted and problem C with more 13000 Accepted :)

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

i hate the problem B :(

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B > C > A

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

So, 15 authors couldn't see that B > C > A ?

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

    Unfortunately, that is true :( We are really sad about it, because we were worried that B might be of the same difficulty as C based on the round testing (it took people around the same amount of time to solve them), and we tried to fix this by giving them almost equal score.. It is really hard to predict the difficulty of a particular problem for round participants, and we are disappointed that we couldn't sort it out properly. However, based on the little information we had, it might have turned out the other way as well if we did swap them. We are truly sorry for misjudging problems' difficulties!

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell what's wrong in 219096582 solution for D?

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.