valeriu's blog

Codeforces Round #804 (Div. 2)
By valeriu, history, 2 years ago, In English

Hello, Codeforces! Or, as we like to say in Romania: Noi nu spunem asa ceva, Codeforces!

We are proud to finally invite you to participate in Codeforces Round #804, which will start on Monday, July 4th, 2022, 14:35 UTC You will be given 5 problems and 2 hours to solve them. We greatly recommend to read all the problems, statements are very short and straight to the point.

In this round, the theme is not Independance Day related. I know, maybe we should've made the theme "Freedom", but we are not Americans and the puns within the problems were already written.

Joining me on the problem setting panel are:

Also, we would like to thank:

Here is the scoring distribution: $$$500 - 1000 - 1500 - 1750 - 2500$$$.

Good luck & have fun & the third part!

UPD1: Editorial is up!

UPD2: Winners!

Div 2:

Div 1:

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

Comments Comments (137)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

As a tester, please upvote the op. The problems were most fun I've seen in a while...

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

As a setter, I setted.

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

    as the problemsetter that published the announcement, I did neither problemset the problems in the current contest nor did write the announcement mainly because my problems are too bad lmao skill issue git gud bozo

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

    As a tester, I tested.

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

    As a Vip-Tester, I Vip-Tested.

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

    As a contestant, I registered

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

    Happy 1 year anniversary!

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

As a tester, I can confirm that the problems were very fun! :D Hope you have fun too!

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

As a non-tester, considering who are setters, I strongly recommend you participating in #804.

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

As a Mihai fan, does Mihai show up in statements?

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

Yay! Finally a classic Div 2 with 5 problems :)

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

Hope my friend kozliklekarsky will reach candidate master in this round!

Marinush

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

No Freeforces then ;D

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

Haha "noi nu spunem asa ceva" actually translates as "we don't talk like this"

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

    it translates to "We dont say such a thing, Codeforces!"

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

Love Romania!

Greetings from Greece!!!

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

Commented so this would stay in recent actions as deserved.

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

Gheal what was your #804 order at KFC? ;)

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

    If I recall correctly, a hot double booster with a side of medium fries and coke.

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

I am gonna perform good in this contest.

→ Reply
»
2 years ago, # |
  Vote: I like it +111 Vote: I do not like it
You'll never know !
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    damn, how'd you discover this?

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

      Inspect Element

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

      Darkmode slightly entered the room and sat in a corner without coming into attention of anyone

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

Why is no-one talking about the colors tester are arranged -- It's the flag of Romania!!

Greetings from Greece!

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

    oh, I just noticed the Blue-Yellow-Red theme! That's really cool.

    Also... I kinda saw 2-3 comments about Romania here (in Editorial and Comments), is July 4 something special in Romania? Like ik it's Independence Day for the U.S, but what about Romania?

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

Good Luck!

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

I want to be green,crying.....QAQ

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

As a newbie, Hope for some easy and straight forward statements

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

    I first wanted to do some sarcastic insults, but then, I figured there is just no point to it and it isn't even funny. I will leave this anyway

    We greatly recommend to read all the problems, statements are very short and straight to the point.

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

    Don't hope so in Codeforces Div2. Try Codechef Div4 instead, it has good problems for beginners

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

      I first wanted to do some sarcastic insults, but then, I figured there is just no point to it and it isn't even funny. I will leave this anyway

      We greatly recommend to read all the problems, statements are very short and straight to the point.

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

Only 5 Problems? Do they have the same difficulty as the problems in the same position in previous codeforces Div.2 Round ? Are you doing this to response to the call in an entry which says not to waste problems since they're too difficult for Div.2 official participants? If so, I think it is a good start for codeforces to search a way to reform the contests.

For some reason I can't take part in this contest , but I hope to see what difference will the new Div.2 round problemset bring to codeforces and participants,wish all of you to have a happy codeforces round!

And thanks to the contest maker for his/her contribution to make the statements brief to save our time.

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

    Short answer: idk

    Long answer: I don't think I am allowed to respond to any of your questions before the ending of said contest. I leave this comment as token that after the end of the said contest I will modify my response as to actually give you a concrete answer

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

    So, mainly the way the coordination went vis-a-vis the fact that we only had 5 problems was that the only one that proposing div2Fs was me (which is was a big mistake), and when I found O(N*log(N)) solution in E, most testers found that it sufficed for the difficulty of the contest. As such, the fate of the round was decided way long before we had Olympia considered as a tester, and as such even before her blog.

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

