MarkBcc168's blog

Codeforces Round #807 (Div. 2)
By MarkBcc168, 2 years ago, In English

Hello Codeforces,

We are glad to invite you to Codeforces Round 807 (Div. 2), which will be held on Jul/15/2022 16:35 (Moscow time). As usual, the round will be rated for participants with ratings lower than 2100, while those who have higher ratings are encouraged to participate unofficially. Please note the unusual start time.

You will be given 6 problems to be solved in 2 hours and 15 minutes. There may or may not be interactive problems, so you are encouraged to prepare in case they do appear by reading this guide.

The round is authored by abc241 and me, while joining us is also inwbearX who contributed significantly to the preparation. This is our first time setting rounds in Codeforces, and it wouldn't be possible if there were no support from the following people.

The score distribution is $$$500$$$ — $$$1000$$$ — $$$1250$$$ — $$$1750$$$ — $$$2500$$$ — $$$3000$$$.

We are looking forward to your participation. Good luck and enjoy our round!

Update: the editorial is up!

Update 2: Winners!

Div. 2

  1. stemroot
  2. UtopianZ
  3. WYZFL
  4. H_stove
  5. myeeye

Div. 1 + Div. 2

  1. tourist
  2. SSRS_
  3. stemroot
  4. Um_nik
  5. arvindf232
  • Vote: I like it
  • +280
  • Vote: I do not like it

Comments Comments (132)
| Write comment?
»
2 years ago, # |
  Vote: I like it +105 Vote: I do not like it

As a tester, please give me contribution.

One of my favourite rounds.

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

    ok, that's enough information to make me ignore this contest

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

    I would say when a candidate master (or higher) claims that a contest is in favor of his, it's much more overwhelming for me since I could only do up to 1400+ (maybe 1500 or 1600)

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

    As we know, A round author must be at least expert. Then, how a specialist is the author of this round?

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it
    Do you judge contests by only problems A and C...
    → Reply
»
2 years ago, # |
  Vote: I like it +49 Vote: I do not like it

As a tester, the problems are interesting and high quality, also be sure to read all problems.

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

    "High quality"? Is that a caution for newbie,pupil and specialist guys? :")

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

      Nope :D

      I meant that the difficulties are well balanced, statements are easy to understand and the topics are also diverse. All in all, it's a fun contest for people of all ratings!

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

As a tester, this round's problem-set interested me so much. Highly recommend reading all problems.

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

Hope that this will be my last rated div2.

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

As a tester, I gotta stop doing this as a tester comments but I mean this round is really really cool, the problems are very interesting idea-wise and that's smth I really appreciate. Congrats to the problem-setters, and I hope u enjoy this round as much as I did!

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

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

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

Have a feeling that a lot of people will be one hour late for the contest.

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

    I would have been an hour late if I didn't see this comment. Thanks.

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

Watch out! The contest is 1 hour earlier than usual time.I also didn't notice it first :3

→ Reply
»
2 years ago, # |
  Vote: I like it +119 Vote: I do not like it
Codeforces bathroom?
→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope This round would be my last round as a pupil

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

    Pupil Tag is not leaving me so easily :(

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

    Me too, though i became Specialist earlier 2 or 3 times, I want to be a real Specialist

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

    me too

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

    Congratulations, I think you'll be cyan today, I lost it with time and penalties:(

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

Hope ths will be my last div2 as Expert

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

Note the unusual start time :)

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

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

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

Given the authors, it looks like the round will be IMO-forces (but in a good sense).

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

As a tester, hi.

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

I wish high rating for everybody, who reads this comment )

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

I usually don't pass contests because I always forget about them, and this has happened so many times that I now set an alarm for each new contest and I will definitely pass this contest!(I really hope)

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

.

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

Very excited!!

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

I hope today's competition will be amazing. Let's try to solve more problems. I wish you all good luck and success! I believe in each of you.

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

good luck！！

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

As a participant, please give me contribution.

One of my favourite rounds.

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

I hope this will be my last round as newbie :) Good luck guys!

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

I hope i will be solve problem C

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

Thanks for the support Alfheim. ::::))))

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

expecting to reach expert in next few rounds

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

interactive problems do make me scared

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

A friendly reminder that the contest starts in about half an hour. Good luck!

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

as a not good problem solver and 900 rating should i dare take participate in this contest?

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

10 minutes left before the start of the contest. Looking forward to it!

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

Looking at the submissions, C should be easy but holy hell I feel incredibly dumb for not being able to solve it

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

I got TLE in some submissions where the verdict should be WA or RTE. Why did this happen?

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

    Because your solution was not able to reach the final solution where it can be decided about the correctness of solution.

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

I think problems are a bit hard!

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

