Всем привет!
Через несколько часов начнется Codeforces Round #164 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса.
Главным героем в задачах будет Манао, немало лет напрягавший умы грузинских участников. Добраться до страничек Codeforces ему помогли Gerald, помогавший мне в подготовке раунда, и Delinur, которая перевела условия на английский, за что им отдельное спасибо. Также задачи тестировали Seyaua, sdya и Aksenov239.
Распределение баллов по задачам немного нестандартное: 500-1000-1500-2500-2500.
Удачи :)
UPD: Соревнование завершено, поздравляем победителей:
Разбор задач можно найти здесь.
Have fun. I feel that it will be a good round
Infinite while, place in round decrement with only one when winning 100(successfull hack)+nb_point_of_problem, Problems solved over 9000 before "ProblemsSolved = min(ProblemsSolved,5);" and "good luck" after the end of the contest... And yes, I am very fun at parties.
Hi , gojira First contest at codeforces written by you :) , Looking forward for it. Some day I believe I will also write a contest for codeforces :)
Who is eligible for round preparation?
They have not mentioned any age restriction on the FAQ page. So I believe that there is no constraint except your problems should be interesting.
Yes but I saw somewhere Mike saying that they usually trust orange or orange+ users.
I really do not have such idea , Only Mike could clarify that whether there is some strict rating policy for writing a contest.
I had previously tried to submit problems for div 2 only contest , But as far as I think they were not as good standard as it should be.
http://codeforces.net/blog/entry/6290#comment-116753
But still if you are purple I don't think there is a problem .
Let me know when you get the answer
and what we will get in return...?
164 = 74 + 74 + 4 + 4 + 4 + 4
what does it mean?
too difficult, 164 = 74 + 74 + 4*4
164 = 47*4 + 4 — 7*4, palindrome :)
No, Round 164 div 2 == Round 82 == 82.
when i became a red coder :(
compile yourself first)
never give up :)
Капец вы все невтемщики хватить писать всякую понятную очевидную чужь, достали, я тут захожу чтоб почитать что — то, то что интересно или что — то смешное, а тут всякая чужь !
(a-b)^2 + (a+b)^2 = 2*(a^2 + b^2) => 2.5^2 + 3.5^2 = (6^2 + 1)/2 я это имел ввиду када писал убер задачу)
segodnia budet 164 raund rebita skora na4netsa u4astvuit 2322 vot tak vot
This is round 164 & 164 = 12^2 + 4^2 + 2^2 = 10^2 + 8^2 Here , 12+4+2=10+8=18 Again , 164 = 13^2 — 2^2 — 1^2 = 14^2 — 6^2 +2^2 Here , 13-2-1=14-6+2=10 What a combination :D
As, 164 = 12^2 + 4^2 + 2^2 = 10^2 + 8^2 , the problem points could be distributed like this --> 3000,1000,500,2500,2000 , as 3000:1000:500:2500:2000 == 12:4:2:10:8
Один я обновлял страничку с участниками в надежде, что наберётся 3000 ? :)
Да
Wow! So many participants!
pages of in queue. judges are down?
I am waiting in queue 3+ minutes.
everything is ok now.
Больше 300 решений в очереди, это нормально?
Уже начало проверять
My solution seems to be forgotten.
It's testing around 30 minutes
I hope I wasn't the only one who didn't know what expected value is :(
Как скоро разбор? особенно интересует задача D)))
Выложу скоро после окончания.
Спасибо за контест, жаль не добил задачу Д, интересен разбор, хотел решать графами, но не получилось)
В Д нужно было писать оптимизированный O(n*h^4) ?
у меня O(n * h3)
Ну там O(n*h^3) есть, а вообще я видел что O(n*h^4) заходят.
У меня был nh^3*128. Это планировалось?
Изначально планировалось только O(n*h^3) с маленькой константой, но так как на C++ O(n*h^3)-ные массивы свободно умещались в ML и TL, а на Java многомерные массивы тормозят и жрут много памяти, да и задача была не из простых, решили поднять ограничения. Хотя 128 конечно удивительно.
То есть сохранять кто был последним? Тогда там будет 3 дополнительных. Писал волну, которая должна была это учесть, но к сожалению она работала 37 сек :(.
Я хранил, сколько ступенек назад была ступенька в каждом из оставшихся направлений, и для направления последней ступеньки, валидное ли оно или по нему уже не забраться. Получалось [N][2][h+1][h+1][h+1].
Можно было уменьшить количество состояний, если хранить высоты отсортированными.
В Алмате экстремальный контест, 6,3 балла а мы пишем cf
Ага. Я допиливаю последние строчки С-шки, весь дом трясет(мы на втором этаже), люстра под потолком пляшет, на меня орут чтобы я на улицу выходил, а в ответ: "Ща С-шку сдам и приду!!!"
Combinatorics round with nice problems, I liked it! Thanks to the creators!
Спасибо за контест, особенно понравилась задача С :)
Дело было как) Я сперва думал что мое решение правильное, нашел в комнате паренька у которого решение выдавало не то на макс тесте. Решил взломать и тут бац! Оказалось перебор с sqrt не совсем правильно и тут понеслись взломы :) P.S. Все ждал когда меня взломают. Спасибо авторам за контест
Зачем нужен перебор с sqrt?
Ответ можно сразу выписать без перебора, главное понять, как это множество выглядит.
Даже если 1 ≤ n, m ≤ 1000000
Всё равно решение уложится.
На самом деле, я не знал, какой тест подобрать для взлома :) На маленьких всё было вроде правильно, а большие вручную не проверишь. Решил выбрать самый большой, не ошибся :)
Это был Я???
My solution was really forgotten(
It's still testing on the test1
Баг, скорее всего: когда идет систест, то процент(сколько завершено) не обновляется.
По поводу обновления статуса: добвляются какие-то древние посылки(6минута, когда уже показываются результаты 40-й)
Я заметил такое: нажимаю отправить, появляется страничка со статусом, решение идет где-то в тестах 6-7, затем опять показывает первый и по порядку.
ДА! ДА! ДА! У меня на Д зашло ТАКОЕ решение! 3029636 :)))
Ну ты крут)))
Спасибо, контест был довольно-таки интересным, несмотря на то, что задачи были скорее A-A-A-E-E. Кстати, кто как ломал C? У меня +3 тестом «6 6».
тоже самое, тоже +3 :)
аналогично) я еще одного по Б сломал на тесте 2000, у него было переполнение:D
int t; cin >> t; cout << (t * t * t + 5 * t)/6;
а формула довольно-таки интересная)
+5 тем же тестом
Can anybody help me in understanding the reason behind using comparision function ??
The change in expected total length from swapping the order of adjacent tracks [i] and [i-1] is equal to
since [i] might now be repeated due to [i-1], but [i] can no longer cause [i-1] to be replayed. Swapping has an effect on the expected playtime of these two tracks alone, so it's always best to swap pairs for which such a change is positive.
You could intuit that continuing to make such swaps would look a lot like bubble-sort (or rather, is bubble-sort); more rigorously, use some simple algebra to show that the expression above is consistent as a comparator.
and how do we calculate the expected total length?
A song will be replayed every time it is liked but a later song is disliked, plus the once the first time it is seen. We take the chance of being liked multiplied by expected number of later dislikes and add one:
I am new to codeforces , can anyone tell by when my rating willbe update :) ?
very soon, be patient ;-)
nice problems, enjoyed the contest
Hi gojira,
I really enjoyed the problems, thanks for the contest. I saw a lot of hacks for 3rd problem, that's good, thanks again ;-)
B.
Love win =) результаты(смотреть среди официальных участников)
9 successful hacks in problem 164C - Автоматное программирование :D it was really funny :D
9 successful hacks in problem C :D it was really funny :D
9 down votes incoming!
:D :D
Оперативный разбор
whew,that was really lucky for me,first time contest writer from my country first time div 1 ^_^
В задаче B зашло решение в 1 строчку(если не считать ввод и вывод): s:=n*(sqr(n)+5)/6;
Could not understand Problem B — Buttons. Can anyone explain it? words "push" and "press" are same? "some" does it mean single button or can be group of buttons?
Yes the words "push" and "press" mean the same. You can only push one button at a time and you need to output the maximum value of the number of times you can push the button, before getting the right permutation.
My submission with id 3029515 got wrong answer on first test case. But its giving the correct answer in my system
How is that possible?
http://codeforces.net/contest/268/submission/3029515
It really returns 2 on your system?
It returns 3 on my system which is the correct answer. On the judge it returns 2. It is pretty weird.
Are you sure? This line doesn't really do anything except check for floating-point error...
On my PC it works too, but on ideone it does NOT — http://ideone.com/ooqeop
In debug mode there is different output:
ideone:
my PC:
Thanks for the information. but this is very strange.
In 268A, I submit 3 times and get WA on test 6, which have the right answer is 6, but the system returns 83. Anyone can explain that for me ?
lines 27-28: instead of
should be
Thank for your suggestions
Поздравляю всех с новым рейтингом(пусть даже нехорошим)! Самое главное в соревнованиях такого типа я думаю "Опыт", а опыт всегда повышается! Поздравляю! =)
please can someone tell the way to solve problem C...
You can view all the sources here: http://www.codeforces.com/contest/268/status/C . To solve the problem, you must think of a greedy algorithm based on a mathematical observation. Good luck !
Editorial is already available.
Спасибо за раунд! Интересные задачи и понятный разбор:) Было бы интересно порешать Ваш див1-раунд.