Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### Stepavly's blog

By Stepavly, history, 9 months ago, translation,

Happy New Year, Codeforces!

UPD: We have received such different opinions about the order of problems, that we cannot be completely sure about it. We recommend you to read all the problems and do not strongly hope that the difficulty for you necessarily coincides with the order in the round.

<almost-copy-pasted-part>

Hello! Codeforces Round #693 (Div. 3) will start at Jan/04/2021 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. We tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

The problems for this round were invented by MikeMirzayanov and prepared by Supermagzzz and Stepavly

Thanks to MikeMirzayanov for platforms and coordination of our work. Thanks to darkkcyan, Aris_244_, Mukundan314, PrideBlack, Nemo, pashka, Rox for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

UPD: Editorial

• +413

 » 9 months ago, # |   +83 Is this the first Div. 3 contest announcement by a "newbie"?
•  » » 9 months ago, # ^ |   +40 newbie with 2165 rating, now everyone wants to be newbie with this rating.
•  » » » 9 months ago, # ^ |   +10 except for whom his rating is above 2165
•  » » » » 9 months ago, # ^ |   +2 Great!! Edge cases are important :}
•  » » 9 months ago, # ^ |   +5 I hope i reach this new newbie level .
 » 9 months ago, # |   +63 New Year Magic -- Newbie arrange a contest for LGM....xD.
•  » » 9 months ago, # ^ |   +11 I literally thought he is a newbie....xD
•  » » » 9 months ago, # ^ |   +19 LGM's gonna have hard time solving newbies problem... XD
 » 9 months ago, # |   +15 Seems no tester will ask to give him contribution for this contest.
•  » » 9 months ago, # ^ |   +61 Actually, as a tester...
 » 9 months ago, # |   +29 No Hello 2021 this time?
•  » » 9 months ago, # ^ |   +10 Very Unlikely as first contest is hello and is not scheduled yet and a div3 after 2 days which makes it nearly impossible.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +44 This round will be in New Year's style. This isn't Hello 2021, but we hope you will enjoy it!
•  » » » 9 months ago, # ^ |   -14 New Year is celebrating the fact that the earth orbited the sun an integer number of times since an arbitrary day...
 » 9 months ago, # |   +4 Missing vovuh
 » 9 months ago, # |   +3 Happy New Year Codeforces! <3
•  » » 9 months ago, # ^ |   +3 I will participate as an International Master XD what an irony :v
 » 9 months ago, # | ← Rev. 2 →   +14 Thanks a lot to Supermagzzz and Stepavly for preparing the div. 3rd competition.
 » 9 months ago, # |   -62 As a LGM, Give me some contribution!!.
•  » » 9 months ago, # ^ |   +51 I think you need some rating as an LGM.
 » 9 months ago, # |   +1 pog
 » 9 months ago, # |   +8 Div 3 will flood LGM xDDDD
 » 9 months ago, # |   +23 meme
 » 9 months ago, # | ← Rev. 3 →   0 this blog proves that upvotes are given on the basis of rating mainly!blog was written 92 minutes ago and still only 63 upvotes xD
 » 9 months ago, # |   +5 If I change my rank to Pupil can I participate?
 » 9 months ago, # |   0 Coders on "pupil" can also take part in Div 1 !!???ILLUSION 100 XD
 » 9 months ago, # | ← Rev. 2 →   0 Count of LGMS participating officially in Div3 will be more than that of pupils and newbies xd
•  » » 9 months ago, # ^ |   +1 edit: **Count of LGMs
•  » » » 9 months ago, # ^ |   +4 Please focus on making a new season of prison break :P
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   0
 » 9 months ago, # |   -6 Why is only one Div 3 conducted in a month? I feel for beginners at least 2-3 Div. 3 Should be conducted for Practice. [Just a Suggestions]..
