Здравствуйте! Уже в ближайшее время состоится второй раунд, в создании которого я принимаю участие. (Первый был — Codeforces Beta Round 56.) Он будет несколько похож на предыдущий. (Но тот вроде бы был не так плох. :-)!) Надеюсь этот Вам тоже понравится.
Собственно я являюсь автором всех задач кроме одной, которую мне как раз предложил Gerald.
Огромное спасибо Gerald за всё, он постоянно улучшал мои задачи.
Так же соавтором со вчерашнего дня является cerealguy, который подготовил, на мой взгляд, самую сложную задачу в наборе. (Он стал соавтором после прорешивания первой версии контеста где-то за один час. :-)!)
Также благодарность pashka, который в самом начале подготовки оценивал задачи.
Конечно же спасибо главному переводчику кодефорсес — Delinur.
А также спасибо системам "Polygon" и "Codeforces" при реализации раунда
И без грибов не обойдётся и этот раунд!
Надеемся условия задач такие же короткие, как в первом контесте.
"Я не буду раскрывать пока, кто помогал готовить раунд"
Делаем ставки:)
Вот насчет "Просьба не пользоваться википедиями-шмедиями." — это официальное правило этого раунда (тогда надо об этом как-то более громко объявить), или это просто просьба?
Просьба.
Тогда это очень странно — вот вы, пожалуйста, не пользуйтесь википедией, и те, кто все-таки будут пользоваться, получат над вами преимущество
На самом деле википедия не должна помочь. :-)!
Предупреждение, чтобы участники не тратили на неё время, а решали задачи? :)
Author of this comment regrets about being so foolish.
17:06. Паника!О, если еще есть ресурсы на обновление поста, это еще не паника :-)
Edit. А, у нас... А у нас почему?
Призываются боги
Выпасаются овцы
Триангулируются пирамиды
Сбор ежей
Кто-то перепутал codeforces с twitter. Ну ладно, пока это хотя бы смешно.
где?
Виталик проникся идеологией администрации и решил тоже переписать историю. Все нормально.
Когда я писал, изменено еще не было, но вопрос уже был:(
Я не проникся. Я утомился. И переписал пост на нормальный...........
Кстати, в английской версии кто-то все-таки спалил участие cerealguy в подготовке раунда.
Потому что я в английской версии писал адекват. Чтобы иностранные люди не поняли насколько я неадекват. :-)!
Здесь тоже это будет.
...При создании задач несколько хлопьев всё-таки пострадало…(с)-здесь можно уловить тонкий намек на него)
And are there dynamic problem max scores used?
Same question as Betlista. How about the scores and order of problems?
Задачи будут сортированными по сложности или нет?
Мммм, пасхалки. Я люблю пасхалки)
..главному переводчику сия Codeforces?
..спасибо системам для реализации раунда??
Привет от старого доброго Prompt-a?
Пока "радость доставляет" описание:)
Русский — родной язык автора.
Именно. Я бы не стал иронизировать, будь это не так)
http://mirror.codeforces.com/blog/entry/4468#comment-90693
Да, кстати. Может, "главному переводчику ВСЕЯ кодефорсес", а не "сия"? Нет, может, конечно, я чего-то не понимаю, но в том случае, если это не так, попрошу исправить, ибо глаза режет)
What about the ordering of the problems? Are they arranged in the order of difficulty?
Yes.
Какой тонкий намёк на то, что D, по мнению некоторых, сложнее, чем E =)
Я что-то пропустил и за взломанное решение стали давать -100? UPD: это взломы, не туда глянул
Как решалась С? :)
a,b -> 3*a+b, 3*b+a = ((3,1),(1,3))*(a,b)^T Далее используем быстрое возведение матрицы в степень.
Сорри, я идиот. Не тот вариант контеста открыл. Приношу извинения.
Вы перепутали С из див1 с С из див2.
Да, я уже заметил. Мои извинения.
Если подумать, то можно увидеть закономерность — ответ для N это сума всех чисел от 1 до 2^n. Сорри, это С див. 2.
Только для n=10^18 это немножко долго работает). Я про 2^n.
Есть алгоритм русского крестьянина.
Вау, спасибо большое, даже не догадывался о таком)
Он позволит найти 2^{10^18} mod P, но не позволит просуммировать 10^18 чисел. Так что нужно еще вспомнить про сумму арифметической прогрессии.
а зачем суммировать, если там 2^(n-1)*(2^n+1)?
yermak0v предлагал именно "сума всех чисел от 1 до 2^n".
А так — каким образом можно додуматься до такой формулы сразу? Я пока вижу варианты — заметить закономерность, доказать рекурренту, свернуть в прогрессию; написать матрицу, найти ЖНФ, посчитать степень. Или я туплю, и можно сразу написать формулу?
Числа от 1 до х — это арифметическая прогрессия с d=1, a1=1.
Ну да. И нужно ее просуммировать (на бумажке). Видимо, я неправильно понял вопрос "зачем суммировать".
Увидеть, что в i-й строке i подходящих треугольников, а строк 2^(i-1), то есть ответ — сумма натуральных чисел до 2^n, то есть 2^n*(2^n-1)/2.
Ну, я решил так — всего 4^n треугольников, треугольников, смотрящих вверх, на 2^n больше, чем треугольников, смотрящих вниз. Таким образом, ответ — (4^n + 2^n)/2. Так что вариантов решения — тьма)
Author of this comment regrets about being so foolish.
Author of this comment regrets about being so foolish.
Author of this comment regrets about being so foolish.
сумма чисел от 1 до x считается за О(1)
Вот это — легко х*(х+1)/2
x*(x+1)/2
Бинарное возведение в степень? Не, не слышал.
Что такое ва5 в задаче D? Я на эту ***** больше часа убил, так и не нашел.
У меня то же самое один в один, но я хоть вовремя забил и сдал С. Ты когда считаешь k^2^d, то случайно может оказаться, что k делится на p, а 2^d — на p-1. Тогда k^2^d равно все-таки 0, а не 1.
Попробуй 5 2 2 5. Правильный ответ — 1.
Дима, вот я сразу написал брут в пять строк (пишу обычно невнимательно и с багами) и сверил с ним на мелких тестах. Гарантированно сдалось с плюса. Правда, пока проверял макс-тест, побеждал TL на джаве и переписывал на всякий случай на плюсы, прошло пол-контеста...
В C предполагались потоки или что-то поинтереснее?
Я решал динамикой за n^5 o_O
У меня какая-то фигня за квадрат, тесты вроде бы проходит)
Мою фигню за квадрат взломал Egor за несколько минут до конца...:)
Я взломал одну такую фигню, тоже претесты проходила) Не читая Ваше решение: проверьте на тесте
3
1 1 1
1 1 1
2 2
4
Проходит. Ну это тест такого же типа, что я ниже написал.
Правда, систесты не прошло.
А именно, можно динамикой узнать для каждых весов и каждого l, r, какое максимальное количество хлопьев может упасть в эти весы с отрезка от l до r.
А можно узнать подробнее? Я же писал максимальный поток (все w можно воспринимать как ограничения на вершинах), но естественно набажил без опыта.
Ну, для каждый весов и каждого отрезка можно тупо перебрать, какая (левая) часть отрезка пойдет в левые весы над ними), а какая — в правые.
вроде можно дп от четыерх параметров: [номер уровня][начало отрезка][конец отрезка][номер весов на к уровне] = true / false
могут ли упасть в весы на к-том уровне хлопья с отрезка
Если дп возвращает true, как много хлопьев падает на уровень ниже?
ну все хлопья с отрезка
Ну тот факт, что вершина может быть продавлена, не гарантирует, что все хлопья с отрезка могут на нее упасть.
да я уже осознал
Нельзя. Написал такое и час пытался понять что же не так. Контрпример: 3
5 1 5
2 3 4
2 5
10
На 10 попадает не весь отрезок 5-1-5 а только 5-х-5, потому нужна ДП не с тру/фолс а с числовым значением — какой максимальный вес с этого отрезка можно прокинуть.
есть такое дело(
Кстати, вопрос на засыпку — а есть ли какое-то решение через потоки?
Интересно на случай, если перед нами обобщенная задача, в которой реально динамику прикрутить трудно, потому что падает на те, которые не обязательно снизу, для некоторых перепрыгивает уровень и т.д.
Т.е., вопрос в том, как делать задачу "_найти максимальный поток, который для каждого ребра, по которому течет >0, удовлетворяет ограничениям снизу для этого ребра_".
кто-нибудь может объяснить, почему это решение получило такой вердикт?
Когда все равны нулю стоило выводитьs 0 0глупость.
или 0 0 0
Я уже испугался...
пофиг, что выводить. Расстояние все равно 1
когда все равны нулю, пофигу что выводить
1-1:D
с чего бы это стоило? да и тем более я видел решение именно такое, только на паскале
точность?
точность
Интересно, с какой максимальной точностью заходит. У меня 10^(-18).
10 - 12.
%7f -> %.7lf
выводите с большей точностью
да вроде итак просят с точностью 6, я вывожу один лишний знак
Там точность в логарифме, а не при сравнении самих чисел.
Точность у логарифма != точность у числа, так что не понятно
Требуются чтобы расстояние совпадало с точностью до 6 знака.
*логарифм расстояния, если быть точнее.
Расскажите, как дойти до этого решения, я туплю, видимо.
доказать для двух чисел и поверить)
Я так же делал. Смеюсь теперь над тернарниками, которые мои друзья писали)
Доказываем для двух(считаем производку функции x^a (s-x)^b), для трех не доказывал, должно делаться также.
Все просто :) нужно минимизировать функцию x^a y^b z^c при условии, что x+y+z=C. Вроде бы известно, что можно минимизировать не саму функцию, а её логарифм . тогда нас интересует минимум a ln x + b ln y + c ln z. Это обычная задача на условный экстремум. Составляем функцию Лагранжа L = a ln x + b ln y + c ln z + lambda* (x+y+z=C). Считаем частные производные, прицепляем условие x+y+z=C и вот оно ответ :)
максимизировать*
Ну да :) Просто привык, что обычно функции минимизируют. Да и тут собственно не важно, все равно только один экстремум.
Матан помнить полезно, оказывается...
Эх, чуть-чуть не успел еще одного поломать. Ставлю на то, что решение doraemon по задаче 185C - Хитроумная жирная крыса упадет на тесте
Правильный ответ —
Fat RatI hate hack announcement on prob A because of I misunderstanding with the problem :(
Спасибо за контест! Как решалась B(div 1)?
если a = b = c = 0, выводим 0 0 0, иначе S * a / (a + b + c), S * b / (a + b + c), S * c / (a + b + c).
интересно, а почему?
Сначала писалось правильное решение с тернарным поиском, а затем его запуском понималось простое решение :о)
Сначала брались бумажка и карандаш, потом включались мозги, а потом понималось простое решение
Вот блин, из-за тупого бага не сдал Е. Там предполагалось решение за O(NlogNlog(answer)) или такое не пройдет по времени?
Я вроде придумал решение за O(n log n) за 15 минут до конца.
Да, добавил один иф и прошло за 2.3.
М-да. Кошмарный для меня контест. В A не разобрал случай, когда строки разной длины, попросту не прочитав о такой возможности в условии. В B решал абсолютно другую задачу, 5 минут искал багу в том, почему же это моя программа выдает неправильные ответы на претесты. А потом так "погодите-ка, я же не ту задачу решаю!" :\ А что было в C я так и не пойму, пока не гляну лог. Первые две посылки выводили (4^n + 2^n)/2 по модулям, естественно. Неправильно. В третью посылку, уже ради прикола, отчаявшись в поисках баги, отправил (2^n + 1)*2^n/2 и это зашло. Непонятно..
В общем-то, думается мне, контест получился хороший, но, явно, не для меня. В любом случае, спасибо авторам за контест ;)
Вероятно, потому, что деление по модулю — это почти всегда не то же самое, что взять по модулю, а потом поделить. Можно поделить на 2, только если мы только что на 2 домножили и после этого ещё не брали по модулю. В общем случае нужно не делить, а домножать на обратное.
Ааа.. Ясно, спасибо. Я как-то об этом совсем не подумал, буду иметь в виду)
problem A was unclear until correction came. Why should we assume that we must make exactly one swap unless it is mentioned?
Problem C had problems too. Did the authors mentioned anywhere that we must count smallest triangles? though it is obvious after counting triangles in figure, it should've mentioned been in the statement. And also the problem was google-able,just find 1st few n's and search in google,you'll get this: http://oeis.org/A007582.
I understood "A" from the very beginning. Also, didn't see any problem with description in "C". Seems that problems were with translation=)
A was ambiguous. Some may understand correctly at first glance,some may get confused. I am unlucky and got confused :(. C didn't have any big problem,but they should've mentioned about smallest triangle.
You are looking answers for contest problems on google? Hm...
oeis.org have a collection of a huge number of sequences. Anyone could've find the formula. The fact i want to point out is "Contest problem shouldn't be google-able".
for the purpose of increasing your coding ability, it is the 'best' idea to come up with the solution on your own, rather than browsing through the web... also, once you are past some level, browsing through the web is not dramatically fast as browsing through your brain; one requires some physical effort under time-pressure while the other is almost purely mental (modulo writing things)...
You are right. But still my point holds: “Contest problem shouldn’t be google-able”. Once someone is almost sure that he'll find the answer in a certain site,googling is not a slow process!
why would you ever do that, if you are under a premise that you'd like to improve yourself?
your rating isn't going to go above certain threshold however hard you try to cheat.
Why are you minusing yongwhan posts? He's right. There are problems on onsites, where if you can use google — you can solve the problem. If you use oeis here — it's really cheating, because you shoud think it like onsite round without internet.
There are rules for Codeforces rounds and different rules for different onsite rounds. For example, on CROC onsite participants were also permitted to use Internet.
Either you set strict rules for your Codeforces round and make them clear and available before the round, or I don't see why one should treat using OEIS as cheating.
If you can come with a solution yourself, then does the problem really teach you that much?
If you search oeis and read the oeis explanation, does that mean you are not learning anything? oeis' entry about this seems quite interesting and you would be forced to learn a couple of things before implementing the formula.
Aren't you assuming that everyone's objective is to learn? In a contest with rating or prizes, sometimes the objective is do get a good performance. Because it IS a competition. And getting a good performance by using legal means makes you happy and proud.
Looking a sequence at oeis is actually quite a fair method to solve a problem. In fact, in the case of being a programmer, it is sometimes better not to reinvent the wheel. It is actually a skill to know yourself to be able to estimate when it is better to come up with a solution yourself, and when it is better to use a tool (oeis is a tool, as much as wikipedia and google).
I can assure you that a lot of guys had fuzzy memories about Lagrange multipliers today and used wikipedia to remember them. Hey, I actually did exactly that, but got confused when the Lagrange method in wikipedia used a = constraint instead of <= (Did not notice the obvious thing that in order for the result to be optimal then x+y+z=S). Without this confusion, I would have used wikipedia to solve D/B.
The ironic bit about this is shafaet_du's point is actually that problems shouldn't be googleable. Because he does not want anyone to be able to solve something by googling. So, in fact you two are arguing for the same thing. For a contest in which google isn't used to solve the problems.
But I do not really think the problem being googleable is a big issue by itself. It is a big issue when the problem is meant to be original. But this problem certainly was not meant to be original- just a linear recurrence, like any other.
Specially because oeis lists millions of sequences, and as such it is very difficult to make a linear recurrence problem that is easy and cannot be solved with oeis.
Is it really true that "At a certain level, browsing your brain is faster than browsing the web"?
I am not sure I would even remember STL syntax such as how to use upper_bound without google.
I agree. So what do you think about this contest?
Скорость тестирования прямо впечатлила и очень порадовала :)
Problem B — this is programming or math contest?
Common, it was very simple formulae, you can ask the same for C...
It's different. B is really about math
He meant problem B from div 1, not div 2.
Ou, I'm sorry, I didn't realize O:-)
Can somebody explain the solution of B?
Let
a_iis number of /\ triangle, andb_iis number of \/ triangle afteri-th day.Then (a_i,b_i)matrix((3,1),(1,3)) = (3a_i + b_i, a_i + 3b_i) = (a_(i+1), b_(i+1))
So, we need calculate (1,0)*matrix((3,1),(1,3))^n
Is binpow solution better ?
better than what? my solution is binpow, because you can calculate it for O(n)
Also, it is possible (it will be run-time better, but code-time worse) to transform this matrix to Jordan normal form, and get a formula for the task.
It turns out that just as with problem A, the solution can be found on Google along with an explanation.
I wonder if there was a traffic spike to that page today...
It feels that it is better to learn searching by Google instead of practicing on sport programming :)
Or you can do it that way.
if you are referring to http://mirror.codeforces.com/contest/185/problem/B, it's just an application of Lagrange multiplier.
very similar problem is given in Project Euler -- Problem 190.
Or just use AM-GM inequality:
Assume that a, b, c are not zero:
Equality holds when x/a = y/b = z/c
Edit: Thanks wack-a-mole for pointing out my error.
Shouldn't that be
? (The difference is
1/(a+b+c)instead of1/abcin the RHS of the inequality)but algorithm is a branch of math...
I respect math, but I find that algorithmic programming & logic tasks are different than calculating logarithms and using numeric math theorems.
There is a lot of number theory problems in algorithm contest. Got an AC of most those problems only needed a few lines. Just because the number theory is more discrete than calculus? But no one promise that all the problems is discrete ? I stand ready to meet new challenges and adventures in contest.
I used ternary search on B. (I got WA because of a silly precision error not related specifically to using ternary search, after fixing it, I pass)
just because x+y+z = S+1e-9 :(
I've also just managed to get my failing simulated annealing solution to pass, after changing the code to use iostreams instead of cstdio.
Just because I output #.-INF when the a, b, c are all zeros.
Hi Aksenov239
"Problem scores will be as always." is really misleading information, there are at least 3 score strategies — the one with constant score for each problem (defined by author), dynamic max scores and ACM scores. Also in constant score strategy there could be problems with equal max score (f.e. 500, 1000, 1500, 1500, 2500), so it's not always the same ;-)
Кто как решал А? Я написал быстрое возведение в степень матрицы, но видел что многие написали что-то покороче.
Ответ — это 2^n * ( 2^n+1 ) / 2
или 2^(n — 1) * (2^n + 1)
Неа, при n = 0 не проходит. Кстати, я на этом пролетел. Точнее поставил замок и не смог досдать.
Можно, например, заметить, что всего треугольников будет 4^n, из них повёрнутых вверх больше на 2^n.
Можно заметить, что разность между видами треугольников равна 2^n на n-м шаге. Ну а треугольников на n-м шаге 4^n, откуда следует простая формула
P.S. я тоже матрицу возводил))
Сначала не заметил, что сторона 2n, а не n, и вывел формулу
. Прочитал условие и прикрутил двоичное возведение в степень. :D
Я вообще только сейчас узнал, что сторона = 2n o_0
Мда, тернарник похоже писать плохо. А ведь у некоторых зашел...
У меня два вложенных зашли, если ты про задачу B.
Да я идиот, я вместо того, чтоб в логарифмах считать, считал втупую, и там Infinity вылезало)
А казалось бы, математик.
Кто? Я?
) ну, когда-то был, ко крайней мере: вот, например.
Палево
Тогда я про производные и логарифмы почти ничего не знал :)
Конкретно вот эта задача на нер-во о средних (выше объяснено, если что) — традиционно в лагере на неравенства, после 7-го класса. :)
Вы минимизировали исходную функцию, а значение этой функции не всегда влазит в double. S=1000, a=197, b=198, c=199 А вот вариант с логарифмами вполне заходит.
контест — УГ
Must write 12 digits after decimal point in order to got problem B right :| I don't think we need this tricky in an easy problem. It took me a lot of time thinking why my solution is wrong, and I don't have time to work on the other (more interesting) problems. :(
I was looking for such case, where rounding is problem, do you have some? I'm sorry, wrong div again O:-)
Yeah I wonder how the tolerance for div1 problem B works... My wrong answer was because the outputs summed to 814.0000000010 when S was 814. I thought it would be fine since ln(814.0000000010) — ln(814) < 1e-6.
я один сначала прочитал название задачи С, как "Хитрож*я крыса")
не материться после раунда ой как тяжело, но только на себя, к контесту претензий нет)
Кто-нибудь нашёл пасхалки?
Нашёл, по C тупой жадник заходит: http://mirror.codeforces.com/contest/185/submission/1660898
А он доказывается?
Да не, полная тупость с жадным рюкзаком. Тесты слабые :( Там идея очевидная: давайте получим множество предметов слева сверху и справа сверху. Попробуем сломать оба уровня сверху. Те, которые только слева кладём на левую чашу, которые только справа на правую. Остальные пробуем тупо жадненько рюкзаком распихать, авось получится.
Если можешь построить тест — убивать автора :)
Давайте. Плевать. Я устал уже.
6 1 1 3 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 9 15
Правильный ответ "Fat Rat", мой заходящий код выдаёт "Cerealguy".
Шестёрка должна быть суммой на каком-то префиксе, и нам её не собрать.
Ок, понял, спасибо.
Не надо никого убивать, тесты можно и добавить, главное чтоб авторское решение было правильным, а то там внизу ветки есть подозрения.
WOW!!! BLAZING SYSTEM TESTS :)
For Div1 problem C, what should the output be for the following input?
I thought the answer should be "Fat Rat", since all oats have to fall to the bottom to make the last scale break, but to make the two scales on the 5-th row both break, we need to have the 3-rd oat fall to (5,1) and 4-th oat fall to (5,2). But then (2,3) scale have to fall to both left and right, and doesn't satisfy the condition in the problem.
BUT the judge solution outputs "Cerealguy" (I know this since I wrote a solution that pass pretest, and hack other people's code with this testdata). Is there anything wrong in my understanding of the problem?
-
I find no mistake in your explanation. Are you sure with your hack input?
UPD : It turns out that judge solution is really wrong.
My solution, which passes system tests, fails this test.
My understanding of this case is:
(deleted wrong stuff that was taking up space).
Fourth 2 won't break the scales.
sorry, it was wrong
I asked the admin about a similar test (attached) after the match. The conclusion was that the author's solution is wrong ( :( ) and they are now trying to find a fix for this.
Edit: Sorry, I misread it.
Does anyone's solution return the correct answer for these two tests?
Mine does: 1658921
6
1 0 2 4 0 1
1 9 2 4 9 1
1 9 1 9 1
1 1 1 1
This test case should output Fat Rat, But your code output Cerealguy
Hack announcement ***** Unfortunally, your solution on C has been hacked :(
You know what? It seems like the best solution is mine. It's a coded in last minute and submitted for fun random solution, which got WA 49 (the same test as mentioned above). xD
And here is the star: solution.
But it is possible to hack it, of course :)
Funny, I wanted to hack it, but didn't manage to do it in the last minute because of slow connection. Now that I tried it locally, it gave the correct answer on my case.
I suggest you to replace 10024 with 7474, 7744 or some "lucky" numbers :)
Your joke is not very funny, as well as this little statistic:
Using 1 (one) iteration my solutions is getting WA 44; solution
Using 47 iterations my solutions is getting WA 49, as well as with 10024 (or 7474 or 7744 like you said).
Sad :(
Mine does too: http://mirror.codeforces.com/contest/185/submission/1659598 But it fails the test
8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
2 1 9 1 1 1 2
3 9 1 9 1 3
3 1 9 9 4
4 9 9 4
4 9 4
4 4
8
(returns "Fat Rat", and the correct answer is "Cerealguy")
So as it seems this is going to be unrated? Strange — two consecutive rounds (#117, #118), both having wrong author solutions.
this should be rated for division 2. there were only two people who got this correct; also, they should fix the solution and redo the system test.
it's highly disappointing otherwise; I think people in the community will start losing respect for CodeForces if the contest has problem, where the author's/test's solutions are wrong.
iff there is a test case in the system case that does not work using the judge solution should the decision of unrating the contest arise; even then, re-doing the system test may be a best option, to salvage people who did well in the contest.
Эх, какая неприятность. Надо мне знать тонкости python2. А то писал и тестил B на python3, а, как оказалось, целочисленное деление стало определяться как "//" только в третьем :(
Никто не подскажет,почему я не могу просматривать код участника,находящегося в одной со мной комнате, по заблокированной задаче?Когда я щелкаю по задаче,появляется окно с двумя вкладками: Код,История. Во вкладке "Код" вместо кода серый квадрат, а под ним кнопка "Взломать"
I got precision error in problem B even after printing 8 digits after decimal.I think in such problems the precision of output should be specified in the problem statement.
it was 'indirectly' given in the problem statement in terms of log; I calculated that printing 10 after decimal would be barely sufficient.
or you can say 'implicitly' instead of 'indirectly' :)
How did you get 10 digits? Do keep in mind it's natural logs.
Написал по задаче про грибных учёных естественное решение, получил WA на тесте 7. Долго пытался понять, в чём ошибка, не сумел. И увидел удивительную картину, когда открыли претесты:
Test: #7, время: 10 мс., память: 1380 КБ, код возврата: 0, код возврата чекера: 1, вердикт: WRONG_ANSWER Ввод 7 8 2 2 Вывод 4.66666667 1.16666667 1.16666667 Ответ 4.666666666666667 1.1666666666666667 1.1666666666666667 Протокол тестирования wrong answer X+Y+Z should be <= S. Found 7.0000000100.
Если присмотреться, то авторский ответ точно также должен получить WA, и по той же самой причине. Может, стоит оговаривать что-нибудь про округление чисел?..
В "B" у второго дивизиона написано "Выведите финальную таблицу результатов: n строк, каждая строка должна содержать номер соответствующего гнома и итоговую максимальную величину его гриба ровно с двумя знаками после точки. Ответ будет считаться правильным, если он абсолютно точный."
Здесь нет слово округлить, и я не округлял. А оказалось, что надо было. Все-таки неплохо было бы уточнять такие вещи(
А что там округлять? У меня решение полностью в целых числах.
Буквально еще месяц назад я не понимал, как это подло — не хватило минуты чтобы решить задачу на контесте. В последний месяц это превращается прямо в какую-то горькую иронию.
Hello coders,
is there a good tutorial about matrix construction for computation of sequences as in div2 C problem? I tried to find the matrix, but failed, so I solved it later using
formulae.
Thanks ;-)
Let A and B be numbers of up and down triangles. Then the transformation after 1 year is (A,B) -> (3*A+B,3*B+A). It is exactly transformation given by matrix T = ((3,1),(1,3)). Now you can calculate T^n % p, and write out sum of it first row.
But I'm not interested in that one concrete case. I'd like to know how to find such matrix in the future for another recurrent sequence...
You want to find y_n. You should introduce some additional variables x^1_i,..,x^m_i, so that you (y_{i+1}, x^1_{i+1}, ..., x^m_{i+1}) from (y_{i}, x^1_{i}, ..., x^m_{i}) is linear. Now you can write this dependence as multiplication by matrix, and use fast pow.
Many people enjoy hacking others..T^T I hate the input about “0”
Why? It gives you a chance to fix your code. I would have scored 0 points if yeputons hasn't been kind enough to hack my initial wrong solution :)
Is the contest rated?
Could any one explain the logic behind the problem D Div-2 ???
do the calculus..
For example, ternary search 1661095
@codeKNIGHT: You can use Cauchy Inequality One way to use it is to write x^a = (x/a)^a * a^a, and similar with y^b, z^c, then use Cauchy on P = x^a * y^b * y^c. We have the maximum value of P when x/a = y/b = z/c = (x+y+z) / (a+b+c) = S / (a + b + c)
could you explain more deeply.
Are you sure Cauchy Inequality. May be you actually meant Cauchy-Shwartz or Cauchy-Buniakovsky ?
I don't know what it's called exactly in the world, but in my country we call this "Cauchy Inequality": ((a1 + a2 + ... +an)/n)^n >= a1*a2*...*an for all non-negative numbers a1, a2, ..., an. Equality is hold when a1 = a2 = ... = an. You can try to apply it here: P = x^a * y^b * z^c = a^a * b^b * c^c * (x/a)^a * (y/b)^b * (z/c)^c = a^a * b^b * c^c * x/a * ... * x/a * y/b * ... * y/b * z/c * ... * z/c <= a^a * b^b * c^c * ((x/a + ... + x/a + y/b + ... + y/b + z/c + ... + z/c) / (a + b + c)) ^ (a + b + c) = a^a * b^b * c^c * (S / (a + b + c))^(a + b + c)
Edit: I think its name is AM-GM as peter50216 said in the post above :)
In my country (pele is from the same country as me) we use "Cauchy inequality" to talk about the inequality:
(a+b)/2 >= sqrt(a*b)(and also its general form)
I'm not sure about the international name of it :)
Edit: sorry about the double explanation. I typed so slowly :(
You can use Lagrange's method
задача В див 2. Объясните, почему на тест
ответ
? Разве, например, для 5 ответ не 6076.24?
(938 * 6) — (938 * 6 / 100) * 48 + 862 = 3788.56
Блин, могли бы в сэмплы добавить случай t1<>t2. Думал, что рост уменьшается на к% значит скорость после перерыва становиться на к% меньше.
Контест рейтинговый ? А то ждать не ждать..
А почему некоторые попытки выделяются в мониторе синим?
Выломанные
А почему тогда некоторые выделяются синим по-темнее, а некоторые по-светлее?
Блокированные/не блокированный вероятно. Только там не цвет, а жирность
In problem B, I failed a case because the sum x+y+z exceeded S slightly.
However, the statement explains how it will deal with precision errors.
"A natural logarithm of distance from the center of the Universe to the given point in the metric of mushroom scientists shouldn't differ from the natural logarithm of the maximum distance by more than 10 ^- 6"
IMHO, things should have been different. There shouldn't be a part that requires exact precision and another part that does not. It made me think that the only check I had to comply with in regards to precision was the logarithm one (and that case that my first solution fails, gives an answer with a logarithm that is within 10 ^- 6 of the optimum answer).
Another thing I mentioned to organizers during the contest. In one part, it says that 0^0 = 1. And in the other, log(0) = -inf. This was quite an ambiguity, because 0^0 suggests you to use X=0 when a=0, but if log(0) is minus infinite then the logarithm of you using 0 would be -infinity.
IMHO, instead of including arbitrary definitions for undetermined values, it was better to avoid a,b,c,s != 0 altogether. They did not really add that much to the problem (besides of the ambiguity).
I agree to vexorian completely. And, there's one more thing I want to say.
My first submission failed on pretest, and the Judgement Protocol says:
Why 4.666666667 + 1.166666667 + 1.166666667 > 7 AND 4.666666666666667 + 1.1666666666666667 + 1.1666666666666667 <= 7?
There's hidden output constraints? Or the judge's solution wrong?
Немного о взломах: я считаю что в коде нужно как-то отличать букву l и цифру 1, сегодня чуть не сделал неудачный взлом из за этого.
Нужно подсветку синтаксиса, давно ждём.
Ага, а ещё нормальный шрифт, нормальную прокрутку и чтобы без флеша работало.
А также возможность копирования и запуска на произвольном наборе тестов.
Интересная опция — запуск на произвольном наборе тестов =) Результат можно предсказать заранее: 95% RE при чтении, остальные WA/PE/TL.
пока авторы разбираются, что делать с C, расскажите кто-нибудь D, пожалуйста)
А с C есть какие-то проблемы?
есть
комменты не читай @ сразу отвечай
еще
Комментов много, нужный еще и на английском.
О жаднике: что он проходит — это конечно плохо, но не делать же из-за него нерейтинговым.
Почему бы и не сделать?
потому что если добавить тестов и пореджаждить, то в итоге это не повлияет на проведение контеста, как будто бы сразу было все ок.
ага, я за ^^
Проблема не в жаднике, проблема в том, что авторское решение неверно.
Авторское — не динамика 4мерная? Или она не верна?
Неверна.
Ну, звучит странно, конечно, но это же не повлияло на ход контеста? Если только оно работало правильно на претестах. Так что почему бы не сделать рейтинговым.
Если были взломы, на которых ответ изменился, то повлияло
И если задача без решения — тоже повлияло(в пользу тех, кто проскипал и решал D/E)
Ну, во-первых у нас общий делитель любых 2 — это либо 1, либо 2. Если 2, то надо в конце разделить на 2r - l. Теперь посчитаем произведение. Заметим, что если t = k2l, то искомое произведение — это (t + 1)(t2 + 1)(t4 + 1).... Если раскрыть скобки, то получим геометрическую прогрессию
черт возьми, раскрыть скобки я и не догадался :(
красиво-то как)
Что то же самое (может, кому-то понятнее) — домножить на (t-1) и раскрывать одну за другой скобки.
Спасибо жюри, за то, что они были очень отзывчивые и полно отвечали на все вопросы.
Сарказм или не сарказм? Ведь не угадаешь.
Вечно вы ищите, что-то плохое :) Они правда сегодня отвечали полно, как никогда)
особенно, учитывая мою беду со взломами =)
div2 problem d, just amazing! Who can explain why?
int main(void){ int S,a,b,c;
cin >> S >> a >> b >> c; if(a == 0 && b == 0 && c == 0){ printf("0.0 0.0 0.0\n"); return 0; } double x = a / (double)(a + b + c) * S; double y = b / (double)(a + b + c) * S; double z = c / (double)(a + b + c) * S; printf("%.20f %.20f %.20f\n", x, y, z); return 0;}
Arithmetic Mean >= Geometric Mean
so using Lagrange multiplier idea, we want to maximize
f(x,y,z) = x^a y^b z^c subject to x+y+z<=S; so,
we have Lambda(x,y,lambda) = x^a y^b z^c + lambda(x+y+z-S).
Now, differentiate this with respect to x,y,z,lambda assuming none of a,b,c is zero (otherwise, it becomes equation in 1 or 2 variable, which is simpler than this problem).
ax^(a-1) y^b z^c + lambda = 0 bx^a y^(b-1) z^c + lambda = 0 cx^a y^b z^(c-1) + lambda = 0 x+y+z-S = 0 (4)
then,
-lambda = ax^(a-1) y^b z^c = bx^a y^(b-1) z^c = cx^a y^b z^(c-1).
now, factoring out x^(a-1) y^(b-1) z^(c-1), we observe that ayz = bxz = cxy
so, setting xyz = P (and assuming x,y,z are non-zero), we can have
a/x = b/y = c/z
so, from here, it's obvious that
y = b/a x z = c/a x
now, notice that
x = (a/(a+b+c))S using (4); by symmetry, we deduce the other guys; when a+b+c=0, we notice that a=b=c=0, which means we can choose w/e respecting the constraint a+b+c<=S.
btw, for more variable, we have, obviously, xi = ai/(sum ai) S, which is really what this problem is trying to get at (at least I thought).
Thanks,
lagrange multiplier method, try to google or baidu this.
hi i saw a solution accepted in problem A and i have a test with fail , what have to do in this case?
Just resend newer solution.
UPD: if it's your solution ;)
If it's other's solution — you can double click on his solution, then press hack and send a test.
you should check it again and if you are sure post it here
i think something wrong with java compiler on codeforce. i get wrong answer on test 1 when in my compiler(eclipse jdk6) gives right answer. damn it :@ link to solution
yor compareTo is incorrect.
http://mirror.codeforces.com/contest/186/submission/1662152
Your solution with modified comparator which gives the Accepted .Link
Oh..sorry I think I was a bit slow in typing :-(
А раунд будет рейтинговый?
Наверное да(т.к. не сказано что будет не рейтинговым), хотя хочется что бы бил не рейтинговым!
Контест будет не рейтинговый для всех,или только для див 1?
C div 1, из-за которой весь сыр-бор, также и E div 2, так что если контест и будет нерейтинговым, то для обоих дивизионов сразу, конечно же)
Hi
I am seeing
printf("%.16f %.16f %.16f", x,y, z); this is how people have solved the problem
why this is wrong? printf("%f %f %f", x,y, z);
I am talking about Codeforces Round #118 (Div. 2), problem: (D) Mushroom Scientists
Insufficient precision.
But how was the precision decide in this case ?
Вот тебе и паника. :) :(
isn't the contest rated? why the rating doesn't update?
read the discussion above; the status, I think, is officially pending.
however, you are right that division 2 SHOULD BE rated; to be strict, after rejudge; there aren't that many people who got affected by this fatal failure.
Я не понял. Что опять нерейтинговый контест? Ну сколько можно? Это уже не смешно. Второй раз за последние 2 недели для второго дивизиона.
Ну свяжись с организаторами, сделай несколько контестов, все только рады будут=)
Я понимаю Ваш сарказм, но я только хочу сказать что обидно так второй раз подряд без рейтинга писать. )
Нерейтинговые контесты??
What's up with the rating?
There are problems with Div1C/Div2E — jury's solution is incorrect. This problem is under investigation and round can be unrated.
So it WON'T be rated?
Probably it won't be.
Both divs?
May be no, because not so many people have solved E in Div2.
I think this issue really only affected quite a bit in division 1, because many hackings and etc. failed and so on.
Considering very small fraction of people solved it in division 2 (1 or less / room in general), I really think the effect of this problem is minimal when it comes down to even hacking, let alone getting the problem correct.
Of course it'd be the best if the system test is re-run to make it perfect after getting the right solution out, I think division 2 should remain rated at the least.
Так как правильно решать С? :D
Сверху же написаны, вроде, все способы, и все верные. Самый простой и логичный — 2^n*(2^n + 1)/2, где 2^n ты считаешь с помощью бинарного возведения в степень, в котором на каждом шаге берешь результат по модулю.
Я думаю, речь шла про другую цэ :)
Он синий. Логично, что синий спрашивает про С с Див 2, а не про Див 1. Если моя стандартная логика здесь не сработала, то простите уж, но не стоило так яростно минусить, я так считаю -.-
Записываешь зависимость треугольников от предыдущих значений треугольников вверх и треугольников вниз: a[i] = a[i — 1] * 3 + z[i — 1], z[i] = z[i — 1] * 3 + a[i — 1]. Что довольно легко вывести. Затем записываешь матрицу перехода и замечаешь, что ее просто нужно возвести в степень. А у меня вот две первые упали...
Хм, и за что минусы? Не правильно? Я сдал это решение
Речь про С из другого дивизиона.
И эта задача решалась существенно проще, кстати.
It's not rated in div2?
So will it be rated?
Снова перетестили, все решения, которые не упали до этого, упали теперь. Неужто у авторов есть правильное решение?
Теперь бывает WA/57, WA/62. Вчера вечером, кажется, 55 или 56 всего тестов было.
Да, вижу, у меня у самого WA 62, а вчера AC было =)
Please, stop worrying about rating. We are working under problem "C". But it seems, that it is NP-complete. But all tests was right, because of their simplicity — we check them out with brute-force algorithm. There is only problem with hacks.
Contest will be rated anyway? o_O
We are thinking now about it. But if it will be rated, we will return all the right solutions, that passed systests. (Because systests — are right.)
What are you thinking about?? All problems must have solutions! In other case contest must be unrated!
Don't you think that every problem must have reference solution which works correctly and fast enough for every test within given constraints? Otherwise it is unfair to the contestants.
Yeap. I agree. And we are working under solution. And it seems, that brute-force algotithm works fine.
do you mean Polynomial brute-force algorithm that will be TLE just to generate the outputs? It will be unfair to the contestants. (just like RAD has just said)
Nope. Which don't get TLE.
But you just said that this problem is NP-complete! How come it won't get TLE?
Just good brute-force.
And I think, people, who was minusing my post, don't understand how hard to make contest without collisions.
Don't you understand, that other problems are high quality. Don't you?
We understand that the other problems are good (but still too mathy IMHO -- A, B, D are all about math). I also understand that it is hard to organize a contest without troubles. But you must accept that a fatal mistake on a single problem can ruin your contest and make people dislike it.
But it's very pitty, that they can't understand D and E, because of the problem in C.
It is just not very fair to rate a contest in which there was a impossible problem. In my case I am surprised that the rating is still being considered even after finding out that the problem is probably NP-complete. Just enjoying you had the luck that the system tests were weak to allow a very cropped bruteforce to pass does not really make it fine.
And this is regardless of how well or bad the other problems were. The quality of the other problems was just ok and I liked the contest, but that does not mean it should be rated. There were even hacks with wrong outcomes. The existence of problem C/E has affected the contest results in a negative way.
And do you want tutorial for this contest? (Without problem "C".)
I see no reason for not wanting to a tutorial.
I think, because almost all don't like this contest. :-)!
I see that somebody doesn't want. Ok. I will not do it.
No, no, everybody wants.
I see it by minuses. I'll do it anyway. Because D and E — very good problems.
Not really. Some people "minus" your comment on "almost all don't like this contest". It may just mean that, they don't agree with this statement.
And there are more upvote than downvote for "And do you want tutorial". So many indeed want to have it.
Personally I wish to know how to approach D, E, and the tricks in implementing B (not using a closed-form) accurately.
So please just let users some time to vote...
There are no very special tricks in B for using, for example, ternary search. Except that you probably need to handle 0 cases separately and if you can predict that the check x+y+z is done without epsilons, you have to solve for S-1e-9 instead of S to avoid your x+y+z turning greater than S in the judge's comparison.
I also checked against a*log(x)+b*log(y)+c*log(z) in the ternary search comparisons, but I am not sure this was needed.
Maybe I am writing this a bit too late. For the Triangle problem, you can solve without matrix exponentiation. Just form a recurrence relation in n of no of upper triangles. Solving it which is quite straightforward (but a little long) for anyone who knows basic math. The answer is 2^(n — 1) + 2^(2* n — 1). We can also think of a combinatorial argument for above answer which seemed to me a good exercise.