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

Автор wxhtzdy, история, 2 года назад, По-английски

Hello Codeforces!

We are glad to invite you to Codeforces Round 798 (Div. 2) which will start on Jun/10/2022 19:35 (Moscow time). Please notice the unusual time. You will be given 5 problems and 2 hours to solve them.

The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially in the round.

All problems are prepared by n0sk1ll and me. We would like to thank:

Thanks to NEAR for supporting this round, details can be found in this post.

We are looking forward to your participation!

Score Distribution:

$$$500-750-1250-1750-2500$$$

UPD: Editorial

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

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

Why only one div2 tester?!

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

    And also I am wondering how has a cheater become a tester!

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

      Setter (blog author) is a cheater himself, lmao.

      Y'all can downvote, but look at the author's last round and prove my opinion wrong (IOI selections proved my opinion correct yet again as a supposed 3500 solver, finished behind 1800 rated people).

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

        To prove my point further — MysticPanda and SigmaMale06 are both alts of his (exact same submissions are sent from his main account after doing contests from alts).

        The tester of GR19 is a friend of his and it took him roughly the same amount of time to do C/D and F/H, simply unbelievable.

        Not to mention he's done 3500-rated H before tourist and jiangly and dozens of LGM's failed on the problem, sounds sus?

        And let's not forget that alts fail to solve a 2000-2200 rated problem almost every time.

        Many of people from "Racunarska Gimnazija" are also known for participating in plagiarizing and violating CF rules and which organization does this person belong to?

        Regionals, National finals, IOI selections? Which contest did this person perform like a GM? Well no contest, as even I've beaten him in regionals with 30% point difference.

        Again, you may choose to downvote this comment heavily, but too many points go to prove what I've stated is straight facts.

        CodeFoces is becoming a joke if you let a cheater propose a contest and people of CF keep defending him through hiding the truth. You may propose a round but can't hide the standings my friend and your history of cheating is still present on the internet.

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

          Serbian Competitive Programming Lore

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

          Why didn't you tell this after GR19?

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

          MikeMirzayanov please look into this

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

          Come on bro, I'm not defending wxhtzdy because he is my friend, but because you attack him for no reason. Seriously? First of who gave you permission to reveal the school he goes to, if he himself doesn't reveal this information, its clearly private. Second thing if you look at his submissions before that contest, its clear that data structures are the type of problems he is really good at solving. Also, you beat him on regionals? That is not the place to flex your knowledge, especially since he had 40% better score than you on the Serbian Informatics Olympiad, where may I mention was 1 data structure problem on second day, and he got ac on that one. On GR19, where he got to red, a tester was from "Matematicka gimnazija", a school which is basically our rival school for programming, and no person from there would reveal problems before the contest to him. One last thing before I go, where is the "Racunarska gimnazija" stereotype coming from?

          PS: it's hypocritical of you to write this for upvotes (particularly last line), and then write this up here(for even more).

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

            The last line of my original post was sarcastic.

            The school is not revealed by me, it was public info stated in his profile. Yes, he did change it later, but that doesn't change the fact that it was public before.

            I'm not flexing regionals, just saying an alleged GM couldn't solve a simple linear algebra problem for more than 15/100 points. My friend toniskrijelj beat him by a huge margin in the olympiad as a 1900-2100 rated person. Should he be a grandmaster as well then? Oh and he's good at DS? You mean Radewoosh and 10s of other LGMs aren't?

            Everyone got AC on the DS problem the second day including me, so that contributes nothing to proving he can solve a 3500-rated problem especially after never having solved a 3000-3500 problem in practice before.

            People from "Matematicka Gimnazija", "Gimnazija Jovan Jovanovic Zmaj" and "Racunarska Gimnazija" are very good friends most of the time, just like n0sk1ll is a friend if wxhtzdy. So yes, they're very likely to share info between each other.

            The stereotype comes from multiple people performing almost too well in 1-2 contests and then performing terribly for the next 15 contests (just take a look at submissions of your friends, no need to elaborate on that one). Also many of you have 2-3 alt accounts because of saving stupid internet points.

            Your reasoning is foolish at best and doesn't defend anything. Wxhtzdy cheated and everyone with brain cells can see it.

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

              I do not say he is cheater or not, But sometimes even a LGM can't solve a really simple problem that an expert has solved in a contest, So the fact that a GM always can solve simple problems in your opinion is completely wrong !

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

                It's not always, but his alts, onsite contests and the sole fact he never attended a single contest later show that he can't solve a 2400-2500 problem, yet we're discussing whether he could do a 3500 problem in 30 minutes.

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

                  He hasn't participated in contests after that because he said he wanted to go to the Olympiad as a red. Doesn't mean he would have lost rating, but he didn't want to risk it

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

                  I mean really, he has 2700+ problems solved just on Codeforces, out of which there are 96 2100 problems, 86 2200, 49 2300, 63 2400, 38 2500, 18 2600, 10 2800, 7 3000, a 3200, a 3400 and a 3500 problem, which makes it around 350 2100+ problems. I didn't even mention oj.uz.

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

                  Any reasoning for him changing country to china, changing name to wxhtzdy which is wxhtxdy (MiracleFaFa) with one letter changed, erasing full name, city and school he is going to? (his profile during GR19)

                  Skipping contests just to have high rating, while your average rating is probably below 100-300 points is similar mentality of a cheater trying to have higher rating than the rating he is currently capable of.

                  Yeah, his wish to go to Olympiad as red probably made him submit H after his predicted delta went under what's enough for him to pass 2400 rating during the GR19.

                  Your hypothetical scenario is probably what happened, there is difference between solving a problem in 1 month vs 30 minute span DURING contest (extra stress and what else), you just cannot compare these two to be equal.

                  And the fact that he has ton of problems solved literally proves nothing, you can easily solve 3000* rated problems with editorial which isn't real life scenario in contests. He has like 500 solved 800* rated problems which he probably did to increase his ego because it boosts his problem solved count shown on his codeforces profile, which again shows that he cares about surface looks making him more likely to cheat to increase rating.

                  Despite all of this, ignoring all the facts and assuming that he didn't cheat, chances of this all happening on coincidence are very low. I guess it was just his lucky day lol.

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

                  maloy-uspokoysya.

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

              First problem day 2 wasn't to prove he can solve those, it was just to say there weren't hard DS problems so he couldn't prove it. People from these schools are friends but rivals too, so they wouldn't share problems between each other. You realize how dumb it is for one person to make all 3 problems on the Olympiad, while there is a LGM whose problem was accepted for IOI who didn't make any problems on it. The school WAS public info, it isn't anymore. Even if, in a hypothetical scenario, he had that problem before the contest, how could he solve it without the editorial if he isn't good enough. He had 1000 on qualifications while your friend nohax had 850, and you had 790, which proves it was just a bad day for him, and shit problems on SIO. Simple linear algebra? Come on you go in a school where you do advanced maths, much before other schools, and its not simple linear algebra, cuz if it were he would have solved it. If you didn't waste your time on this maybe you would have performed better then him on SIO, looks like someone is jealous of others talent for CP.

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

              I love how wxhtzdy is maybe doing cp to perform better next time while you are spending time on this

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

              Just wanted to come back to this comment after the IOI22 and IOI23 made some things more clear.

              Oh, toniskrijelj beat him by a huge margin at the Olympiad?

              What did he win at the IOI 2022 again?

              And in case I have to educate you, wxhtzdy won a silver at the IOI 2023, that is as good as the Serbian competitive programmers get (not counting one of them).

              Oh also, I think you know this guy, SomethingNew. Look familiar? Yeah that's because he was also at the IOI 2023 and he and wxhtzdy had a very similar performance at the IOI this year. Wanna know what's interesting about this guy? Look at the standings of the same round you accused wxhtzdy for cheating in. Yeah, that's right, he placed even better than him on that round, however he couldn't have cheated on that round, but clearly, the IOI tells us that they have a similar skill level.

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

                I'm not gonna argue about IOI23 performance by wxhtzdy, props to him for performing so well, well-deserved. He was always a good competitor, but his performance in GR round remains suspicious.

                His 2022 performance was poor at all stages and cannot be compared to the 2023 one. You're comparing toniskrijelj's performance to wxhtzdy's in two completely different years which is a lame argument.

                EXIT: Toni beat him in all stages when Miloš was considerably weaker, Toni got to IM easily and beat Ilya in contests so the comparison makes no sense. I'd argue this version of Toni wins silver as well, but that is all left for speculation.

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

                  Yeah that is a fair point, however:

                  1. We can argue that the Serbian competitions are more oriented towards math, obvioisly, since the comitte is mainly from the Mathematical Gymnasium. This also means that you and your friend Toni have an adavntage in comeptitions, as your school works with the same program as that school

                  2. You might try to argue that Toni could win silver this year, however however Miloš is 2 years younger, and also has proof of him being worth the IOI silver. This is not even important because we are not arguing who is better but did Miloš cheat.

                  3. Codeforces round are way different from actual Olympiads, as the time is different, the problems are also made by random problem setters so you performance depends heavily on the luck factor. I'm not saying there is no luck factor in Olympiads, I'm saying that you have more control over it.

                  These are not all the arguments I have, but some of them

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

                  Nikad neces biti gas

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

                  Please stop arguing about it. Yes, performance was really good and is suspicious. Is it proof of him cheating, no.

                  And that was such a long time ago, it really does not matter that much now.

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

                  bajo nisi svestan rucna lakat prva desna

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

          false, wxhtzdy is next tourist

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

          Think about it this way: at least only him got (allegedly) the solution from someone else-- at least the problems didn't get leaked completely on some bongmonolian telegram server or some shit

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

        Lol, why are they down voting? You made valid points.

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

        BlameForces

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

        I do not think that he cheated, he just got lucky on GR19 and got unlucky at IOI selections. No matter what you think, you cannot deny that he is really good in programming.

        Why do you even care if others are cheating? You are supposed to participate for yourself and improve your own skill. I see no point in arguing if someone cheated.

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

      I'm not a cheater, I'm a Serb (most stronkest)

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

