sevlll777's blog

Codeforces Round 908 (Div. 1, Div. 2)
By sevlll777, history, 14 months ago, In English

Big greetings, Codeforces!

I am happy to invite you to Codeforces Round 908 (Div. 1), Codeforces Round 908 (Div. 2), which will be held on Nov/07/2023 17:35 (Moscow time).

This round will be rated for everyone. In both divisions, you will be given 5 problems and 120 minutes to solve them. All problems were cooked by me (sevlll777).

The traditional thanks-list to everyone who took part in the creation of the round. Thanks,

I hope you will like the problemset and ideas hidden in the problems! It's guaranteed that statements are understandable, short, and, of course, ✨ stylish ✨.

Have fun!

Score Distribution:

Div. 1: $$$500$$$ — $$$1000$$$ — $$$1250$$$ — $$$2250$$$ — $$$2750$$$

Div. 2: $$$500$$$ — $$$750$$$ — $$$1500$$$ — $$$2000$$$ — $$$2250$$$

UPD: Editorial

UPD2: Congrats to the chAAAmpions!

Div.1:

  1. maroonrk

  2. Ormlis

  3. Um_nik

  4. tourist

  5. 5sb

  6. Swistakk

  7. jiangly

  8. Radewoosh

  9. ethening

  10. hank55663

Div.2:

  1. Redpo

  2. shenzihan

  3. lq5

  4. zookeeper780

  5. omsincoconut

  6. vishav_mehra

  7. menezesd2

  8. darling51707

  9. kanao_enjoyer

  10. bleeding

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

Comments Comments (150)
| Write comment?
»
14 months ago, # |
← Rev. 2   Vote: I like it -48 Vote: I do not like it

:""

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

Wow, So exciting to see this round, I hope it will be interesting.

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

This round will be tasty if all problems cooked by sevlll777.

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

Why so many mysterious ppl living in Antarctica

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

    Why so many mysterious new chinese accounts always winning rounds

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

hope i can reach Specialist this time

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

as a tester, I loved the tasks

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

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

I hope it will be great contest and get more points.

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

How is the rating system?

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

Will the rating still roll back? It's been a long time since I've had a rollback it feels like

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

I feel so happy when you said the statements short ... Thanks

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

Hope the fast editorial, not too fast eventually :)

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

I wanna reach pupil :') hopefully i dont mess this up

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

I want to back Red by CF908 before my last ICPC, Shenyang 2023. Good luck!

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

It's guaranteed that statements are understandable, short, and, of course, ✨ stylish ✨.

sevlll777 roasting Codeforces on Codeforces. Less go!!

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

3-second-forces

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

    why are you not giving contest

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

      because I've failed in the selection test for our national olympiad for high school students, so my goal for cp is basically over, I just came here to read the problems for fun

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

        Dont Worry ,, Dont Leave CP ,Something Big will be ready for you in future.

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

          yeah I'll come back when I enter university, now maths and physics for my university entrance test is my main focus

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

          thank you.

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

D and E are too tough for me. Hopefully my current points are sufficient to become dark blue after the round.

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

Worst contest I've ever seen!

What is the point? Details and implementation?

Please be aware of your problem's quality before you bring it out!

You are wasting 20000+ people's time and feeling!

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

    I suppose you refer to Div1C problem, yes it's problem mainly about fast and correct implementation, but it's surrounded with B and D which involve almost zero implementation, so what's the problem of having one problem where you need to be actually careful about impl?

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

Div2D was too easy to be D!

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

    Can you please tell how to solve it?

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
      ← Rev. 4   Vote: I like it -11 Vote: I do not like it

      First, sort b. Iterate through a from begin to end, and if we meet any a[i] that is <= b.back(), just insert b.back() before a[i]. Then, if after iterating the array a, b is not empty, just insert the remaining element to c. This ensures that the LIS of a will only be increased by at most 1

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

      Sort b. greedily insert b from large to small before the first a[i] that is less than or equal to the current b you're inserting

      submission

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

    I spent more time thinking on it than on three others problem I've solved combined :)

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

What was that A ^-^

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

I love this contest, because it is very tasty!

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

