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

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

Hi everyone!

I would like to invite you to my fifth Codeforces Round, that I set with my friends FastestFinger, Vivek1998299 and ridbit10.

We are excited to bring another contest within a week :D

With that said, I bring to your attention our new Codeforces Round 648 (Div. 2) that will take place on 07.06.2020 17:35 (Московское время). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.

I would really like to thank:

You will be given 7 problems and 2 hours 15 minutes to solve them.

Good luck! :D

The scoring distribution will be: $$$500 - 750 - 1250 - 1500 - 2000 - 2500- 3000$$$

Upd: Quick Editorial — Hope you guys enjoyed the contest :D

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

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

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

<tester's-comment>

As a tester, I found the problems diverse and very interesting to solve. I think this is will be a fun round for many. Participation is recommended :>

</tester's-comment>

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

may be the fastest scoring distribution ever

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

Deleted

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

    Ah, shit. Here we go again.

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

      This blog is still not in home page, I wonder what happen after couple of hours :P Comment box will be flooded with those "proud" comments like previous round xd

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

      Ah shit. Here we go again!

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

        plagiarism detected :P

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

        Yes that level of spam will happen here xD

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

          Definitely, I think I will come back every few hours just to look at the comments lol XD

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

        Hahaha, honestly didn't notice this.
        I just thought it to be an appropriate meme to comment, so I did. :)
        Btw, why will I farm contribution even after this? :)

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

          I did not want to accuse you of plagiarism or contribution farming. All I was trying to say was, the recurrence of "Ah shit here we go again". aaargh. nevermind. All fun is lost when you have to explain the joke.

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

      i dont know why but whenever i read this line anywhere Gta San Andreas music sound starts playing in mind

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

    Seriously your dream was having 2 Indian rounds in a week ? Congratulation in that case.

»
4 года назад, # |
  Проголосовать: нравится -78 Проголосовать: не нравится
even Div. 1 participants should find some of the tasks interesting

If that is the case, why not take a div-1 round in parallel with 3 shared tasks (Div.2 C, D, E) ?

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

    They need to get Div1 D,E,F then. Which is not easy to make

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

      They already have 7 problems. Both Div-2 and Div-1 would have 5 problems each with 3 shared.

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

        That fits the contest problem-count wise. But what u are asking for is making the last 3 problems of div2 (which authors think are fine for div2) to last 3 problems of div1. They obviously won't be difficult enough.

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

        I have solved C, D, E. I am not at that level so I can solve Div1ABC, so for Div1 this problem would be very easy.

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

          I regret saying what I said. He said the tasks would be interesting for Div-1 users so I thought that maybe they would be hard. Turns out it was a speedforces with an easy F..

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

Is it just me or are others too wondering where Ashishgup and friends have been during the last few months?

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

Was confused how did the comments from last Ashishgup's contest announcement changed only to find out it was a new contest XD

»
4 года назад, # |
  Проголосовать: нравится +115 Проголосовать: не нравится
even Div. 1 participants should find some of the tasks interesting

goodbye rating.

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

    But it will be tough for everyone so it should not affect your raking as it is relative, what was the point as if it is only tough for some, not all

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

I'm so tired and sleepy right now that I read it as..

You will be given 2 problems and 7 hours 15 minutes to solve them.

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

Why is this blog still not on the main page yet?

I want my daily dose of cringe (from the proud Indians in the comments) and i cant wait any longer!

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

that C looks hard

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

Thanks Ashishgup and Team For this effort.

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

We are also excited to see another contest within a week :D Thanks

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

I hope after the contest Ashishgup will be one the top ten contributors(as he has +155).

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

[retracted]

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

Ashishgup be like : "yalgaar ho"

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

Does that score distribution mean that it will be a speed-forces? With an easy D?

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

Eagerly waiting for the div 2 A. It was pretty nasty and amazing at the same time, the previous contest by the same authors.

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

Also this time we expect memetorials.

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

CF-Community

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

"We are excited to bring another contest within a week :D" Cool.

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

Truly said — I become more excited when I see the score distribution like this way..

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

Is score distribution related to the rating of the problems ?

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

    Since you seem to be an old CF contestant, this question is a little bit of weird!

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

ohh god..once more contest prepared by[user:Ashishgup]...amaizing previous contest #646 ...does anyone remember "Guess The Maximums" problem ?... a very tricky one...hope to see more good problems this time also...

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

Back to back Ashishgup rounds, nice :D. You are a nice motivation for me to prepare nice contests.