Excited to participate in this one. I hope for some nice problems.

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

Thanks for the early Score Distribution!!

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

If any of the problem setters require a tester they can message me :)

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

5 problems what's this 2017?

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

I'm genuinely curious about how testers are selected for each round?

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

    There is a discord server for testers. They tell you when they need testers for a round and you tell them if you want to test it. To join the server you have to be invited by someone who is in it.

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

It sounds a very good contest! score distribution came quickly this time !!

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

22.35 is unfriendly to Chinese college students, and 0.35 is even more so.

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

Welp, good luck everyone

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

The blog title doesn't say Div. 2 so I got excited thinking there'd be a Div. 1, then was disappointed.

I feel scammed, so downvoted

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

as a tester, I suggest you to do this round, because it's the bestest round because it's 100% Serbian (bestest country)

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

Greedy Score Distribution!

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

I am not good at dp problems, so i want to solve a lots of dp problems. But in cf, when i use tag DP, there comes problem which can be solved by greedy/binary search/others 75% of time. That's demotivated me and i see no improvement on dp.

I know about atcoder & cses dp set, i am solving those. But i want to solve cf/cc like dp problems, so where i will find those? Basically i need cf like dp problems where the solution is only and only dp based, can you suggest any?

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

    You can add tags to your search in the problem set, but as for "where the solution is only and only dp based" I wouldn't recommend that, because it'll only limit your thinking instead of trying to connect all the stuff you know into a working solution, which is a very valuable skill.

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

    Here is a mashup for DP https://codeforces.net/gym/302977

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

