### wxhtzdy's blog

By wxhtzdy, history, 2 months ago,

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 months ago, # |   +51 Why only one div2 tester?!
•  » » 2 months ago, # ^ | ← Rev. 2 →   +9 And also I am wondering how has a cheater become a tester!
•  » » » 2 months ago, # ^ | ← 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 months ago, # ^ |   +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 months ago, # ^ |   +122 Serbian Competitive Programming Lore
•  » » » » » 2 months ago, # ^ |   +26 Why didn't you tell this after GR19?
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +17 MikeMirzayanov please look into this
•  » » » » » 2 months ago, # ^ |   +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 months ago, # ^ |   +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 nohaxjustsoflo 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 months ago, # ^ |   -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 months ago, # ^ |   +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 months ago, # ^ |   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 months ago, # ^ |   +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 months ago, # ^ |   +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 months ago, # ^ |   +18 .
•  » » » » » » » 2 months ago, # ^ |   +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 months ago, # ^ |   -26 Ayy man, not gonna waste much time here but
•  » » » » » » » » » 2 months ago, # ^ |   -23 Not my opinion its fax
•  » » » » » » » » 2 months ago, # ^ |   +2 Regarding school not being public info, everything posted on the internet stays there forever and you should be aware of it.Archive.org showing his school
•  » » » » » » » 2 months ago, # ^ |   -19 I love how wxhtzdy is maybe doing cp to perform better next time while you are spending time on this
•  » » » » » » » » 2 months ago, # ^ |   -8 now that's what we call a perfect way to end the conversation
•  » » » » » 2 months ago, # ^ |   0 false, wxhtzdy is next tourist
•  » » » » » » 2 months ago, # ^ |   +1 imagine becoming the next tourist without even participating in rated contests.
•  » » » » » » » 2 months ago, # ^ |   +5 I believe that will change as well
•  » » » » » 2 months ago, # ^ |   -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 months ago, # ^ |   -10 Lol, why are they down voting? You made valid points.
•  » » » » 2 months ago, # ^ |   0 BlameForces
•  » » » » 2 months ago, # ^ | ← 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 months ago, # ^ |   +22 I'm not a cheater, I'm a Serb (most stronkest)
•  » » » » 2 months ago, # ^ |   +5 I meant Sarvesh10
•  » » » » » 2 months ago, # ^ |   +16 no no, too late, you are going to Serbia now
•  » » » » 2 months ago, # ^ |   -22 there is a saying in romanian Cine se scuza se acuza. (dar chiar asa, cine?)
•  » » » » » 2 months ago, # ^ |   0 janes romanes?
 » 2 months ago, # |   +35 Excited to participate in this one. I hope for some nice problems.
 » 2 months ago, # |   +13 Thanks for the early Score Distribution!!
 » 2 months ago, # |   +15 If any of the problem setters require a tester they can message me :)
•  » » 2 months ago, # ^ |   +12 +1, If you need a cyan tester, please ping me :)
•  » » 2 months ago, # ^ |   +2 Yeah, if you are interested and don't think I am too weak,you can ping me too:)
•  » » 2 months ago, # ^ |   0 +1 Im also excited to try testing
•  » » 2 months ago, # ^ |   +1 Yeah I am interested too. It will be gonna learning and fun.
 » 2 months ago, # |   +55 5 problems what's this 2017?
•  » » 2 months ago, # ^ |   +29 I think it's better to have 5 instead of 6 problems for Div2 participants
•  » » » 2 months ago, # ^ |   +1 +. I really enjoy when there are less problems, but they are harder overalls.
•  » » » » 2 months ago, # ^ |   +5 They weren't harder this time though. Or maybe were in the start(like AB), but much easier in the end(DE).
•  » » » » » 2 months ago, # ^ |   0 Kind of. I still wanna kick myself for not solving D this time.
•  » » 2 months ago, # ^ |   0 5 problems contest is not that uncommon.
 » 2 months ago, # |   +13 I'm genuinely curious about how testers are selected for each round?
•  » » 2 months ago, # ^ |   -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 months ago, # |   +12 It sounds a very good contest! score distribution came quickly this time !!
 » 2 months ago, # |   0 22:05 UTC+5.5 is the best time i feel to participate in a contest. any supporters out there!!
•  » » 2 months ago, # ^ |   0 Night owls! There we go... xD
•  » » 2 months ago, # ^ |   -12 Yeah, giving contest with a cup of coffee just feels so good
 » 2 months ago, # |   +12 22.35 is unfriendly to Chinese college students, and 0.35 is even more so.
