Доброе время суток!
Поздравляем победителей и желаем всем удачи в следующем раунде!
Рад всех приветствовать на Codeforces Beta Round #69. Как вы уже догадались, это будет не совсем обычный контест.
Каждому дивизиону достанется по 5 задач. Некоторые задачи встретятся и там, и там; другие же будут предназначены для конкретного дивизиона. Но с точки зрения участника не должно быть разительных отличий от других раундов.
Обращаю ваше внимание, что подобный эксперимент проводится впервые, поэтому вполне вероятны некоторые технические трудности и неожиданные проблемы. Если такое возникнет, то прошу отнестись с пониманием. =)
И ещё: разбалловка в первом дивизионе будет 500-1000-1500-2000-2000. У второго дивизиона будет классический вариант 500-1000-1500-2000-2500.
Раунд готовили Alex_KPR, dagon и Marishka. Много полезных вещей делали RAD, it4.kp. Задачи переводила Мария Белова. Контролировал весь процесс Майк Мирзаянов.
Всем удачи! =)
_____________________________________
Не забудьте проголосовать, понравилось ли вам разделение по дивизионам, или нет =)
_____________________________________
Первые десять мест в первом дивизионе заняли:
Первые три места во втором дивизионе заняли:
_____________________________________
Первые десять мест в первом дивизионе заняли:
Место | Кто |
1 | vepifanov |
2 | KADR |
3 | hos.lyric |
4 | Zhukov_Dmitry |
5 | e-maxx |
6 | Romka |
7 | ivan.popelyshev |
8 | Shef |
9 | RAVEman |
10 | ktuan |
Первые три места во втором дивизионе заняли:
Поздравляем победителей и желаем всем удачи в следующем раунде!
_____________________________________
Опубликован разбор.
В четвертой не надо ничего знать, но надо аккуратно написать. В пятой нужно знать одну вещь, но зато задача - школьное упражнение на это знание.
Если бы они шли в порядке E-D, соотношение решивших могло поменяться в пользу E, я считаю.
...И контест ещё потом перенесли чуть-чуть.
Хочется сказать огромное спасибо анонимусу, ибо перезванивать посреди ночи и спрашивать, кто это был, уже как-то неудобно =)
Желаю всем рейтингового матча без багов в условиях задач и тестах:)
Чтоб удовольствие от отличного времяпровождения не испортилось от таких мелочей.
По-моему надо поправить FAQ. Там написано, что рейтинг 1500+ означает участие в первом дивизионе, на деле оказалось, что нужно как минимум 1650.
эксперименты это хорошо, но:
мне идея не понравилась.
Я всегда участвую в обоих дивизионах, хоть и отношусь ко второму.
Были бы контесты в разное время, была бы возможность поучаствовать и в 1-ом и во 2-ом.
Конечно, я на дорешивании решу несколько задач из 1-го, но хотелось бы в нём и поучаствовать.
ИМХО.
Условия, конечно, прикольные... Только легенды к задачам сочиняются чтобы облегчить понимание задачи. А у вас они иногда к задаче не имеют никакого отношения.
Например, какое отношение имеет попадание в цель наковальней к корням того квадратного уравнения? Физический или не физический смысл как-то найти сложно... Потому после 10-тиминутного чтения остается ощущение, что всё-таки я неправильно понимаю условие. И тратится ещё 15 минут времени чтобы найти хоть какую-то связь между условием и легендой.
Эдик, ну ты сам про себя всё знаешь ;)
А вообще у меня тоже раньше были серьёзные проблемы - я всегда умудрялся понимать условия не так, как все, и решать другие задачи ))) потом эта беда постепенно улетучилась
А в общем контесте подразумевается разделение дивизионов по комнатам?
Вот не понимаю, почему большинство голосовавших поддержало идею разделения контестов.
Если в общем контесте участники делятся по комнатам, то для div1 оба варианта совершенно одинаковы: они в своих комнатах решают контест div1.
Получается, что участники div2 проголосовали за то, чтобы не иметь возможности пытаться решать сложные задачи. А они что, вечно собираются сидеть в div2?
Я бы понял, если бы речь шла о том, что теперь всегда будет по 2 контеста. Но ведь контесты div2 only никто не отменял.
Потому что в раздельном контесте можно решить четыре задачи, а в общем только две. Первое делает человека более счастливым :о)
Писать сложный контест и решать в нем только А и В -- это не очень круто тоже.
Второй же дивизион при предложенном подходе сможет отработать пять идей по своему уровню. С чего Вы взяли, что они не будут иметь возможности решать сложные задачи? Напишут свой контест, потом прорешают div. 1. Вечно сидеть в div. 2? Ну что Вы. Подрастут, заматереют (всему своё время) — и пробьются в первый дивизион. И эта составляющая тоже очень важна.
По-моему, могут быть две причины столь поздней попытки осуществить разделение: схожесть с топкодером и увеличение затрат на организацию раунда.
Конфуций.
Я не о шансах сейчас, да и не о Петре конкретно, а о самой возможности выступать в соревнованиях определенного высокого уровня. Что при разделенных контестах станет не всем доступно.
А для начинающих, повторюсь, div2 only и возможность самостоятельно решать задачи с множества сайтов никто не отменял.
Претендуешь на высокий уровень? Имей высокий рейтинг.
4 взлома по B... 1 взлом по А, причем пример который в начале условия описан 2 5
ну что за люди пошли...:) халявные 100 баллов
Надо ограничение на претесты писать не в формате входных данных.
Хотел посмотреть может ли a быть нулём, смотрю в формате инпута: 0 < a, ну и заслал без этого случая.
Очевидное решение для отрезка (b,a), если он существует (там вероятность в каждой точке 1),
а для отрезка (0,min(a,b)) можно провести медиану и относительно нее "свернуть" так же, как при суммировании арифм. прогрессии сворачивают относительно середины. Тогда граничный переход в явном виде не нужен, он интуитивно очевиден.
Интересно, другие авторы тоже собираются этот приём (радикальное несоответствие баллов сложности задач) брать на вооружение или впредь можно всё-таки будет спокойно читать задачи в привычном порядке?
PS Еще никто не ругнулся по поводу того, что эта задача была на тему "кто знает, тот решит, а для остальных гроб". Даже странно. Или есть простое решение без инверсии?
C решается несложной динамикой по поддеревьям.
Пусть f[v] - количество бобров, которое мы можем съесть, спустившись в это поддерево и вернувшись в корень.
g[v] - количество бобров, которые останутся в вершине v, когда мы полностью обработаем поддерево.
Чтобы посчитать значения для вершины, поймем, в какие поддеревья и в каком порядке нам надо заходить. Понятно, что это выгодно делать в порядке уменьшения f[child(v)]. Пока есть возможность (т е пока в текущей вершине еще есть бобры), заходим по разу в каждое поддерево. При этом уменьшаем k[v], т к это цена возврата из поддерева. Если после этого бобры в нашей вершине еще остались, пытаемся попрыгать между v и каждым child(v) столько раз, сколько можно (min(g[child(v)], k[v]) раз). f[v] - это сумма всех накопленных величин, g[v] - это оставшееся k[v], если мы больше не можем совершать прыжки вниз.
If q > 0, equation x2 + q = 0 has no roots.
If q < 0, equation x2 + q = 0 has root
Can you please explain the case about 0 b
x2+q = 0
q<=0;
result = b/2b = 0.5
Саша, Саша... Ты обещал, что даже придирки все учли!!! Ты посмотри в условие задачи А, а особенно в формат вывода... Нельзя так писать!!! Я долго думал, а потом послал все-таки решение, где действительно выводилось то, что написано в формате вывода! Потом выяснилось, что надо верить тому, что написано в середине здорового условия, а не в формате вывода. Я не прошу сделать контест нерейтовым, попытку неудачную хотя бы уберите, пожалуйста.
P.S. Дословная цитата из условия:
Выведите два целых числа — минимальную разницу в опыте между персонажами, которые получат максимальное и минимальное количество очков опыта, и максимальное суммарное количество симпатий в группах (количество дружб между персонажами, оказавшимися в одной группе).
Ну ладно бы написали... Хотя бы в тестах из примера бы опревергли такое понимание. Нет же! Тесты из примера прошло на ура. Вот скажи, какие у меня могли быть после этого сомнения?! Я официально прошу мне и всем, кто послал такое же решение до правильного, отменить такую посылку. Я просто не знаю у кого это просить, поэтому прошу здесь.
Мораль отсюда такова. Надо не искать как можно больше интерпретаций, а решать ту задачу, которую имел в виду автор. Как ты будешь читать его мысли сквозь текст условия - это твои проблемы.
А можно вспомнить, что на финале у тебя будет условие на A4, где, вполне возможно, в первых двух абзацах будет только одно значимое (но очень значимое!) для решения слово, причём это будет слово thousand. Да и без этого в условии запросто может быть неоднозначность. И формат вывода надо будет восстанавливать из сэмпла.
Так, давайте разбираться. Такое действительно иногда происходит, но совершенно в другом случае. А именно, когда существует два разных правильных понимания условия! У нас же совсем иная ситуация. У нас (если очень формально подходить к пониманию) нет ни одного правильного понимания! Ваше понимание условия неверное т.к. в услвии прямо сказано что именно надо искать. Иными словами, вы что-то послали при неверное понимании условия, причем вы знали, что оно неверное. И с какой это радости эту посылку должны не засчитывать?
Поймите правильно, я никого не выгораживаю. Мы виноваты в том, что условие получилось противоречивым, а вот ваша вина в том что вы сделали посылку не уточнив, что же надо выводить.
Так я не понял перед посылкой вы видели что ваше понимание противоречит условию или нет? Если да, то вы знали что ваше понимание неправильное, если нет, то вы невнимательно читали условие.
Вы как-то сами себе противоречите, давайте уже определимся наконец что там произошло.
Так, я кажется понял откуда у нас с вами такое дикое непонимание...
Похоже у нас абсолютно разные определения того, что называется "верное понимание" условия. Вы, как я понимаю, считаете, что верное понимание то, которое у жюри, так? Я понимаю, что верное понимание то, которое следует из условия и не противоречит ему. Т.е. я считаю, что участник прежде чем решать задачу должен найти верное понимание. И он будет знать верное оно или нет. И вот если его верное понимание почему-то не совпадает с тем что у жюри, то вот тогда он может оспаривать вердикт.
Вообще, при противоречиях в формате инпута/аутпута и основной части я бы выбрал, все-таки, основную часть. Просто потому, что не первый раз примерно так и верно всегда описание в основной части.
P.S. в обсуждаемой задачи форматы читал мельком, диссонанс не возник и все сразу понял правильно.
P.P.S. согласен с мнением предыдущего оратора, ЛЮБОЕ неправильное понимание условия - камень в сторону жюри и авторов.
Применение его к данной задаче выглядит так. Если требуется оптимизировать по одному параметру, а при прочих равных - по второму, то это одна задача. Если же требуется оптимизировать по двум разным параметрам - то это две задачи. На кой ляд, спрашивается, автор бы хотел, чтобы участники решали одновременно две разные задачи, да при этом ещё и упоминал эти два параметра в некоторой связке в центре условия?
Что должно говориться в формате вывода? Помоему там должен быть именно формат вывода. Т.е. условие говорит что надо найти, а формат говорит как это вывести. Отсюда я делаю два вывода:
1. Пытаться понять что надо вывести на основании формата совершенно неправильно. И условия надо стараться составлять так, чтобы у участников даже мысли такой не возникало.
2. Надо стараться вообще ничего существенного не писать в формате вывода. То есть там должны быть фразы типа: "Выведите одно число - ответ на вопрос задачи" ну или подобные вещи, никак не комментирующие что это за число. Ясно, что когда вывод сложный, то так просто описать не получится, но надо стараться.
Неужели так трудно признать, что контест не прошел без косяков?
Нисколько не трудно. Более того, я это уже признал, да и Александр тоже об этом говорил.
Мне совершенно не понятно, зачем писать такую огромную легенду и разбрасывать части условия по всему тексту
Это сложный вопрос. Скажу честно, я тоже очень не люблю длинные условия. Для меня нет ничего лучше сухого, строгого, скучного, формального условия на пару строк. Но это тот случай когда в дело вступают личные предпочтения. Кому-то нравятся красочные условия с какой-то историей, более того различного рода легенды стали традицией в спортивном программировании. Тут видимо ничего не поделать и все будет зависеть от предпочтений автора той или иной задачи.
После трех-четырех попыток ужать фразу, я забила на вопрос (зачем так много букв?) потому что при следующем ужиме потерялся бы смысл.
Ну вот тут я с вами совсем не согласен. Ну не может быть такого, что вы не смогли сформулировать то, что вам не понятно менее чем за 1000 символов. Зачем было вставлять цитату? Можно своими словами. Русский язык достаточно богат чтобы в этих рамках выразить такую мелочь...
опаздал, уже ответили. удалил
Полное решение"? :o)На будущее: лучше делать скриншот не всего экрана, а вырезать кусок. На нетбуке кошмарно смотрится :)
В вашем коде проблема с vector<int> gr[3]. Вы объявляете этот массив локально, и считаете, что сразу после объявления там автоматически пустые vector<int>. На самом деле это не гарантируется. Это то же самое, что объявить локально int a[3] и рассчитывать, что там сразу нули. Если добавить в ваш код инициализацию массива пустыми векторами, crash исчезает.
И всё-таки, пока не поздно, я перейду на белую сторону. Там дело не в конструкторе, и не в массивах (чтобы там не писали, но запуском можно убедиться, что конструкторы и деструкторы вызываются для элементов локальных массивов). Возможно, это глючная сборка MinGW (которую я порекомендовал для языка C++0x), возможно проблема с GCC 4.6 (я это проверю как перегружусь), а может мы все плохо знаем C++, и этому странному поведению есть разумное объяснение, которое нужно найти.
Длинное доказательство :), но даже здравый смысл говорит о том что вы правы! К сожалению, как я уже написал, проблема не в этом, здешний GCC вызывает конструкторы не POD-типов в локальных массивах.
====================================================
Ну всё-таки международный стандарт С++ существует. Вижак глотает vector<vector<int>> потому что это фишка нового стандарта C++0x, GCC 4.3+ его также глотает с ключом “–std=c++0x”. По поводу конструкторов, то что я писал – это самая настоящая глупость. Когда мы пишем a = b; для старого значения a вызывается деструктор, а после – оператор копирования, и никак иначе! Тогда если объекты не будут инициализированы во время объявления, для неинициализированных значений будут вызываться деструкторы при первом же присвоении. А long double по стандарту не меньше чем double (а double не меньше чем float), и может на разных компиляторах или архитектурах отличаться так как implementation-defined.
PS: Баг исправили, код товарища SkorKNURE получает Полное решение .
А почему так пассивно плюсуем автора?
Кому-то не понравился контест?
З.Ы. считаю что в див2 было все отл. спасибо Александр
P.S. Обидно, конечно, что очевидная задача на инверсию стояла пятой (ну это, как говорится — сам дурак, читай все условия).
Как-то умудрился пропустить клар и весь контест фигней страдал=(
Не увидеть ни слов о том, что p и q вещественные (кстати, а были ли эти слова в исходной редакции условия?), ни слов о том, что a и b - целые, попытаться глянуть за выяснением этого момента на пример инпута, но вместо этого посмотреть на аутпут и увидеть два вещественных числа %) И решить, что a и b сами по себе вещественные %)
В спешке в задаче с наковальней глянул на ограничения претестов ( "а" там было строго больше 0) вместо общих, и задача упала на тесте где а==0
:-((
Snowy, Hex
Anka, Chapay, Cleo
Troll, Dracul
gives 89, 5
I didn't solve it too, but with another reason: inaccurately read problem statement and didn't round down x/y, so found best case in floating numbers. Fail
Split them as (Snowy, Hexadecimal) (Anka, Chapy, Cleo) (Troll, Dracul)
Может, в будущих подобных контестах лучше называть одни и те же задачи в разных дивизионах одинаковыми буквами (или начинать задачи 2 дивизиона с C или добавить буквы X,Y ко второму дивизиону)
Ну или называть задачи A1, B2 и т.п. - иначе будет возникать путаница в обсуждениях
Мне кажется, что, если на задачу есть одна попытка и оценивается только полное решение, то это издевательство, не давать участникам возможность проверить данные, которые пришлось вводить ручками.
содержимое претестов - это не элемент случайности, это просто информация, которой участники контеста не обладают, согласно правилам соревнований
Ну с точки зрения участника это тот же датчик случайных чисел. Вообще он как-то устроен, и в большинстве случаев это простой линейный конгруэнтный генератор, но можно считать, что числа равномерно распределены. Так и тут. Вообще, есть подсказки: имя автора задачи, предыдущие обсуждения претестов на CodeForces... Но в целом, если решение (своё или чужое) прошло претесты и нужно тестировать (чтобы себя проверить или другое решение завалить), одни придуманные тесты — пустая трата времени (есть в претестах), а другие — нет.
Пусть есть два хороших теста по задаче. Первый есть в претестах, а второй — нет. Если я придумал первый, но не придумал второй — я фактически теряю время, проверяя на нём себя или других. Если я придумал второй, но не придумал первый — то время проходит с большей пользой. Это можно назвать нежелательным элементом случайности.
Там не надо ничего вбивать -- проверяешь два верхних угла. Если только в одном О -- то в зависимости от того в каком и вертикальность фигурки.
Проверяешь верхний и левый центр, если в одном из них О -- то в зависимости от того в каком и вертикальность фигурки.
Иначе она работает в обоих направлениях.
Is there something wrong with GNU C++ 4.6?
Because in my Code::Blocks 10.05 with mingw IDE on Windows, no RTE!
vector<int> a[3];
You know, if int a[3] defined in function it may not be filled with zeros. So, vector<int> may not be empty and even valid, so you try to do something with invalid vector. Of cause, it's RTE.
May be Visual Studio initialize local variables, I don't know.
vector< vector<int> > g(3);
Thank you!
I don't think it's true. Rizvanov in his post above referenced to some site, not a C++ standard - that's not a good source.
And it looks like it's a bug in compiler, but not a "feature" of language. I think it's a nonsense when you can't simply use local array of structures or classes - should we call placement-new for each of them? I don't think so, C++ is not Java :)
I reported the bug yesterday, and today it was fixed (the problem was in optimizer - BTW all such programs crash only in O2, and this is another hint that this is a compiler problem, not a language's one).
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48695
Что за дискриминация?)
Вы посмотрите на этот график рейтинга. И пусть хоть кто-нибудь попробует сказать, что это менее труёво, чем сразу же быстрый взлёт в топ. Тут видно: чувак качался... и качался... и КАЧАЛСЯ... Ещё и TCO потом выиграл...
Посмотрел :)
Отсортируй раунд #8 по дивизиону #2 ;)
Все в первый раз там выступают...
"if there is a horizontal domino chip with its left half in column j then there are no horizontal domino chips with their left halves in columns j - 1 or j + 1. "
It's not equal to the second one.
Почему в старых контестах (например, в этом) нельзя посмотреть тесты?