Hope to get to CM this time! (I think I have just done it!)

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

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

super excited!

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

What is the story about the usual time is 17.35 !!

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

    I also see 17:35 in the blog for some reason. I think it is in Russia time, so it is still the usual time.

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

    Ah yes, editorial mistake. Modified now, we are sincerely sorry for this

    This happened as an oversight from my part, as the timezone I live in is UTC+3, so it seemed normal to me to add the time at which it will start for me, ignoring the fact that other countries may exist

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

      Well, now it is just "Monday, July 4th, 2022, 14:35 UTC" (I live in UTC+3). I was really scared

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

Orange name, I am coming!

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

Please do something about the contest start time announcement in the future.

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

No!I will get 0!

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

what criteria qualifies you for "vip-tester" over regular "tester"?

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

    Vip-tester: their feedback made a significant change in the problemset.

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

Good luck & have fun & the third part! this guy is obsessed with 3 some next level

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

Doing C for the whole contest, getting the right logic (presumably), implementing everything in a large code and fix edge cases and then WA on pretest 2. And you never know what's wrong.

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

    What was the logic for C though?

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

      What i don't get in c is, it is written that the only permutations similar to a=[4,0,3,2,1] are [4,0,3,2,1] and [4,0,2,3,1]. can someone tell me why [3,0,4,2,1] is not a permutation of [4,0,3,2,1]? it satisfies the condition of MEX too

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

        The mex of the last 4 elements isn't equal (4 in original permutation, 3 in your permutation)

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

        If you take just the last 4 elements of those two arrays, then MEX is different.

        That is MEX(0,4,2,1) = 3, while MEX(0,3,2,1)=4.

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

        because mex of subarray (0,3,2,1) of a = 4 and same subarray in [3, 0, 4, 2, 1] is (0, 4, 2, 1) for which mex = 3 since mex is different for same subarray, this is not similar permutation

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

    I can totally understand you.

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

Problems were interesting.

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

How to solve E lol

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

IDK. I found B difficult for me .

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

how to solve C?

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

How to do Problem $$$D ?$$$ Any hints?

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

    An interval can be completely deleted if it's even length and there is no strict majority element. Using this fact, just do $$$O(n^2)$$$ dp.

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

      How to do the do?

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

        One can think of this problem as choosing the maximum length subsequence with equal elements, such that the interval between the chosen consecutive elements can be deleted completely. It's very similar to a classic LIS problem.

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

Problem C: https://yukicoder.me/problems/no/1709

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

    (I'm not saying that the writer/tester should have noticed it and rejected the problem. It was used in a small Japanese contest so it is understandable that many people don't know this problem.)

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

    Something similar was on CodeChef too https://www.codechef.com/submit/CONSTMEX?tab=statement, although the problems are slightly different, the idea and hence the solutions are pretty similar

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

Thanks for the round! I think the problems are interesting.

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

How to solve D?

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

How to solve C? I spent almost all the time but still have no idea.

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

    First, I saved the positions in array c; Then having a range called l,r with initial values of l = c[0] and r = c[0], I iterated through numbers from 1 to n-1. if c[i] changes l or r, I just updated the l and r; otherwise, multiply the answer by the positions available inside the range.

    My submission: https://codeforces.me/contest/1699/submission/162803936

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

The most difficult Div2 I have participated in recently

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

unordered_map sucks! In problem D, unordered_map sol > 2000ms array sol = 143ms, 15x faster Why am I always FST?

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

This Guy Posts Solutions on YouTube in real time. Can we do something about that? He always gets 500 to 600 views during contests

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

Well balanced contest I guess!

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

    It could've been balanced better, but I'll assume you are joking.

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

Third best round this year. Waiting for more :yum:

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

This is the most unlucky round for me ever... Long time ago i missed +70 delta because forgot to write cout << "\n";, and now I missed my CM title because i forgot to change mod 998244353 (from the previous round) to 1000000007, making an incorrect attempt. Now my rating is 1896...

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

Great contest! I think the problems are great. There's only one small suggestion that I'm gonna give you: The main test for D is not strong enough, as you let some wrong codes to pass the main test, for example, the code with N^3 complexity and some wrong dp which can be Hacked by the following testcase:

testcase

Hope next time when you propose a contest on Codeforces you can strengthen your main test and test more to make a better contest.

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

    Unfortunately, none of our testers had this wrong dp. All $$$n^3$$$ solutions submitted during testing got TLE on pretests. Pretest $$$2$$$ contained all possible tests with $$$n<=10$$$ and I assumed that it would catch any reasonably wrong solutions. The other tests were also (supposedly) strong enough.

    I'm very sorry for this issue.

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