How to solve C?

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

    You realize that if a fixed point gets selected, it basically goes to the last position of the array. That means that if you want to reverse the moves, you have to start at the last position, to then look which element becomes the last element after the next iteration etc. You can turn this into a functional graph, on which you do binary lifting with k steps. One case that you have to look at is if a_i > n, then there is no edge from this node going out.

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

1A is interesting, 1BCD is implementing race.

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

Errichto leaked the solution of problem A: https://www.youtube.com/watch?v=F4rykKLcduI&t=374s The question was similar though

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

    This may be the most spoiled solution in all of history. I read it today and had to double check the date of the contest thinking there was no way a question like this would get through testers if 1.2 million people have seen it before.

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

Best Interesting contest Ever, I love it. But the worst thing that from problem A to D in Div.2 was leaked in youtube and this thing waste others effort So be good and don't copy answers " You are just deceiving yourself :)"

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

What is Div1 lol, B > C > D in terms of difficulty. Most of my time on Div1D was trying to prove why the obvious approach wouldn't work since it feels way too easy for its spot in the contest.

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

I think the contest was great. Maybe its true that D was too easy but I am happy for my first A-D in a Div2 round

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

Wow, this was a very weird contest for me. I don't know why but I stumbled so hard on the first problem itself.

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

Where did the [3,2,3,4,3] array come from in the first test case example on https://codeforces.net/contest/1894/problem/C ?

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

Very nice problems! I also seem to remember I liked some div2 contest from you. Well done!

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

I feel that div1D is too easy, and it can be easily implemented using a greedy simulation approach.

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

Div. 1C seems too straightforward for a Div.1C, you can basically figure out 80% of the solution right after reading it.

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

Some people says that problem Div1B/Div2D is implementation heavy, but here is my solution:

  • Sort array $$$[b_1, b_2, \cdots, b_m]$$$.
  • Now we can assume $$$b_1 \geq b_2 \geq \cdots \geq b_m$$$.
  • For $$$i = 1, 2, \cdots, n$$$, do the following thing (initially $$$\text{cur} = 1$$$):
  1. While $$$b_{\text{cur}} \geq \max(s_i, s_{i+1}, \cdots, s_n)$$$ is satisfied, append $$$b_{\text{cur}}$$$ to answer and add $$$\text{cur}$$$ by 1.
  2. Append $$$a_i$$$ to answer.
  • Lastly, append $$$b_{\text{cur}+1}, b_{\text{cur}+2}, \cdots, b_m$$$ to answer.

For example, if arrays are $$$a = [7, 4, 5, 1, 2]$$$ and $$$b = [3, 9, 8, 0, 6]$$$, the answer is as follows:

  • First, sort the array $$$b$$$. The array will be $$$[9, 8, 6, 3, 0]$$$.
  • Then, add all elements in $$$b$$$ which is greater than $$$\max(a_1, a_2, a_3, a_4, a_5)=7$$$. The current answer is $$$[9, 8]$$$.
  • Then, append $$$a_1$$$ to answer. The current answer is $$$[9, 8, 7]$$$.
  • Then, add all elements in $$$b$$$ which is greater than $$$\max(a_2, a_3, a_4, a_5)=5$$$. The current answer is $$$[9, 8, 7, 6]$$$.
  • Then, append $$$a_2$$$ to answer. The current answer is $$$[9, 8, 7, 6, 4]$$$.
  • Then, add all elements in $$$b$$$ which is greater than $$$\max(a_3, a_4, a_5)=5$$$. Nothing will be added.
  • Then, append $$$a_3$$$ to answer. The current answer is $$$[9, 8, 7, 6, 4, 5]$$$.
  • Then, add all elements in $$$b$$$ which is greater than $$$\max(a_4, a_5)=2$$$. The current answer is $$$[9, 8, 7, 6, 4, 5, 3]$$$.
  • Then, append $$$a_4$$$ to answer. The current answer is $$$[9, 8, 7, 6, 4, 5, 3, 1]$$$.
  • Then, add all elements in $$$b$$$ which is greater than $$$\max(a_5)=2$$$. Nothing will be added.
  • Then, append $$$a_5$$$ to answer. The current answer is $$$[9, 8, 7, 6, 4, 5, 3, 1, 2]$$$.
  • Lastly, append all remaining elements. The final answer is $$$[9, 8, 7, 6, 4, 5, 3, 1, 2, 0]$$$.