I'm so curios, how many hours a day you spent for your contest? And so, how many hours it took to prepare this one?

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

    Can i please test your next round?

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

      Hi! I estimate that it took us an average of $$$2$$$ hours per problem to come up with it, and roughly the same amount of time to prepare it on Polygon :)

      So around a total of $$$4$$$ hours per problem

      @Testing, sure! We'll invite you to test our next round :D

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

Can somebody please tell me what information can we infer from the scoring distribution?

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

Please make a contest like last time.

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

Namoosan vote up konid

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

MikeMirzayanov- I think you are about to add another standing to CF's home page called most hated users. — You know, every single comment of mine is disliked for at least 30 times by default — And also CF has blocked me from commenting twice :) — However I'm too polite :/

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

6 years back a visionary leader by the name of Honorable Narendra Modi democratically became the prime minister of the world's biggest democracy. His vision of Digital India to transform India into a digitally empowered society has certainly lead us to this proud moment where an Indian becomes the first person to hold 2 rounds within a week. Certainly its a proud moment for all the Indians on codeforces today. So excited...Jai Hind !!!

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

    Just Shut up.

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

    As a fellow Indian, I request you to pls stop posting cringe content on CF. It only degrades everyone's opinion about us

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

    This was cringy af.. to the next level..

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

      I'll take that as a complement.

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

        Indeed. The best thing a quality cringe provides is the firm belief in itself. You embrace it and take everything said to as a compliment. Thanks for THAT quality of cringe. Now I'll make myself believe that I indeed gave you a compliment and then replied with a greater cringe just to show you what cringe of the first water can do to someone. No Offense.

        P.S. I think I failed with the quality of cringe but nvm.

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

          Wow, I didn't get that but I liked that.

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

            Wow, I didn't get that but I liked that.

            I feel the exact same when I read the explanation and code of some F or G.

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

              Lol. I'll suggest writing down an array and trying the shifting operations. Understanding how it can be done in 3n/2 operations is definitely difficult, rather first try to understand if it can be done. For G, initially don't think much about what a submask/mask is (those words are heavy and intimidating for me too). Just try to think about what bits are different. In the last part, they have said about using 6 bits, which might further intimidate you. But if the explanation were to be more complete, it isn't that difficult to understand. The reason is that there are 13C6 numbers which have 6 bits on and no two could be submask of each (note that the submask thing is necessary only for the second approach, not for the suboptimal one).

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

                Welp.. I think u took it too far.. But thanks tho.. ur explanation is GREAT and I'm looking forward to solve that question with this. (y) Cheers mate!!

                But what I meant there was just an analogy to SOME F and G :)

                Have a good time. X

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

        .

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

    Cringe on CP platform is just something to be cherished. Cannot find it anywhere else!

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

    we dont't do andh-bhakti here....(Indians can relate)

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

    Damn. The bhakti is strong af. Never knew we had middle-aged Indian uncles joining CF.

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

      Never knew we had dumb kids who cant understand sarcasm joining CF.

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

Nice Score distribution .

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

Excited for the Indian Round!!

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

The scoring distribution makes me happy and afraid at the same time!

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

Contests of Ashishgup always offer really good graph problems!

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

Ashishgup is now in top 10. Great!

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

Is there something wrong with problem's div1D checker? I got AC, but when i look at test logs i see stuff like this in several tests

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

    82738980 -> link to my submission

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

    It's okay. The relative error, which is $$$|1 - \frac{pa}{ja}|$$$, where $$$pa$$$ is the participant's answer and $$$ja$$$ is the jury's answer, is indeed less than $$$10^{-6}$$$.

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

[DELETED]

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

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

Untitled

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

That's a truth...

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

Congratulations to Ashishgup.I think you are first Indian to be in top 10 in contributors in code forces.

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

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

How is contribution calculated , i mean Ashishgup has +162 and BledDest has +126 ,But BledDest has authored many contents than Ashishgup

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

is it rated?

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

Is it only me who feels that 1st question is comparatively difficult to other Div2 contests when there are Indian setters!

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

Hello, MikeMirzayanov my net connection got lost. So, I can't compete now fluently. Moreover, I have submitted A and B. Please make the round unrated for me

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