•  » » 9 months ago, # ^ |   +2 do them
•  » » 9 months ago, # ^ |   0 It's not easy to make Div 3's. Problems should be interesting as well as beginner friendly. If you want more beginner friendly contests, do all ABC's.
•  » » » 9 months ago, # ^ |   +4 I tried solving ABC's but it's hard to find Editorials of past Contests since mostly they are written in Japanese. For Recent Contests, it's available, even If I try asking here on CF instead of helping me people just downvote me. That's why I was asking for a few more Div 3. Since 4-5 Div. 2 are also happening every month and their Questions are also Unique in the same way at least 2 Div. 3 Should also be conducted for Practice. because Editorials are available and more number of People Give Codeforces Contests so It's easy to discuss with them after the contest.
•  » » » » 9 months ago, # ^ |   +3 ABC blog comments are more than enough to understand and solve all problems. Don't put in your own comment if it's not a genuine query. There are multiple comments explaining all problem solutions already. Also dont ask people to debug. figure it out on your own. you won't be downvoted otherwise. as for Div2's, they are prepared by various authors. but Div3's are only prepared by a handful of people and that is not likely to change.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Agreed but if you want to practice more Div 3 like contests you can always go to other platforms such as AtCoder. Easier contests are conducted more frequently there.
 » 9 months ago, # |   +8 Meow hopes that he gets some positive delta this contest :3
•  » » 9 months ago, # ^ |   0 +50 delta for everyone who participates... lol!!
•  » » » 9 months ago, # ^ |   0 I hope me and u get more that +50
 » 9 months ago, # |   -7 A VERY GOOD PROBLEM(C) ON CONSTRUCTIVE ALGORITHMS. LINK : https://www.youtube.com/watch?v=lZplaUOpPnk HOPE YOU GUYS WILL ENJOY THIS EXPLANATION VIDEO !!!
 » 9 months ago, # |   -13 wow 7 problems on a div3, this is gonna be interesting :))
 » 9 months ago, # |   0 As an expert, give me contribution
