После долгого перерыва (болезнь, конференция и много других вещей) состоится новый Div.3 раунд!
<copy-pasted-part>
Привет! В Oct/12/2018 17:35 (Moscow time) начнётся Codeforces Round 515 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста. Вам будет предложено 6 или 7 задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</copy-pasted-part>
Также спасибо arsijo, Decibit, PrianishnikovaRina и nooinenoojno за помощь в подготовке и тестирование раунда!
UPD: Жду всех желающих в местном Discord сервере сразу после контеста для обсуждения задач.
UPD2: Разбор опубликован.
UPD3:
Поздравляем победителей:
| Rank | Competitor | Problems Solved | Penalty |
|---|---|---|---|
| 1 | nickyrio | 6 | 165 |
| 2 | smokescreen | 6 | 205 |
| 3 | lanven | 6 | 239 |
| 4 | RockButterfly | 6 | 242 |
| 5 | wythend | 6 | 330 |
Поздравляем лучших взломщиков:
| Rank | Competitor | Hack Count |
|---|---|---|
| 1 | Gabies | 82:-24 |
| 2 | djm03178 | 33:-3 |
| 3 | Laggy | 27:-10 |
| 4 | wanderer163 | 11:-1 |
| 5 | antguz | 10:-1 |
Всего было сделано 231 успешных взломов и 322 неудачных взломов!
И, наконец, люди, отправившие первое полное решение по задаче:
| Problem | Competitor | Penalty |
|---|---|---|
| A | CopeCope | 0:01 |
| B | stafdasca | 0:06 |
| C | nickyrio | 0:04 |
| D | nickyrio | 0:11 |
| E | somanaik | 0:15 |
| F | Ohyeeeeee55 | 0:50 |
Hope this div — 3 won't be like last div — 3
What happened last time?
Last time?!? When?
Codeforces Round 506 (Div. 3)
He means the latest Div. 3 round :)
I guess SHOToRSAVARE_KAZEMSHAHR ment that the latest Div. 3 has been held so much time ago that nobody remembers it.
I meant that last div -3 contest was tough enough.. :3
vovuh с выздоровлением!
When did vovuh become Schrodinger?
Sometimes the the number of problems changes right before the start of the round :) It might happen, but in this round (I hope) will be exactly 6 problems :)
Now I understand the true purpose of your profile picture
IT'S TIME TO UP YOUR RATING, GUYS
How can I improve my level to solve C&D?
Practice past C and D problems.
Wow!
About 1 month the Div.3 contest came again!
I feel surprised!
The last Codeforces Round before NOIP 2018. RP++.
Rp++
RP<<1
Div 3 only? Not good.
Finally a contest by my favourite problem setter after a long time. I love Div 3. :)
finally div 3 , i wish it will be esiear than last one
Unfortunately, clashing with Snackdown :(
Duration of snackdown is of 3 days. You can easily participate in both
Ohh ..I didn't notice that.
if my rank is above 1599 can i participate in div 3
yes , but it will be unreted
thx
High rating & Good luck!
Thanks, bro :)
Come on, come back into Saratov, we miss you
Есть несколько участников, включая меня, которые зарегистрировались на соревнование, когда имели меньше 1600 рейтинга, но на последнем контесте апнули и стали экспертами. В списке зарегистрированных участников такие товарищи не отображаются как участники вне конкурса. Бага, фича или для таких участников контест рейтинговый?
Мы скоро рассмотрим этот вопрос и постараемся исправить ситуацию. Кажется, что так быть не должно.
High rating & Good luck
Wish you all get +100 rating!
Guess Mike hasn't yet been able to find an algorithm to make that happen...
Some wishes can never become reality unfortunately :(
Hoping for no delay...
I guarantee that there will no delay because of problems readiness :) So there will no delay if nothing special happens...
Thanks vovuh, I always get +ve rating in your contest.
Good luck!!I hope we will learn alot.
Hey vovuh, i suggest that you should become Master quickly, because your color doesn't match top contributors's colors, which makes me a little uncomfortable.
Ahah, this makes me laugh :D I will become Master as soon as possible, hope I can do it :D
This isn't Div 3
This Div3A was much, much harder than Div2A typically is. It also didn't have any coding, just math.
Maybe it seems equivalent but not harder.
Wth happend to my brain in problem B
Same, but for me it was an error of index in the vector, it took me like 20 min to find it.
in div(1+2) last contest I solved 3 problems but in div3 Idk why I always become dumper than homer (simpsons)
the problems aren't that hard but it's like my brain gets numbed because I'm telling myself these are div3 too easy
how to solve D ?
start from behind till you run out of boxes .
How did you think that you will have to start from behind?
It's specified in the problem statement that you can remove boxes from start.
"Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has."
Use greedy, start from behind and keep a temporary sum, as soon as this temporary sum is bigger then k take another box, if you have an available one, if not then you just end.
in case : 3 2 5 2 5 1 wouldn't the distribution be [1 2] [5] so the answer is 3?
Every box should contain Consecutive elements
I keep reading the problem statement and can't see where was that mentioned.
Any way thanks for the clarification mate.
It wasn’t said directly but you can understand it from the statement .
What is formula dp for problem B?
Is it dp?
You can use greedy
Really ? I wasn't able to figure out a greedy solution during the contest. In the back of my mind i was still thinking that a Div3-B can't be a DP problem.
Now after the contest, i saw a few codes, many were done neatly using Memoization. Can you share what Greedy approach you have used ? And which approach would be easier to Debug here ? Greedy or DP ? (I think DP looks neat enough here)
For every position X that is not heated i look for the first heater from the position X + r — 1 backwards to position X — r + 1. The next X is the position of the heater I chose + r.
For coding and debug DP is better. It is short code.
Codeforces Round #515 (Div. 1 + Div. 3, combined)
How to solve C?, I was thinking in a segment tree but i wasn't sure.
two prefix arrays for books placed on left and right.
Can you elaborate please ? I would love to know a new way to solve the problem ?
You can map the book ids to a set of consecutive integers which are ordered according to the order in which we put the books on the shelf. (Let's call these integers — "second IDs") (Use a C++ std::list or even std::map for this)
Then for third type Query, you can use the mapping just created and binary search for the second ID of the required book in the second ID collection(Either a vector or a SET) and using the smallest second ID and largest second ID in the collection you can get the answer.
Two arrays for books on left and on right. You can see my solution. Don't think you would need to find an easier one:
http://codeforces.me/contest/1066/submission/44217835
I used segment tree for fun. http://codeforces.me/contest/1066/submission/44219102 If you don't understand the code I can explain with more detail
Can you explain what you kept in node and how did you managed query and update?
I created a center position far enough so i csn go left in every query and never have a negative position. Each node has 1 if position is occupied and 0 otherwise. Every left query ocuppies a node left to the last one and similar with right queries. You end up with a segment tree where leafs look like this: 000...01110111000...000 I save another array where a[id] is the position of the book in the segment tree. Now queries are simple Query from 0 to id (id not included) is the sum of all 1s left to id. Which is what you need to delete so id becomes the leftmost one. Query from id+1 to N which is from id to rhe rightmost node of the segment tree is the sum of all 1s right to id. Which is what you need to delete so id becomes the rightmost one. I hope i explained it well. Good luck!
That's some precious and articulated explanation! Thanks! I just learnt segment tree few days back, and I got accepted following your approach. Learned a simple but effective technique, storing the position in the segment tree to another array. Thanks again.
Contest was so poorly managed. See what I encountered when I opened problem B:
Explanation Part: In the first example the heater at the position 2 warms up elements [1;3], the heater at the position 3 warms up elements [2,4] and the heater at the position 5 warms up elements [5;6] so the answer is 3.
6 2 0 1 1 0 0 1
But there wasn't any heater at pos 5.
Problem Scenerio Part: If n=6, r=2 and heaters are at positions 2 and 4, then Vova can warm up the whole house if he switches all the heaters in the house on.
How can heater on pos 4 warm 3 to 6? r is 2 so it should warmed up 3 to 5.
Asking this, the contest team replied it was an typo and to refresh the page. What about the 15-20 minutes I wasted scratching my head off over the explanation? Why wasn't any announcement made? Assuming the typo was fixed much earlier, what about the people who have had opened the tab in the very beggining? Do I get consideration for that time penalty? Even after replying my question, they didn't make any announcement.
I too left the problem B during the contest because of that. I thought it was not my thing.
I will describe it to you. I cannot make any announcements by myself. Mike was too busy with the Southern Quarterfinal preparation, other admins (or who have access to make announcements, I don't know) didn't have the access to this contest. So how I can post an announcement if I have no rights to do it?
First of all, thanks for explaining the reason. I get it. I won't blame the contest team for this. But definitely CF team should come up with a better system. Giving access to make announcements to contest creators won't be bad for a start. You don't expect this kind of bugs from one of the world's leading competitive programming hosts.
I understand your opinion. In fact I had hold this contest alone and answer all the clarification by myself. Sorry if sometimes you has got bad answers or don't understand my replies.
From your part, I suppose you did what you could do best. Thanks for the quality problems, though.
is there is any greedy solution of problem D?
The main solution is to reverse the array and simulate the process from the end. You can think why it is always true :) Editorial will be posted a little bit later
I Liked the contest, really felt like a Div. 3 competition.
I would like to know if there is Hack data in the D question using the traversal method from the back to the front.
No, this solution can be proved (I will describe it in the editorial) and this cannot be hacked.
Thx
sir there is hacking going on you can't tell these .
Подскажите пожалуйста, как решать F? Upd. Вопрос решен
very nice contest
The editorial is published now!
P.S. I write this comment because of [cut] of the blog at the main page. Someone can miss that the blog is already published because of this [cut].