Let's see if we can tackle D this time !!

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

I hope to reach an expert rating in this contest :)

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

Hope to again become specialist in this conrest

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

** Please notice the unusual time **

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

TerryWang Orz

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

hope I don't enter "Farsh Mode"

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

lol cheaters authoring cf rounds and mike doesn't remove it

clown world never ends

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

Sorry I am new here. Why can't I see the register button for this contest? In the email it is said that registration is open till 5 minutes before contest begins but it is showing registration closed for me. And if I logout, I can see the register option. Someone pleasee help.. This is my 2nd contest so I am confused

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

    You are already registered. If you view participants, sort by rating and scroll down to your rating you should find yourself already in the list.

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

Eagerly waiting for the contest. Hope to see some nice problems. Guys note that the timing is 2hr late than usual.

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

Eagerly waiting to lose expert

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

Hoping to solve two problems today. Fingers crossed.

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

i am not able to enter in contest.

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

Good Luck Everyone :)

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

It's my first experience of participating in the contest at CF. Good luck!

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

Hope to become Blue today.

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

Guys, I am not able to register. Am I not eligible or something?

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

    There is a rule that you have to register 15 minutes before the contest starts. Contests also have late registrations, after 10 minutes of contest start, you can register(probably as unrated, I am not sure)

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