•  » » 9 months ago, # ^ |   0 are you talking for negative contribution?
•  » » 9 months ago, # ^ |   +10 contribution is yours mr.expert
•  » » 9 months ago, # ^ |   0 Where is EVA?
•  » » » 9 months ago, # ^ |   0 i have changed my handle because i do it every year
 » 9 months ago, # |   -6 will we have any extra rating rise as a new year gift? jk XD !!
 » 9 months ago, # |   +11 Codeforces Please fix the problem of rendering as Unable to parse markup [type=CF_MATHJAX]\$ Unable to parse markup [type=CF_MATHJAX]instead of real data in Questions after update or maintenance you made today between 0:05 to 4:05. All question are showing Unable to parse markup [type=CF_MATHJAX]$instead of data .  » 9 months ago, # | -8  » 9 months ago, # | -15 is this contest rated for me? •  » » 9 months ago, # ^ | 0 yes  » 9 months ago, # | -6 For some time, I thought it's an unofficial announcement. •  » » 9 months ago, # ^ | 0 But why? •  » » » 9 months ago, # ^ | -7 Because the post is written by newbie.  » 9 months ago, # | 0 For a moment, I was like "oh my god did vovuh changed his handle..." and then I saw vovuh on the top contributor list. sigh of relief...  » 9 months ago, # | 0 The first div.3 contest(and also the first contest) of the year! I hope the this contest will have good problems and strong tests. Good luck to everyone in codeforces! XD  » 9 months ago, # | +6 Hoping for less plagiarism this year cheers!  » 9 months ago, # | -7 My first contest as LGM  » 9 months ago, # | 0 I hope you guys enjoy the first 2021 Codeforces contest. Good luck!  » 9 months ago, # | 0 What can be more satisfying than starting 2021 with a Div 3.Happy New Year Codeforces  » 9 months ago, # | 0 Magic is very good, we can be master for a few daysThanks to CodeForces  » 9 months ago, # | -12 hope to become pupil soon as a Legendary GrandMaster  » 9 months ago, # | -15 Happy New the Contest !! 1st contest of 2021 is for the the beginners of the programming world  » 9 months ago, # | ← Rev. 2 → +3 I love it when div 3 contests are unrated for me. I wait for the day when I could say the same for div. 2 contests :)  » 9 months ago, # | +36 As a tester, please give me the problem setters contributions. They have done a great job preparing fun, yet challenging problems! I highly recommend reading all problems ;)  » 9 months ago, # | 0 div.3 is more comfortable contest.  » 9 months ago, # | -27 as a grandmaster, I won't participate in this contest . . . so Newbies can improve their rankings (lmao . . . happy new year) •  » » 9 months ago, # ^ | 0 hmm, Legendary GM!! •  » » » 9 months ago, # ^ | -17 yes ... that's right legendary grand master :] •  » » » » 9 months ago, # ^ | 0 You can only participate in Div-1 lol!! •  » » 9 months ago, # ^ | 0 18 down votes? wow that was only a joke guys take it easy  » 9 months ago, # | +3 this contest will be div 3 so does this means there will be more cheating in this contest than the previous one, are measures taken regarding plagiarism?  » 9 months ago, # | +3 First contest of the year! And first ever unrated official contest for me!  » 9 months ago, # | 0 I think that codeforces will arrange happy new year contest but starting by div 3!!!  » 9 months ago, # | +11 For anyone interested, I'll be doing a post-contest stream on Twitch. •  » » 9 months ago, # ^ | 0 Hey man! Any reason for choosing Twitch over YouTube? •  » » » 9 months ago, # ^ | +3 My impression is that Twitch is "streaming-first", but I don't really know haha, I just picked one. I do upload all my past broadcasts to my YouTube, though, if you'd like to watch there. •  » » » » 9 months ago, # ^ | 0 I do watch them on YouTube! You have great content. Twitch has this reward system that does not allow everyone to request problems. Maybe YouTube has it too? Anyway, overtime I will gather points to ask. All the best!  » 9 months ago, # | 0 Thanks a lot to Supermagzzz and Stepavly for preparing the div. 3rd competition.  » 9 months ago, # | ← Rev. 2 → -33 What does it mean by this? anonymous pictures website  » 9 months ago, # | 0 Since almost half of the players are cheaters in almost every cf/cc contest as it is revealed. so if you feel sad due to poor performance then be happy with your performance as you are not the cheater and assuming you original rank as current rank/2 xd.  » 9 months ago, # | +2 2021 be like: Newbie makes div3 for Legendary Grossmaster.  » 9 months ago, # | 0 Newbie has made div3 for Legendary Grandmaster. lol ;)  » 9 months ago, # | +2 can i take part in thí contest ?? i'm newbie. •  » » 9 months ago, # ^ | +1 Yes, everyone with a rating less than 1600 can take part in DIV3 contests  » 9 months ago, # | 0 Tomorrow is my birthday. I will try to be green on the basis of the results of Codeforces Round #693(Div3) . •  » » 9 months ago, # ^ | +1 happy (early) birthday bro  » 9 months ago, # | 0 can anyone explain the algorithm of how this rank masquerade thing is working ? is it assigning lower positions to people higher than the position rating or vice versa as well? just asking . xD •  » » 9 months ago, # ^ | ← Rev. 2 → 0 I guess everyone is chosing a colour that they have never got/think they can't achieve unless they perform abnormally :P •  » » » 8 months ago, # ^ | 0 yaa this might be true. xD  » 9 months ago, # | 0 I'm an expert coder! •  » » 9 months ago, # ^ | 0 haq!  » 9 months ago, # | +1 everyone has dream to become Legendary Grandmaster  » 9 months ago, # | 0 Anyone from react-native background here? •  » » 9 months ago, # ^ | 0 Yeah  » 9 months ago, # | +2 Hello guys happy new year. New Year new me and now i am PUPIL so for the new year resolution i will no longer post troll comments and will become red coder in 2021.  » 9 months ago, # | ← Rev. 3 → +46 Message the from writers: We have received such different opinions about the order of problems, that we cannot be completely sure about it. We recommend you to read all the problems and do not strongly hope that the difficulty for you necessarily coincides with the order in the round. Сообщение от авторов: Мы получили настолько противоречивые мнения о порядке задач, что не можем быть полностью уверенными в нём. Рекомендуем прочитать все задачи и не сильно надеяться, что сложность лично для вас обязательно совпадёт с порядком в раунде. •  » » 9 months ago, # ^ | 0 I think you should put this message in the announcement •  » » » 9 months ago, # ^ | +6 This message is already in the announcement :)  » 9 months ago, # | +13 The best way to do good in DIV 3 is to think like DIV 3..  » 9 months ago, # | +15 What happened to Hello 2021? •  » » 9 months ago, # ^ | 0 I believe 2020 got it....Mission failed, Get em next time...  » 9 months ago, # | 0 One Piece touched 1000 I want to too. (All hail future pirate king)  » 9 months ago, # | +6 Such a nice contest with excellent problems!Though problems where a bit on the easy side.  » 9 months ago, # | 0 Enjoyed it  » 9 months ago, # | 0 (AFTER CONTEST) How to solve E? I tried Binary Search but it had some problem, maybe implementation,I don't Know. •  » » 9 months ago, # ^ | 0 Binary Search + Segment Tree (My solution is probably overkill) •  » » » 9 months ago, # ^ | 0 Why simple Binary Search won't give optimal solution? •  » » » 9 months ago, # ^ | 0 I just used sorting + two pointer •  » » 9 months ago, # ^ | ← Rev. 2 → 0 I sorted the input by pair . For first case where$h_j
