Привет всем!
Сегодня в 19:30 по Московскому времени состоится юбилейный Codeforces Round #200. Раунд будет проведен в обоих дивизионах и будет рейтинговым.
Задачи раунда подготовили Евгений Вихров (gen), Андрей Вихров (andreyv) и Геральд Агапов (Gerald). Как всегда, выражаем благодарность Михаилу Мирзаянову (MikeMirzayanov) за системы Codeforces и Polygon. Отдельное спасибо Марии Беловой (Delinur) за перевод условий задач.
В этом раунде вы поможете безумному учёному Майку реализовать его причудливые затеи и поставить необычные опыты. По мнению авторов, в задачах поддерживается хороший баланс математики и программирования. Также мы старались сделать условия задач по возможности короткими и понятными :] Как всегда, мы считаем, что каждый участник найдёт себе задачу по вкусу.
Желаем всем участникам удачи и интересного раунда!
UPD1: Разбалловка задач стандартная:
DivI: 500 1000 1500 2000 2500
DivII: 500 1000 1500 2000 2500
UPD2: Поздравляем две лучших пятёрки победителей!
Посоны, я буду синим, атвичяю
Ну я тогда фиолетовым=) атвичяю(с)
Посоны, я тожи буду синим, атвичяю!
Я — зеленым?!
судя по текущим результатам несколько больше, чем зеленым :)
Эх, значит не судьба.. )
Лол, пацаны сказали — пацаны не сделали. Это за основу взято :D
А вот даже не обещал, а взял и вернулся в синие. из фиолетового)))
Посоны, в следующий раз точно синим буду, инфа стопроц
Не будет 200 футболок?
расходимся:)
Придется ждать 256 раунда.
У меня на аватарке Гена Короткевич!!!
I love that balance between mathematics and programming!
In round #100, the top 100 participants were awarded t-shirts. How nice if top 200 will be awarded in #200 and so on :-) Seriously, what will be the next round which awards the top X participants? Haha~
Top 200 will be awarded in CF #200 and so on ? So after next few years Mike have to buy more than 1000 T-shirts :) What about your sons in the future when they start to compete :) I think Mike need to Open a T-shirts factory for next generation :)
There wasn't any surprise for this round! I was waiting a long long time for this day and CF #200! :)
It will be better if there are extra T-shirts for coders which behaved excellently in CF Round #200!
Time flies! Codeforces #100 is my first round, and now it comes to #200 rapidly.
It gives a lot of fun, hope it to be better and better.
(of course it's already terrific now, except the network speed some times... )
Также мы старались сделать условия задач по возможности короткими и понятными :]
Вот за это спасибо
I like your handle gen! MCZ Xian, a Gen user in Street Fighter 4, won EVO this year. EVO is the biggest fighting game tournament in the world. Did anyone watch it too on stream ?
Sorry for being off topic :p
Thank you :)
What about awarding all participants with +/- 20% of rating. If their rating is going to increase, increase it 20% more and if it is to be decreased, decrease it 20% less :-D
Rating changes are irregular in a way — even if you get the same place, the rating change depends on the others who compete (your 'relative place'). So that'd be hardly noticeable.
А а а... футболки?
Интересно один я думал что в этом раунде не будет футболок.
Which Mike is he? :D
So which is the score distribution? :-"
and score distribution ??
Score distribution is standard
Nice problem set linking science with coding :) !!
cf was unavailable for long time. time should be increased.
my code in mingw32 output correct answer but here ,cf said wrong answer!!!:| why?
different compiler may result in a slightly different result. Or may also happen when u compile using windows or linux. maybe u should post your code so we could check what is wrong with it?
Как решается С(div.1)?
Я решал с помощью бинарного поиска по ответу
Делаешь бинпоиск по ответу. Потом для данного времени проверяешь, успеют ли они побывать на всех m дорожках. Это сделать нетрудно, так как каждая из головок в правильном ответе будет покрывать полный отрезок.
score distribution was so wrong
I wonder what's wrong with the score distribution?
A>B>C
Кто-нибудь писал в D div 1 sqrt-декомпозицию?
Задача на дерево Гомори-Ху на контесте КФ. Огонь!
Гомори-Ху FTW!
У вас отсекаются решения за квадрат поисков потока?
Возможно, что такие решения пройдут, всё-таки надо было большие ограничения ставить. :/ Структуру нам подсказал Gerald, и мы вместе придумали задачу на этом дереве.
Ну вот, прошли =(
One of the best contests I ever participated on CF. Less to code more to think :)
Один из лучших раундов. Особенно div2 задачи.
правда ли, что в претестах D div 2 ответ был только Yes?
I loved the round and absolutely loved the problem statements and setting 5/5
How could I approach problem C efficiently?
I only managed to deduce a formula for some special cases... If anyone could give me some tips that would be great :)
Thanks,
Bruno
f(a,b) = a/b + f(b, a%b);
But this might fail according to this
Good catch. (fortunately it passed according to given scenario)
The question permits only a.)one resistor; b.)an element and one resistor plugged in sequence; c.)an element and one resistor plugged in parallel.
so u only can add one resistor at a time to the existing element. (u cannot add two elements)
solve (a, b) = (b / a) + solve (min(a, b % a), max (a, b % a))
and solve (0, a) = 0;
Explanation: you assume that b >= a, then you will take (b / a) resistors for taking in series with other resistors, so cost (b /a) for those resistors.
For remaining you need to use 1 and x in parrallel which is a / b = x / (x + 1). which means x = a / (b — a).
Расскажите, пожалуйста, а какой ответ на тест в задаче 343A - Рациональное сопротивление:
у меня 15.
Ох я тупанул, там же "элемент и один резистор".
А я решал для "элемент и элемент".
И на этом тесте тогда получается 13.
Ой я тупанул :) вроде все верно решил :)
Как решать такой вариант задачи? Когда можно присоединять не только один резистор, а целый элемент?
Я не знаю, я сразу написал наивное решение, долго думал. Потом от безысходности решил заслать, как потом оказалось, правильное решение. Зашел в комнату, первый же человек, понятно, был с таким же решением. Решил взломать — неудача, решение вывело 15.
15 пишет.
Да, и вот, например, на тест 6 5, правильней ответ будет 5, а не 6, как у многих, кто уже получил AC (параллельное соединение из 2 Ом и 3 Ом) http://puu.sh/4raj0.png
В условии чётко прописано, что параллельно подсоединять можно только схему и резистор в один Ом, а не любые две составные схемы из резисторов.
А почему в задаче A div 1 правильный ответ на тест 6 5 — 6. Ведь можно расположить 2 резистора сверху и 3 — снизу. Получим 1/ (1/2+1/3) = 6/5. Или я в чем-то ошибаюсь?
Ответ чуть выше.
Да, я потом заметил. Просто долго писал, а удалять вроде нельзя
Cпасибо большое за раунд!
In Div1, problem A, in my room, I saw two people use %lld to read or write 64-bit integers in c++, so I hack one of them, but unsucessful. Does it mean is using %lld to read or write 64-bit integers is no longer banned? Maybe next time, the warning "Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier." can be removed.
%lldwas never banned. It is just recommended to use%I64ddue to historical reasons. With modern MinGW%lldseems to work as well.The warning cannot be removed as some people could be using old compilers on their own Windows computers, and then wonder why
%llddoes not work locally.I think that means "there exists at least one number when %lld will read not exactly the same as %I64d will under some compiler" rather than "it will always read wrong". So maybe you just didn't guess with hack :)
E can be solved by using Gomory-Hu algorithm. It takes the graph and in O(n * flow time) computes a tree such that maxflow from a to b is the minimum weight of an edge on a path from a to b (at first glance one can be amazed that such a tree exists but after some thought it makes sense). So we just have a tree and have to find a permutation that maximizes sum of the lightest edges on paths v_i -> v_{i+1} Answer to this problem is sum of weights of edges in such a tree. Just take the heaviest edge and use divide and conquer algorithm.
А мне может кто-нибудь объяснить зачем в D 500000? Чтобы опять любители Java шли лесом?
Чтобы отсечь корневую?
Разобьемся на блоки по
операций. Каждый блок обработаем за линию целиком. Осталось учесть влияние внутри блока. Это делается за 
запросов является ли a предком b.
Нельзя один блок за линию отработать, там порядок выполнения важен. Это можно как-то обойти?
Как так нельзя. За линию находим самое позднее опустошение в каждом поддереве, за линию самое позднее наполнение из предков и сравнили?
Наверное, голова сейчас вообще не варит ;D
Были опасения, что пройдут какие-нибудь корневые эвристики. Вообще-то, наше неоптимизированное решение на Java работает две секунды, поэтому мы посчитали, что 4 секунды разумное ограничение.
Мне кажется, что в этой задаче любые корневые эвристики написать сложнее, чем правильное решение. Я верю, что С++-style Java решение может работать довольно быстро даже без оптимизаций, но это же не повод
Ну по ощущением, то что я описал выше, будет где-то в два раза короче по коду. И придумалось раньше лично у меня.
Еще хотелось бы отметить — 2х для АСМ — нормально. 2х для подобного формата — годится только если есть макс тест в претестах. Возможно это стоит даже отдельного топика для обсуждения
Nice problemset!
Especially for problem E, the solution is quite simple (maxflow-mincut theorem) but it's hard to think in that way. :)
Thanks; the intended solution was to use Gomory-Hu tree, as Swistakk explained earlier.
I see. That tree can be easily obtained by analyze it in this way:
Suppose X-Y is a minimal cut of graph G. Then:
Then we focus on X and Y and do the same thing.
Exactly. That's how Gomory-Hu works :). But it's not straightforward to prove that these bounds are really the best ones.
Frankly saying, sometimes I really don't understand people's reasoning regarding to rating comments. I described solution to E and gen replied "Intended solution was as Swistakk explained" and got more pluses than me and few posts below cgy4ever explained Gomory-Hu algorithm and I said "yes, that's how Gomory-Hu works" and I got more pluses than him :P.
EDIT: Note that ratings I am reffering to may vary. When I was writing this comment cgy4ever's comment got +5 and mine response got +8, but now he has got +16 and I still got +8 :D.
It's even weirder when there are 2 comments below each other, both saying something along the lines of "good luck", one of them is rated around -50 and the other around +50. The only reasonable explanation is heavy trolling of some comments.
As for me, I usually vote minus on "spam" comments (those that only contain one of the usual phrases related to contests etc.), plus on comments that contribute something to me or are well written (that, of course, requires the comment to talk about something useful, meaningful) and for comments that are just random short replies or I'm unsure of how to vote, I don't vote at all.
Last Wednesday i took 10 random new neutral comments with 0 votes each, upvoted random 5 of them and downvoted other 5. In 12 hours first 5 had +2, +11, +5, +4, +8, and second 5 had -9, -5, -8, -3, -4 respectively. Funny, isn't it?
Yeah, that's one type of trolling. Just voting the more common option. Voting randomly is another common type. (In general, trolling is anything that isn't based at all on your view of the content.)
Not like we can affect it, anyway. And when one has large contribution, it starts only depending on blogs — comments have much lower weight, so unless you're getting like +50 or -50 for one comment, it doesn't affect contribution at all...
Первая красная точка! Спасибо авторам!
Хотелось бы иметь возможность на вкладке "запуск" запускать решение, используя генератор теста, потому что сейчас сложно проверить реальное время выполнения на тестирующих компьютерах на больших тестах, особенно с учетом новых компьютеров.
В качестве полумеры можно встраивать генератор внутрь решения.
Можно конечно так, но, во-первых, для этого еще что-то надо писать (и не забыть удалить), а во-вторых, чтение, например, 106 элементов (int-ов) занимает у меня 0.3 секунды, что немало
Rating update was quite fast! :)
Can anyone tell me why this code fails on time limit ? (Div.1 Problem C)
just my guess:
l1=5; r1=7; while (l1+1 < r1) { m1=(l1+r1)/2; if (true) l1=m1; else r1=m1-1; }Change
l1,r1andm1toint.http://codeforces.net/contest/343/submission/4472161
thanks )) but why?? :(
Большое спасибо, за удачный контест!!!
We want T-shirts : )
I wanted them too... ;(
физика доминирует
Почему нельзя разложить третий тест (199/200) задачи DIV2-C на: 1/50 + 1/40 + 1/5 + 1/4 + 1/4 + 1/4?
Соединить параллельно круга на 50, 40, 5, 4, 4, 4 резисторов. А потом их соединить последовательно? И того потратить 50 + 40 + 5 + 4 + 4 + 4 = 107 резисторов. Подскажите пожалуйста где у меня ошибка?
Потому что разрешено добавлять только по одному резистору, нельзя склеивать любые два элемента. В условии мы это подчёркивали как могли (; А общая задача, наверное, решается достаточно медленной динамикой.
А я сколько раз перечитывал, так и не понял... обидно
Согласно условию, последовательно (как и параллельно) можно соединять только элемент и резистор.
Any hints for Problem D div2 ?
My solution is prolly the easiest, though longer than optimal, to understand. I use linked list and remove ++s and --s http://codeforces.net/contest/344/submission/4465292
You can just use a stack and assign digits for + and -. Let's say '+' is 1 and 0 is '-' . Then you can do the following:
If current character's code(0 or 1) is the same as the stack's top, then pop, otherwise push the code in the stack. Then, if the stack is empty the answer is "Yes", and if it is not, the answer is "No". Here is my solution 4464633
i realy like div1 problem D , i think range assign with segment tree is not intended solution , is it?
It is actually, the core of the solution is to color some whole original tree subtrees in logarithmic time.
Time limit is 4 seconds , so i think that , intended solution is heavy — light decomposition.
Nop, time limit 4 was set for Java solutions.
i see.
The contest was very specific! It was about any kind of science: Chemistry, Physics, Math, ... . gen was right. It had questions for any tastes. :D
Is 21/10 a valid test case for Problem-C (Div.2).....?
acc. to me (7) and (3) in parallel results in (21/10) which equals to 10 resistors minimum. But acc. to AC soln's. ans = 12.
Pls clarify!!!!!!
You cannot combine 7 and 3 in parallel. According to the question, you can combine an element with just one 1 ohm resistor. Hence, combination of two elements in parallel in not permitted.
Thanks for the clarification ...
And 6/5 is also a wrong case. We can use (2) and (3) to get it: 1 / (1/2) + (1/3) = 6/5. So the answer should be 5, not 6.
You should read the statements more carefully.
There are only two types of combination:
1) x -> x + 1
2) x — > 1/(1/x+1/1)
There is no x,y -> 1/(1/x+1/y)
What a great contest, I really enjoyed it...
I tried to hack this solution on test case "++++" because of the intermediate state (s[2] == s[-1]), but no runtime error, why?
Well, since it's not Pascal with its range checking for everything, he just access whatever byte is before the char array. It is most likely accessible to the program (hence no segmentation fault) and since we have no idea what's in there, it can only possibly affect the code if there is '-' or '+', meaning that in at least 127 out of 128 cases it will run just fine.
thanks..i think i should ask this question to cpp compiler :P
What I liked about this round was that the problems were more connected to the real world than usually. Solving them almost felt like doing some actual work:) Way to go, gen!
I became red and feel very happy!!! And first I solved 4 problems. Div1 D was very very cool problem! (I could answer the different types of queries by using the same euler-tour array!!) That should be one of my most favorite problems!! Thanks for writer.
Where can we get an Editorial for this round?
Don't worry guys, we will complete it by evening.
Done, enjoy. ;)
I think no one wrote about the solution of Div1 D, so I write it.
third query can be said, "which was the last operation, adding water to the ancestors of the node, or emitting water from the children of the node?".
So we want to calculate two values -- the time of last operation no.1 which added water to the ancestors of the node, and the time of last operation no.2 which emitted water from the children of the node.
Both queries can be done with the different segment trees to the array of Euler-tour.
So we can solve this problem in O(Qlog N).
not O(Qlog N) , O(Qlog NlogN)
This can be solved in O(Q log N), but I know another solution whose order is O(Q log^2 N). (Actually I found this at first, but I thought it is too slow to get accepted and too hard to code, so I tried to find another solution.)
In this solution, we can use heavy-light decomposition or the general technique of merge the data structures like std::set.
The problems were interesting! I liked them!
Hello,
Anyone has any tips about Problem E for Div. 2?
I am totally clueless about it and still trying to grasp logic of problems C and D...
Hint for problem E Div. 2 (Read Time):
Try binary search the answer. For particular time T you have to determine if it is possible to read all tracks (p1..pm) in time T.
Another hint:
Thank you!
What a nice tag for the blog post :) "everybody reads tags" Thanks for the laugh!
I think there is an issue with Problem 343A — Rational Resistance. Here according to the editorial the answer to the ratio 6/5 would be 6(I have verified this with an accepted solution). But this ratio can be achieved with a resistance of 2 and 3 in parallel, which makes the number of resistors required equal to 5 which would imply the editorial and the system tests to be wrong.
Am I missing something here?
you cannot put resistance of 2 and 3 in parallel.
According to the problem statement you can only put Ro and Re in parallel where Ro = 1.