•  » » 2 months ago, # ^ |   0 and cet exam......
 » 2 months ago, # |   0 seems like it's gonna be speed forces!!!!
 » 2 months ago, # |   0 Welp, good luck everyone
 » 2 months ago, # |   +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 months ago, # ^ | ← Rev. 2 →   +21 Downvoted you because you are being scammed
 » 2 months ago, # |   0 Please notice the unusual time .............
 » 2 months ago, # | ← Rev. 5 →   -14 meme
 » 2 months ago, # |   +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 months ago, # ^ |   +33 100% agree
•  » » 2 months ago, # ^ |   +7 bestest comment
•  » » 2 months ago, # ^ |   -27 NO, ALBANIA IS THE BËST AND STRONKËST ÇOUNTRY IN THË WÖRLD beÇAUSË OF THË MIGHTY ILLYRIAN PËOPLË!!!!
 » 2 months ago, # |   0 Greedy Score Distribution!
 » 2 months ago, # |   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 months ago, # ^ |   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 months ago, # ^ |   +2 Here is a mashup for DP https://codeforces.com/gym/302977
•  » » » 2 months ago, # ^ |   0 not allowed
•  » » » » 2 months ago, # ^ |   0 Yes my bad, invitation is needed. Here: https://codeforces.com/contestInvitation/dbdc3d98d7378b34a4a47114864882815a7669e9
 » 2 months ago, # |   +3 Let's see if we can tackle D this time !!
 » 2 months ago, # |   +9 I hope to reach an expert rating in this contest :)
•  » » 2 months ago, # ^ |   +2 Good luck!
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Thanks bro
•  » » 2 months ago, # ^ |   0 I hope so
 » 2 months ago, # |   0 Hope to again become specialist in this conrest
•  » » 2 months ago, # ^ |   0 By Speedforcing A,B,C without any penalties. Ez
 » 2 months ago, # |   0 ** Please notice the unusual time **
 » 2 months ago, # |   0 TerryWang Orz
 » 2 months ago, # |   0 hope I don't enter "Farsh Mode"
•  » » 7 weeks ago, # ^ |   0 lol
 » 2 months ago, # |   0 If only the rounds were held before 13:00 utc, with the UTC + 8 time zone, it remains either to go to bed after 12, or to participate only virtually.
 » 2 months ago, # |   +95 lol cheaters authoring cf rounds and mike doesn't remove itclown world never ends
•  » » 2 months ago, # ^ |   -9 Cheatforces
 » 2 months ago, # |   +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 months ago, # ^ |   +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 months ago, # ^ |   +19 In 'friends' section in participants you can also find yourself easier.
•  » » » » 2 months ago, # ^ |   +20 loll am dumb.. thanks a lot!!!
 » 2 months ago, # |   +16 Eagerly waiting for the contest. Hope to see some nice problems. Guys note that the timing is 2hr late than usual.
 » 2 months ago, # |   +24 Eagerly waiting to lose expert
•  » » 2 months ago, # ^ |   +12 Best of Luck :)
•  » » 2 months ago, # ^ |   +6 successful
 » 2 months ago, # |   +9 Hoping to solve two problems today. Fingers crossed.
•  » » 2 months ago, # ^ |   +8 same 1 to 2 problems :)
•  » » » 2 months ago, # ^ |   +3 Good luck you both!
•  » » » » 2 months ago, # ^ |   +8 You too :) Good luck
•  » » » » 2 months ago, # ^ |   0 thanks, you too.
 » 2 months ago, # |   0 i am not able to enter in contest.
•  » » 2 months ago, # ^ |   0 Don't worry. You are already registered. (see this comment)
 » 2 months ago, # |   +3 Good Luck Everyone :)
 » 2 months ago, # |   0 It's my first experience of participating in the contest at CF. Good luck!
 » 2 months ago, # |   +8 Hope to become Blue today.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 Keep faith bro whole community is with you.
•  » » » 2 months ago, # ^ |   -16 I am not. I give 0 Fs about mine and everyone's rating
 » 2 months ago, # |   0 Guys, I am not able to register. Am I not eligible or something?
•  » » 2 months ago, # ^ | ← 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 months ago, # ^ |   0 Oh, thank you so much. I didn't know this :)
 » 2 months ago, # |   +11 Thanks for such an easy A :)
 » 2 months ago, # |   +6 Hated it.clearly visible by the number of participants.