Ashishgup you should stop making contest. Your constest aren't good at all. It contains very weird questions. Please codeforces don't let your status go down because of them. Many people registered for the contest but a lot of them just backed off. This is sad. Your Div 2 problems are interesting but it doesn't qualify for the real contest maybe a unrated one (practice round) would be better. :)

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

    Div. 2 contests are targeted towards somewhat experienced programmers. If you feel like div. 2 is too hard for you, there's no shame in starting off in a lower division. I recommend participating in the division you can comfortably solve at least 2 problems during a contest (if you want some challenge) or the lowest division that is still rated for you.

    Regarding practice contests, you can always participate in old contests virtually (basically a simulation of the real contest) or just solve old problems until you feel like you are ready to take on div. 2.

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

      I am seeing Experts with 1800 rating and CMs not being able to solve A in my friends list. While the entire contest may be good, A is certainly overkill for a div2.

      Personally, I have not been able to solve a single question till now. While I cannot claim to be good at CP, I have generally been able to solve AB in div2 at least.

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

        A is not overkill. its just difficult and require more logical thinking than other As. What is the point if all the Div2 As are cakewalks ?? sometimes its refreshing to see questions which are just not speed test and requires you to think for some time.

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

        Sorry, but contest was too easy for div2, i think it's div3 level. if u cant solve so easy problems u should just practice a much better

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

Hi!

