С Новым годом, Codeforces!
UPD: Мы получили настолько противоречивые мнения о порядке задач, что не можем быть полностью уверенными в нём. Рекомендуем прочитать все задачи и не сильно надеяться, что сложность лично для вас обязательно совпадёт с порядком в раунде.
<almost-copy-pasted-part>
Привет! Во 04.01.2021 17:35 (Московское время) начнётся Codeforces Round #693 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы будем расстроены, если у многих попадают решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи на этот раунд были придуманы MikeMirzayanov и подготовлены Supermagzzz и Stepavly
Спасибо MikeMirzayanov за платформы и координацию нашей работы. Спасибо darkkcyan, Aris, Mukundan314, PrideBlack, Nemo, pashka, Rox за помощь в подготовке и тестировании раунда.
Удачи!
</almost-copy-pasted-part>
UPD: Разбор
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 .
Supermagzzz and Stepavly's rounds have been extremely high quality, so I am excited!
Supermagzzz and Stepavly's rounds have been extremely high quality, so I am excited!
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?
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
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
If I change my rank to Pupil can I participate?
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.
Meow hopes that he gets some positive delta this contest :3
+50 delta for everyone who participates... lol!!
wow 7 problems on a div3, this is gonna be interesting :))
As an expert, give me 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 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...
Hoping for less plagiarism this year cheers!
Happy New the Contest !! 1st contest of 2021 is for the the beginners of the programming world
I love it when my div 3 contests are unrated for me. I wait for the day when I could say the same for div. 2 contests :)
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
methe problem setters contributions. They have done a great job preparing fun, yet challenging problems! I highly recommend reading all problems ;)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!!
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!
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.
what rank should we get in order to have a +ve delta?
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.
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
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...
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)
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 .
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 then sorted. 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.
Nice contest (although I will have quite a negative delta ;'( )
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 B?
say you have
cnt_11s andcnt_22s. pickx1s (out of cnt_1) and picky2s (out of cnt_2). If there is some combination such thatx + 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.
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 ??
Can Someone Explain, How to solve E using 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
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
https://mirror.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.
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.
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
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;
..
minimum.add(new pair(A[0].h,A[0].w,A[0].index));
Cheaters
Cheaters on telegram group
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!
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
I'm upset coz of weak pre-tests in problem A however, thank you for the good problems statement,,
You miss the contest number
Can someone explain why 6->2->5->1 isn't a valid path for the first testcase of the sample input for problem G?