•  » » 2 months ago, # ^ |   0 can any one tell me what is diference between educational and div 2 round ?
•  » » » 2 months ago, # ^ | ← 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 months ago, # |   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 months ago, # ^ |   +1 Any assumptions that are not stated in the question are most likely false
 » 2 months ago, # | ← Rev. 2 →   0 Literal chills :_) Great contest btw (and I mean it in a sarcastic way)
 » 2 months ago, # |   0 Hate those 5-task contests D:PermutationForces <3
 » 2 months ago, # | ← Rev. 3 →   0 Problems A and B were shit
 » 2 months ago, # |   +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 months ago, # ^ |   0 my submissions got skipped .. and I didnt even know the peoplw with whom my solution is matching . waht to do? please help!
 » 2 months ago, # |   +33 First 4 pblms could hv made a good leetcode contest.
•  » » 2 months ago, # ^ |   +1 Disagree!
 » 2 months ago, # |   +9 How to solve D?
•  » » 2 months ago, # ^ |   +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 months ago, # ^ |   +1 Very practical idea, thank you.
•  » » 2 months ago, # ^ |   +18
•  » » » 2 months ago, # ^ |   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 months ago, # ^ |   +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 months ago, # ^ |   0 Oh, very cool, thanks. Didn't know about that trick.
•  » » » 2 months ago, # ^ |   0 I also thought of the same idea but was struggling in its implementation :( Read Editorial and its solution is also quite good.
•  » » 2 months ago, # ^ |   +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 months ago, # ^ | ← Rev. 2 →   +5
•  » » 2 months ago, # ^ | ← 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 months ago, # |   0 What was the observation for C?
•  » » 2 months ago, # ^ |   +1 Tree is binary, so after each step only one new vertex can be infected.
 » 2 months ago, # | ← Rev. 2 →   +8 D was very similar to 1658E - Годзё и игра на матрице. In fact I solved it by reading the editorial for that problem.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +9 I'd say more similar to this
 » 2 months ago, # |   +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 months ago, # ^ | ← Rev. 2 →   0 How? For e.g3 2 4 16I don't see a way to do this in less than 3 operations, unless i'm missing something?
•  » » » 2 months ago, # ^ |   0 Decrement 16. 15&4>0, 15&2>0
•  » » » » 2 months ago, # ^ |   0 thank you :)
 » 2 months ago, # |   +25 E is a mastapiece!
•  » » 2 months ago, # ^ | ← Rev. 3 →   -39 *masterpieceEdit:- Is this site full of psychopaths. Downvoting my comment for no offensive reason.
 » 2 months ago, # |   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 months ago, # ^ |   +1 Either I save my left child or my right child. WLOG assume it is left childthen 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 months ago, # ^ |   0 Thanks
•  » » 2 months ago, # ^ |   0 The greedy approach you mentioned fails!. Consider14 1 2 2 3 3 4 4 5 4 6 3 7 2 8 1 9 9 10 9 11 10 12 11 13 11 14 
 » 2 months ago, # |   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 months ago, # |   0 Anyone runtime error in problem C. This is my solution couldn't figure out why it is getting runtime error.
 » 2 months ago, # | ← 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 months ago, # ^ |   0 Can you say for what case it fails?
•  » » » 2 months ago, # ^ |   0 Oops, missed this line "no character is contained in both strings". Nvm, tests are strong.
•  » » » » 2 months ago, # ^ |   0 Okay cool.
 » 2 months ago, # |   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 months ago, # ^ |   0 cache results for each quadrant and pick max. probably this will MLE...160126114
 » 2 months ago, # |   0 BruteForces moment
 » 2 months ago, # |   +64 What is the purpose of making the tree in C binary lmao