Unfortunately, CF-Predictor may not be able to handle as many contestants/users as we have today. I have an idea for the optimization that should resolve the issue, but

  1. I need time to implement it.
  2. I'm not 100% sure it'll help (because I'm using a free heroku account and it has bunch of limitations).

If the extension or usual website (http://cf-predictor-frontend.herokuapp.com/) go down today, feel free to use another replica

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

This round sucks!!!

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

Wired Contest. I can solve ACDEF, but just can't solve B.

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

This round will teach most of the new comers that logical thinking is the first step in competitive programming, not the knowledge of all the data structures and algorithms. The first thing you need to develop is logical thinking. The one contest comes where you need to think instead of use some tricks or data structures, do not complain about the lack of it. Logical reasoning and thinking is an important part and should be treated at such.

Also the problem difficulty is increasing uniformly, which has somewhat become rare in recent contests. Kudos to setters !

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

.

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

Can someone tell me whats wrong with following logic for D ?

I take count of bad and good and if good person are zero, answer is always yes.
If bad persons are zero, check if all good can reach the end or not.

Now I check if any Bad person has a good person immediately next to him. If yes, then they cannot be blocked and answer would be No. If all the bad persons can be blocked, I block them and then check if all the remaining good persons can reach the end or not.

Any idea what I can be missing ??

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

    WRONG EXAMPLE

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

      This is an invalid example, because the statement says 'It is guaranteed that the cell (n,m) is empty'

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

    Yes thats what I also did and it passed pretest. I block by putting wall on 4 side of B.

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

    Your idea is right but you did something wrong on implementation.

    dx should be {0,0,1,-1}.

    ll dx[] ={0,0,1,1};
    ll dy[] ={1,-1,0,0};
    
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You have to block all neighbours of bad persons also. This is clearly necessary, and we can prove it is sufficient.

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

    Maybe you made the same mistake I did. I didn't notice that if a cell has a bad person then you can't block that cell.

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

After E:

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

.

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

After knowing E solution:

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

How to solve E??? I know maybe it uses greedy strategy, I tried something with choosing numbers with highest bit set and then choosing atmost 2 more, just random submission. So someone give a subtle clue please!

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

    Just choose maximum or between 3 vals.

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

    There always exist an optimal solution with $$$k <= 3$$$

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

    $$$n = 1$$$, ans = $$$a[0]$$$.
    $$$n = 2$$$, ans = $$$a[0]$$$ | $$$a[1]$$$.
    else ans is triplet with maximum or.

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

      Can you show example when we need triplet, not just maximum element?

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

        If I understood you correctly.

        3

        1 2 4

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

          Oh, maybe I misunderstood the question. What output will be for this example?

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

            Should be 7 which is the OR of the 3 numbers.

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

              But we can just take the k = 1 and sequence {4} for this example, and we get the same answer, no?

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

                I think you misunderstood the question. If we take just the 4 answer will be 4.

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

        In the case of 3 numbers with "independent" bits, like $$$2^0$$$, $$$2^1$$$, $$$2^2$$$ it is optimal to choose all 3.

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

      How to find the triplet with maximum or?

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

        Brute force, O(n^3)

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

          Umm, then I want to die.

          This don't pass.

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

    the best way to make a set is using K=3 or 2 or 1:

    if u choose 3 number and trying choose 4th number to change anything, 1st 2nd or 3rd must constain some bit that u find in 4th number. but u already have this bit, so u dont need k > 3

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

      Oh my god I was thinking about that max(1, k-2) condition and choosing 3 but thought $$$n^3$$$ wont pass. Maybe it can be done in $$$O(n^2)$$$ but I get your point, nicely said.

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

        O(N^3) will pass

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

          Mine did not :thinking:

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

            I looked at your code, you should simply have used or operator | rather than looping over 60 or so bits! I guess that lead to TLE.

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

          Oh yes you are correct I calculated operations as $$$500^3 \times 64$$$ (64 for the bits of numbers) but I think its not like that

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

        to don't get this mistake again u can calculate time of work (kinda), if u have n'3 with n = 500, code will make 1,25 * 10^8 operations. we have very weak operations and c++ can make 4 * 10^8 of weak operations (if u use pragma u can reach 10^10 op.). c++ can make 10^8 of big(idk how say it) operations (like n log of segment tree). => u code will pass the pretest in this problem

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

      why is this true?

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

What is the solution for G?

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

any hints for A and B?

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

    For A
    take all the rows and columns which are all zeros.
    now whenever you make a move, one row and one column is reduced. so the max number of moves possible are minimum number of available rows or columns. That numbers decides who wins the game.

    For B
    If there is atleast 1 element with b_i 0 and 1, you can always sort the array. Other wise check if it is already sorted or not.

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

The worst round i've ever seen. ABEF — is like A, but many participants can't solve just because it's E,F and can't be so stupid. ABEF is much easier than CD (bcs here u need some brain)

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

I got two WA in A and one in D -_-

Nice problems!

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

May be Fastest Editorial overall ..Thanks

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

Took me 6 attempts to realize.. Just one dfs call was required in D. facepalm

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

Great round! Excellent variety of problems. Finally doesn't look like mathforces/bitforces and real algorithmic round.

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

Though I did not give this contest I can tell that this is the best div2 round ever.Ashishgup orz

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

Whats-App-Image-2020-06-07-at-1-03-53-AM

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

Definitely one of the best rounds I have ever participated. I really enjoy these problems which emphasize the process of thinking and proving special properties, instead of the boring implementationforces.

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

F was so easy for me, and was a 2-liner, why was it kept before E? I would've got F much earlier but I couldn't get E and so went on to G as it was interactive, and read F only at the end of the contest. So unlucky :(

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

WTF was testcase 38 in F?

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

Was G something like there are only 63 elements we care about at most so pick random subset of half the remaining elements to narrow down where it could be? Only other idea I had was parallel binary search but couldn’t narrow down past 20 queries with this

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

    Yep, i guess it should work, i was trying to code it but unfortunately i couldn't come up with a good implementation, so i ended up with half of a spaghetti-code.

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
    This solution for G is wrong
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Right this is the parallel binary search I mentioned. I actually don’t think you can do better than 20 queries with this method, but I could be wrong. One way to describe your queries is that the i’th query contains all elements with the i’th bit set to 0. I think the problem is that you only get information for the entries that you didn’t query. So if the first element has a lot of unique bits then they won’t be detected ever, I believe. So I think it is possible to create some adversarial cases that force you to use more queries. You might be able to prevent this through randomization, but not entirely sure.

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

Whats-App-Image-2020-06-07-at-1-01-35-AM

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

Nice contest. I enjoyed solving all :p

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

Hey nice problems, thanks!

But one suggestion. In A text goes like "...and does not share a row or column with any...".

The usual wording is more like "Does not have a row or col in common". The word "share" is most of the times used to denote borders of cells next to each other. Since as a problem that would make sense, too, it is missunderstandable.

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

How do you downvote an announcement after upvoting it :-/

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

I really liked the problems, nice job Ashishgup, indeed it was never a normal div2 round, i think they were very nice for IQ/creativity test. They were like problems in first round of Computing Olympiads in Iran, but indeed they were way harder. Thank you all(authors, coordinator and etc) for such nice problems.

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

After a lot of wrong answers,the pretest passed in last 12 seconds for D xD

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

may be swap(A,B) better ..i think B is more easy than A.. :3

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

Adhoc Forces How to downvote an announcement please say

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

    Observation Forces I'd say

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

      Ya every problem involving a lot of observation Observational Problems till A and B are OK but when C and D and E involve it then it becomes shit ,hope setters in fututre will keep it in mind!

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

        The what, so all div1 contests are shit because their DEF div1s usually involve a lot of observations and that should only be limited to AB div 2s instead?

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

Can anyone explain E for test case 2 1 1 4 1 8 how can we get 14 , if i take both 2 and 8 there will be 3 ones which don't have their 2nd and 4th bit-set so how is the condition "at least max(1,k−2) (max(6-2,1)=4) elements of the subsequence have the i-th bit set in their binary representation" is satisfied for the 2nd and 4th bit?pls explain

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

    choose the triplet $$$2$$$ $$$4$$$ $$$8$$$.
    0010
    0100
    1000
    bits with i = 1, 2, 3 can be taken since they have atleast a one in their binary representation and since k = 3, we need atleast just 1 bit so our answer will be 14.

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

    Take 8, 4 and 2. Then k = 3.

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

    k is the length of the chosen subsequence (k = 3), the length of the main sequence is n (n = 6).

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

Nice problems! Sorry to bother, but could someone please help me understand why I got a runtime error on prob A pretest 1 82790397? I see nothing wrong with it, also it runs fine compiled on my machine. I ended up rewriting the code in python to make it work. Thanks

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

    I think it should've been "col(m), row(n)" instead of "col(n), row(m)".

    (Since vectors reserve a bit more space than you asked for to allow amortized O(1) pushback, making this mistake doesn't necessarily cause a Run Error (I think), that could be why it worked on your machine but not on the server.)

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

      ... aaaand you are right. Embarrassing mistake. Thanks a lot for checking!!!

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

Problem E i submitted it using DP with 500*3 instead of BF (500)^3 but it gave me WA on TEST 6 can anyone explain please the code

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

Nice problems but I feel like the difficulties (from problem to problem) could have increased a bit faster — with such small increases it felt more like Div. 3 to me (that is, more stressful than Div. 2 due to needing to solve more problems to stay in the "positive rating change"-range).

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

Problem D video editorial: sOlUtiOn

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

My idea for the solution to D is check if the bad guys can reach the end, if yes, then block all the neighbouring cells. Then check if all good guys can reach the end. Why does this fail on pretest 7?

Link to my submission : https://codeforces.com/contest/1365/submission/82872417

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

    If there is a bad guy in a neighbour of the destination cell, then your code is blocking the destination cell. In such cases, if there is a good guy in a cell reachable from the destination cell, the answer should be "No", but you code prints "Yes". See this case for example:

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

      There's a typo in my code. That's why it fails. But for your case the answer is YES right? because you can build a wall above and below the bad guy.

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

A request to future problem-setters, please try to break a long sentence into several sentences. For example this one:

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

    Yep for the first 20 mins I was like I need to do summation of 2^i for each element or essentially the sum

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

The whole contest gets ruined if the first problem does not go as planned and the statement was quite misleading. I solved the whole time considering border should not be shared for each cell. Even any announcement was also not made to clarify the statement. Is it enough reason to make round unrated as a lot of participant wasted a lot of time on this which was rather a very easy problem ? PS — I completely understood the problem only after reading editorial otherwise it was a mystery to me.

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

    There was nothing misleading in the statement. It was written that you can only claim cells which do not share a row or column with any already claimed cells.

    There was no announcement, because there was no need of an announcement.

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

C-Constructive

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

Does failing on sample tests counts for penalty??

If not then for me, It's showing 3 penalties even though one of the wrong attempt is wrong answer on pretest 3 (last sample case)

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

No hacks at all in this contest O_o

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

Ashishgup contest exist !

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

For those who didn't solve, you just had to go through all the possible triples (x, y, z) and look at the maximum among x | y | z.

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

I hope for a div. 3 round before the next educational one or in place of it. Anyone agree with me?

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

Very nice problems and strong tests, congratulations!

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters, fix wrong division cases and update ratings them again!

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

Any idea why i am getting TLE on this? It is the same idea as in the official solution...

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

    For every 'G' you are Calling bfs i.e. at max n^2 times. But what you should be doing is calling bfs one time from the final cell and count how many 'G' can be reached from there.

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

      yah..figured it out afterwards.. thanks anyways.. but btw i could run bfs from every g if i would use dsu :)

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

    I think u have the same problem that I had on contest. You have to mark cells you were and don't start bfs from all good persons "G" (if you elier were in this cell "G" and you could arrived to cell (n, m) you don't should to check this again).

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

      yah... this is one way to optimize.but it is not optimal i will implement tomorrow both dsu and bfs from (n,m) :))

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