→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Full solution apart from declaring these objects — very implementation heavy xddd

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

    I just guessed my solution, thank you for a nice way to prove it.

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

What's the solution to problem E?

My approach was to check for a fixed len was to check number of elements of value len we are forced to take for every multiset. These values will change only in multisets in which element len is present, so I am recalculating in that only and I am handling overflow by using int128. And I am checking for len E [minimum len, min(min len+m+1, maximum len)] Is the WA on test 2 related to int128?

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

This was a decent one. Thanks a lot for the problemset. Hope i can reach CM...

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

Who let him cook?!

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

implementation round and speedforces. Not a good idea to put all these tasks in one round.

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

I was bamboozled by D, worth a ton of points, but easier than B and C xd

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

It turns out that I've submitted two exactly the same solutions to problem Div.1 B 231765593 and 231765621 due to internet connection errors on the cf side and they counted as a resubmitted solution, so the corresponding penalty (-50) applied. Is it possible to cancel one of these submissions so that the penalty would not be charged (because under normal conditions codeforces would not allow submitting exactly the same code twice)? sevlll777

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

    One of the submissions have been ignored, should be ok now

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

    Same here. I submitted solution 231748393, but I couldn't find it in the status queue or my submissions page. I refreshed the page again and again, waited for a few minutes, but my submission list was still empty. Then I submitted 231749171 again. Suddenly, both submissions appeared in the submission list. The server issues had a significant negative impact on my overall experience with this contest, and I must admit I didn't enjoy it at all.

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

Really nice contest and interesting problems. Thanks a lot!!!

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

Problem A must be 3500

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

I would not say that this is the worst contest I've ever seen in my life. Cause apparently, there are also many, many, 74TrAkToR rounds before.

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

sevlll777: I hope you will like the problemset and ideas hidden in the problems! It's guaranteed that statements are understandable, short, and, of course, ✨ stylish ✨.

Div2A: What is the point of put "It is guaranteed that the given sequence of plays corresponds to at least one valid game scenario, for some values of X and Y" and "? — if it is impossible to determine the winner of the game" together in statement? It's not short enough?

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

    what? it's key part of the statement

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

      This is November, not April. This is normal round, not April Fool round! Why do you make statement like that? Someone will keep thinking about which test cases will be output "?" and waste much time and someone will just try to guess the solution and don't know why it works :)

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

        I think you have some fundamental issues with understanding problem statement, or I completely not understand you.

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

I feel almost A(21min) = B(34min=55-21) = C(27min=82-55) = D(22min=104-82).