A classic div contest and as a contestant i really enjoyed this one.Thank you very Much.

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

    I enjoyed it a lot as well.

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

    cheating lol!!! Your problem C solution is matches with HermioneGragersBesty even the variable names.. and you added extra for loop for what??

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

      Hey listen,juat throw this false blame on someone,i swear i haven't copied it from someone and why don't you ask Hermione that why he added so many comments in his orogram?...Is he afraid thar he might get caught? Look i have applied my own logic and it may possible that variable names are same and i swear i didn't even know who the hell is Hermione. So just throw this false blame on somebody else...

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

        The contradiction of this statement is that you know they put a shit ton of comments, but then claim you don't even know them...

        Nevertheless, it does seem like the two codes are different

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

Problem A is very similar to my problem XORABC from CodeChef April Long 2022.

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

    hi! I am working hard on problem solving ,,but my rating is constantly decreasing ..can u see what i am doing wrong or should i keep practicing and have patience?

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

      Because you are blaming an innocent,that's why.

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

        if u r so innocent just explain what is an extra loop doing in ur code??

        for(int i=0;i<n;i++){

        }

        lol!!!

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

          It's so easy to explain it that I often do it so when I realize my wrong in my code and modify it quickly to get more pts in contests.

          That is only one of the possible reasons.May be he Ctrl+A+V and too lazy to delete other things.So many explanations isn't it?

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

I am so happy for becoming pupil in this contest by achieving rank 2401.

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

I got -inf but good round!

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

Thanks to the round,make me to green

Hope I won't back to grey again

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

    Same, I also hope so. Because I also became green in this round.

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

It's bad that 4 of 5 div 2 winners are probably alts

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

On the fifth sample test case of problem D, originally the question stated that [4, 4] was the only reachable array of 2 elements. I thought that was correct, but the wording now reads "one possible". Possibly a stupid question but what other array is reachable, and how? The only other number it could be is [3, 3], but I cannot see how that could be achieved.

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

    [3,3] can be achieved too.

    1 5 2 3 3 3 4 4 4 4 3 3

    1 5 2 3 3 4 4 4 3 3

    1 5 2 3 4 4 3 3

    1 5 2 4 3 3

    1 5 3 3

    3 3

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

      Yes! How did I miss that. Thank you.

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

I received a mail after the contest that my solution for Problem C coincided significantly with one solution(My solution — 162794304 other solution ,162779144. This coincidence occurred becoz almost same question already came in Codechef once — Do Not Touch the MEX. I knew that and copied the editorialist solution of that problem Solution. As the solution was already published before the contest, hence there is nothing wrong in copying it. I request MikeMirzayanov to look into this ASAP.

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

My ratings from this round disappeared! any news?

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

Oh no

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

Where did my rating go????

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

Today I got mail from from codeforces, that my solution 162783009 for the problem 1699B significantly coincides with solutions pallavvarshney76/162777169. Clarification : It was just a coincidence. The logic was very simple and the implementation can match with anyone. In my case, it is just matching with a single person which shows that I have not copied from any source , also I have not used ideone.com . I never got this type of complain earlier. Kindly look into it and do the needfull MikeMirzayanov. Um_nik, antontrygubO_o ,BlueDiamond, lucaperju, atodo LucaIlie, borgar02, freak93, Ionut_Padurariu, Lemur95, FairyWinx, Brodicico, apostoldaniel854, Kirill22, Olympia, lavish315, Kuroni, caheman, theodor.moroianu, TheScrasse, 244mhq, VladHaivas0205, Tudy006, stefdasca, CaesarPP, Fanurie, elizatoma000w, mat50013, IacobTudor, codrincrismariu, Matteo.Verz, mircea_007, amcbn, mihneacazan, armand09 Artyom123,Gheal ,tibinyte, valeriu

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

    If you are greatly in distress (as I can observe), do know that the problemsetting area of any organization of any contest does not and can not interfere with any area of the plagiarism check. As such, don't bother the problem writers into this, let alone the testers.

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

      Can you please tell me how to contact to problemsetting area of Organization. It is very stressful that i again become newbie after working hard.

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

        Aa I said, we do not have tangents with that area. I only assume (as you did initially) that it is managed by MikeMirzayanov .

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

    I feel completely embarrased and frustrated that I did not make it to this list. Although, it seems your loyalty to the OP is greater than I thought-- You took his advice and not mentioned me publicly

    → Reply