Can anyone tell me why my code gets "Memory limit exceeded on test case 8". I first mark walls around 'B', if there is a 'G' sharing a side with 'B' code outputs 'No'. Then do a reverse traversal from destination (n-1,m-1) using bfs and mark all reachable nodes. If a node is 'G' and not reachable i output 'No' else 'Yes'.

Link to my submission — https://codeforces.com/contest/1365/submission/82880705

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

_Nice problem set.I hope everybody enjoy this round _

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

Enjoyed the contest, thanks!

Of the problems I worked on: A, C, D were very good. I did not like B. In general I hate these problems with one-line solutions. Anyone else?

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

Isn't it allowed to hack a solution after the end of contest? When I click on hack it! The page shows "You can not hack the submission".

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

can anyone help me with why my algo for prob E is wrong-

we need to take only 3 elements to maximize the value, so for first element we will take the maximum one as it will give the best result,now we need to care about all the unset bits of the first element as the set bits will be set in our final answer too, so we change the rest of the numbers of the array such that for any number in the array, at position i if it is set in our choosen first element and it is also set in the number of the array we unset it.

In this way we will get an array which will be devoid of all the set bits of first choosen element then from that array we can again take the maximum element as it will be the biggest contributor, again we can do the same operation to take the third element.

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

@Ashishgup