How to solve C ?

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

    recursion. Try to find in which of the copy paste operation we performed.

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

      can be done iteratively as well

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

    For every query, process operations backwards one by one, keeping track of the current length of the string. Note that each operation adds (r — l + 1) length to the string.

    Suppose k <= length before the operation. Then just throw away the operation and reduce the length.

    Suppose k >= length before the operation. Then if the operation is from l -> r, then the answer for k — previous length is the same as the answer for l + k — previous length, so just recursively find the answer for such a k.

    char ans(int k, deque<char> &d, vector<pair<int, int>> ops, int current_length) {
    if(k < d.size()) {
        return d[k];
    }
    else {
        int previous_length = current_length - ops.back().second + ops.back().first;
        if(k < previous_length) {
            ops.pop_back();
            return ans(k, d, ops, previous_length - 1);
        }
        int diff = k - previous_length;
        int t = ops.back().first;
        ops.pop_back();
        return ans(t + diff, d, ops, previous_length - 1);
    }
}
    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Similar to what EmilyBloom and barun511 said, you should answer each of the queries using recursion.

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

Why cannot we see tutorial yet?

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

waiting for solution ... i think it would take hardly 5 — 10 min... everyone is becoming fast here.

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

In some contests there is a hacking phase of 12 hours in some there is not. Can anyone tell me in which contests hacking phase is there and in which it is not??

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

    in educational rounds , in div4 and in div3 we have 12 hrs hacking phase

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

    Contests like educational, div 3 and div4 have a dedicated hacking phase of 12 hours whereas other contests (like div2) have hacking phases which are active only during the contest.

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

Any hint for D?

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

    Think of the 1's as groups

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

    Look at what happens to the groups of consecutive ones/zeros under the operation.

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

    I may be wrong and fail the system tests so take this with a grain of salt, but I figured that the condensed version of the strings (let's say, the array [1,5,2,3] for the string 10000011000) cannot change its size using any number of operations (meaning no continuous segment of zeroes or ones can disappear or be born). That observation helped me.

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

First Div 2 where I solved 4 problems! Edit: Yay! I'm an expert now!

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

For me, Problem B seems so much confusing. if we take a test case such as : n=5 the array looks like 2 1 1 0 4 how is the answer 5? I think the answer should be 7.

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

    One sequence of moves is

    • i=1 j=4: [1,1,1,1,4]
    • i=1 j=5: [0,1,1,1,5]
    • i=2 j=5: [0,0,1,1,6]
    • i=3 j=5: [0,0,0,1,7]
    • i=4 j=5: [0,0,0,1,8]
    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it should be 5 ig how 7?

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

can someone pls give me some hints for problem E?

Thanks in advance.

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

D was easier than C, right?

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

Very nice problems!Congrats to authors!

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

I really liked today's contest, I was able to solve the first three problems, but I didn't have enough time for the fourth one, in general, the problems were very interesting and exciting, especially problem C, thanks to all the creators of this contest!

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

A harder version of problem D appeared in yukicoder, a Japanese contest: https://yukicoder.me/problems/no/1209.

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

    Well, I apologize for that, but please understand that there are just too many problems out there, and it's impossible to check them all. Thanks.

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

      I don't think it should've been noticed, but I just think it is beneficial information so I posted. Sorry for misunderstandable post. Thank you for a great contest. I enjoyed it a lot!

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

In problem E, I try binary search + segment tree, its time complexity is O(nlog^2n), when n equal 2e5, it remain less than 8e7, why it get TLE? code link

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

    Based on our testing, the segment tree has a high constant factor that an O(nlog^2 n) is very hard to pass. We apologize for the strict TL.

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

      Oh, I ignored those constant. Thank you for your reply!

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

Oh my god, this isn't funny anymore. In round 804 my new rating was 1898, but I wasted 1 attempt on C because I put whe wrong module (998244353, from the previous round, not 1e9+7). But today, my new rating Again seems to be 1898, according to Carrot, and today I also wasted an attempt, because I forgot to write something I invented at the beginning, which makes me miss my first CM again, And a div1 round for the first time. F

But the round was great.

upd.: No, 1899.. That's insane.

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

Internet in Serbia is very good guys. First 25 minutes I wasn't able to submit A, and then last 55 mins internet was so bad that I can't submit B or C(both was ac).

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

Who is stemroot?

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

Ratings updated preliminary. Unfortunately Mike won't be in touch until July 19th, so cheaters from this round and further rounds will be removed later. We can guarantee that they will be removed not later July 20th.

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

    Добрый день

    Извините, не могли бы вы подсказать пожалуйста во сколько сегодня примерно рейтинги обновятся?

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

Is there anyone E using bitset or set to do it, ask for a code

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

Under the standings section of this round I see a positive delta of 39 but my rating change shows 15 positive delta. Anyone have an idea about this?

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

my friend：“Hello！” me：“How do u know I become a Expert？” （sorry...I got 807 mixed up with 808.But luckily，I can say it again in 808！）

→ Reply