Thanks for such an easy A :)

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

Hated it.

clearly visible by the number of participants.

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

    can any one tell me what is diference between educational and div 2 round ?

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

      both of them dedicated for div2 users but the only difference is hacking:
      in educational round: there is 12 hours after the end of the contest for free hacking without any penalty points.
      in regular div2 round: you can hack a solution only during the round and there are penalty points for unsuccessful hacking and points for successful hacking.

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

Hi, For tree questions like C, it is guaranteed that is there is an edge between u and v and u>v, then u is farther from the root than v? Thanks.

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

Hate those 5-task contests D:

PermutationForces <3

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

Problems A and B were shit

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

There must be some kind of trap in D. It is so easy, yet so few have solved it so far. Hope I pass system tests.

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

First 4 pblms could hv made a good leetcode contest.

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

How to solve D?

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

    I did it with dynamic programming from all 4 sides — top left, top right, down left, down right and took maximum of them for one cell, then took minimum of all these cells. I don't know if it's right tho.

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

      Thanks for sharing this page link, learned a new technique.

      Can you please share any link of the proof of this equation from the book :
      |x1 − x2| +|y1 − y2| = max(|x1' − x2' |,|y1' − y2'|).

      Thank you in advance.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    • Plane rotation by 45'

    • ans = (Median by x, Median by y)

    • Plane rotation reversal

    I was looking at the area around the point after rounding, but maybe you can be more accurate in this

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

      Oh, very cool, thanks. Didn't know about that trick.

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

      I also thought of the same idea but was struggling in its implementation :(
      Read Editorial and its solution is also quite good.

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

    I realized that the answer is a convex function and we can find local minimum by some ternary-ish search but felt like there must be a more concise solution

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

    For each cell you can compute the fathest black cell. You can do it this way: If the current cell is in row a and in column b There are four cases: 1. Black cells who are to the left and up, the distance for them is a-i + b-j 2. Black cells who are to the right and up, the distance for them is a-i +j-b 3. Black cells who are to the left and down, the distance for them is i-a + b-j 4. Black cells who are to the right and down, the distance for them is i-a + j-b Notice that a and b are constants so we always want to maximize the other terms, i.e. -i-j, -i+j, i-j, or i+j. So now we want to find the maximum for the other terms. Notice for the first case for example we want to know the maximum of -i-j in the submatrix whose top left cell is (1,1) and whose bottom right cell is (a,b). We can create "Prefix submatrix" that can get this things for us and that we update along the way. The other cases can be handled the same way

    Edit: People were much faster than me at replying haha

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

What was the observation for C?

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

D was very similar to 1658E - Gojou and Matrix Game. In fact I solved it by reading the editorial for that problem.

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

Key Idea for E: The answer is always going to be less than or equal to 2 (excluding the mandatory +1 for all the zeros). Hint: Consider the trailing zeros of each element in binary.

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

E is a mastapiece!

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

How to Solve C ?

I tried removing the one with maximum subtree size : If there are many subtrees at the current level with equal maximum value , just check the subtree sizes of it's children & remove the one which has the smallest maximum subtree size(in it's children) , ended up TLE.

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

    Either I save my left child or my right child. WLOG assume it is left child

    then we repeat the infection process with right child as root.

    We can therefore calculate dp answers for both left and right child and then calculate max of (dp[left] + nodes[right] — 1, dp[right] + nodes[left] — 1).

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

