JeevanJyot's blog

By JeevanJyot, 4 weeks 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. YanZhuoZLY

  4. codinglunch

  5. hank55663

Div 2:

  1. YanZhuoZLY

  2. codinglunch

  3. huyinghao0706

  4. MongoliaTop

  5. RimuruTempest

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

»
4 weeks ago, # |
Rev. 3   Vote: I like it -248 Vote: I do not like it

Fuck off!

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Damn an Indian Round, super excited for this :)

»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +215 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +71 Vote: I do not like it
meme
»
4 weeks 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. :"(

»
4 weeks ago, # |
  Vote: I like it +74 Vote: I do not like it
Meme ;-;
»
4 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it
Fun Fact
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Then, if you could choose, who would be the newbie to also participate in testing?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I would choose you if someday I make a round but for that I need to be assured first that you won't leak my problems otherwise tdpencil or sus will be others whom I will approach

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I guess I promise you I won't leak any problems for any contest that I test, not only yours. I would also be interested what problems you could come up with, it would probably take much creativity to get an original problem(Since there are already 1.6k problems).

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          You just competed 3 times and you already want to be a tester

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

            To make it a bit fair for me, I've started coding with a bunch of different coding languages since at least 4 years ago

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
»
4 weeks 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

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

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

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

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

»
4 weeks ago, # |
  Vote: I like it +150 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Finally...

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems prepared by ashishgup, this round gonna be interesting

»
4 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Looking forward to this !!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited!!!

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

As soon as i get better at coding, I'd like to test out these problems too. I like the creativity in each of the 1.6k problems up until now! (Yes it is considered creative even if it looks like one of those math problems from school)

»
4 weeks ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

Has this round the strongest second pretests:)

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

After a long time finally a div 2 contest .

»
4 weeks 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).

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Contest after a long time, Looking forward for it!

»
4 weeks ago, # |
  Vote: I like it +137 Vote: I do not like it

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

»
3 weeks 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

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

Game theory problems loading

»
3 weeks 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)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

SergiuS2003 will win the round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to be green in this round

»
3 weeks 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! ;)

»
3 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

upvote for the image

»
3 weeks ago, # |
  Vote: I like it -68 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it

Hoping to make a comeback through this round !

All the best to everyone!

»
3 weeks ago, # |
Rev. 5   Vote: I like it -40 Vote: I do not like it

only mfs downvote

»
3 weeks ago, # |
  Vote: I like it -36 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

Hoping to get some increment in rating, too excited

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

I wish I could be green...

»
3 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

1 upvote = 1 less WA on pretest 2

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Liked it only because of Ned Stark)

»
3 weeks ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

worrying :(

WR :(
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That image actually indicated that we can expect strong pretests

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it

.

you can downvote this also, cause you people downvote everything!

»
3 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

I am very excited to participate in this contest. Good Luck to everyone.

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

I am very excited about this contest. Hope so that everyone would perform well in contest. Finger crossed

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

Game Theory Problem for sure!

»
3 weeks ago, # |
  Vote: I like it -67 Vote: I do not like it

»
3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

too many wrong answer on pretest 2 ngl

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

speedforces

»
3 weeks 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)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Jury verdict after everytime I submitted solution C

»
3 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it

我写不出来!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I had very high hopes of becoming green today but I could not solve problem B. So I didn't submit to problem A also as it would decrease my rating :(

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

F**k Div 2 Problems A

»
3 weeks 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 :')

»
3 weeks 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.

»
3 weeks 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!

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C in O(n)?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    The length of the substring is bounded by 8.

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

      Can you explain how you made this observation?

      • »
        »
        »
        »
        3 weeks 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

    • »
      »
      »
      3 weeks 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.

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

      Wowww, you have progressed so much when we last talked.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      tks everyone :|, I solved problem C :D

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

      oh bummer, I didn't think about the 4th case. Seem to pass now that I added a few more if statements, thanks.

  • »
    »
    3 weeks 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

»
3 weeks 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.

»
3 weeks 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)?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

at the starting of system tests everyones A failed system testing ...

»
3 weeks 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?

  • »
    »
    3 weeks 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.

»
3 weeks 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 :(

»
3 weeks 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.

»
3 weeks 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 :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for almost 1 hour i was thinking that In problem C ,they were asked to find largest string

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

I abandoned my ape instincts and spammed submissions.

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Loved problem D !

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

what a problemset. take a bow lord Ashishgup

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the explanation be available?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can find the Problem-solving ideas?

»
3 weeks 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?

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

    Probably you will be quite surprised by this this solution.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

sad short story :)

during contest:

https://codeforces.cc/contest/1605/submission/135163837

after contest:

https://codeforces.cc/contest/1605/submission/135174883

i had the case written in my paper but forgot to type it

»
3 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Really nice D.

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

Sums up my today's contest.

Meme
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it
»
3 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Problem C was a mess

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why cheaters are not being removed either in this round and in past div3 MikeMirzayanov

»
3 weeks 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.

»
3 weeks 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 :(

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldn't solve any problem

»
3 weeks 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.

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks for such a competing contest :D

»
3 weeks 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