wxhtzdy's blog

By wxhtzdy, history, 2 years ago, In English

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

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Why only one div2 tester?!

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

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

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +230 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +244 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +122 Vote: I do not like it

          Serbian Competitive Programming Lore

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +26 Vote: I do not like it

          Why didn't you tell this after GR19?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 2   Vote: I like it +17 Vote: I do not like it

          MikeMirzayanov please look into this

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

          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 years ago, # ^ |
              Vote: I like it +59 Vote: I do not like it

            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 years ago, # ^ |
                Vote: I like it -28 Vote: I do not like it

              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 years ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

                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 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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 years ago, # ^ |
                    Vote: I like it +2 Vote: I do not like it

                  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 years ago, # ^ |
                    Vote: I like it +25 Vote: I do not like it

                  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 years ago, # ^ |
                    Vote: I like it +18 Vote: I do not like it

                  maloy-uspokoysya.

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it +4 Vote: I do not like it

              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 years ago, # ^ |
                Vote: I like it -19 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it -8 Vote: I do not like it

                now that's what we call a perfect way to end the conversation

            • »
              »
              »
              »
              »
              »
              »
              14 months ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                14 months ago, # ^ |
                Rev. 2   Vote: I like it -11 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 months ago, # ^ |
                    Vote: I like it +16 Vote: I do not like it

                  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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 months ago, # ^ |
                    Vote: I like it +19 Vote: I do not like it

                  Nikad neces biti gas

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 months ago, # ^ |
                    Vote: I like it +19 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 months ago, # ^ |
                    Vote: I like it +19 Vote: I do not like it

                  bajo nisi svestan rucna lakat prva desna

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

          false, wxhtzdy is next tourist

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

            imagine becoming the next tourist without even participating in rated contests.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -15 Vote: I do not like it

          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 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

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

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

        BlameForces

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it -56 Vote: I do not like it

        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 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +35 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks for the early Score Distribution!!

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    +1, If you need a cyan tester, please ping me :)

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

    Yeah, if you are interested and don't think I am too weak,you can ping me too:)

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

    Yeah I am interested too. It will be gonna learning and fun.

»
2 years ago, # |
  Vote: I like it +55 Vote: I do not like it

5 problems what's this 2017?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    I think it's better to have 5 instead of 6 problems for Div2 participants

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

      +. I really enjoy when there are less problems, but they are harder overalls.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        They weren't harder this time though. Or maybe were in the start(like AB), but much easier in the end(DE).

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

          Kind of. I still wanna kick myself for not solving D this time.

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

    5 problems contest is not that uncommon.

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -39 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Welp, good luck everyone

»
2 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Greedy Score Distribution!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

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

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

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to again become specialist in this conrest

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

** Please notice the unusual time **

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

TerryWang Orz

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope I don't enter "Farsh Mode"

»
2 years ago, # |
  Vote: I like it +95 Vote: I do not like it

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

clown world never ends

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      In 'friends' section in participants you can also find yourself easier.

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

        loll am dumb.. thanks a lot!!!

»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Eagerly waiting to lose expert

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Hoping to solve two problems today. Fingers crossed.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i am not able to enter in contest.

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

Good Luck Everyone :)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope to become Blue today.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks for such an easy A :)

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hated it.

clearly visible by the number of participants.

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

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

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

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Any assumptions that are not stated in the question are most likely false

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hate those 5-task contests D:

PermutationForces <3

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

Problems A and B were shit

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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 years ago, # |
  Vote: I like it +33 Vote: I do not like it

First 4 pblms could hv made a good leetcode contest.

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve D?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    • 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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

    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 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it
  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the observation for C?

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

    Tree is binary, so after each step only one new vertex can be infected.

»
2 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    How?

    For e.g

    3
    2 4 16

    I don't see a way to do this in less than 3 operations, unless i'm missing something?

»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

E is a mastapiece!

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it -39 Vote: I do not like it

    *masterpiece

    Edit:- Is this site full of psychopaths. Downvoting my comment for no offensive reason.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you say for what case it fails?

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

      Oops, missed this line "no character is contained in both strings". Nvm, tests are strong.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +64 Vote: I do not like it

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

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

    hint?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    I solved that problem with DP. Maybe, computing DP with more than 2 edges would be more difficult for users unfamiliar with such problems.

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

    I guess it's because we can solve it without using dp in the case of binary tree.

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

    And the official solution even uses DP. Great!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it -15 Vote: I do not like it

LOL i solved C using bfs

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

    More details please?

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

      It's always optimal to delete node that directly connected to infected node so at the end all infected nodes will be in path of last infected node to root(last infected node will have 2 or 1 neighbours). So we need to find node that have minimum length of path to root and have 2 or 1 neighbour which can be done using even dfs!https://codeforces.net/blog/entry/103471?#comment-921116

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks for the fast editorial !

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    If you mean larger subtree.

    Yes
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There can't be the same character in both strings bruh

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 3   Vote: I like it -17 Vote: I do not like it

[DELETED]

»
2 years ago, # |
Rev. 2   Vote: I like it -44 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it -52 Vote: I do not like it

    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 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Masterpiece