Was one of the most enjoyable contests, even though I am not that good with trees yet, but problem C was interesting. Thanks a lot!

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

I think A has weak pretests. My wrong solution passed it once. Edit: Even system tests are weak. I have a case which hacks lots of solution in A which are passing the system tests.

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

How to do D? I thought that the optimal point would lie on either of the lines X=(Xmax + Xmin)/2 or Y=(Ymax + Ymin)/2, then I could check it with the boundary points, but it's wrong.

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

What is the purpose of making the tree in C binary lmao

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

someone pls find failing testcase for problem C https://codeforces.net/contest/1689/submission/160135619

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

Problem D is plain boring, Just write 4 loops and make sure you copy paste right in other 3.

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

As a move of sheer desperation, mid-round I managed to get WA on pretest 15 (thanks to the authors for making this possible, as much as I could've FST'd in this manner), and so, could anyone tell me whether my solution is completely off-beat or I just couldn't implement well:

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

    I don't think there should be that many casework lol. One way to go about it is to first check every possible configuration after a single operation (which can be done in O(n^2) naively which still works fine), and if that is not the case, then there exists at least two elements with maximum number of trailing zeros (this is not that hard to prove), and we can simply add one to one of them and subtract one from the other one, and every element is connected.

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

      well there isn't so much casework lmao-- my solution is the same as that which you described, just that apparently somehow I managed to not keep the graph connected in the last case you described (+1/-1), as per the checker

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

    Pretest 15 was the only pretest which needed 2 non-trivial operations.

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

LOL i solved C using bfs

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

The problems were really good, and in my opinion, it is the best Div2 round as compared to the past 4-5 contests. Pretests were also well prepared.

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

Thanks for the fast editorial !

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

I solved A,B within 12 minutes and passed, tried D but no luck. Can I become specialist today ?

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

https://codeforces.net/contest/1689/submission/160132878 Can someone please explain to me why do i get runtime error in this submission of C? Thank you.

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

In problem C, can someone provide a smaller test case in which deleting the child with a larger subtree will lead to the wrong result? Thanks in advance!

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

    If you mean larger subtree.

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

