Блог пользователя JeevanJyot

Автор JeevanJyot, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +805
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 3   Проголосовать: нравится -248 Проголосовать: не нравится

Fuck off!

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Damn an Indian Round, super excited for this :)

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +215 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +71 Проголосовать: не нравится
meme
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится
Meme ;-;
»
3 года назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится
Fun Fact
»
3 года назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

"Brace yourselves for WA on pretest 2"

At least we can expect strong pretests

»
3 года назад, # |
  Проголосовать: нравится +150 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Finally...

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problems prepared by ashishgup, this round gonna be interesting

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

Has this round the strongest second pretests:)

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

After a long time finally a div 2 contest .

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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).

»
3 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Contest after a long time, Looking forward for it!

»
3 года назад, # |
  Проголосовать: нравится +137 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

well Good luck to all

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Game theory problems loading

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

Finally another Ashishgup round!

(waiting for a constructive and a game theory problem)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

SergiuS2003 will win the round

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hoping to be green in this round

»
3 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

upvote for the image

»
3 года назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

1 upvote = 1 less WA on pretest 2

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Game Theory Problem for sure!

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

too many wrong answer on pretest 2 ngl

»
3 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

speedforces

»
3 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Jury verdict after everytime I submitted solution C

»
3 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

F**k Div 2 Problems A

»
3 года назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

"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 :')

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem C in O(n)?

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    The length of the substring is bounded by 8.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain how you made this observation?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +34 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
3 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :(

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +20 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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 :(

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

I abandoned my ape instincts and spammed submissions.

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Loved problem D !

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

what a problemset. take a bow lord Ashishgup

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will the explanation be available?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Really nice D.

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Sums up my today's contest.

Meme
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Problem C was a mess

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :(

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

please help me

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Thanks for such a competing contest :D

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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