Привет всем!
Мы приглашаем вас поучаствовать в Codeforces Round #225, который состоится в понедельник 20-го января в 19:30 по московскому времени. Это третий раунд, где я участвую в качестве автора (другие два: Codeforces Round #198 и Codeforces Round #191 (Div. 2)).
Если вы посмотрите мои прошлые раунды, то увидите, что главный герой задач — Яхуб. Один из авторов этого раунда — ... Яхуб... реальный человек, с которого взят главный герой задач. Знакомьтесь, Rares Buhai (rares.buhai), он же Яхуб. Он является автором задач Div. 2 C / Div. 1 A, Div. 1 D и Div. 1 E. Скорей всего, задачи покажутся вам интересными, поскольку их автор два раза становился золотым медалистом IOI (и он может участвовать еще два раза). Все остальные задачи готовил я. Они мне нравятся, но я буду не объективным, если скажу, что они интересные. Посмотрим, что скажут участники после контеста :)
Как и в прошлый раз, будет небольшой спойлер по поводу задач. Мы постарались сделать задачи разнообразными, насколько это возможно. Чтобы занять высокое место, человек должен уметь решать задачи типа “ad-hoc”, а также иметь хорошие алгоритмические знания.
Как обычно, мы благодарим MikeMirzayanov за Codeforces, Delinur за перводы задач, Gerald за помощь в подготовке раунда и DamianS и ll931110 за тестирование.
Желаем вам высокого рейтинга и фана от задач!
UPD Распределение баллов
Дивизион 1: 500 — 1500 — 1500 — 2000 — 2500
Дивизион 2: 500 — 1000 — 1500 — 2500 — 2500
UPD Контест закончился! Спасибо всем, кто участвовал! Должен сказать, что мы были сильно удивлены вашими необычными решениями задачи D в первом дивизионе.
Победители Div. 1:
Победители Div. 2:
UPD Разбор задач
"Чтобы заполучить высокое место, человек должен уметь решать задачи типа “ad-hoc”・ а также иметь хорошие алгоритмические знания" — вот это спойлер. Удачи.
.
Текст переводил я. Напиши, что тебе не нравится мне в личку, поправлю.
Это третий автор, где я участвую в качестве автора
Это раунд автор, где я участвую в качестве автора
Если вы посмотрите мои прошлые раунды, то увидите, что главый герой задач –ач Яхуб. Один из авторов этого раунда –ач... Яхуб... реальный человек, с которого взят главный герой задач “чб”・
Вот из этой фразы плохо понятно, что rares.buhai и есть тот самый Яхуб.
Все-таки без Google Translate тут не обошлось:)
is the score distribution going to be dynamic ?
Hm, what is an "ad hoc" problem?
It means that the problem has a unique, uncommon or unusual solution.
Problem that depend only on observation , doesn't need a special algorithm to be solved with
Majority of round 225 problems solved by greedy techniqe
problems which are not based on any particular algorithm, and usually based on observations and deduction of patterns.
Ad hoc problems are those whose algorithms do not fall into standard categories with well-studied solutions. Each ad hoc problem is different; no specific or general techniques exist to solve them.
Of course, this makes the problems the fun ones, since each one presents a new challenge. The solutions might require a novel data structure or an unusual set of loops or conditionals. Sometimes they require special combinations that are rare or at least rarely encountered.
Ad hoc problems usually require careful reading and usually yield to an attack that revolves around carefully sequencing the instructions given in the problem.
Ad hoc problems can still require reasonable optimizations and at least a degree of analysis that enables one to avoid loops nested five deep, for example.
I took this definition from USACO Training Pages. I recommend it strongly if you want to improve your level of problem solving.
It' s my first Div.1 contest, looking forward to it. And thanks to the authors, we can have another contest in a few days:)
Another round which is not during weekend :(.
But its at night (in India) so doesn't matter to me!
If you're from the US, it's Martin Luther King Day, so there's no work or school.
Что такое "ad-hoc"?
Я думаю, эта статья лучше любых других объяснений. http://ru.wikipedia.org/wiki/Ad_hoc
Cool! Another round with Romanian problem setters. I can't wait to participate. Will Iahub also be the main character this time, too? :) Or will you also have a Sufle character? :) [ the reverse of elfus ]
Thank you for the hint! It's just now when I realize what Iahub means (the reverse of Buhai).
Я не участвовал в Codeforces Round #191, но 198-й мне очень нравилось. Надеюсь, что 225-й (15^2) тоже будет хорошим :)
"225-й (15^2)" ну просто ОЧЕНЬ важное уточнение:)
Good Luck to everyone!
Seems that it is going to be a very interesting round. Good luck to everyone..
Это мой первый раунд который я буду писать на Java надеюсь все нормально пройдет....
судя по твоей последней статистике...вряд ли(
Разве Вы все прошлые контесты не на java 7 писали? :)
Div1 500, 1500, 1500 ?!
I was aiming at solving A & B now I have to reconsider this :D :D :D
* insert a Courage Wolf picture *
solve A, B and C instead
A round with a very interesting score distribution... It seems that I'll back to Div2 again :)
Do you wish good luck to everyone?
I think the publishing of such link at the contest-blog will reduce the number of similar comments :)
Yeah, this is a sarcasm, and at the same time spam reducer :D
31% No?? LOL :D
When nobody know who you are , you show your real face :D
So every body should ask him self , "What I did when I playing GTA "?
Размял пальцы в Guitar Hero, теперь приступим. :)
where is the link for problems ofRound#225
Kindly, read the Help section. If you don't find your answer in it, feel free to ask :)
http://codeforces.com/help
Finally, a round where we can see the score distribution earlier than expected....
GL & HF!))
I hadn't found any broken solution. Maybe pretests are too strong?
yes...i am trapped in C....
5753253 5754304 5752611
three successful hacks, all from the same room.
NO HACKS for div2! :o
Actually there are. I suppose most of the solutions of div1 B/div2 D will fail.
Есть какое-то решение для C в div2 без дерева отрезков?
Я делал без дерева, ибо чайник.
Создал 2 массива: в первом считаю количество единиц, начиная с начала до каждого элемента, во втором — количество нулей, начиная с конца также для каждого элемента. Потом подсчитываю количество нулей во втором массиве непосредственно перед очередной единицей, и единиц перед нулями в первом. Результатом будет минимальное из двух полученных значений.
Может это слишком"нубский" метод, но претесты прошёл.
ну так и надо решать) я тоже сначал думал поизвращаться, а потом понял, все гораздо, гораздо проще)
Утверждается, что ответ — это количество пар смотрящих друг на друга коров.
Если это про коров то да, смотрим сколько коров смотрят друг на друга, идем слева направо, если она смотрит направо +1 счетчик, если она налево то ответ + счетчик. Если они смотрят друг на друга — значит одна точно потеряет молоко при дойке второй.
У меня претесты прошло такое (возможно, упадёт на систестах, т.к. не знаю, как доказать): Посчитаем для каждой позиции i кол-во коров, которые смотрят направо и их номер <=i. Пройдёмся в цикле, прибавляя к ответу это число, если корова смотрит налево.
P.S. Аналогичный вопрос про div. 1 B.
Всем спасибо)
Problem C was interesting. Same for D where the answer was only 2n — 2 or -1. B was too boring a problem to waste time though.
I believe Answer is not always 2n-2 or -1
You are not allowed to go up or left.
Thanks. I hope some day I'll learn how to read statements
i feel you bro
always, because you can't move up and left
from
(i, j)we can go only to(i+1, j)and(i, j+1)You cannot walk up
the answer for that case is -1 , isn't it?
yeah, you're right
was it a very hard contest for you or just me??
I think it was good contest for me.
I actually got quite much time to think on problem C which isn't usual for me in the contests.
this is how a contest should be. neither too easy nor too hard. well done fchirica.
PS: next time, try to improve the gradient of difficulty of the problems. that was the only thing lacking today. :)
Как решалась D(div 2)/B(div 1)?
Там ответ либо -1 либо 2*n-2.Нужно проверить на -1 и все.
Как за приемлемое время проверить-то?..
Если полностью перекрывается 1 строка или 1 столбец. Или вулкан есть в клетках : (1,x) ,(2,x-1),(3,x-2) ... (y,1).
Ну явно есть другие варианты. Например, что-нибудь вот такое:
......#....#.#..#...##....##........Простите. Ошибся.
А как это доказать?
Нельзя добраться из левого верхнего в правый нижний за какое-то другое количество движений, двигаясь только вправо и вниз. Мы не сделаем меньше, чем 2n-2 т.к. это итак кратчайшее расстояние. Мы не сделаем больше, чем 2n-2,потому что вниз можно сходить только n-1 и вправо тоже только n-1.
Ну очевидно, что если мы можем двигаться только в двух направлениях, то с каждым шагом мы будем приближаться к цели на одну клетку. И любой путь, который мы пройдём (если сможем к ней дойти) будет иметь одну и ту же длину.
Логично, однако, как проверить на -1?
запишем в пары наши входные данные, потом отсортируем, первая координата Y в паре. Идем по вершинам, поддерживаем массив плохих вершин (одномерный). Каждый раз когда переходим на новый слой(т.е. у текущей вершины новая координата Y), если он не следующий (Yold != Ycurr — 1), то удаляем из плохих все, что не вплотную к началу (т.е. оставляем непрерывный отрезок от 1, если он был), если слой следующий (Yold = Ycurr — 1), то добавляем все его плохие в новый массив плохих (все вершины с Y= Ycurr), проходимся по старому массиву вершин, для значения старого v(это на самом деле x), если v — 1 в новом, то значит v тоже плохое. Для быстроты можно все на 2 сетах делать.
Массив плохих вершин? А как сжато хранить? Оо
Эм, их максимум 10^5, кроме тех, что блокируются на 1 слое (т.е. если право не можем уйти)
Ой... Кажется я понял, чем плохо моё недорешение.
извиняюсь, потерто
тут же -1 ответ.
Division 2B, it is intended that you can simply print every single pair?
yaa..
more like printing optimized bubble sort steps will do it within the limits of pairs allowed.
Кто-нибудь писал по C div 1 / E div 2 корневую эвристику? Если да, у кого-нибудь был с ней TL6?
31 раз получил TL6, похоже корневая не заходит (Java)
У меня на С++ не заходила. Вроде по ограничениям должна была. Даже смена массивов на векторы не помогла. А как ее решали вообще?
Двумя деревьями отрезков — для чётных и нечётных по глубине вершин. Естественно, в порядке dfs-а.
Два дерева отрезков: одно для вершин чётной глубины в порядке обхода, второе для нечётной. Нужно прибавлять на отрезке и находить значение в элементе.
Заходит, за 1с. 5754923
Мне кажется, надо делать меньше dfs-ов: где-нибудь раз в 1000 или 2000 запросов производить обновление, тогда зайдет. Не тестил.
Избавился от рекурсии в ДФС-е с подачи Dmitry_Egorov, поднял константу до 4000, задача прошла (с 1000 и даже 2000 ТЛ на 11 и 18 тестах соответственно). Спасибо :)
не уверен, но мне кажется что 6ой претест это т.н. бамбук и соответствующие запросы к самому нижнему элементу с изменением корня
what a terrible system test fail rate on Div 1 B...
div 2 — A is too basic
it always is! those problems is designed so that every participant can get it accepted, even if he/she does it after one or two wrong submissions. :D
Very nice contest :)! The problems were very interesting and fun to solve!
Div1-B оказалась коварной: на систестах упало 142 решения, а удержалось — 41.
This round taught me it's more important to think more than code faster!
I could have much more time and points if I had thought some minutes more!
Thanks for good problemset ;)
Wow, system test for div 2 D was powerful!
The whole system test was powerful :) I've amazed the speed. Maybe need some sleep to be more interesting :)
What's the point of additional constraints in div1E? It can be done in O(2K + N) regardless of how long are given strings. My solution passes in 280 ms.
Cool! Can you share your solution?
Suppose we have an array a of length 2K. We want to construct array b so that bi =
. Partite a into two arrays a' = a[0..2K - 1) and a" = a[2K - 1..2K) and solve the problem recursively for them, obtain arrays b' and b". bi = b'i if i < 2K - 1 and bi = b'i - 2K - 1 + b"i - 2K - 1 otherwise.
This is clearly a linear solution.Actually, this is a O(K2K) solution, my bad.As I can see, it is k*2^k solution as we have k levels with O(2^k) merge for each of them. I have exactly the same soltuion but I do it in non-recursive way. 5753388
Well, the "easy" solution I guess was O(N+2^K*K^3) — by precomputing the amount of words with all possible combinations of 1, 2 or 3 letters and then solving each query with inclusion-exclusion formula, but I managed to optimize it to O(N+2^K*K^2) by using some previous results and that was enough. But this solution heavily uses that the length is up to 3, so that we can stop inclusion-exclusion formula when there are more than 3 bits on.
I've solved the Div1-C with heavy-light decomposition. This is the first time when I use this in contest :) . Is there any simpler solution?
I use heavy-light decomposition too.
It is enough to decompose the tree in such a way that every subtree is represented by continuous interval. You can use a simple pre-order DFS and build a standard segment tree on top of the resulting sequence (or Fenwick tree).
Ohh I see. Thank you!
but if u do that, how will u know which nodes to add
valand which nodes to add-val?I split the tree into 2. Something like node.edges.addAll(all node's children's children) This way, by skipping 2 layer each time, one tree will be a + val, the other will be — val
http://codeforces.com/contest/383/submission/5755796
I converted the tree to linear brackets sequence. For each node, record the smallest begin time and largest the finish time of all the nodes with odd depth of the subtree. Also Record the even part.
After that, just use segment tree to implement the add operation and the query operation.
На задачу Е див2/С див 1, тесты не очень правильные. Если рассматривать граф как ориентированый, то все ровно решение будет работать, хотя в условии написано просто про существование ребра между вершинами.
There is NO Accepted Solution for B in my room (16) ! I haven't seen any problem like this before!
Практически весь контест пытался написать решение с деревом отрезков на B. После контеста, наконец, отловил основные баги. И поймал TLE 9. Потому что я... Ну вы поняли, победитель по жизни, ага.
Если кто-то сможет найти время и объяснить, в чём основные огрехи моего жуткого решения (помимо ущербного стиля), буду очень благодарен. Как мне кажется, ассимптотика решения порядка mlogn. Буду рад, если кто-то докажет обратное.
5758834
Really weak pretests for problem B Div1!
actually, i dont think the pretests were weak. it's just that the system tests were really strong!
There is no weak pretests for problem B div1, there is just a lot of weak solutions :)
How exactly does -50 on wrong pretests work ? Will it only get reduced from that problem if we actually submit an answer for that problem otherwise not ?
Only if you pass the system tests on that problem. And the hacks on it should always count.
Each wrong answer on pretests gives you -50 score for that problem , but you will only get the penalty if you actually manage to solve the problem correctly, otherwise your score for that problem is 0.
You will get the penalty only if you get AC on that same problem later.
I was stuck in B, and didn't take a look at D until there's half an hour left. This taught me to read all the problems before thinking.
It's the first time I solve D :)
I took an unnecessarily long time on C — I could solve it quickly, but silly mistakes appeared. After I solved C, I solved D in about 20 minutes.
D and B should've been swapped. The idea isn't really hard, but it's prone to mistakes.
Perhaps D is D because it is not used in Div 2, while B is.
А кто-нибудь уже разобрался, в чем такой ужас 13 теста в Div.2 D/Div.1 B? Я смотрю, много у кого на нем упало решение в обоих дивизионах.
Тест большой, но кажется он основан на том, что нельзя делать ходы вверх.
Спасибо! Похоже, я даже понял ошибку... =(
Похоже, что-то вроде этого:
...#....#....#........#....#....#...Есть у кого идеи, как такое выловить?
Мой BFS тут явно свалится... Так что пока что нет:(
n<=10^9. BFS тут свалится даже если попытается найти путь в пустой матрице без вулканов =)
Нет Не настолько тупой bfs Если идти по вулканам, доставая их из сета. Мы можем за как раз m log m найти, есть ли у нас "замкнутые" области вокруг клетки 1;1 или n;n Но сюда уже видимо никак не прикрутишь запрет на ходьбу вверх и влево
Конечно я бы не стал писать bfs тупо по матрице :D я б даже создать такую большую не смог бы...
Слишком фейлово, чтоб быть на виду)
There is 150 test cases for B! But All of the failures are on tests less than 13!! :)) I think 13 test cases were enough!
thank you for great contest, but pretest was a bit weak on problem B div 1.
Hello.. I just want to ask something.. why my code got Wrong Answer on Problem A?? When I compile it from my laptop, it gives me the right answer.. And when I submit another for practice and just delete some STL include but my main code is still the same, it keeps get Wrong Answer and the Wrong Answer's test case is not the same.. First it is on Case 8, then second on case 7, the third one on Case 9.. What is going on???
you are trying to use element with indicies -1 and n in your array, Besides, you are using data in that array that was never initialized
I modified your code and got AC 5759068. Hope this help you understand.
If i == 0 then you don't need to check peta[i-1][j], the same is for j. And since you fill the blank from small ij's, you don't have to check peta[i+1][j] and peta[i][j+1] either.
Oh, now I understand.. Thanks, jonathan79717.. :-)
what was the tricky case for problem D div 2 ?!
for me it was this case
i have to go left at some point which is not a valid move
hmm i don't think it was the fail case to my code since i used STL set container , hmm i would like to know what was the tricky for test 13 :'(
lol i see why i fail ;-; , thanks!
Something like this
actually my code works for that case :'c
Try new one
thanks so much i see why i fail...
will there be any editorials for the problems? and when will be the ratings updated?
I got WA on pretest 2 problem B div2 and I lost 50 point :( . I am sure I saw this happened before for some participant and they didn't lose points for WA on given cases !!
There is no penalty only for pretest 1.
You don't lose points only if you'v got WA on the first sample. not all samples.
that participant probably received WA#1 or RE#1. submissions that fail on the first pretest do not receive a penalty.
Thank you for explaining .
Sad to get green again...T_T
you are going to lose atmost 90 rating points xD , the same happened to me in the last contest
I'll be back next contest...
no you won't. you're just too__weak! :D
PS: i was just kidding. hope u didn't take this seriously. :P
Thank you for the contest, and, specifically, for the Div 1/D task.
For me, D was the least interesting xD
Considering that the reason I found it beautiful was because of how well the simple solution is hidden in the task, I do understand your point of view that if you haven't solved it, you might find it the least interesting problem of the lot.
Let's not jump to conclusions here :) I began solving it 10 minutes before the end of the contest and finished it 1 minute after the end. So yeah, not interesting.
OK, sorry, I thought that I had looked at upsolving results and somehow failed.
Anyway, yeah, I most likely enjoyed it was because I didn't stumble upon that idea immediately. If one manages to immediately get to it out, I can even more see how it would be not interesting at all.
Or maybe I just liked the problem so much with no logical reasoning behind it.
And by the way, congratulations with the new colour!
I tried to hack this solution generating the worst case for bubble sort, in which it should TLE, at least in my opinion. Am I wrong ?
Nice contest. Good joob elfus&iahub.
mlc
Does anyone has an idea why my program output for the first example test case in the problem B (Div 2) fails?
http://codeforces.com/contest/384/submission/5758977
It looks like as if it was correct..
for first index in output, your array becomes
1 2 3 5 4 1 3 4 2 5
for next index in output, your array becomes
1 2 3 5 4 1 2 4 3 5
for last index in output, your array becomes
1 2 3 4 5 1 2 4 3 5
Now see, second array is not sorted in ascending order. So it's wrong...
I didn't like Div2-B. But, C was an awesome problem.
And the pretests of A,B,C was strong enough. Technically The system test of Div2-D was the strongest I have ever seen!!!
Thanks to the authors for a nice contest. :)
Div2-B is funny :)
Show my solution: 5752434
Yes! With the restriction of output, you can easily realize that bubble-sort will always satisfy it. And generating the code in just a few minutes, like mine. -> 5754578
I just study C about 3 months so I feel very worst :(( . Can you share code of Div 2 for me ? My email: [email protected]. Tks all :)
you can see anybody's solution ,just click the submission id :p
ratings are not updated yet :(
Mine is updated. Yours should be soon.
Rating has already updated!
А когда разбор будет?
На английском уже есть http://codeforces.com/blog/entry/10476
Who's the lucker here???)))
Nice! I had +3 and became yellow :D
Me :D
Yes! 266 Points added! Any way, I still think that Div2-D is too tricky to solve. And I feel lucky that I solved Problem E first. :)
ur name is FastAC. no wonder u solved it first :D
nice contest !!!!
What a good luck! One Codeforces round that I didn't [have time to] participate in, and exactly in this one, most of my div 2 friends got >= +100!
O(sqrt(N)*N) get accepted for div1 C! 5762148
Oh, if only you knew how many problems on trees I've solved in
...
It's nothing rare, if the time limits aren't tight. Solutions in
often have large constants, caused by the use of segment trees or some more complex operations. Simpler decompositions have worse complexity, but small constants, so they aren't much slower.
Where is the Tutorial?
here
thank you~
Thanks
nice contest
can someone explain a simple solution that everyone writes :) in Div2-C !