•  » » 2 months ago, # ^ |   0 hint?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +4 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 months ago, # ^ |   0 I guess it's because we can solve it without using dp in the case of binary tree.
•  » » 2 months ago, # ^ |   0 And the official solution even uses DP. Great!
 » 2 months ago, # |   0 can anybody tell me which test case i'm failing for C solution
 » 2 months ago, # |   0 someone pls find failing testcase for problem C https://codeforces.com/contest/1689/submission/160135619
 » 2 months ago, # |   0 Problem D is plain boring, Just write 4 loops and make sure you copy paste right in other 3.
 » 2 months ago, # |   +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: SpoilerAll the 0's must be evidently turned into at least 1's. Then, we can do at most 2 operations and we will have a connected graph. How?First case: the graph is already connected. great.Second case: there are multiple connected components, all but one having in their componence a node that contains 1 (and therefore there are two components, as a sidebar) Then, we can take the lonely component and add 1 to whatever node we want. This won't ruin any edges, as the first component isn't changed, and the latter didn't have any 1 bits, so there will not be a case as such, where $0b111$ is added 1 and becomed $0b1000$, destroying formed edges.Third-ish case: there is a value with maximal LSB, from which we can decrement 1. We choose this node as to be the one with the maximal number of edges towards all the others (as a sidebar, the selection of this node would be most optimal when it connects to all the other values, because by the maximality of the LSB there can't be any weird stuff).From this point, we are sure to be connected to almost all nodes, except those that had the same LSB as the decremented value, moreover the continuation is completely identical to cases I and II. Then, if we need, we can take any of the nodes in the component that contains all the nodes with the maximal LSB (if those are disconnected from the rest of the nodes), and add 1 to them, as to connect it to the decremented value-- The main idea is that from subtracting 1 from a node with maximal LSB, we are then sure to connect to all the nodes with LSB lower than that of the aforementioned.I do admit, I may have not been perfectly coherent. I leave, thus, my source code from during the contest, as I hope it could alleviate some potential misunderstandings unaddressed in my redaction of my solution to those kind enough to review my work, or maybe some would find some bugs that make the code stray away from my described solution.
•  » » 2 months ago, # ^ |   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 months ago, # ^ |   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 months ago, # ^ |   0 Pretest 15 was the only pretest which needed 2 non-trivial operations.
 » 2 months ago, # |   -15 LOL i solved C using bfs
•  » » 2 months ago, # ^ |   0 More details please?
•  » » » 2 months ago, # ^ | ← Rev. 5 →   0 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.com/blog/entry/103471?#comment-921116
 » 2 months ago, # |   +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 months ago, # |   +2 Thanks for the fast editorial !
 » 2 months ago, # |   0 I solved A,B within 12 minutes and passed, tried D but no luck. Can I become specialist today ?
•  » » 2 months ago, # ^ |   0 yes, you will
•  » » 2 months ago, # ^ |   +4 Congratulations!!! You became a specialist !
 » 2 months ago, # |   0 https://codeforces.com/contest/1689/submission/160132878 Can someone please explain to me why do i get runtime error in this submission of C? Thank you.
•  » » 2 months ago, # ^ |   0 Its the recursion limit exceeded
•  » » » 2 months ago, # ^ |   0 Thank you for a hint. But why does it go through this limit in my solution?
 » 2 months ago, # | ← 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 months ago, # ^ |   +1 If you mean larger subtree. Yes14 1 2 2 3 3 4 4 5 4 6 3 7 2 8 1 9 9 10 9 11 10 12 11 13 11 14  Deleting 2 (node with larger subtree) -> 8 Deleting 9 (node with smaller subtree) -> 9 
•  » » » 2 months ago, # ^ |   0 Thanks for the example. Understood
 » 2 months ago, # |   0 There was a mail from the system saying that I've copied problem A and problem B. But i haven't neither I've shared my code to anyone. The people that were mentioned who have the same code... I don't even know them. I've written my code on visual Studio. This is very disappointing .Please give me ratings for this contest
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 same here, i also coded in my local ide, and not copied from anywhere....
 » 2 months ago, # |   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 months ago, # ^ |   0 Read the question carefully, its given that a character cannot appear in both the strings so your input is invalid (as 'b' appears in both the strings)
•  » » » 2 months ago, # ^ |   0 oh, got it... silly me XD.
•  » » 2 months ago, # ^ |   0 There can't be the same character in both strings bruh
 » 2 months ago, # |   0 Why do the latest 5-problem Div2s all have their C problem about trees?
 » 2 months ago, # |   0 Who else got Runtime Error on Test 10 for C using python at least once during the contest ?
 » 2 months ago, # | ← 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 months ago, # |   0 my submissions got skipped and i didnt cheated .. what to do?
 » 2 months ago, # | ← Rev. 2 →   0 I thought problem C was a greedy problem. If root has one child, then deleting this child won't spread infection anymore, so the ans is n-2. If there are two children then 1. both the children 2. [the child with less children] of nodes from (1) will be deleted, so the ans is n-3- min(root_child_1.size()-1, root_child_2.size()-1). What am I doing wrong here? If anyone can help, it would be great. my submission link here
•  » » 2 months ago, # ^ |   -8 N-3+ min(..)
 » 2 months ago, # |   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.com/contest/1689/submission/160160596
•  » » 2 months ago, # ^ |   0 Edges are bidirectional as per question.
 » 2 months ago, # | ← Rev. 2 →   -17 .
•  » » 2 months ago, # ^ | ← Rev. 2 →   -26 .
 » 2 months ago, # | ← 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.