•  » » » 9 months ago, # ^ |   0 I had same approach. Some implementation problem must be there.
•  » » » » 9 months ago, # ^ |   0 your code is giving TLE on my computer on test 1 2 10 2 1 9 .You can use that to debug .
•  » » » » » 9 months ago, # ^ |   0 ya that might be the case as well. but on submitting it showed WA on test 2
•  » » » 9 months ago, # ^ |   +8 I sorted by pair because basically width and height could be exchanged as per the problem. Made the implementation very easy
•  » » 9 months ago, # ^ |   0 E has some serious implementation complexity.Let's say we first consider the case of both in same orientation (both standing or both lying on the side). Just sort the array of pairs(height, width) by height. Now, suppose you want to find the answer for ith index. Then find the last index say j before i such that height of j is < height[i].first (c++ array of pairs). If there exists such a j then its possible range will be [0, i-1]. Also, keep another array of minw of pairs which will contain minimum width of the sorted height array till ith index and the index of the minimum width found. Now, the answer will be minw[j].second. Another implementation detail. You need to keep the original indices preserved somehow since those will be changed when you will sort.Now, do this again with different orientation.I could come up with this only and it works fine but it is too heavy on implementation.
•  » » » 9 months ago, # ^ |   0 You can solve E with 1 Fenwick Tree easily
•  » » » 9 months ago, # ^ |   0 For every entry, keep three things : 1. x: min(height, width), 2. y: max(height, width), 3. z: original index. Now sort them with x and start from left, when you go to right, you are guaranteed that the x will only be increasing so you can always get lesser x in left, to find the lesser y, keep track of the lowest y you have seen so far. If current y is greater than the lowest you've seen so far, then its impossible case.
•  » » 9 months ago, # ^ |   +9 sorting + one variable to hold current minima
 » 9 months ago, # |   0 What is test 2 of Problem E?
•  » » 9 months ago, # ^ | ← Rev. 2 →   -10 Sorry for being rude. I didn't meant that :(
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +1 Actually, to the contrary, I think I'm reasonably close, otherwise I wouldn't be asking :)This is similar to a problem that I've seen before so it's likely my implementation has a bug.
•  » » » 9 months ago, # ^ |   +2 A person who has been expert in the past can solve most Div.3 E. So, i don't think there is any flex here.
•  » » » 9 months ago, # ^ |   0 You are not correct. For example my solution for G when i submitted first give WA on test 2 but after i saw my mistake and got AC
•  » » 9 months ago, # ^ | ← Rev. 4 →   +4 Your code is failing on following test : 1210 21 9output should be 2 -1 whereas your code gives -1 -1 . Infact i had very silly implementation mistake due to which i was failing in same test . I Fixed that error during contest .Also Ozymandias_Orz please don't spam comment section by being rude to others (especially to those who are asking genuine help)
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +3 Appreciate this. I see what my bug is — I should've rotated my height and width in cases where height > width, and then sorted. I believe the rest of my implementation is likely ok, so this was my oversight. Yup, that was it. Passed sys tests with this change.
 » 9 months ago, # |   +1 Problem D reminded me of Leetcode — Stone Game VI
 » 9 months ago, # |   0 I am kind of a noob to this so go easy, and this was my first legit competition, but for the time limit it says 2s and when I submitted I got a time limit error and it said it took 2000ms? Does Codeforces record your time if it goes over the limit?
•  » » 9 months ago, # ^ |   0 No, it shows the time as the max allowed time and shows TLE verdict.
•  » » 9 months ago, # ^ |   0 No when you exceed the limit program stops and terminates TLE
 » 9 months ago, # |   0 How to solve Problem C without using DP ?
•  » » 9 months ago, # ^ |   0 check out my solution. I used vector dp like a history. It has nothing to deal with dp, I was lazy to rename it after going out of dp So my idea was that if we go from ai to aj so we don't need to calculate situation where we go from ak to aj and k > i. Because we'll get a smaller number anyway. So we put every calculation of aj in dp vector and check if we've already calculated ithttps://codeforces.com/contest/1472/submission/103281636
 » 9 months ago, # |   0 How to solve B?
