JeevanJyot's blog

Codeforces Round #754 (Div. 2)
By JeevanJyot, 3 years ago, In English

Henlo Codeforces!

We are very glad to invite you to the Codeforces Round 754 (Div. 2), which will be held on Nov/12/2021 17:35 (Moscow time). This round will be rated for participants with a rating less than $$$2100$$$. For higher rated participants, we challenge you to solve problem F ;)

All the problems were authored and prepared by Ashishgup, the_hyp0cr1t3, ExplodingFreeze and me. We have tried our best to create an interesting problemset with clear statements. Hope you enjoy the round :D

You will be given $$$6$$$ problems and $$$2$$$ hours to solve them.

We would like to thank:

Good luck!

Here's the scoring distribution of the round:

$$$500 - 1000 - 1500 - 2000 - 2500 - 3500$$$

UPD: Editorial is out

Also, congratulations to the winners.

Div 1 + 2:

  1. SSRS_

  2. Vercingetorix

  3. MatikaneTannhauser

  4. codinglunch

  5. hank55663

Div 2:

  1. MatikaneTannhauser

  2. codinglunch

  3. huyinghao0706

  4. QuietBeautifulThoughts

  5. MyBotDear

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

Comments Comments (122)
| Write comment?
»
3 years ago, # |
← Rev. 3   Vote: I like it -248 Vote: I do not like it

Fuck off!

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

Damn an Indian Round, super excited for this :)

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

A round by Ashishgup to break the drought, I am excited!!

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

As a tester, I can confirm that problems are simply amazing.

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

Codeforces round after a long time, sadly I can't participate due to my exam. :"(

→ Reply
»
3 years ago, # |
  Vote: I like it +74 Vote: I do not like it
Meme ;-;
→ Reply
»
3 years ago, # |
  Vote: I like it +58 Vote: I do not like it
Fun Fact
→ Reply
»
3 years ago, # |
  Vote: I like it +74 Vote: I do not like it

"Brace yourselves for WA on pretest 2"

At least we can expect strong pretests

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

    Probably, all the problems have only two pretests...

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

      or maybe, we have several pretests but the second one goes hunununununununu….

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

As a tester, the statements are short and the problems are great.

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

Finally...

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

Problems prepared by ashishgup, this round gonna be interesting

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

Now I dont care about rating. Let me see WA on pretest 2

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

"WA on pretest 2" no doubt problems are prepared by Ashishgup.

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

Has this round the strongest second pretests:)

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

After a long time finally a div 2 contest .

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

With Ashishgup as problem setter, we may expect some problem on turn-by-turn game (Source: 5 out of 7 of his contest has such problem).

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

Ashishgup as an author, me ready to brick whole my contest on div 2A :P

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

Contest after a long time, Looking forward for it!

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

rainboy be like : challenge accepted! i'm gonna solve F first.

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

Hope i'll solve the problems in this round :(

well Good luck to all

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

Game theory problems loading

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

Finally another Ashishgup round!

(waiting for a constructive and a game theory problem)

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

SergiuS2003 will win the round

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

hoping to be green in this round

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

As a tester, I can confirm that the questions are really interesting and diverse. And Ashishgup rounds are always fun! ;)

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

upvote for the image

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

"Brace yourselves for WA on pretest 2", nothing new for me), haha

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

Lets see which Game are we gonna Play in this Round !!

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

I haven't had a positive delta in any Ashishgup round. Let's hope for a change in this one.

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

Oh jesus, I am nervous. I'm only 27 points away from expert, I hope I can get them tomorrow.

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

1 upvote = 1 less WA on pretest 2

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

Hope that I won't choke again in an Indian round

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

Game Theory Problem for sure!

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

So many shitty memes in the comments of this announcement. Or it has always been like this and I didn't notice?

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

too many wrong answer on pretest 2 ngl

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

speedforces

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

Participants whose Problem's solution got accepted in 1st attempt..( passing pretest 2)

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

Jury verdict after everytime I submitted solution C

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

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

    Damn True,....

    Just one pretest of problem C was difficult, not difficult but out of context of our thoughts.... :_)

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

F**k Div 2 Problems A

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

"For higher rated participants, we challenge you to solve problem F ;)"

5 minutes left in round completion. No one solved F. Where is rainboy when we need him :')

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

Is F O(N^5) dp? I feel like i moreless got the idea, however it's impossible to implement. Maybe I'm completely wrong.

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

Thanks for the round and F is really challenging, Waiting for the editorial!

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

I am sorry but problem E requires no thinking at all. I wonder how this got accepted...

Also, should Problem F be in a Div2 contest? Even LGMs can't solve it, while 2Fs should have at-least 20-30 solves.

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

