Мы хотели бы подробнее рассказать вам о финале чемпионата, который состоится 21–23 августа в Санкт-Петербурге. Заключительный раунд Алгоритма пройдет в необычном для IT-мероприятий месте — во дворце великого князя Владимира Александровича, построенном в 1870 году.
В финале лучшие участники чемпионата останутся один на один с тестирующей системой. Никакого интернета или заготовленного кода — только «чистая» машина и выбранная среда разработки. За их борьбой можно будет следить посредством текстовой трансляции.
Не откладывайте в долгий ящик регистрацию: тестовый раунд начнется уже завтра.
Ещё одна хорошая новость: мы решили почти удвоить количество сувенирных футболок. Теперь майку с символикой Яндекс.Алгоритма получат 75 лучших участников отборочного этапа и ещё 75 человек, выбранных случайным образом — из тех, кто решил хотя бы одну задачу. И, разумеется, все финалисты.
UPD: Тестовый раунд доступен для участников: http://algorithm.contest.yandex.ru/contest/306.
Зрители смогут следить за развитием событий, перейдя по ссылке http://algorithm.contest.yandex.ru/contest/306/standings.
UPD2 Результаты тестового раунда доступны на сайте соревнований
Удвоить? Было 100, а стало 175)
Прошу прощения, при переводе слово потерялось. Почти удвоить
Чёрт =(
Я так и знал, несмотря на многочисленные заявления в стиле "о боже, опять эти футболки, у тех, кто их получит, и так уже по 20 штук этих футболок", футболочку-то, тем не менее, хочется всем =)
А где ссылка на вход в тест. систему на этом сайте? Или она появится с началом раунда?
Появится перед раундом!
is this contest for Russian only ?
Not at all, statements and the official web site are avaliable in English as well. You can switch the language using button on the bottom of any page of official website or during the registration process.
I think I'm encountering 404…
В расписании написано, что Квалификационный раунд 8 июл 2013, 19:00 — 9 июл 2013, 19:00, длительностью 01:40.
Что не так? заходишь в любое время из этих суток, регистрируешься на раунд, и с этого момента идут 1:40.
Может я чего-то не понимаю, но ведь можно создать два аккаунта, "активировать" один пораньше, посмотреть задания, потом "активировать" настоящий и решать. Итого: продолжительность — сутки.
Так можно делать с точки зрения технических возможностей, но так нельзя делать по причине того, что нарушителей просто дисквалифицируют при обнаружении факта нарушения.
Да и о чем вообще Вы беспокоитесь? Если у людей, занявших 2000-2100 места на квалификационном раунде, и есть шансы хотя бы на футболку, то они, прямо скажу, призрачные.
В связи с появлением случайных футболок этот шанс возрос в бесконечное количество раз и теперь составляет примерно 4%.
Все равно нужно решить хотя бы одну задачу на отборочном раунде.
I am very glad to see that organizers decided to provide more T-shirts as prizes. I think it will greatly enhance the enthusiasm of contestants.
registration page is in russian .......how .i can register and there is no link..4 english ver
Here
thanks...
Where is the contest link?
http://algorithm.contest.yandex.com/
You mean contest will be held on this link??
I believe it will be held here on Codeforces but I'm not 100% sure because it doesn't mention anything on their website.
It's been updated here's the link. http://algorithm.contest.yandex.com/contest/306/
thank you!
На хроме очень тупят дропдаун списки. В частности,я не могу заполнить обязательное поле "уровень образования". Только не говорите, что нужно скачать Яндекс.браузер ;)
У меня самый обычный хром, ничего не тупит. ЧЯДНТ?^W^W Какая версия хрома? Может, Javascript выключен? Или какие-нибудь странные аддоны установлены?
Я пересел потом на ноут, но хром вел себя там абсолютно так же. Зарегался через ИЕ :)
У меня в хроме все нормально.
![](/predownloaded/24/d8/24d8496c5974255383944cdcafaa4eee26d6115a.png)
Версия хрома 27.0.1453.116 m.
У меня тоже были в хроме бесконечные тупняки с дропдаунами, выражалось это в том, что необходимо выбрать 3 значения в них, но при изменении любых двух третий переставал работать :) Я раз 5-6 обновлял страничку и в итоге получилось :) Дерзайте!
Хм... для компиляции Delphi используется fpc. а он Generics.Collections вроде не поддерживает. Опять Дельфийсты в пролёте.
Не оно? http://wiki.freepascal.org/Generics
Только что накидал простое приложение с TDictionary и подключением как в Делфе из uses Generics.Collections. Свежеустановленный fpc 2.6.0 ругается на ненайденный Generics.Collections
На страничке говорят, что у них это в модуле fgl...
Видимо господа минусующие знаю как научить fpc понимать Generics.Collections, но в силу природной скромности об этом молчат. Либо это организаторы, к-е написали о поддержке Delphi без указания версии.
Организаторы всё честно написали:
А вы наверное разучились пользоваться гуглом и читать ответы: вам же сказали, что в FPC есть только модуль fgl, который ограничивается TFPGList, TFPGObjectList, TFPGInterfacedObjectList и TFPGMap. И это совершенно нормально — C++-ники ведь не жалуются, что у них boost'а нет.
Тогда зачем заявлять в поддерживаемых языках delphi, если он не поддерживается нормально.
Что значит "нормально"? Язык — это именно язык, а не всякие библиотеки. Поддерживается именно синтаксис языка Delphi (который существенно отличается от обычного паскаля). Не вижу в этом особой проблемы. Если вам не хватает prewritten generic списка — могли бы и сами его написать ;)
Я может быть тупой, но по-моему если язык заявлен (и причём без номера версии), то это означает что я могу писать в любой среде, которая поддерживает этот язык и быть уверенным, что у жюри всё скомпилируется. В данном случае я не могу использовать, например, RAD Studio XE. Тогда надо было написать что поддерживаем Delphi <=7 или, допустим, компилятор совместимый с dcc32 такой-то версии. Или вообще убрать delphi.
Вы никогда не можете писать в любой среде, "которая поддерживает этот язык", и быть уверенным, что всё скомпилируется (для любого языка). Например, потому, что в вашей системе могут быть установлены дополнительные библиотеки. Когда пишете код — надо всегда думать головой, прежде чем использовать какую-то библиотеку.
Пример: заявлен язык Java, я хочу писать в IntelliJ Idea, а у меня там подцеплено 100500 сторонних библиотек (например, sat4j). Я же не буду жаловаться, что у меня ничего не скомпилируется, если я их буду использовать.
Надо различать язык программирования и библиотеки, какими бы популярными они ни были. И уж тем более надо различать язык программирования и IDE.
http://ru.wikipedia.org/wiki/Обобщённое_программирование
Обобщённое программирование (англ. generic programming) — парадигма программирования, заключающаяся в таком описании данных и алгоритмов, которое можно применять к различным типам данных, не меняя само это описание. В том или ином виде поддерживается разными языками программирования. Возможности обобщённого программирования впервые появились в 1970-х годах в языках Клу и Ада, а затем во многих объектно-ориентированных языках, таких как C++, Java, Object Pascal[1], D, Eiffel, языках для платформы .NET и других. Смотрим сноску 1: "↑ В Delphi и PascalABC.NET" В Delphi есть обобщённые типы и они по дефолту хранятся в Generics.Collections. Если в fpc их нет по этому адресу — он не поддерживает delphi последней версии. Факт?
В английской википедии в статье про Object Pascal: The Delphi language has continued to evolve over the years to support constructs such as dynamic arrays, generics and anonymous methods.
Представьте что было бы если бы заявили что поддерживают C#, но без указания версии, а при сдаче задач все увидели бы что у жюри .NET 1.0 без System.Collections.Generic — вой стоял бы. А с Delphi так можно поступать. Все делфийсты — не программисты, я знаю.
Да блин, вы демагогией занимаетесь. В fpc есть generic'и как возможность языка. Там нет библиотеки с заранее написанными классами, которые по случайному совпадению оказались тоже generic'ами (а точнее потому, что кому-то захотелось скопипастить^W портировать некоторые библиотеки некоторых других языков).
Требования к стандартной библиотеке C# входят в спецификацию языка; спецификации языка Delphi похоже вообще не существует, но если вы её сможете найти и там будет требование "должен присутствовать System.Collections.Generic" — тогда ваши претензии можно будет рассматривать.
Тесты к задачам будут видны?
2337 submission for problem A only 109 got Accepted !!!
most people had precision errors
even I used a user-defined function for comparing that didn't work
Maybe someone could comment how to solve A? Especially those, who got it right at the first attempt.
do you mean R=(abc)/(4*S) or R=(4*abc)/(S)
Of course
, it was a small typo.
you didn't fix the other fraction in your comment :)
It does not matter for solving :)
actually yes it's like you multiplied all fractions with 16
a and b and c themselves may not be integers how can we save the numerator in integer variable ?
Edit: oops got it now , also S may not be integer but 16*S is always an integer
a2 = (x2 - x1)2 + (y2 - y1)2, and so on. (2S)2 = ((x1 - x0)·(y2 - y0) + (x2 - x0)·(y1 - y0))2.
But numerator's maximum value can be (1400)^6 which will cause overflow even for unsigned long long int. How to store the value?
2^63 is around 9*10^18
1400^6 is around 7*10^18
Пара комментариев:
Хочется отправлять задачу со страницы задачи.
Хочется, чтобы система запоминала, что я отправляю копипастом.
Выбранный язык не влазит в селектбокс. я вижу только GNU c+
Это фича, что на Jav'е в F ML при сортировке массива long/Long ов?
Да, у меня тоже был ML. Жюри утверждает что у них есть решение, укладывающееся с тройным запасом..
Не, я верю, что можно например входные данные ручками парсить, а не создавать кучу строк а потом Long.parseValue, но вопрос нахера? не покидает меня.
Как вы все умудрились там ML получить... У меня 14.97Mb, и я ничего специально для экономии памяти не делал. Неужели ArrayList вместо long[]? Я бы такую штуку на полмиллиона побоялся сортировать не только из-за ML, но и из-за TL :)
http://pastebin.com/5HZe6i1e
Хм, неужели это из-за парсинга? oO Как я рад, что когда-то написал нормальную парсилку для контестов.
Ну тупо же — в String считана вся строка с вводом. 2 байта на символ. По 20 символов (учитывая пробел) на число. Еще вопросы?
20*2*500000 = 20M
Размер StringBuffer'а, в который читается строка, несколько больше реального размера строки (он расширяется в два раза). Затем еще происходит копирование в строку. У нас уже 4 мегабайта убиты на массив лонгов. Ну и стандартный Java оверхед. А так я сам не понимаю мемори лимитов в 64 Мб, я надеюсь, что здесь это for legacy reasons
Вроде бы Олег обещает 256 на остальных раундах
Спасибо, с более аккуратным парсером заходит.
а в чем разница ArrayList и Long[] ? Вроде ведь оба должны сортиться одинаково?
ArrayList и Long[] — зло. long[] — ftw. В первых 2х случаях у вас промах кеша при обращении к любому элементу; это всё равно что int*[] на С++ сортировать.
long[] тоже валится по ML (см. мое решение)
Моё решение. Выходит, виноват не ArrayList, а парсинг... Впорос в том, почему оно не собрало мусор. Возможно, имеет смысл изменить параметры запуска, чтобы программы на java собирали мусор при приближении к ML.
А нету там мусора. Есть факт, что весь массив в одной строке и она читается через readLine
Ааа, я сразу и не заметил. Спасибо.
Эээ.
Во-первых long[] как оказалось не ftw, MLится. Я понял, что вы предлааете использовать ArrayList, но не понял в чем может быть преимущество перед Long[], который тоже МЛится (а на Java6 TLится)
Во-вторых, Причем здесь массив указателей — не понял.
UPD: короче, понял предыдущий коммент не правильно, не актуально
Я не предлагаю использовать ArrayList, я предлагаю использовать long[]. "Long[]" и "long[]" — 2 большие разницы; первое — это, грубо говоря, "long long*[]", второе — "long long[]".
Спасибо за feedback. Отправка со страницы задачи будет. Запоминание — скорее всего да, с селектами подумаем, как лучше сделать.
Вопрос к авторам контеста: зачем нужно было требовать в А использование длинки?
я не автор, но длинка там не требовалась
Зачем там длинка?
Я решал по формуле R = a * b * c / (4 * S), а т.к. длины не целочисленные, находил я R^2. Итого на тесте 0 0 1400 0 700 1400 числитель дроби получается больше 10^19, что в int64 не влазит.
1400^6 < 2^63
А каждое множитель не надо на 2 умножить? Там же x * x + y * y
если точки (0, 0), (1400, 0), (1400, 1400), то 2 * 1400^6 > 2^63
2*1400^6 < 2^64 :)
1400^2 * (1400^2 + 700^2)^2 > 2^63
1400^2 * (1400^2 + 700^2)^2 < 2^64
Я не на сишке пишу :).
Ну если на джаве — то BigInteger, если на C++ — то unsigned long long. Не вижу никаких проблем, всё в стандартные типы влезает.
Я тоже проблем не вижу, написал в лоб на биг-интах. Переформулирую исходный вопрос: идея задачи была как раз в том, чтобы не получить переполнение? Или она все-таки подразумевалась как тупая халява, но авторы перемудрили?
Задача на корректный выбор типа данных, то есть авторское решение — решение в unsigned long long. Приведённый ниже тест против double "случайно" в тупой халяве появиться мог весьма с малой вероятностью...
Мое решение с long (на Java) прошло.
Скажу по секрету, в signed int64 тоже проходит :)
решал точно также с unsigned long long зашло
Там не нужна длинка, если хранить в виде дроби.
У меня другой вопрос. Как в А построили такие дьявольские тесты?:)
Нахожу центр через серперы в даблах — ВА. в лонг даблах — ВА. Играюсь с точностью — ВА. Нахожу через формулу Герона — ВА. Пытаюсь все в целых — не влазит в ансайнд ЛЛ.
В результате внезапно зашло следующее — подсчитываем все в целых числах, кроме собственно числителя и знаменателя радиуса, их в даблах заносим. Сравниваем с точностью 1е-10. Почему это работает, а другое нет?..
Считал по формуле
. 4 не нужно, возводим в квадрат. Получается
. Площадь считается как векторное произведение. Числитель порядка 8 * 1018. В чем проблема?
В этом решении действительно все хорошо. Проблема в том, что мало какие другие заходили. Даже не проблема, а вопрос, что это за тесты, в которых при координатах до 1400 потеря точности в abc/4S столь велика, что их нельзя нормально сравнивать с точностью и предполагалось, видимо, решение в целых.
(0,0) (1312,164) (134,1372)
(0,0) (1351,169) (106,1317)
Разность радиусов меньше 2^{-52}
Ни...чего себе) Спасибо
(abc)^2 ~ (2*1400^2)^3 > 2^64
Там координаты положительные.
а сторона 1400sqrt(2) при этом все равно достигается
а откуда 1400, а не 1000?
Можно спросить об этом у авторов
У треугольника (0, 0) — (0, 1400) — (1400, 0)
, (abc)2 = 2 × 14006, только в беззнаковый 64-битный тип влезает.
В общем-то, от "белорусских, японских" и особенно "польских профессионалов" этого стоило ожидать.
Считал по формуле:
..и пока не смог понять, на каком сэмпле точности double не хватит, чтобы адекватно сравнить два радиуса. Кто-нибудь поможет придумать контр-тест?
Там можно решить в целых числах без длинки.
Используем формулу
.
Посчитаем a2, b2, c2 (очевидно как) и 4S2 (через векторное произведение).
Все эти числа влезают в long long.
Теперь надо эту дробь xyz / t нормализовать.
Сначала поделим x и t на их gcd, потом то же самое сделаем с y и t, z и t (это делается последовательно, а не одновременно).
Теперь надо просто сохранить пару xyz и t. c t все нормально, а вот xyz все же может чуток не влезать в long long — это можно сохранить в виде 2-3 чисел по разным взаимно простых модулям (я взял 264 и 109 + 7).
Можно без НОД-а аналогично по модулям сравнивать дроби домножив на знаменатели (R[i] * abc[j] == R[j] * abc[i])(mod p)
Вот смотрю я на ratio accepted/submissions (4.6%, 2.7%, 44.3%, 6.8%, 16.7%, 8.8%) и думаю, а нужны ли такие контесты вообще...
UPD: О, оказывается для прохода дальше, надо было либо решить С в закрытую до 30й минуты, либо решить С в открытую до 9й. Качество зашкаливает.
Может кто рассказать решение F? Мне пока не удаётся обломать своё.
вроде традиционное ratio на вид, хоть для топкодера, хоть для codeforces. разве нет? :)
Ну, откидываем лёгкую задачу. И остаётся 5 задач с ratio < 10% (16.7% — её только tourist и сдал). Ну и получается лёгкая задача, а все остальные либо геометрия с погрешностями, либо конструкционные задачи, либо имплементационный case-work. Я таких комплектов ещё не видел.
А в E какие проблемы? Разве что файл повторно открыть...
Ой, да. Я почему-то в эту таблицу запихал ещё и забитые/пропущенные голы. С ними побольше кейсов. Меньше футбол смотреть надо.
В любом случае, имплементационный case-work. Согласен, что если бы народ решал эту задачу, ratio у неё возможно был бы нормальный.
Пока мы находимся левее автопарка, всегда выгодно брать самую хорошую машинку — это можно доказать, просто сравнив, куда мы доедем, если будем две машинки использовать в одном и в другом порядке.
Далее, если мы очутились правее автопарка, нам всегда хватит ровно одной машинки, которая может проехать М-Д.
Собственно, все. Либо пытаемся жадно доехать до финиша, либо исключаем самую медленную машинку, которая может проехать М — Д, и пытаемся жадно доехать до автопарка.
А если крутая машина нужна, чтобы доехать после автопарка, но мы ее уже заюзали?
Мы сначала выбираем из всех машин, которые могут проехать второй участок, самую плохую и не учитываем ее дальше
цитирую:
"Либо исключаем самую медленную машинку, которая может проехать М — Д" (читай — после автопарка) "и пытаемся жадно доехать до автопарка" (то есть — теми, которые остались)
А что с кейсом?
Ответ 2, а такой алгоритм получит 3, если не рассмотреть остаток слева у этой выброшенной машины.
У меня в решении еще есть бинпоиск, я забыл об этом упомянуть.
А для фиксированного количества машинок:
Скажем так, у нас есть некий универсальный код прогонки для последовательности машин. Мы его запускаем дважды — один раз для отсортированной последовательности, второй раз — для отсортированной последовательности, в которой один lower_bound(m — d) вынут и вставлен в конец. Берем минимум из двух ответов. (Ну, это внутри БП)
работает такое что выбрав самую медленную машину как описано выше, нам уже жадно надо доехать не до автопарка, а чуть раньше — позиция автопарка минус избыток расстояния второго участка пополам
Это у меня и получало WA 16. Возможно я забажил.
Я написал именно это и получил WA10.
UPD. А, все понятно. Я забыл про случай, когда мы можем сразу доехать до финиша из какой-то точки, кроме начальной.
WA10 — это вроде то, что можно "припасенного" чувака заюзать чуть раньше, пока не доехали до d, но уже можем доехать до конца
ОК, спасибо, вроде тоже самое...
Какие есть пограничные кейсы, если мы исключаем самую медленную машинку, которая может проехать М — Д?
Я рассмотрел остаток у этой машины (последняя может забирать уже с точки чуть левее Д), а также если мы вдруг и без последней доедем до финиша. Я что-то пропустил или просто зафэйлил в реализации?
Выбираем наименьшего чувака на котором можно уехать на последнем отрезке. Потом набираем жадно с больших. Случаи кое-какие нужны, правда. Код
Рассмотрим 2 случая:
1) m = d, т.е. база такси находиться в конечном пункте. Понятно, что выгоднее сначала ехать на тех такси, которые могут отвезти дальше, поэтому отсортируем x по убыванию и промоделируем поездки.
2) m ≠ d. Весь путь можно разбить на две части — первая от начала до базы такси, вторая — от базы к конечному пункту. Для проезда второй части нужна одна машина с запасом большим равным ее длины (если такой нет, то проехать нельзя). Найдем минимальную такую машину и отложим ее в сторону. Отсортируем х (без отложенной) по убыванию. Снова будем моделировать, но на каждом шаге проверять не хватит ли нам отложенной машины доехать до конца.
При этом нужно учитывать случаи, когда:
текущая машина не может доехать к нам.
мы уже приехали и отложенная машина нам не понадобилась.
Код
Это тестовый раунд. Задачи не оригинальные, а когда-то использовались на этапах кубка (или еще где). Задача была проверить систему под нагрузкой
Can i have the test case 9 for problem A?
Tests are usually not disclosed in this type of competitions. It decreases motivation to prove your theoretical solution and test/debug your code.
We decided to publish the competition archive, you can find it at the competition site
Расскажите, пожалуйста, решение задачи D
У меня зашло перебором)
а Вы можете подробнее рассказать
Пусть у нас будет рекуррентная функция F(N, From, Del) — N текущее число, From — минимальный делитель который можно взять, а Del — вектор для чисел из текущего ответа. В ней перебираем следующий делитель и запускаемся соответсвенно F(N/d, d+1, Del + {d})
А вот поясните пример с 4. Вот Вы сначала в ответ положите 2-у, что неправильно. Или я что-то неправильно понял??
Суть перебора в том, что он проверяет все варианты. Мы пробуем положить 2, и тогда запустим F(2, 3, {2}). Из-за того, что из двойки разложение на делителей больших 3 нельзя, то этот вариант отбросится. Попробуем положить 4, тогда F(1, 5, {4}), а это уже "крайний" случай.
Найдём все делители числа N. Затем, для каждого делителя найдем его делители, просто перебирая найденные делители до корня. В итоге мы перебираем все тройки i, j, k, что div[i] * div[j] = div[k] (если div[k] делится на div[i], то j можно найти бин. поиском зная div[j]). Добавим в вектор g[j] очередную пару (i, k). Теперь динамика: dp[i][j] — наилучшее разложение делителя j, если использовались делители 1..i. Переход: dp[i][j] = max(dp[i — 1][k]), где i * k = j. Все возможные переходы мы уже сохранили в g, так что просто перебираем i, и переходы из g[i], при этом динамику можно записывать в тот же массив, если j перебирать по убывании.
Неожиданно симпатично все выглядит, единственная просьба авторам системы к следующим раундам — добавьте, пожалуйста, строчку с моим местом в положении участников (или где-то и так можно свое текущее место увидеть без пролистывания?)
Спасибо! Постараемся добавить такое.
Если на контесте отправил задачу "в тёмную" и она не зашла то даже после контеста её ресабмитить нельзя?
У меня тоже не получается. Странно
К сожалению, сейчас нельзя, но мы это исправим.
У меня MLE в E, как решить без сохранения списка имен команд? Длина имены <= 300, количество команд <= 300000
Можно переоткрыть файл
Спасибо. Теперь прошло :/
Авторам хочется высказать много ненависти за 500
000 в задаче F. Вроде правда на firefox не воспроизводится, только в хроме.
Было бы неплохо, если бы где-то можно было посмотреть, на каком месте находишься хотя бы ты, не говоря уже о своих друзьях
Про себя будет, про друзей тоже собирались, но пока не успели.
В системе не отвечают, спрошу тут: Возможно ли дорешивать задачи, отправленные на раунде вслепую?
Ну и возможность отправлять решение прямо со страницы задачи была бы кстати.
Мы постараемся сделать дорешивание слепых задач возможным. Возможность отправлять решение со страницы задачи тоже в планах.
Теперь дорешивание всех задач стало возможным.
в чем причина РЕ1? во всех online judge w+ работает нормально
еще, обычно ошибки на 1ом тесте не считаются в штраф, ибо он совпадает с sample
Обычно — это где, кроме Codeforces?
PCMS2Client, informatics.mccme.ru
PCMS2? На полуфинале вроде даже compilation error дает штраф
а, я подумал почему-то про первую часть вопроса, так да, только CF кажется
Может freopen("number.**in**", "w+", stdout); //PE1
Мы не давали права на чтение вашего выходного файла, только на запись. Добавим права на чтение.
Когда будут известны 50 рандомных, прошедших в отборочный этап?
Не проще ли принять участие в квалификации и попасть в число 2000 прошедших квалификацию?
Согласен, просто интересно узнать
Будет новость, ждите
Я теперь поучил мaйла. Конечно я случайный, место 350. Хорошо, потому что термин квалификационного раунда мне не подходит.
how to solve D?
div1 or div2 ? XD
only joking
Seems that my code will describe my solution much better than me.
Будет ли разбор ? Можно ли будет посмотреть тест на котором упало решение ? Как узнать, кто попал в те 50 случайных человек ?
Я решал D вот так:
В чём ошибка ? На слагаемые я вот так раскладывал:
На тесте
правильный ответ
Выходит я должен не "склеивать остатки" в разложении на сумму, а искать к ним пару из "остатков" других степеней ?
Разбор будет. Тесты на такого рода соревнованиях не выдаются. Новость про прошедших также будет.
Это на какого рода соревнованиях? На NEERC, например (да и на многих других ACM-контестах), после окончания можно скачать архив, который включает в себя не только тесты, но и решения жюри. На TopCoder и Codeforces можно посмотреть протокол тестирования. На RCC выкладываются архивы с тестами. На GCJ и HC тесты можно скачать даже не после, а во время контеста. Есть, конечно, OpenCup, но мне кажется, что это не тот контест, на который стоит равняться в этом плане. Поэтому не вижу причин, по которым Яндекс не мог бы выкладывать архив с тестами после тура.
Финал ICPC, не?
С прошлого и позапрошлого года есть архивы.
Сильно снижает мотивацию искать ошибку до победного конца, не зная теста, как на реальном соревновании. Но раз все так заминусовали мой комментарий и заплюсовали твой, то выложим.
Ну раз отношение сообщества к этому вопросу так изменилось и все люто минусуют,- значит выложим тесты. У меня осталось со старых времен мнение, что надо учиться находить ошибку, не зная тест, на котором ошибка.
Разумеется, надо уметь, поддерживаю.
Но точно так же поддерживаю мнение, что тесты должны быть выложены, и вот почему:
Есть возможность убедиться, что тест корректен. Например, проверить валидатор или написать его самостоятельно.
Есть возможность использовать задачи для тренировок. Например, если я нашёл 10 задач на какую-то тему, удобнее, чтобы они были собраны в одном контесте, а не раскиданы по 10 online judges.
Можно убедиться, что набор тестов полный. Например, валит какие-то совершенно идиотические решения. А если это не так — можно добавить соответствующие тесты к себе на тренировку.
Никто не гарантирует, что Яндекс.Контест будет доступен еще месяц, год, десять лет. Точно так же никто не гарантирует, что при полном обновлении системы (которое наверняка когда-нибудь произойдёт) старые соревнования случайно не исчезнут. Пример: то, что иногда происходит с тренировками на CF. А задачи не должны теряться.
С другой стороны, выкладывание полного архива задачи делает её палёной раз и навсегда. Дальнейшее использование её в тренировках, которые влияют хоть на что-то, кроме индивидуального обучения (например, проход на сборы, получение зачёта, локальное соревнование, что-нибудь ещё) — сомнительная затея. С этой точки зрения задача в открытом доступе — это не плюс задача, а минус задача в "банке задач".
А то, что её разыгрывали на официальном соревновании, да ещё и с разбором ещё ничего не значит?
Или речь про абстрактную задачу?
Скорее про абстрактную. Переформулирую: я считаю, что ценность задачи для переиспользования понижается, когда она переходит из состояния "публичны условие и разбор" в состояние "публичен архив с тестами". И в обратную сторону переход невозможен.
Но это с точки зрения человека, у которого есть доступ к некоторым архивам задач, и лежащие там задачи вот таким образом меняют ценность. Понятно, что те, у кого такого доступа нет — а при выкладывании хоть к каким-то появляется, — наоборот, скорее порадуются публичным архивам с тестами. Но вместо этого, например, можно передавать архивы с тестами только между тренерами, как это часто и делается.
Поскольку я одна из заинтересованных сторон, мне сложно судить тут «объективно».
Выложено на сайте соревнования
Кто-нибудь может рассказать как решалась "B. Три дроби"?
возможно(и скорей всего так) есть общее решение , но если расмотреть все варианты?
4/(4*k) ==1/k(1/2+1/3+1/6)
4/(2*k)==1/k+1/(k+1)+1/(k(k+1))
остаётся сложный случай когда n — нечётно тут всегда можно разложить на аликвотных что :(
надеюcь можно перебором первой дроби найти случай когда числитель второго слагаемого 1 что всегда можно разложить на сумму
4/n=1/z + остаток
где z начинается с (n+3)/4 и пока не получим удобный остаток 1/t который при ответе развернём на сумму 1/(t+1) +1/((t(t+1))
если же есть(имхо для многих чисел есть ) 2/m =1/p+1/q то поиск z облегчается.
Здесь присутствует необходимая теория; то есть большинство случаев решается конструктивно или жадным алгоритмом Фибоначчи для поиска египетских дробей. Получаем, что надо найти решения для простых p<15000, для которых p=24k+1. А это уже делается предпросчётом.
...А можно ещё проще — никаких статей не читать и заметить, что если 4/n=1/a+1/b+1/c, то 4/mn=1/ma+1/mb+1/mc.
Соответственно, достаточно предпросчитать локально перебором ответы для всех простых n<15000 и затем уже достроить таблицу значений.
В коде достаточно хранить b и c, a вычисляется по формуле nbc/(4bc-nb-nc).
Не надо никакого предпросчета и конструктива.
Переберем
c
отn/4
до3*n/4
. Для данныхc
иn
наa
иb
имеем уравнение((4*c-n) * a - c*n) * ((4*c-n) * b - c*n) = (c*n)^2
Факторизуем
n^2 * с^2
с помощью заранее посчитанного массиваmin_prime[]
решетом Эратосфена. Формируем эффективно (рекурсией или еще как) все делителиn^2 * с^2
и перебираем делительd
. Для данного делителя находимa
иb
из(4*c-n) * a - c*n = d
и(4*c-n) * b - c*n = n^2 * c^2 / d
и проверяем подходят они или нет.Также сохраняем ответы для всех
n
, чтобы не считать одно и то же два раза.Если оценивать грубо, то суммарная сложность такого решения зашкаливает, но оно зашло за 0.054.
UPD
Но если это объединить с конструктивом и запускать только для простых чисел вида
24*k+1
, то должно получится мега шустро — за секунду можно будет насчитать все ответы до миллиона, я думаю.Will there be an editorial for this contest?
Yes, there will be.
Были серьёзные проблемы в Firefox 22.0: каждые секунд пять весь браузер подвисал на секунду-другую. Такое ощущение, что либо что-то вычислял, либо ждал ответ от сервера циклом for.
Ну а у меня например Firefox 22.0 не подвисал. И как вы предлагаете разработчикам искать, в чём проблема? :) Неужели так тяжело запостить технические детали — OS, аддоны браузера, конфигурацию машины... Тем более, там есть ссылка на багрепорт, которая автоматически технические детали заберёт.
Да, тяжело, если не знаешь, что может потребоваться. А где есть ссылка на багрепорт? Я с ходу не заметил ничего, кроме "обратной связи" в футере.
Впрочем, мне уже ответили, что это может быть связано с тем, что я использовал "старый интерфейс" по адресу http://contest.yandex.ru , который при обновлении монитора каждый раз на клиенте просматривает и фильтрует всех участников, вместо того, чтобы предоставить это серверу. Полагаю, что использование "нового интерфейса" должно решить проблему.
Ну так да, я про "обратную связь" и говорю; а народе это называется "багрепорт" :) Про "старый интерфейс", наверное, надо было знать — вроде ссылок на него нигде нет. Впрочем, он мне нравится несколько больше — форма самбита находится на странице с задачами и логичнее оформлена, и монитор полный, а не только 50 человек (может, это главная причина тормозов?).
Hi
I'm advanced, but can I participate in the Qualification round?
Yes, you can
seems awesome but what is Yandex
It's the 4th largest search engine in the world, surpassing Bing recently by the number of searches and succesfully competing with Google in Russia for many years. You can read more here and here and here
Друг зарегистрировался после конца тестового раунда и хотел посмотреть задачи, но у него вместо задач пустая страница с надписью "Соревнование началось" или "Контест начался" (не помню точно). Это баг или так задумано?
А можете сообщить в личку его логин, чтобы мы проверили, что именно происходит?
Буду очень благодарен, если кто-то, решивший F. Taxi, найдет баг в моём решении. http://pastebin.com/zFJ2T4b1 WA12
Решал по точно таким же рассуждениям: http://mirror.codeforces.com/blog/entry/8168#comment-138554 Правда, код у меня вышел короче.
Блин, только написал здесь, и сразу же сам нашел :) А до этого два дня страдал. Последнюю проверку if (p >= d) надо было заменить на if (p + x[lcar] >= m), потому что то, что мы не доехали до таксопарка без использования отложенной машины, еще не значит, что мы не можем с её использованием доехать до аэропорта.
Problem E: submitted a program that outputs nothing.
Accepted.