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

Is this the first Div. 3 contest announcement by a "newbie"?

newbie with 2165 rating, now everyone wants to be newbie with this rating.

except for whom his rating is above 2165

Great!! Edge cases are important :}

I hope i reach this new newbie level .

New Year Magic -- Newbie arrange a contest for LGM....xD.

I literally thought he is a newbie....xD

LGM's gonna have hard time solving newbies problem... XD

Seems no tester will ask to give him contribution for this contest.

Actually, as a tester...

No Hello 2021 this time?

Very Unlikely as first contest is hello and is not scheduled yet and a div3 after 2 days which makes it nearly impossible.

This round will be in New Year's style. This isn't Hello 2021, but we hope you will enjoy it!

New Year is celebrating the fact that the earth orbited the sun an integer number of times since an arbitrary day...

Missing vovuh

Happy New Year Codeforces! <3

I will participate as an International Master XD what an irony :v

Thanks a lot to Supermagzzz and Stepavly for preparing the div. 3rd competition.

As a LGM, Give me some contribution!!.

I think you need some rating as an LGM.

pog

Div 3 will flood LGM xDDDD

memethis blog proves that upvotes are given on the basis of rating mainly!

blog was written 92 minutes ago and still only 63 upvotes

xDIf I change my rank to Pupil can I participate?

Coders on "pupil" can also take part in Div 1 !!???

ILLUSION 100

XD

Count of LGMS participating officially in Div3 will be more than that of pupils and newbies xd

edit: **Count of LGMs

Please focus on making a new season of prison break :P

That's not gonna happen I am afraid :(

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]..

do them

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.

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.

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.

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.

Meow hopes that he gets some positive delta this contest :3

+50 delta for everyone who participates... lol!!

I hope me and u get more that +50

A VERY GOOD PROBLEM(C) ON CONSTRUCTIVE ALGORITHMS. LINK : https://www.youtube.com/watch?v=lZplaUOpPnk HOPE YOU GUYS WILL ENJOY THIS EXPLANATION VIDEO !!!

wow 7 problems on a div3, this is gonna be interesting :))

As an expert, give me contribution

are you talking for negative contribution?

contribution is yours mr.expert

Where is EVA?

i have changed my handle because i do it every year

will we have any extra rating rise as a new year gift? jk XD !!

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 .

is this contest rated for me?

yes

For some time, I thought it's an unofficial announcement.

But why?

Because the post is written by newbie.

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...

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

Hoping for less plagiarism this year cheers!

My first contest as LGM

I hope you guys enjoy the first 2021 Codeforces contest. Good luck!

What can be more satisfying than starting

2021 with a Div 3.Happy New Year CodeforcesMagic is very good, we can be master for a few days

Thanks to CodeForceshope to become pupil soon as a Legendary GrandMaster

Happy New the Contest !! 1st contest of 2021 is for the the beginners of the programming world

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 :)

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 ;)div.3 is more comfortable contest.

as a grandmaster, I won't participate in this contest . . . so Newbies can improve their rankings (lmao . . . happy new year)

hmm, Legendary GM!!

yes ... that's right legendary grand master :]

You can only participate in Div-1 lol!!

18 down votes? wow that was only a joke guys take it easy

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?

First contest of the year! And first ever unrated official contest for me!

I think that codeforces will arrange happy new year contest but starting by div 3!!!

For anyone interested, I'll be doing a post-contest stream on Twitch.

Hey man! Any reason for choosing Twitch over YouTube?

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.

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!

Thanks a lot to Supermagzzz and Stepavly for preparing the div. 3rd competition.

What does it mean by this?

anonymous pictures website

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.

2021 be like: Newbie makes div3 for Legendary Grossmaster.

Newbie has made div3 for Legendary Grandmaster. lol ;)

can i take part in thí contest ?? i'm newbie.

Yes, everyone with a rating less than 1600 can take part in DIV3 contests

Tomorrow is my birthday. I will try to be green on the basis of the results of Codeforces Round #693(Div3) .

happy (early) birthday bro

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

I guess everyone is chosing a colour that they have never got/think they can't achieve unless they perform abnormally :P

yaa this might be true. xD

I'm an expert coder!

haq!

everyone has dream to become Legendary Grandmaster

Anyone from react-native background here?

Yeah

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.

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.Сообщение от авторов:Мы получили настолько противоречивые мнения о порядке задач, что не можем быть полностью уверенными в нём. Рекомендуем прочитать все задачи и не сильно надеяться, что сложность лично для вас обязательно совпадёт с порядком в раунде.I think you should put this message in the announcement

