MarkBcc168's blog

By MarkBcc168, 21 month(s) 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

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +105 Vote: I do not like it

As a tester, please give me contribution.

One of my favourite rounds.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -39 Vote: I do not like it

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

  • »
    »
    21 month(s) 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)

  • »
    »
    20 months 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?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it
    Do you judge contests by only problems A and C...
»
21 month(s) 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.

  • »
    »
    21 month(s) 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? :")

    • »
      »
      »
      21 month(s) 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!

»
21 month(s) 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.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it
Meme
»
21 month(s) ago, # |
  Vote: I like it +31 Vote: I do not like it

Hope that this will be my last rated div2.

»
21 month(s) 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!

»
21 month(s) 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).

»
20 months 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.

  • »
    »
    20 months 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.

»
20 months 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

»
20 months ago, # |
  Vote: I like it +119 Vote: I do not like it
Codeforces bathroom?
»
20 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope This round would be my last round as a pupil

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

    Pupil Tag is not leaving me so easily :(

  • »
    »
    20 months 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

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

    me too

  • »
    »
    20 months 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:(

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

Hope ths will be my last div2 as Expert

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

Note the unusual start time :)

»
20 months 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).

»
20 months 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).

»
20 months ago, # |
  Vote: I like it +25 Vote: I do not like it

As a tester, hi.

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

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

»
20 months 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)

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

.

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

Very excited!!

»
20 months 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.

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

good luck!!

»
20 months ago, # |
  Vote: I like it -12 Vote: I do not like it

As a participant, please give me contribution.

One of my favourite rounds.

»
20 months 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!

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

I hope i will be solve problem C

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

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

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

expecting to reach expert in next few rounds

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

interactive problems do make me scared

»
20 months 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!

»
20 months 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?

»
20 months 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!

»
20 months 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

»
20 months 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?

  • »
    »
    20 months 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.

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

I think problems are a bit hard!

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

How to solve C ?

  • »
    »
    20 months 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.

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

      can be done iteratively as well

  • »
    »
    20 months 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);
        }
    }
    
  • »
    »
    20 months 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
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why cannot we see tutorial yet?

»
20 months 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.

»
20 months 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??

  • »
    »
    20 months 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

  • »
    »
    20 months 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.

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

Any hint for D?

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

    Think of the 1's as groups

  • »
    »
    20 months 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.

  • »
    »
    20 months 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.

»
20 months 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!

»
20 months 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.

  • »
    »
    20 months 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]
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it should be 5 ig how 7?

»
20 months 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.

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

Very nice problems!Congrats to authors!

»
20 months 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!

»
20 months 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.

  • »
    »
    20 months 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.

    • »
      »
      »
      20 months 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!

»
20 months 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

  • »
    »
    20 months 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.

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

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

»
20 months 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.

»
20 months 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).

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

Who is stemroot?

»
20 months 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.

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

    Добрый день

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

»
20 months 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

»
20 months 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?

»
20 months 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!)