A: Interesting, but little bit heavy implementation for D1A. (my approach is SCC+BFS)
B: One idea task, but it's not easy like AGC-A. Great!
C: Small data structure, but it's almost logic test.
D: PROOF BY AC (I think it's around 1500pt to just get AC)

And one another thing, it seems no one got FST in Div1. Congrats!!

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

    You might want to look at some other implementations of A...

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

    Problem A actually only needs to be considered backwards.

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

    lmao

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

    Unfortunately, I have a good friend who got FST on D1A :(( (and is div. 1)

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

great contest!!!

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

Kinda feels like people who say that the problems are obvious implementations mean that there is an easy-to-believe greedy... For example, it would be very nice to see an easy solution* (and by that I obviously mean that you can rigorously prove it, otherwise it is a heuristic, not a solution) for the problem (div1) D. And B. And C.

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

    The problems itself are all fun imo, but it's questionable that making a contest full of this type of problems is good or not.

    Contests serve more than just a list of problems, splitting those into several contests, adding different types of problems can both make the contests better and those problems be more enjoyed by participants

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

      Which problems are supposed to be similar in this contest according to you? And what other kinds of problems you think would improve this contest?

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

        Something like "spending time on draft and find a set of super cool observations, then implement in <=5 minutes without any detail"

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

          I think C and E are both of that kind... Well, E is not 5 minutes, but not far.

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

            I will try 1E tomorrow... Maybe you are right, it's my skill issue.

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

            C is? What is the cool observation in C? The 1e9 variables made to make the problem look difficulty? Did you mean B? Also, unless youre top 10, its more like ~15mins implementing C

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

              Looks like I'm in the minority here, but for me C was an interesting problem and I didn't get it right away. My first thought was about knapsack-like DP, because we need to achieve a particular size of the resulting set. And the fact that you can take everything but then greedily remove items to get to the correct size was a nice observation. Then to finish it off you need to realise that you can do it only for the sets with this number present, which makes the complexity proportional to the input size. For me that's an interesting sequence of steps.

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

        Just like others have said, the implementing difficulty between two correct approaches can be huge, thus resulting in the B solution one thought of could be a lot harder that the D he found out. If you can always think of the easier solution then it's fine, but for middle-level contestants the experience can be frustrating

        and the bad experience is based on the fact that there's a relatively high possibility one can find himself not solving in the right order, which can't happen if there's only one(or two?) problems of this type in one problem

        upd: the type i'm talking about, is that 'the implementing difficulty between two correct approaches can be huge', and some other features i will explain in the reply

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

          First of all, I don't think that your comment answers any of my questions. I don't see how your answer is even connected to the topic discussed, which was "making a contest full of this type of problems". What is the type?

          Second, do you think that all possible solutions to B should be easier to implement than all possible solutions to D?

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

            if the D requires a lot of thinking then it's fine to have a harder-to-implement B, but you should notice that the problems in this contest also have one thing in common, is that you can get a solution right after you finish reading the statement, the only thing deciding the implement difficulty of your solution is if you noticed some 'observation' at the first glance. I'm assuming here that in a short, rapid-paced contest like CodeForces you won't continue thinking of another solution if you actually have got one and it's not uninplementable like a 10K code.

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

              You must be very good, because the only problem from this contest that I solved right after finishing reading was A.

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

                Fine but it's really clear, that a lot of contestants get to the harder-to-implement solution before the easier one

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

                  I don't see an issue with that.

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

      Or actually maybe there can be a problem pool stuff like to collect problems rejected because breaking balance of a single contest and reuse them together later. Making it way easier to improve a round's quality, and maybe also making it possible for harder rounds to happen more often

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

    So what should I do when I found a heavy-implementing but provable solution?

    For common rounds, I spent around 3 minutes for some easier implementation and it has worked for 90%+ times.

    However in 74TrAkToR rounds I felt there is a huge gap between "a correct solution" and "a easy-to-code solution".

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

    I don't understand what is there to prove in C (since I just explicitly determine all possible results) and B (since it is obvious why it works once you get an idea). C is just straightforward from the construction and I guess there is no way to think of the algorithm for B without getting understanding equivalent to the proof of its correctness

    For D, well — I didn't have a rigorous proof, but I had near certainty that what I've done is correct. I think this is a valuable skill to estimate what is the probability of your algorithm being right in the absence of a formal proof and I didn't have any doubt regarding that while implementing that.

    I go through shelves in arbitrary order, fill each shelf from left to right and always put a cube of the color with the highest number of unused cubes out of these colors that I am allowed to put right now. Seems quite obvious that you wouldn't want to put any less frequent one, because why would you want to do it? At this point any two colors that I am able to use right now are completely symmetrical, no past affects them in any way, so my intuition tells me that this is >95% correct before attempting any proof.

    But yeah, rigorous proof is not obvious I guess. Let's say that the most frequent allowed color is $$$A$$$ and has $$$x$$$ cubes in it, but we decided to use less frequent color $$$B$$$ with $$$y<x$$$ cubes in it. Let's create a sequence of occurences of A and B in the remainder of the current shelf (but include the B we've just put too) and all of the following ones in an arbitrary order. Look at the difference between number of As and Bs on all nonempty prefixes. The first number is -1, but it ends up being positive, so there is a moment where we go $$$-1 \to 0 \to 1$$$. This is a moment of two consecutive As such that the prefix ending on the first one has equal number of As and Bs. Let's flip that prefix. We get another viable configuration, where we put A instead of B in the first position, as desired.

    Though that proof is just "for fun", it doesn't support my point or anything. But the fact that the past does not affect my choice in any way (as long as I restrict my current choice to allowed colors), so all allowed colors are symmetrical — is a very strong intuitive argument for why this is correct and I had no intention on wasting my time during the contest for the rigorous proof of that even though I am bit of a purist as well and sometimes get fever while listening to these "proofs by AC" as well

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

Would have been better if div2D/div1B problem had explicitly mentioned LIS contains strictly increasing elements :( Got solving the wrong problem the entire contest.

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

Div2 A should be better ;(

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

If you think you're stupid:

231749854

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

round was a bit speedforces, but problems were nice!

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

I liked the problems, but statement of Div 1 C drives me crazy. Math-heavy explanation of simple things does not sound like fun. I don't mind the formal definition of things, though ideally they should follow the explanation you can relate to, not substitute it.

"Minimize anti-beauty" sounds like double negation in some sense, why inventing a word? If you follow the statement style it should've been called f(S). If you want to make it prettier, call it "ugliness of set" or "cost of set".

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

    The idea was that beauty is something we naturally want to maximize, therefore anti-beauty is something we want to minimize :D but ugliness would've been better choice, you are correct, not good enough in english I guess

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

third question was fabulous

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

Div 2A was inspired (perhaps a little too straightforward-ly) by this YouTube video (featuring Errichto)
Errichto's interview with Joma Tech

The question is mentioned by Kamil at 4:23, when he gives an example of competitive programming questions.
Seemed like a really fascinating solution to me even when I had first seen the video.
Side note: The hints in the Editorial mention tennis and volleyball, quite like how they were brought up in the above-mentioned video

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

A similar problem as problem A, with the same solution, was mentioned in this interview with Errichto

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

yayy I became expert! Thanks for the contest.

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

I'm not really sure about it, but I think that again I wasn't able to get AC because of worse constant factor ;_;

Got stuck on memory limit too. Especially (I think) the stuff about doing something like that:

void rec(int v) {
    if (v<=n) rec(v+1);
    if (condition) {
        //something that creates variables and releases them right after this block
    }
}

I've knew before that if it wouldn't be inside of an "if" statement then all the memory would be allocated right after entering the function and I guess that the existence of the "if" statement doesn't change much. Can somebody confirm?

I've discovered this fact painfully in other problem some time ago, where the condition was called only a few times, but because of this insta-allocation my solution was quadratic instead of something faster. Here it just made constant factor bigger (and memory complexity just like time is still linear), but ML also turned out to be too tight for me.

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

    I highly prefer generous time limits, especially when there is no unintended solution that the authors are trying to separate from the intended one, but they just arbitrarily decide to set the TL to be 2x or 3x of their implementation in C++.

    To all other authors: please don't do that! Consider what solutions you are trying to allow, and what solutions you are trying to disallow. Consider other programming languages besides C++. Set the constraints accordingly. Time limit equal to the geometric mean of the slowest implementation of the intended solution and the fastest implementation of the unintended solution is a good starting point.

    To sevlll777: thanks for setting all time limits to 3 seconds and keeping all constraints (except E) under $$$2 \cdot 10^5$$$. That's much better than setting $$$n \le 10^6$$$ and TL = 1 second for no reason.

    However, to be fair about today's Div.1 E, an $$$O(n)$$$ solution is obviously possible if you just use DP and store all vertex/edge colors going out of the subtree in the DP state — the constant factor would be around $$$3^6$$$, though. So, in a sense, this problem is all about the constant factor.

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

      Radewoosh's solution looks exactly like DP with matrix exp. So I would say this time TL was even too generous, considering that it is possible to get AC with it.

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

        Well, still linear if it changes anything (actually $$$\mathcal{O}(n+\sqrt{d})$$$) with multiplying vector by matrix everywhere except for prepro. I don’t think that these matrices can be counted as “complexity”, as if numbers higher than 3 would be allowed then the model solution wouldn’t work anymore (as far as I understand it), so I think it’s still a constant factor.

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

          Yeah, it's totally a constant factor. Your solution is absolutely linear, and mine is $$$\Theta(n \log C)$$$. I still think that you didn't solve the problem :)

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

            I see the point and it makes sense, so I was about to agree, but I thought more about it and I think that I won’t (at least without hearing anything more).

            Let’s consider cases with 2 very different solutions to the same problem. How can they be different?

            • One has better time/space complexity — that’s an obvious one, we should somehow be able to distinguish them.
            • One has better time/space constant factor — that’s different than the one above, I don’t think that the solutions should be distinguished (if possible) — if this is the only difference between them then why should one be treated better while probably both can perform better depending on the implementation. Ofc I understand that sometimes we should stay sane with TLs to don’t let anything worse pass, but I don’t see what bad could’ve happened if E would have $$$n \leq 10^4$$$. Why I don't think that the solutions should be distinguished? I guess it's rather clear, but I'll address it in the final paragraph.
            • One is easier to implement — sounds nice, if you’re an author of course you are happier seeing nice and clean solutions etc., but from the view of the participant the other one is harder to come up with, so it’s a trade off for participants and again I wouldn’t say that one of them is more correct.
            • One of them is somehow smarter — I think this is the point in yesterday’s E. When you’re the author you also want to see that people have deeply understood your problem, that’s obvious, but what if they don’t? If this in the end goes to the previous point (about implementation time) then some participants should finish later and that’s it, but if you think that your solution really is the smarter one then… prove it, there are ways (AtCoder does it all the time). I could say that my solution is really “smarter”/“better” as it does not require thinking and it’s just coding (btw. I don’t think that ofc). As far as I understand if in yesterday’s E authors wanted to make use of the nice formulas, then why wasn’t it (for example) incremental problem (list of edges being added in order to the graph)? Model solution for each edge would store also the time that it appears and searching such final graph would give all the answers in not so much more complicated way. But the problem wasn't about it, the problem was static. I think that saying that I didn’t solve the problem because my solution wouldn’t extend here is like saying that you didn’t solve it because your solution wouldn’t extend for $$$n \leq 1000$$$ and $$$numbers \leq 7$$$ ($$$n$$$ is small so it wouldn’t take an hour to solve a testcase, it still would be linear).

            So it comes up to the question “is it ok as an author to use the TL to set boundary for AC somewhere in the middle of the sequence/set/bunch of observations that you can make to make your solution simpler/nicer/faster up to constant factor (and each of these observations would improve one of these)?” I think in general it's considered kind of a dick move because you force the participants to squeeze their solutions in some (for example technical) ways and I also think like that. Of course, most of the times authors face some slower solutions (slower in terms of complexity) that they want to disallow and they can't set the timelimit as high as they want, but I think it wasn't the point yesterday as I don't think that with $$$n \leq 10^4$$$ something would change.

            Summing up:

            • You didn't want to let me pass — why not incremental problem?

            • You wanted to let me pass — why TL and ML so small?

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

              as it does not require thinking and it’s just coding

              That's it.

              I am not being serious when I say "I still think that you didn't solve the problem :)".

              From my standpoint it is obvious that you can do cactus DP with some constant-size matrix. Reasons why I consider it not to be a solution for this problem:
              - The solution is obvious for div1E
              - I would not approve such a problem
              - The limitations are clearly turned out to the max to try to make this not fit in TL
              - It is clear that the fact that there are only 3 colors is super important, and all the ways in which good coloring is constrained is also important

              I understand that this is highly personal, and it seems that you care much more about winning than me. I don't participate in contests to write brainless algorithms, I participate in contests to solve problems. Author intent is important for me. And in this case I can see that author clearly knew about the existence of such a solution and tried to show that it was not intended. I listened.

              You wrote a code that produces the correct answer without understanding why this problem is even set. I understood what the problem was about.

              Your solution is valid and it is aligned with your understanding of competitive programming. It is not aligned with mine, and I think I have a right to this opinion. I do not agree with "Radewoosh didn't solve the problem", but I agree with "Um_nik thinks that Radewoosh's approach is not a legit solution to the problem".

              About setting TLs and limitations: you have a maxim that complexity is the most important thing and having complexity not worse than intended automatically means that you solved the problem. I am more about the intent. If the author thinks that the model solution is better (in any sense chosen by the author: faster, more interesting, simpler etc.) and they can construct a problem proving that — they are good to go.

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

                Don’t get me wrong, I totally agree that the model solution is far nicer than the crazy dp and it makes me a little bit upset that a nice set of observations and a way to understand something is used in a way that allows omitting it.

                I understand what you’re saying and I have to say that I’m kind of surprised about the differences in our understandings of the nature of CP. The stuff that you are talking about sounds to me exactly like things that differ CP and math competitions — understanding the problem fully/blah blah (blah blah isn’t meant to be offensive) vs coming up with correct and fast enough algorithm/coming up with creative ways to surpass standard ways and just pass all the tests (I mean for me that’s the difference). Maybe not even coming up with correct algorithm but implementing it, cause you don’t need to know anything about proofs. So it’s kind of right that I see the “nature of CP” in a different, more mechanical way (in practice it often varies, because of these creative ways).

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

              I completely agree with your summation. I had to make the problem incremental, but I didn't do it because of my stupid prejudices. It was a big mistake from my side, and I will try to not repeat in the future.

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

                I actually don’t think that it’s a big mistake, but rather that it could’ve been done in a better way in my opinion/I would do it differently. By “my opinion” I mean assuming that “complexity not worse than model should get AC”, so I have some (my own) understanding of, huh, conventions (?). I figured out that if people kind of read what I post, then it’s ok to write some actual thoughts which might be useful for someone, that’s why the message was so long, not to offend you or anyone in any way. Every problemsetter went through a lot of smaller or bigger fuckups (definitely including me) so I guess it’s nice to share insights.

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

      Oh my god, am I the only one with a normal solution without cactus DP?!

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

        Well, maybe you can argue that your solution is "clever"/"tricky", but the word "normal" belongs to cactus DP imho :p. It's easy (to think of) and natural and does not need to take advantage of the quirks of the statement which was very carefully adjusted so that these arbitrary facts somehow work out into a solution, while the dp solution does not care and can be adjusted and generalized however you want.

        I remember that a year ago Polish ICPC contest featured a problem where a standard solution with $$$O(n log n)$$$ time and memory could have been applied. But they added a weird constraint that the graph contains a 1-2-3-...-n-1 cycle and that the values on edges are up to 50000 (the general solution does not care about these at all), so that they can then solve the problem in some acrobatic adhoc way giving $$$O(n \sqrt{D})$$$ (D was a range of values) time and the only advantage of it was that it got $$$O(n)$$$ instead of $$$O(n log n)$$$ memory and they set the memory limit specifically low. I was ... not amused

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

so ✨ stylish ✨

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

Deleted

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

The overall difficulty distribution for the Div 1 is more like a Div 2 contest.

Normally Div 1 contest has several 3000+ problems. But we only have 1 this time.

Actually E is hard, Which makes the gap between D and E huge.

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

    Just clarifying: there was a problem F in Div1 during almost all of testing phase. But we decided to cut it a week before contest, to make contest more fitting in 2 hours round. Tho D turned out to be easier than expected, and point about gap is very fair. And Div1 usually have 2+ hard problems when it's duration is at least 2:30.

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

I think the problem D should appear in MO but not OI.

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

i want to know why all numbers is same ,ans is -1 i do not understand

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

    Because you don't have enough pair of numbers to fulfill 2 requirements.

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

Nice problems ... Thanks !

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

Thanks for this round. But the statement of task A wasn't short.

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

Took me almost 2 hrs to solve C during the contest, but after the contest, solved D in around 15 minutes. :(

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

LOL, the problem A in Div2 xDD I've heard it so many times, it's a running joke among my friends lol

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

A is the hardest problem in DIV2 LOL

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

Statement in Div2 A problem belike

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

@sevlll777 in question A of this contest .Suppose we have a case where AAAB (or let's say)AABB

then for which x and y will B win these cases?

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

    It is guaranteed that the given sequence of plays corresponds to at least one valid game scenario, for some values of X and Y

    but sequences which you give are invalid

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

      oh yes i forgot about that line .

      thanks for your help.

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

Update : Deleted

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

Hello! 
I received a notification from Codeforces stating that my solution for the problem problem link was flagged for similarities with other submissions, resulting in my disqualification from the contest. I believe this is a wrong accusation , considering the problem's simplicity, which naturally leads to resemblances in solutions.

Upon reviewing other submissions, I identified some differences in my code, such as my use of ordered map whereas all the other submissions have use of unordered_map . My coding style, indentation spacing and input/output formatting, remains consistent with my previous submissions in all my past contest submissions which is also quite different from other submissions. After grinding competitive programming for almost a year now it would be stupid for me to resort to copying solutions at this stage.

I kindly request MikeMirzayanov a reconsideration of my submissions to get this contest rated for me.

Here is my solution — link



Here are some other solutions which were mentioned in the message :

Submission 1

Submission 2

Submission 3

Submission 4

Submission 5

→ Reply