This message is already in the announcement :)

The best way to do good in DIV 3 is to think like DIV 3..

What happened to Hello 2021?

I believe 2020 got it....Mission failed, Get em next time...

One Piece touched 1000 I want to too. (All hail future pirate king)

Such a nice contest with excellent problems!

Though problems where a bit on the easy side.

Enjoyed it

(AFTER CONTEST) How to solve E? I tried Binary Search but it had some problem, maybe implementation,I don't Know.

Binary Search + Segment Tree (My solution is probably overkill)

Why simple Binary Search won't give optimal solution?

I just used sorting + two pointer

I sorted the input by pair<height,width> . For first case where $$$h_j<h_i$$$ and $$$w_j<w_i$$$ , we can traverse the array and keep track of person with smallest width for height less than $$$h_i$$$.

For the other case , we can take $$$h_i = w_i-1$$$ , $$$w_i = h_i-1$$$ and we can solve it similar to above.

I had same approach. Some implementation problem must be there.

your code is giving TLE on my computer on test 1 2 10 2 1 9 .You can use that to debug .

ya that might be the case as well. but on submitting it showed WA on test 2

I sorted by pair<min(height, width), max(height, width)> because basically width and height could be exchanged as per the problem. Made the implementation very easy

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.

You can solve E with 1 Fenwick Tree easily

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.

sorting + one variable to hold current minima

What is test 2 of Problem E?

Sorry for being rude. I didn't meant that :(

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.

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.

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

Your code is failing on following test : 1

2

10 2

1 9

output 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)

Appreciate this. I see what my bug is — I should've rotated my height and width in cases where height > width, and

thensorted. I believe the rest of my implementation is likely ok, so this was my oversight.[Edit] Yup, that was it. Passed sys tests with this change.

Problem D reminded me of Leetcode — Stone Game VI

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?

No, it shows the time as the max allowed time and shows TLE verdict.

No when you exceed the limit program stops and terminates TLE

How to solve Problem C without using DP ?

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 it

https://codeforces.com/contest/1472/submission/103281636

How to solve B?

N^3 worked for me If totalsum is odd its NO Else checked if currsum can be totalsum/2

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.Its Subset sum problem(DP). Although , People solved it greedily too.

Well well can you share your idea.

Dynamic Programming for div3 B?

It's just two if statements after counting no of one and twos

103202827

Problem E was simple Fenwick Tree implementation

Or just sorting :) I recommend you to read the editorial

Can you Explain ??

yet again I couldn't solve any problem and it's div.3. I am amazed by my dumbness. shame on me :(

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.

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.

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.

I could only solve 3 problems, too bad for a student

when the editorial is published

I really liked the problem set. Thank you for the contest.

Can Someone Explain, How to solve

Eusing Fenwick Tree ????Is rank predictor broken?

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.

Actually, he said about the cf-predictor site where rank prediction were given before the official rank update.

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

Problem B is same as Codeforces Round 248 — A. Kitahara Haruki's Gift

Wanna find more similar than this ?

Go check out this 416. Partition Equal Subset Sum — Leetcode.

IMO

problem Fis 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

https://codeforces.com/contest/1472/submission/103249540 What's wrong in this? Pls look it..

check your code test details. in this case,

5

2 1 1 1 1

is not working properly.

thanks brother

Can someone please explain the approach for B (non DP approach)?

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

In problem E, can {$$$h_i,w_i$$$} be equal to {$$$h_j,w_j$$$} for two different $$$i$$$ and $$$j$$$?

Yes,it is possible

I think yes, they can be equal. I mean, why not?

Can you please help me with this WA?

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.

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.

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 !!!

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.

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.

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.

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

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^__^

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.

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!

First tell me Why are u cheating

Am I!!

How do u find he 's cheating, is there any evidence?

the lion, the witch, and the audacity of this..

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.

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));

Fuck you piece of shit. YOu have no morals & u filthy dickhead should go to fucking hell.

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

I really found the problems really interesting. Thanks for such wonderful problems

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!

If My submission gets Hacked. How can I check For what input it failed or gave TLE. Is there a way?

How is my new user handle?

Testing on hacks completed or not?

done, but the change in ratings will take some time to appear.

What does it depend on? I'm newbie

how long?

It would feel like light years If you are eagerly refreshing to check the ratings update

Was it an unrated round? I hope not

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.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.

I'm upset coz of weak pre-tests in problem A however, thank you for the good problems statement,,

You miss the contest number

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??

Hello, I am a real newbie. Please can someone explain to me question E. I am not able to wrap my head around it.