•  » » 9 months ago, # ^ |   0 N^3 worked for me If totalsum is odd its NO Else checked if currsum can be totalsum/2
•  » » 9 months ago, # ^ |   0 say you have cnt_1 1s and cnt_2 2s. pick x 1s (out of cnt_1) and pick y 2s (out of cnt_2). If there is some combination such that x + y * 2 == (cnt_1 - x) + (cnt_2 - y) * 2, then you can distribute candies in a way that both Alice and Bob have equal total weight.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Its Subset sum problem(DP). Although , People solved it greedily too.
•  » » » 9 months ago, # ^ |   0 Well well can you share your idea.
•  » » » 9 months ago, # ^ |   0 Dynamic Programming for div3 B? It's just two if statements after counting no of one and twos103202827
 » 9 months ago, # |   +1 Problem E was simple Fenwick Tree implementation
•  » » 9 months ago, # ^ |   +5 Or just sorting :) I recommend you to read the editorial
•  » » 9 months ago, # ^ |   0 Can you Explain ??
 » 9 months ago, # |   0 yet again I couldn't solve any problem and it's div.3. I am amazed by my dumbness. shame on me :(
•  » » 9 months ago, # ^ |   0 Don't lose hope. I went through this in 2 contests. So no worries and don't feel bad and pity on yourself.Just remember to do these things for sure till next div 3 round. 1. Attend all the contests till next div 3 round. 2. Upsolve all the problems using editorial after contests no matter how advanced the topic is. 3. Devote atleast 4-5 hrs daily on problem solving and aim to solve 2-3 problems within that time that are above your current rating level.And today I got A, B, C and D Accepted during the contest and E had some implementation difficulty but I cracked the logic.
•  » » » 9 months ago, # ^ |   0 So you're telling me to solve(upsolve) A,B,C,D,E,F in all contests? but I don't think I would do that after c.
•  » » » » 9 months ago, # ^ |   0 Well making progress in CP isn't that easy. You gotta put in some more effort to achieve quick results. Also, maybe for now you can skip E and F and instead do some more B and C or even consider virtual contests for practice.
 » 9 months ago, # |   0 I could only solve 3 problems, too bad for a student
 » 9 months ago, # |   0 when the editorial is published
 » 9 months ago, # |   0 I really liked the problem set. Thank you for the contest.
 » 9 months ago, # |   +1 Can Someone Explain, How to solve E using Fenwick Tree ????
 » 9 months ago, # |   +6 Is rank predictor broken?
•  » » 9 months ago, # ^ |   0 Why do you think so?Obviously, the ratings will be updated only after the hacking phase is finished. In general also for contests without any hacking phase, ratings are updated anytime within 24 hrs.
•  » » » 9 months ago, # ^ |   +2 Actually, he said about the cf-predictor site where rank prediction were given before the official rank update.
•  » » » 9 months ago, # ^ |   0 rank predictor refers to https://chrome.google.com/webstore/detail/cf-predictor/ocfloejijfhhkkdmheodbaanephbnfhn?hl=en (or something similar), when I use it it shows the predicted rating assuming no more changes (no more submissions or hacks), that's why it's called a predictor
 » 9 months ago, # |   0 Problem B is same as Codeforces Round 248 — A. Kitahara Haruki's Gift
•  » » 9 months ago, # ^ |   0 Wanna find more similar than this ?Go check out this 416. Partition Equal Subset Sum — Leetcode.
 » 9 months ago, # |   +25 IMO problem F is really cool, at-least for me, cuz I solved it using $DP$ and compressing the $2 \times n$ grid: an even distance between two blocks is equivalent to them being adjacent, and an odd distance is equivalent to them being 1 apart.103308145
 » 9 months ago, # |   0 https://codeforces.com/contest/1472/submission/103249540 What's wrong in this? Pls look it..
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 check your code test details. in this case,52 1 1 1 1is not working properly.
•  » » » 9 months ago, # ^ |   0 thanks brother
 » 9 months ago, # | ← Rev. 2 →   0 Can someone please explain the approach for B (non DP approach)?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Let there be x number of 1's and y number of 2's in the original array. The total sum would then be total = x + 2*y. If total is odd then there is no way of diving the array into two subsets with equal sums.Else if total is even there are two cases: If (total/2 is odd) you definitely need one 1's in both subsets to make their sum odd. So if there are no 1's in the original array, it can't be divided. If total/2 is even you can always divide it
 » 9 months ago, # |   0 In problem E, can {$h_i,w_i$} be equal to {$h_j,w_j$} for two different $i$ and $j$?