I have a doubt in problem A. Let's suppose we are given strings as "abcda" and "bbbbb" and the values of n, m, & k are 5, 5, and 19 respectively. So, we can make the required string "aabbbbb" (5 b's) which will be lexicographically smallest string possible(we took 2 a's from string 1, and then took all the b's from string 2 and then string 2 became empty and thus we got that), but if we solve according to the editorial or any similar approach which is described then we will get the string "aabbbbbb" (6 b's). So the previously mentioned string should be the answer as it is of length 7 and is a prefix of 2nd string. (also according to dictionary the smaller string should come first).

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

Why do the latest 5-problem Div2s all have their C problem about trees?

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

Who else got Runtime Error on Test 10 for C using python at least once during the contest ?

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

Can someone please check my submission — 160152177 to E? It shows wrong answer on test 50 and there the jury's reason is that graph isn't connected. But my code checks the connectedness initially and it involves pretty elementary dfs which I can't find any mistake in.

update-fixed

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

Can someone tell me how in the 2nd pretest 2nd testcase the input edges are 3,1 and 3,2. Isnt the tree supposed to be rooted at 1. How does that work.
Link to my submission: https://codeforces.net/contest/1689/submission/160160596

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

[DELETED]

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

I gave the codeforces round 798 div 2 yesterday. Today I received a message stating that my solution for problem B coincides with a number of users, and I have been thrown out of the contest. Problem B was a easy problem. It might be possible that many people have same code. Please investigate the matter.

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

    The message is here for your kind reference.

    Attention!

    Your solution 160103728 for the problem 1689B significantly coincides with solutions Sattu_45/160099066, N_Assass1n/160100029, Nonunou/160100053, senju/160102702, Zer0/160103728, shubh_k_04/160103825, hydracody/160107390, Gurpreet_1/160107617, 2020uce0063/160108774, agamya.vrishabh/160109739, codeblaster_20/160109812, habib_toshev/160110709, prachi_007/160111563, madhurtoo/160111641, shreymishra2708/160112448, aditi.ojha.min20/160113447, aditi_ojha_21/160113816, gabdyq/160114250, arjun_0207/160114516, krishagarwal535/160114531, BANDeputat/160115107, ArijitDalui/160115210, Night_N0mad/160116674, ramsampell_123/160117422, rahgeer/160118106, tarun_1801/160118246, Chutkicoding/160118336, nam_j/160118957, ayush222sagar/160118998, ATGP07/160119810, bapi123/160121793, NoiceOp/160123135, tempMail1/160123286, Avi_afrid/160123337, BrxDeputat/160123536, Shake-Her/160124454, sahaj_279/160125689, kaushik_35/160125738, ishitgarg1231/160126911, devanshkapri/160126964, drtank/160126980, RandomNumber97/160127515, prachi15/160127769, aman584/160127809, seekingmygreat/160127922, akashrs/160128302, shubhanksagar3/160128904, rohit_kumar_/160128905, roy0123/160129195, nj234/160129276, Harneet_9042/160129384, Commander_coder/160129457, sun_shine11/160129480, aks2001/160131274, 203ashish/160131675, anipatil21/160131980, Shubhamshu/160132285, Rxhul_12/160133135, Pranay_2020/160133221, Shaun_2002/160134063. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

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

Hi, MikeMirzayanov. I received a message from the system saying that: "Your solution 160093839 for problem 1689A significantly coincides with solutions leaf1415/160093839, kyadekhrahahai/160109391." It appears that my source code template was copied from a past contest and used in kyadekhrahahai/160109391. Here is evidence that the code already existed before the contest. (https://codeforces.net/contest/1690/submission/159728484) Thanks.

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

    Yep, but I reviewed codes of kyadekhrahahai and it seems both solutions (A and B) are cheating. They match with solutions other solutions based on massive leak. As you wasn't punished, I don't see a reason to revert the punishment.

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

      Thanks for your reply. Reading the message "Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.", I concerned that I would be punished if I did not plead my case.

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

Your solution 160100374 for the problem 1689B significantly coincides with solutions dinosparton_013/160100374, jwalit7/160107778. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

Today , i received this mail , You can chech our submissions and even our language is also different , it is just a false plag or just coincidence.

I would request MikeMirzayanov to look into this and revert my rating back as clearly there is no fault of mine.

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

Your solution 160100374 for the problem 1689B significantly coincides with solutions dinosparton_013/160100374, jwalit7/160107778. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

Today , i received this mail , You can chech our submissions and even our language is also different , it is just a false plag or just coincidence.

I would request MikeMirzayanov to look into this and revert my rating back as clearly there is no fault of mine.

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

Masterpiece