How to solve problem C in O(n)?

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

    The length of the substring is bounded by 8.

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

      Can you explain how you made this observation?

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

        First, lets understand that if there is aa, so answer will be 2. Then if this up statement does not work in our string, then we its obvious that i, that s[i] == 'a' are at least at distance > 1, because first statement doesnt work. Then lets see what we can get from here. We can see that if there is s[i] == s[i + 2] and s[i] == 'a', either way it will be our answer. Then lets find another case when there is something like that abca, acba answer will be 4 there. If these all cases doesnt work, then i that are equal to 'a' are at least at distance >= 2, and if we think little bit we can see that we have abbacca, accabba. Thats all. Sorry, for my bad english and may be bad explanation

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

      How is an len=8 substring possible? For me its bounded at 7.

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

    There are only 4 cases: 1. aa 2. aba 3. abca 4. abbacca

    And you can prove that if the gaps between the 'a's are greater than 3, then it is impossible to get a good substring.

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

    you can observe that you need only 1 operation, or none at all if it's already sorted, let's call X the number of 1's in the string, it's a binary string so you can tell if it's sorted by looking at the last X bits if they are all 1's then it's already sorted, if it has zeros then we choose those zeros with the ones that are not in this group. 0001111 (it's sorted because the last 4 digits have 4 ones(all of them)) 00110101 (here we can say the last 4 digits has 2 zeros in them, so we take those with the ones that are not included)

    *if it's not clear 0 0 1 1 0 1 0 1 the last 2 ones are already in place (no need to do anything), the last 2 zeros need to be replaced by ones, the first 2 ones are the ones(all that is left) to be replaced it will always be non-increasing because the ones that we choose are always in the front

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

I dont like very much that style of problem statements, where there are a lot of details explained, and then in the last third of the text some more or less related question is asked.

Better give a first sentence to understand the idea of the problem, then come up with the details.

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

For problem D, was the idea based on placing numbers according to their most significant bit (using the fact that a tree is bipartite)?

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

For D, the final idea that came in my mind was that we will try to end the game at every node itself. Which summed up that there cannot be neighbours with their MSB equal. But no clue how to solve this construction. Any hints?

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

    Yes, the idea is correct. We can try to end the game at every node. For every node, try to make sure that all neighbors have an unequal MSB.

    Color the graph white and black (such no two nodes are the same color).

    Notice, number of numbers with MSB at Position 0 = 1, number of numbers with MSB at Position 1 = 2, number of numbers Position 2 = 4, and so on.

    Let number of white nodes be w and black nodes b. Consider min(w, b). Consider the binary representation of min(w, b) For now, assume w<b. Let's say w=5. In Binary it is 101. So take numbers with MSB at position 1 and 3, and use those to color the white nodes. Use the remaining numbers for black nodes.

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

How to solve problem B ?

I thought of a O(n) solution but couldn't solve it.

Then I later saw that that n<=1000. By that time 1hr had already passed so I gave up :(

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

This was my idea of D —

First, the condition u^v<=min(u,v) meant we can only go from u to such v that their MSB is in same position. Eg 4 to 5 ,6 ,7 etc. Then we need even path lengths (length = no of edges) to make those nodes optimal. After this I was kinda stuck. Is this approach correct?

P.S I liked C. Nice observation required.

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

rip rating -122

spammed 1.5h on C and wrote a BIT and a monotone stack. nothing worked so I got frustrated and started writing garbage. HA HA HA HA HA HA!

I tried to submit some curse words but the contest ended :(

good problems though. My bad. D was pretty okay, but I didn't solve it on contest :(

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

I abandoned my ape instincts and spammed submissions.

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

Loved problem D !

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

what a problemset. take a bow lord Ashishgup

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

Question F is so strange that I thought of three false algorithms!

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

And now i have delta -108 instead of -3 :(

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

When will the explanation be available?

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

Can we use binary search in problem C?

int l=1,r=n; int mid = l + (r-l)/2;

Iterate over string to find if there is a valid substring having length mid. If this condition is true, then right = mid-1 else left = mid+1;

Will this approach work?

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

    No binary searching won't work. You can consider S = "aabbaa" for example. Substrings with length 2, 3 or 5 that satisfy the problem conditions exist, but there is no valid substring with length 4. The key to this problem is observation: The smallest possible lengths are only one of [2, 3, 4, 7] or -1 if there is no valid substring.

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

I didn't take that meme serious, and then...

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

Really nice D.

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

Sums up my today's contest.

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

Problem C Editorial :- https://www.youtube.com/watch?v=EWhmvHCB19k

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

Problem C was a mess

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

    if you couldn't solve problem C it doesn't mean it is a mess

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

Problem A should be rated at least 1200. Even though it's a one liner it takes a lot of effort for beginners to deduct the answer. Especially with weak mathematical background. Some of the 1200 problems are easier to solve just by working through the problem. The problem is very good but it should be rated properly. It's definitely not 800 and 900.

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

I had the correct solution of problem C when I saw it last night. However, due to some mistakes on coding, it took me one extra hour to work it out, which made my rank only 3000+, I should have been in the top 1500 :(

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

Thank you so much for making this round, really enjoyed competing.

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

WA on pretest 2 was my close friend in this contest. I don't know why it didn't leave my side.

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

I want to know what the difference is between these two WA and AC

please help me

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

Thanks for such a competing contest :D

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

Problem D was nice I really enjoyed it while upsolving but it doesn't seems to be a 2100 rated problem

→ Reply