•  » » 9 months ago, # ^ |   0 Yes,it is possible
•  » » 9 months ago, # ^ |   0 I think yes, they can be equal. I mean, why not?
•  » » » 9 months ago, # ^ |   0 Can you please help me with this WA?
•  » » » » 9 months ago, # ^ |   0 Not sure what you are trying to do there, it is hard to understand.However, I think you cannot ignore that h and w can be swapped. One simple way to do this is swap all pairs so that h>=w.
•  » » » » » 9 months ago, # ^ |   0 But, if the method is correct, it should pass even of I don't swap pairs as you mentioned.But that's okay, I will try debugging again. It actually went too late night yesterday, so I was unable to debug =D.
 » 9 months ago, # |   0 DIV 3 PROBLEM C VIDEO TUTORIAL LINK https://www.youtube.com/watch?v=7FFzXk-brRU I have tried my best to give you guys proper intuition of this dp problem. Hope you guys will enjoy this video !!!
 » 9 months ago, # |   +3 Please take a look at user ImTheBest004. Based on the time the account was created and the submissions made by the user during the contest, it seems to be an alt. Thanks.
 » 9 months ago, # | ← Rev. 2 →   0 My solution to E:Clearly, we can rotate any friend in the input, and the answer remains the same. Suppose we rotated all of them to be wide-and-short. Then we can remove the ability to rotate friends while taking pictures, and the answer remains the same. Proof: if X is narrow-and-tall and can stand in front of Y who is wide-and-short, X can be rotated and still stand in front of Y.Hence, we rotate all friends to wide-and-short and then remove the ability to rotate them any further. The constraint for X to stand in front of Y becomes: 1) X has width strictly lesser than Y, and 2) X has height strictly lesser than Y.Consider sorting the friends by width and then answering queries in this order; when considering a certain friend X, define the set of candidates to be the set of other friends which satisfies constraint (1). Note that the set of candidates for X is a subset of friends we've considered before X, and the set of candidates increases as we answer more and more queries. Among the candidates, it suffices to check the one with minimum height.My solution to F:If there are any two blocked cells in the same column, we can split the squares at that column, and consider the left and right subproblems. Hence it suffices to solve the case where each cell has distinct columns.For there to be a solution, the number of blocked has to be even. Also, if you colour each cell black and white like in a chessboard, for there to be a solution, the number of blocked black cells must be equal to the number of blocked white cells. If you sort the blocked cells by column number, it turns out that there is a solution IFF every adjacent pair of cells has opposite colours.
 » 9 months ago, # |   0 I have a question, for question E. At first, I thought the topic was asking how many people can be before the number i, so I searched the Internet for how to get a numerical ranking in the set. Unfortunately, I searched for a long time and only found a function called distance. (I didn't know its complexity was O(n) at the time, I only knew it after the game). Fortunately, the sample data reminds me that I read the wrong question. But I have a question, that is, if the question is to ask for how many people can be before the number i, can it be solved with set? Or must other methods be used? If I have to use other methods, is there any sample code and teach me how to do it? I hope that the kind people will answer this question for me, thanks in advance.
•  » » 9 months ago, # ^ |   0 You can sort the people by h, and maintain a multiset of all w values. Then loop throug all people.In the loop first remove the current persons w from the multiset. Then find for the current person the number of persons with smaller w by binary search on the multiset. The multiset is sorted by w, so the number of smaller/bigger entries can be calculated once we know the position of the "next" bigger one. see function upper_bound().I implemented the problem this way, in spite on not needing the count, but only one random one. 103306560
•  » » » 9 months ago, # ^ |   0 I don’t quite understand what you mean, there is such a line in your code auto it=f.upper_bound({get<1>(a[i]), n}); It stores only the iterator pointed to by an element. But the distance between it and f.begin() still needs to be obtained through the distance function? But unfortunately, the time complexity of the distance function is O(n). Or do I not fully understand what you mean? In addition, I think this problem does not need to use mulset, a set is enough to solve. Just store the value*1000000+number in the set (you can see the code I submitted during the competition), I don’t like to use mulset very much, so if I don’t need it, I try not to use it^__^
•  » » » » 9 months ago, # ^ |   +3 You are right, I assumed distance() would work in O(1). However, the principle works. For example we can compress the h and w values, then use a segment- or fenwick tree instead of the multiset.The principle is that we maintain the set of elements which are to be considered in one dimension in a structure that allows us to query the other dimension.
 » 9 months ago, # |   0 When I see my rank in the standings table, it is 178 but in friends standing, it is 240. Can anybody explain the reason for this? Thanks in advance!