Test cases for F is not strong enough.

I believed I hacked some AC submissions using this data set. Obviously the right answer is No, but they all returned Yes.

1 3 8 9 8 9 8 9

Submissions:

https://codeforces.com/contest/1365/submission/82823958 https://codeforces.com/contest/1365/submission/82854157

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

    I remember as a master you can hack other's solutions after contest.

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

    Became Candidate Master. Wait! that may have already vanished while you are reading this or soon going to be.
    Solved 6 questions. Pretests passed. Not celebrated, as I miss corner cases many times :|.
    System testing passed! Still waited for rating updates.
    With gain of 93 points, became Candidate Master for the first time. Celebrated hard!!
    Now, I came to know that I missed a test case, which was probably missed by author too.
    Tragedy!!
    That's fine, I'll try my best next time! ;D
    At last, good questions. Kudos to the setters and also to the one who pointed out the mistake!

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

greedyforces

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

For problem D, something seems wrong with the judge. The solution that I submitted shows few accepted test cases(as it eventually gives a TLE). However, those test cases should also not pass as the output of my code is completely different.

Judgehttps://codeforces.com/contest/1365/submission/82901062
Ideone:
- Test Case 3 — https://ideone.com/Rfss7o
- Test Case 4 — https://ideone.com/heJHCG

Can someone help me in understanding is something actually wrong, or it is just me.

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

    Can you explain what type of difference you have noticed?

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

    Input data is not enough. You can see that the three dots at the end are not part of the input.

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

      Sorry, I didn't pay enough attention. I thought dots are the last line of the input(since dots represent blank spaces).

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

Anyone solved E by DP ?

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

    I tried but stuck in time limit that its is taking O(n^3*64) which is not acceptable

    My idea is store dp[i][j][k] where the i is index that till ith index what is the maximum value of length j and for the corresponding bit k.

    But this is 64 times more slower for this problem

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

Hope you guys enjoyed the contest :D

Ashishgup are you an ididot or what

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

Problems are really enjoyable to solve

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

Is it just me or does anyone else also feel that problem C is the new B and Problem D is the new C in the recent rounds?

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

It's enjoyable round.But,I couldn't solve any of this :( Will try next to do more better :) Anw,Should i learn C++ or keep going with python3?

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

    This round, I did everything in Python 3 except E. Last round, Python 3 was too slow for A which really messed me up (I could have just translated it to C++, but I was too stubborn).

    If you don't know C++ yet, it never hurts to learn. But use the right tool for the right job: if time limits aren't tight, a package like itertools can save you a lot of programming time.

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

    Learn C++ and quit python as early as possible.

    You might not understand why I say so and python might seem very easy to code rn but you will sure face difficulties (like recursion limit in python or TLE with same logic that gets accepted in cpp) as you continue to grow. Although you can get it accepted in python as well but it becomes very troublesome and requires some extra effort. Also, there are some questions with zero accepted solution in python. I wrote the same logic in cpp and it worked but no one could get it accepted in python because of TLE.

    So, why not just write in cpp and avoid many issues. Speaking from personal experience. Good luck :)

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

      I agree with your points, see I have only used Python till now in contests but now I am converting myself into CPP bcoz it's the best tool for Competitive programming. My strategy in contests is to use Python for constant time or linear time algorithms and switch to CPP for tree and graph-based problems.

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

D solved using dsu (disjoint set union) if anyone needs it : SoLuTiOn