•  » » 9 months ago, # ^ |   +12 First tell me Why are u cheating
•  » » » 9 months ago, # ^ |   0 Am I!!
•  » » » 9 months ago, # ^ |   0 How do u find he 's cheating, is there any evidence?
•  » » 9 months ago, # ^ |   +7 the lion, the witch, and the audacity of this..
•  » » » 9 months ago, # ^ |   0 Solution for E :Just for a particular hi, check whether there exists a smaller w among the all h smaller than hi and similarly among the reverse pair, check whether smaller h exists for smaller ws. This can be done storing the minimum among them. I used coordinate compression to achieve this.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Can you point whats wrong in this code? It got accepted on "PRETESTS" If we remove if(a.w>A[0]. w)break; code.. minimum.add(new pair(A[0].h,A[0].w,A[0].index)); ` long min=A[0].w; for(pair a: A) { int n=minimum.size()-1; if(a.h==minimum.get(n).h)continue; else { minimum.add(new pair(a.h,a.w,a.index)); if(a.w>A[0].w)break; //min=Math.min(min, a.w); } } outer:for(int i=0; i
•  » » 9 months ago, # ^ |   0 Fuck you piece of shit. YOu have no morals & u filthy dickhead should go to fucking hell.
•  » » 9 months ago, # ^ |   0 Maybe you checked the "show unofficial" on the top right, and it's showing more people. But in your friends standing the rank that shows up is the official rank
 » 9 months ago, # |   0 I really found the problems really interesting. Thanks for such wonderful problems
 » 9 months ago, # |   0 Hi. Can you help me find out what my problem is? I get wrong answer on test 2986 My Code:. It is about problem E. Thanks!
 » 9 months ago, # |   0 If My submission gets Hacked. How can I check For what input it failed or gave TLE. Is there a way?
 » 9 months ago, # |   -6 How is my new user handle?
 » 9 months ago, # |   +2 Testing on hacks completed or not?
•  » » 9 months ago, # ^ |   +2 done, but the change in ratings will take some time to appear.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 What does it depend on? I'm newbie
•  » » » 9 months ago, # ^ |   0 how long?
•  » » » » 9 months ago, # ^ |   +1 It would feel like light years If you are eagerly refreshing to check the ratings update
•  » » » » » 9 months ago, # ^ |   0 Was it an unrated round? I hope not
 » 9 months ago, # |   0 Hey there I just got this message from system saying that those people wrote the same code as I did , now I know that I don't use platforms like ideone I use my favorite editor **VScode ** so all my code is private and local none of it goes public.I write my code using really standard rules, so the code looks similar to others that might the reason, I would love to get my codes back as well as my participation in the round Codeforces Round #693 (Div. 3)Codeforces Round #693 (Div. 3), I don't care how I did in this round I want my rate to change cause its just a new year and I wanna go back to solving more problems on this platform.note : I think I did good in this contest. I was hyped to see the ratings don't put me down :)Thanks alotAttention! Your solution 103286677 for the problem 1472D significantly coincides with solutions Fumetsu_no_kitsune/103286677, johnJ21450/103289999, vk99/103290163, aditya_pratap1/103290631, fakeaccforcf1/103290725, Kryptoniom/103291794, coder1234/103292576, booliandm/103292787, ikdjfkjnfkjnvjk/103293168, asimmc/103294702, riya.ras144/103296299. 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.com/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.
 » 9 months ago, # | ← Rev. 2 →   0 I participated in the contest and even made 3 submissions (2 AC) in the contest time. However, it does not show in my profile under "contests "and my rating too hasn't changed. Why is this so? I am kinda very new here so still tryna figure things out.Edit: Done! I guess it takes some time tp update.
 » 8 months ago, # |   0 I'm upset coz of weak pre-tests in problem A however, thank you for the good problems statement,,
•  » » 8 months ago, # ^ |   0 You miss the contest number
 » 8 months ago, # |   0 Hey can someone explain the editorial for e. I did not get how the case when one person is standing and one person is lying has been considered in the editorial solution??
 » 8 months ago, # |   0 Hello, I am a real newbie. Please can someone explain to me question E. I am not able to wrap my head around it.