Яндекс.Алгоритм 2011 - Квалификация 1

14 лет назад, # |

← Rev. 2 →

Round FAQ:
1) Round will be rated (affects rating).
2) Rules are Codeforces standard rules. Please read them carefully!
3) Also be sure you are registered for the contest! Find yourself here.
4) If you passed this qualification - you can participate 2nd qual. and it also affects your rating.

===

FAQ Раунда:
1) Раунд рейтинговый.
2) Правила: стандартные правила Codeforces, прочитайте их внимательно!
3) Проверьте свою регистрацию на соревнование! Найдите себя здесь.
4) Если Вы квалифицировались в этом раунде - Вы можете участвовать и во втором квалификационном раунде, и он тоже будет для Вас рейтинговым.

→ Ответить

PavelChadnov

14 лет назад, # ^ |

Посреди рабочего дня можно найти 10 минут, чтоб сдать задачу, которой вполне может хватить, чтобы пройти, а на рейтинг это пагубно повлияет. Кто-то это уже где-то писал

→ Ответить

14 лет назад, # ^ |

А что дороже - рейтинг или квалификация Yandex Open?

P.S.: Мы тут в английской ветке флудим.

→ Ответить

Mahdi

14 лет назад, # ^ |

It would be nice to have a page about this competition, the rules, the advancers and etc.

→ Ответить

http://mirror.codeforces.com/blog/entry/1830?

14 лет назад, # ^ |

→ Ответить

Mahdi

14 лет назад, # ^ |

I meant something more formal with subpages and a rich format.

→ Ответить

PavelChadnov

14 лет назад, # |

больше не флудим в английской

можно было дать выбор, многие бы, я думаю, обрадовались

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

да, такая возможность наверное была бы полезна не только для этого контеста

UPD: http://cforces.reformal.ru/proj/?ia=123895

→ Ответить

14 лет назад, # |

Стоит ли говорить, что рекорд по количеству зарегистрировавшихся побит?

→ Ответить

ahmed_aly

14 лет назад, # |

+10

"The registration will be opened during the whole contest."

This was written in the email which was sent to me about this round, but I see that the registration is closed.

→ Ответить

14 лет назад, # ^ |

← Rev. 3 →

Ignore this comment

→ Ответить

wackloner

14 лет назад, # |

← Rev. 2 →

Будем считать этот завал следствием недосыпа =__=

→ Ответить

Tranvick

14 лет назад, # ^ |

+10

Не у одного меня мозги не работают в 8 утра =)

→ Ответить

yeputons

14 лет назад, # ^ |

У вас хотя бы утро. А у меня сейчас - полчетвёртого ночи :)

→ Ответить

14 лет назад, # |

← Rev. 2 →

During the last minute of the contest, I tried to hack with a Python generator submitted as a file named "tt". Had no time to name it nicely.

I've got the following error.
-----

Traceback (most recent call last):

  File "<string>", line 1, in <module>

IOError: [Errno 2] No such file or directory: 'tt.py'

-----
So, the server tried to open "tt.py" when the file was named just "tt".

I believe it's not the intended behaviour. Will it be corrected?

UPD: The test is incorrect anyway, so it won't affect the results.

→ Ответить

14 лет назад, # ^ |

I'll try to investigate this issue

→ Ответить

Petr	14 лет назад, # \| +46 Thanks for the contest! There's one thing that confuses me: were contestants still separated by division? If yes, it looks unfair because tournament advancement may be easier if you're in div 2. → Ответить

Petr	14 лет назад, # ^ \| +10 (this is similar to the debate about "IronMan" seeding in TopCoder) → Ответить

14 лет назад, # ^ |

Yes, it means newcomers which actually would have belonged to Div1 if they competed at CodeForces before had an advantage.

→ Ответить

14 лет назад, # ^ |

+25

Yep, I thought about it just few minutes before the contest. In future, we will not use division-separation on tournament rounds.

→ Ответить

ahmed_aly

14 лет назад, # ^ |

Will use division separation for the next rounds?

→ Ответить

14 лет назад, # ^ |

It will be for typical Codeforces rounds, but not for tournaments.

→ Ответить

14 лет назад, # ^ |

→ Ответить

14 лет назад, # ^ |

why my above comment is not shown? is this a bug?

→ Ответить

14 лет назад, # ^ |

→ Ответить

NKolotey

14 лет назад, # |

+14

За пятнадцать минут до конца раунда сайт был недоступен с 503-й ошибкой. Починилось быстро, но всё равно тревожный звоночек.

→ Ответить

Tranvick

14 лет назад, # ^ |

У меня ошибки выдавало не только за 15 минут. По сути в течение всего контеста периодически появлялись =/

→ Ответить

14 лет назад, # |

-26

Ух ты, блин! Еще б 15 минут-и я бы все 5 сдал!

5 задача сильно понравилась.

→ Ответить

14 лет назад, # |

Спасибо за контест!

Впервые пытался взломать чужое решение.

Первый раз - получилось, у другого участника была ошибка в алгоритме, вбил тест руками, сломал.

Во второй раз вижу, что у участника в задаче A решение за квадрат. Пишу генератор на питоне:

N = 10**5//26

S = "qwertyuiopasdfghjklzxcvbnm" * N

print S + S[::-1]

Перехожу в окно взлома. Оставляю поле для ввода теста пустым. Выбираю язык программирования (Python 2.6). Выбираю файл с генератором. Поле "параметры генератора" оставляю пустым. Отправляю. Получаю результат - некорректный тест и сообщение по-английски, насколько я помню, означающее, что тест - пустой.

Что я делаю не так?

→ Ответить

sdryapko

14 лет назад, # ^ |

Насколько я понял, там по условию нельзя, что бы строка в выходном файле была пустой. Сам ломал таким же тестом, только в начало добавлял символ 'а', а в конец 'b'

→ Ответить

14 лет назад, # ^ |

+12

Да, спасибо, так и есть!

→ Ответить

14 лет назад, # ^ |

Вероятно, там было написано, что ответ на ваш тест - пустой. По условию задачи это недопустимо.

→ Ответить

14 лет назад, # ^ |

+12

А, точно, да, у меня же все пары удаляются, ответ - пустой будет. Не подумал про это.

Спасибо!

→ Ответить

14 лет назад, # ^ |

Возможно не тест пустой, а результирующая строка пустая, после удаления всех пар.

→ Ответить

14 лет назад, # ^ |

Спасибо, так и есть!

Но поскольку впервые что-то ломал, то подумал, что я не разобрался с тем, как сдавать генератор.

→ Ответить

Petr	14 лет назад, # ^ \| +3 По условию, после удаления дубликатов должна остаться непустая строка. → Ответить

14 лет назад, # ^ |

Да, спасибо, забыл я про эту тонкость в условии.

→ Ответить

zafar_sust_bd

14 лет назад, # |

+15

What is the problem with u guys(codeforces or ....).Why problem statement is so confusing.What does it mean ?

"if two consecutive numbers were separated by spaces only (one or more), then exactly one of them should be left"

what does it mean =>

---- It means one number will be removed.

---- It means one space will be removed.

---- It means all spaces except one space will be removed.

During contest i submitted with the second explanation above & i got Pretest passed.

Now if i get WA for this reason is it my problem ??

→ Ответить

imrankane2005

14 лет назад, # ^ |

+11

I took it as one number will be removed. I was confused whether which number to remove.
I bet on the left one and got WA . I was dumb enough to not able to think one space will be removed. Though i still don't know what is the correct one from your three choice.

→ Ответить

zafar_sust_bd

14 лет назад, # ^ |

-9

It is quit normal for anyone to be confused.

If codeforce can't translate problem statement into English so what is the meaning to set a contest in english version.

→ Ответить

P___	14 лет назад, # ^ \| ← Rev. 2 → +12 "Polycarp wants to add and remove spaces in the string s to ensure the following:" It is written in the statement. I was also thinking a while about this point, but the statement is ok. → Ответить

IvayloS

14 лет назад, # ^ |

→ Ответить

IvayloS

14 лет назад, # ^ |

I can not copy paste it here but there is my clarification and the answer:

Please broadcast a message about the spaces as if two numbers are separated only by spaces ... exactly one of them should be left - this may refer to numbers.

Answer:

1. "Polycarp wants to add and remove spaces in the string ... "
You are not allowed to do anything else (remove numbers etc.), only add and remove spaces.

2. In every sample test removing numbers doesn't work.

3. There were no other such questions.

→ Ответить

Mahdi

14 лет назад, # ^ |

Same problem. very confusing statements and I think none of the pretests were about the numbers.

→ Ответить

ktuan

14 лет назад, # ^ |

Hmm, for me, it means something like: if you have "1<space><space>2", you need to remove all-but-one spaces, so it becomes "1<space>2". I try to challenge other by this case, but it is an invalid case. Now, my conclusion is: we don't need to understand that sentence in order to solve this problem :(

→ Ответить

poopi

14 лет назад, # ^ |

Are you sure? I took the statement as "one number will be removed." and my solution hacked by "5<space><space><space>9". and also I successfully hacked a solution with:
"3464574575367357<space>4674575368345646835<space>56,...,...,56,456,...,"
So the statement was matter.

→ Ответить

ktuan

14 лет назад, # ^ |

How come :( yeah I'm pretty sure that I tried to challenge other by that case, and I couldn't as it show: invalid case... That's why I thought that numbers should be separated by "," or "..." and stop making other challenge. Grrrr I should have many successful challenges

→ Ответить

poopi

14 лет назад, # ^ |

Check your hack, you will see this message: "FAIL Expected EOLN (stdin)"
You didn't press "Enter" key. The input should end with end of line character. At first I had same problem.

→ Ответить

ktuan

14 лет назад, # ^ |

I think I pressed "Enter" (this time I'm not so sure), and there was no explanation except "invalid case". Anyway, it's ok for me :)

→ Ответить

14 лет назад, # |

Расскажите, пожалуйста, решение задачи D.

→ Ответить

14 лет назад, # ^ |

Банально жадно решалась с такими ограничениями.

Перебираем альбом на первом месте, затем просто на каждом шаге выбираем альбом с максимально оставшимися снимками, который не стоит слева и справа.

Итого: O(M * N * M)

→ Ответить

shilov

14 лет назад, # ^ |

На самом деле даже альбом на первом месте перебирать не надо, ведь оно ничем не отличается от всех остальных.

→ Ответить

14 лет назад, # ^ |

А, точно, кольцо же.

→ Ответить

Petr	14 лет назад, # ^ \| +15 А как выбирать если несколько с максимально оставшимися снимками? Если брать с минимальным номером, то не работает. Взлом: 8 3 3 1 4 Такое решение строит 3 1 3 1 3 1 2 ? и на место ? поставить нечего. → Ответить

Sammarize

14 лет назад, # ^ |

← Rev. 3 →

Я сделал так: всё тоже самое, только сначала отсортировал альбомы по убыванию количества снимков. Все тесты прошло, этот тоже.

Не знаю, почему, если честно =) Наверное, случайно)

→ Ответить

shilov

14 лет назад, # ^ |

Мой пост ниже объясняет, как я поступал в такой ситуации, на этот тест мое решение дает ответ: 3 1 3 1 3 1 3 2

→ Ответить

14 лет назад, # ^ |

Не зря я значит перебирал первый возможный альбом.

У меня жадное выдаёт:

8 3

3 1 4

1 3 1 3 1 3 2 3

→ Ответить

14 лет назад, # ^ |

Нет, перебирать надо. Пример:

4 3

2 1 1

После того, как мы ставим на первое место 1, мы затем ставив 2 3 ( потому что снимков в них - макс оставшееся, 1), затем ставим 1 - все плохо.

А меж тем ответ 1 2 1 3 существует.

→ Ответить

Deamon

14 лет назад, # ^ |

дада, 102 тест) прелесть просто

→ Ответить

Egor	14 лет назад, # ^ \| 0 Не надо перебирать. Достаточно во всех местах кроме последнего в сортировки при равенстве количества в первую очередь брать то, что на первом месте → Ответить

Petr	14 лет назад, # ^ \| 0 А как это доказать? → Ответить

Egor	14 лет назад, # ^ \| +1 У меня есть доказательство, но мне очень влом писать. Расскажу при встрече → Ответить

Petr	14 лет назад, # ^ \| 0 Ок, если не забудем :) → Ответить

Alex_KPR

14 лет назад, # ^ |

эм, а это разве не очевидно? я пользовался этим фактом для решения задачи

→ Ответить

14 лет назад, # ^ |

Куприн, с покраснением:)

→ Ответить

Alex_KPR

14 лет назад, # ^ |

благодарю, Чумаченко) тебя с оранжевением ;)

→ Ответить

14 лет назад, # ^ |

+13

Ваше доказательство напомнило эту байку :)

→ Ответить

Alex_KPR

14 лет назад, # ^ |

гм, это вовсе не доказательство)

был один случай, когда хороший знакомый рассказывал решение задачи, и когда я попросил обоснование, он просто ответил: "моё решение правильно, и акцептед это подтверждает" =)

→ Ответить

Ferlon

14 лет назад, # ^ |

Хмхм... хорошая байка. Год назад на одном экзамене мне в качестве последнего был задан вопрос, на который я не знал ответа. Однако, хорошо подумав, я сказал: "Вы в своей книге об этом не написали". Получил 5. Думаю, это настолько же справедливо, что и заключать о правильности решения по вердикту жюри :)

→ Ответить

zeliboba

14 лет назад, # ^ |

можно еще положить на нечетные места (кроме последного, разумеется) самый толстый альбом, а потом то же самое. Это вроде проще доказать.

→ Ответить

14 лет назад, # ^ |

Спасибо. Я чувствовал, что это какой то баян и как то тупо решается. Но увы, не допер.

→ Ответить

ifsmirnov

14 лет назад, # ^ |

С таким решением меня взломали тестом

6 3

3 2 1

Программа пытается поставить 1 2 1 2 3, на последнем шаге единицу поставить не может и выводит -1. На каждом шаге я действительно выбираю альбом с максимальным числом оставшихся. Что тут не так?

→ Ответить

shilov

14 лет назад, # ^ |

Я при равном количестве фотографий в нескольких альбомах отдавал приоритете тому, из которого фотография стоит на первом месте.

→ Ответить

14 лет назад, # ^ |

Ну я максимальное всегда выбирал в одном и том же порядке -- первое максимальное от начала, поэтому у меня:

6 3

3 2 1

1 2 1 2 1 3

→ Ответить

Romka

14 лет назад, # ^ |

Благодаря таким решениям у меня +500 =)

Надо кроме этого ещё по возможности как можно раньше поставить все элементы из того альбома, из которого взяли первую фотографию, иначе будет, как у LoonaTeg

→ Ответить

volkhin

14 лет назад, # ^ |

← Rev. 3 →

+42

Мое решение - если в альбоме более n/2 снимков, можем считать, что их n/2 - остальные не сможем расставить. Если теперь в альбомах в сумме менее n снимков - ответ нельзя. Сортируем альбомы в порядке убывания в них снимков. Теперь берем поочередно альбомы и расставляем снимки через одну позицию - сначала все четные позици заполним, потом все нечетные. Никакие два одинаковых не будут стоять рядом и все позиции будут заполнены.

→ Ответить

14 лет назад, # ^ |

о, спасибо)) это больше похоже на обоснованное решение:)

→ Ответить

14 лет назад, # ^ |

Без сортировки вроде бы вот такой вот тест ваша программа не пройдет:

6 3

2 3 1

→ Ответить

volkhin

14 лет назад, # ^ |

Угу, точно. Решение с ней и посылал, а сейчас забыл зачем.

→ Ответить

cerealguy

14 лет назад, # ^ |

Нужно быть аккуратным, если в каком-то альбоме окажется ровно n/2 снимков.
4 3
1 2 1

→ Ответить

14 лет назад, # ^ |

-15

Я так бегло просмотрел и заметил, что вроде как никто из отписавшихся не отправил наиболее безыдейное решение на задачу D.

Очевидно, что если для цепочки и есть хотя бы какие-то запары с расстановкой, то для цепи уже никаких. Так давайте переберем значения первого и последнего элемента (они должны быть различны) и будем очевидной жадностью искать ответ для цепочки со второго элемента до предпоследнего. Там уже понятно, что каждый раз надо ставить наиболее частовстречаемый элемент из допустимых.

→ Ответить

14 лет назад, # ^ |

Действительно, бегло:)

→ Ответить

14 лет назад, # ^ |

То есть решение за O(NM³) уже где-то было описано? Я вроде еще раз глазами пробежался по комментариям и не нашел такого. Решения, где перебирается только начальный элемент не предлагать - оно требует хотя бы чуть-чуть подумать.

→ Ответить

14 лет назад, # ^ |

Если идея "перебрать первый + жадность" верна, то очевидно, что идея "перебрать первый, последний + жадность" отже верна. То есть может решения с двумя переборами описано не было, но из того, что было написано, ясно что оно тоже верное. А "идейность" - понятие субьективное.

→ Ответить

Petr	14 лет назад, # ^ \| +10 Почему понятно - ведь на предпоследнем элементе тогда может лажа возникнуть, на него есть дополнительное ограничение - несовпадение с последним. → Ответить

14 лет назад, # ^ |

Да, но раз мы перебираем все варианты последнего, то среди них же будет и тот, который стоит в правильном решении, и там лажа не возникнет.

→ Ответить

Petr	14 лет назад, # ^ \| 0 Почему? Не факт же что правильное решение находится жадно? → Ответить

14 лет назад, # ^ |

Выше было написано два решения: одно с перебором первого, второе - где на первое место сразу ставится жадно максимум, что идентично первому из-за цикличности. Решение с перебором первого и последнего - идентично решению с перебором первого и второго - идентично решению с перебором первого и подставлением максимума на вторую позицию - идентично решению с перебором только первого, которое было описано выше.

(Это все безусловно верно в том случае, если первые два описанных жадных решения действительно верные, а не просто прошли все тесты:) Но если они верны, то тогда решение с перебором двух идентично им.)

→ Ответить

Petr

14 лет назад, # ^ |

Тут есть два момента.

1) Мой комментарий был ответом KhaustovPavel на его реплику о том, что есть решение, не требующее доказательства как очевидное. Я объясняю, почему очевидное доказательство не проходит. Мы не опираемся на верность каких-либо других решений, так как это противоречит цели - получению решения, которое очевидно верно.

2) "идентично первому из-за цикличности" - не понимаю. Вроде выше же было показано, что решение где на первое место ставится жадно максимум неверно без дополнительных хаков )

→ Ответить

14 лет назад, # ^ |

Ну в моей реализации я всегда смотрел оба элемента - предыдущий и последующий (для рассматриваемого интервала они всегда существуют). Изначально все незаполненные элементы просто ставил равными -1.

Если мы пришли в состояние, когда мы не можем поставить на предпоследнюю позицию ни одного элемента, это означает, что где-то в случае, когда у нас было два альбома в которых осталось равное число неиспользованных изображений мы выбрали не тот. Рано или поздно мы придем к варианту, когда на последнем месте стоит тот самый элемент, который тогда мы выбрали при равенстве. Так как порядок приоритетов у нас всегда фиксированный, то и в этот раз мы опять выберем его же там в середине и к предпоследнему элементу у нас будет все тот же элемент, что и в прошлом случае, но на этот раз он не будет совпадать с последним.

→ Ответить

Petr

14 лет назад, # ^ |

Нет, мы не выберем его же в середине, так как поставив его на последнее место, мы уменьшим его счетчик на 1, и поэтому все наши решения, возможно, будут другими.

Кроме того, непонятно почему "в случае, когда у нас было два альбома в которых осталось равное число неиспользованных изображений мы выбрали не тот" - а вдруг нужно было брать очередное изображение не из максимального альбома?

→ Ответить

14 лет назад, # ^ |

Ну... Каждый раз нам необходимо максимизировать число вариантов, которые у нас все еще остаются. То есть наша цель - минимизировать количество альбомов, в которых уже не осталось изображений. Отсюда я сделал вывод о целесообразности выбора альбома с наибольшим числом изображений.

А по поводу "в середине" - я не ясно выразился. Я имею в виду то, что при равенстве мы будем выбирать теперь уже тот, что стоит в конце (если это возможно).

→ Ответить

Petr

14 лет назад, # ^ |

Непонятно, почему нам нужно максимизировать число вариантов, которые еще остаются. Нам нужно, чтобы не осталось ноль вариантов, а сколько их будет на промежуточном шаге - неочевидно. Так можно было бы любой жадный алгоритм доказывать :)

Про "в середине" все еще не понимаю. Можно конкретный пример?

→ Ответить

14 лет назад, # ^ |

Для теста:

N = 7, M = 4

A₁ = 1, A₂ = 2, A₃ = 3, A₄ = 1:

Предположим, что мы всегда будем выбирать элемент, которого у нас в запасе больше всего. При равенстве количества будем брать наименьший по значению.

Мы предположили, что первый элемент последовательности равен 4, а последний равен 3, тогда:

4 2 3 1 2 ? 3

На позицию предпоследнего элемента нам нечего поставить, что нас не устраивает. Предположим, что последний элемент равен 2 (первый все так же 4):

4 3 1 3 2 3 2

Как видим, где-то там в начале тройка уравнялась с двойкой, но так как в порядке приоритетов двойка идет раньше тройки, то она не осталась на предпоследнюю позицию.

По поводу выбора элемента, который у нас имеется в самом большом количестве... На самом деле нам желательно сделать так, чтобы в конце (на предпоследней позиции) осталось 3 варианта, тогда мы в любом случае сможем поставить предпоследний элемент. Если осталось 2 или 1, то нужен порядок приоритетов, который позволит удержать к этому моменту допустимый элемент. Это уже по части предыдущего утверждения. Помимо прочего, нам не важно, сколько у нас имеется в запасе каждого элемента. Нам важно только количество различных элементов. Не может же возникнуть ситуации вида "нам нужен именно ЭТОТ элемент", может быть лишь ситуация "нам нужен любой элемент кроме ЭТОГО". Так давайте будем до последнего поддерживать количество различных элементов как можно большим.

На звание строгого доказательства это не претендует :)

→ Ответить

Petr	14 лет назад, # ^ \| +6 Ага, примерно понятно, спасибо :) → Ответить

Milanin

14 лет назад, # ^ |

Почему-то на обоснование "наиболее безыдейного решения" потребовалось больше всего текста :)

→ Ответить

14 лет назад, # ^ |

На контесте я для себя это обосновал так:

"Если не это, то что?!".

→ Ответить

KADR

14 лет назад, # ^ |

Кстати, я примерно так же обосновывал решение для себя :)

Вообще тупая жадность не прошла претесты, в итоге я решил написать как можно более навороченную жадность, думая что если уже она не пройдет, то не знаю что дальше буду делать. Получилось извращенное решение со сложностью O(N²M²logM), которое мало того что прошло, так еще и за 30мс отработало.

→ Ответить

14 лет назад, # ^ |

=======================

Мое тоже отработало за 30мс, но там это происходило из-за того, что если ответа нет, то все варианты быстро отбрасывались еще на стадии расстановки, а первый же найденный ответ сразу же выводился в файл и на этом работа программы окончена. Как правило, если ответ есть, то он находится достаточно быстро.

→ Ответить

goo.gl_SsAhv

14 лет назад, # ^ |

← Rev. 2 →

я посортировал все албомы по убыванию фотографий в них, на первое место ставим фотку из первого альбома (в нем максимальное число фоток). очевидно что если решение есть, то есть и такое. затем рекурсивно перебираем какие фотки будут поставлены на места 2, 3, 4 (они могут быть из одного и того же альбома, если не соседствуют, и эти фотки перебираются только из четверки самых толстых альбомов) затем заполняем массив начиная с позиции n до позиции 5, каждый раз беря фотографию из альбома, в котором на данный момент больше всего фотографий. Доказательства у меня конечно нет, но интуитивно мне верилось что такое проканает.Поясняю почему мне в это верилось. Давайте поставим на первую позицию фотку из самого толстого альбома, а затем будем жадно расставлять до самого конца. У нас может построится решение, а может обломаться тем, что в конце две фотки окажутся из одного альбома. В случае если алгоритм олбомался, а решение существует, можно переставить несколько фоток местами и получить решение. Последнее утверждение требует доказательства, но мне показалось оно разумным и решение прошло тесты. итого 4^3 * n * m. Интересно уже увидеть авторское решение, задача мне не понравилась если честно, чувство такое что я какой-то чит вогнал.

→ Ответить

goryinyich

14 лет назад, # ^ |

-10

У меня зашел перебор с грамотными отсечениями - пихаем символы по кругу, если на каком-то этапе осталось запихать L символов, и в какой-то кучке больше L/2 + L%2 фоток - то уходим. Естественно, до этого нужно кол-во фото во всех альбомах сделать равным N, убрав лишние из самых больших альбомов.

→ Ответить

http://mirror.codeforces.com/blog/entry/1858#comment-35830

14 лет назад, # ^ |

В моей комнате было отличное решение maggot092, оно прошло систесты. Решение такое. Сначала оставим от каждого a[i] не более n/2 и проверим, что это вообще возможно. Затем будем ставить a[1] первых, a[2] вторых, и так далее, пока не поставим n штук, на позиции в следующем порядке: сначала 1, 3, 5, ..., а потом 2, 4, 6, ... (нумерация с единицы).

→ Ответить

cerealguy

14 лет назад, # ^ |

→ Ответить

Petr	14 лет назад, # ^ \| 0 Это вроде то же самое, что volkhin написал выше? Как отмечено выше, это работает только если еще и отсортировать a[i] по убыванию. → Ответить

cerealguy

14 лет назад, # ^ |

Сортировать не обязательно, просто четное n и альбом с n/2 - это особый случай.

→ Ответить

Petr	14 лет назад, # ^ \| 0 Да, все верно. → Ответить

14 лет назад, # ^ |

← Rev. 2 →

Да, это я туплю. Конечно, выше описано то же самое. И действительно есть отдельный случай n % 2 = 0 && ~~m = 2~~ альбом с n/2 фотографиями.

→ Ответить

Petr	14 лет назад, # \| +6 Oops (a < b && t[i] > cutOff) \|\| (a > n && t[i] < cutOff) and I've tested in on many cases :) → Ответить

forest

14 лет назад, # |

+10

Куда пропало соревнование

→ Ответить

http://mirror.codeforces.com/contest/81/status

14 лет назад, # ^ |

→ Ответить

14 лет назад, # |

Рейтинг будет считаться по общей таблице или будут созданы таблицы дивизионов?

→ Ответить

14 лет назад, # ^ |

-43

Лучше б таблицы дивизионов не создавали. Возможно проскочу в оранжевые тогда:)

→ Ответить

14 лет назад, # ^ |

-41

Проскочил:)

→ Ответить

14 лет назад, # ^ |

-36

Кому-то не понравилось что я оранжевый? Почему так активно минусуют?

→ Ответить

14 лет назад, # ^ |

+12

Меньше на вклад смотри. Что ты все время из-за него загоняешься? Когда у тебя появилась одна оранжевая точка - это еще не оранжевый. Да и вообще на CodeForces уже даже красный цвет ничего не значит. Тут рейтинг скачет как давление в 80 лет. За один раунд вот так можно подлететь на 200+ рейтинга если ты еле влез в топ100. И красный может за один раунд вылететь в фиолетовые.

→ Ответить

Skiminok

14 лет назад, # ^ |

Я за время своей CodeForces-жизни побывал почти во всех доступных цветах :) За исключением единственно серого, но я не сильно переживаю на этот счет =)

→ Ответить

Sgr	14 лет назад, # ^ \| ← Rev. 3 → 0 А есть ли те, кто побывал во всех цветах? Вспомнился текст из песни "Эй, жители неба, Кто на дне ещё не был? Не пройдя преисподней, Вам не выстроить рай. Эй, жители дна, Гром смеётся над вами. Чтобы быть с ним на равных, Есть один путь - наверх!" → Ответить

Ferlon

14 лет назад, # ^ |

← Rev. 2 →

У меня вот последняя строчка этого припева, кстати, даже возведена в ранг подзаголовка ЖЖ =)

→ Ответить

14 лет назад, # ^ |

-25

Паш, мне на него вообще пофиг. И, заметь, я написал "проскочил".

→ Ответить

t.gogniashvili

14 лет назад, # |

HI, can anybody tell me how to solve C?

→ Ответить

14 лет назад, # ^ |

we have to Max
( a1 + a2 + ... + aa ) / a + ( b1 + b2 + ... + bb ) / b

to common divisor
( b * ( a1 + a2 + ... + aa ) + a * ( b1 + b2 + ... + bb ) ) / a*b <= cnst

b * ( a1 + a2 + ... + aa ) + a * ( b1 + b2 + ... + bb ) --> max

then guess that if b > a, then ai sould be >= bi
else if a < b

if a == b we must output 1 1 ... 1 1 2 2 ... 2 2

→ Ответить

t.gogniashvili

14 лет назад, # ^ |

i can't guess this statement " then guess that if b > a, then ai sould be >= bi
else if a < b ",can you explain me?

→ Ответить

14 лет назад, # ^ |

lets try to prove that for 2 numbers
we have a, b and numbers x and y (let x > y)

ax + by - ay - bx = (a-b)(x-y)
x - y > 0, so if a > b and a - b > 0, ax + by - ay - bx > 0

and finally ax + by > ay + bx

→ Ответить

goo.gl_SsAhv

14 лет назад, # ^ |

S1 / A + S2 / B ->max

S1 + S2 = total sum of all a[i]

if A = B then output 1 1 1 ... 2 2 2

if A > B we need to maximize S2, else S1

if A > B

we need to sort array of marks, S1 = a[1] + a[2] + ...+ a[A], S2 = a[A + 1] + ... a[A + 2] + ... +a[n]

we can count how many marks 1 we must to include in S1, how many marks 2 we must to include in S1..

→ Ответить

Ministr

14 лет назад, # |

-45

МЕНЯ ВЗЛОМАЛИ НА НЕКОРРЕКТНОМ ТЕСТЕ :(

ЧТО ДЕЛАТЬ ???.....

→ Ответить

sdryapko

14 лет назад, # ^ |

+11

Что за тест? Может ты не понимаешь почему он корректен?

→ Ответить

Georgy

14 лет назад, # ^ |

-21

Дряпко, в клубе три чела сидят, и ты хочешь сказать что все не понимают??

→ Ответить

14 лет назад, # ^ |

+16

Видимо, так.

Solution verdict:
TIME_LIMIT_EXCEEDED

Чем мериться количеством, можно было прочитать ещё раз внимательно.

→ Ответить

14 лет назад, # ^ |

1) Не писать жирным и подчёркнутым текстом.
2) Откуда информация, что тест некорректный?

Какая задача, какой тест?

→ Ответить

Ministr

14 лет назад, # ^ |

-8

В условии гарантировалось, что в ответе будет хотя бы один символ, а в взломе вывод пуст..... :(

→ Ответить

14 лет назад, # ^ |

+25

Это потому что там TLE.
Видимо если решение не проходит по времени, то и чекер не запускается. Поэтому в строчке answer пусто.

→ Ответить

safeasmilk

14 лет назад, # ^ |

-8

Запускается там чекер. Не сразу понял в чем дело, пришлось символ спереди добавить, чтоб взламать решение. :)

→ Ответить

14 лет назад, # ^ |

Видимо сначала тест проверяется на корректность, потом тестируется решение участника, потом тест запускается на авторском решении.

Если решение участника падает (по времени например), то авторское решение не запускается и строчка остаётся пустой.

→ Ответить

14 лет назад, # ^ |

← Rev. 3 →

Мне больше интересно другое...

Я сломал решение 424785 тестом [ab]49999раз + [ba]49999раз + с.
Затем прошло точно такое же решине на паскале:

var
 s : ansistring;
 i, n : longint;
begin
    readln(s);
    n := length(s);
    for i := n - 1 downto 1 do if (s[i] = s[i + 1]) then delete(s, i, 2);
    writeln(s);
end.

И это же решение снова ломается подобным тестом! Правда не видно каким точно... Но суть вроде та же.

Может бага в системе?

→ Ответить

Ministr

14 лет назад, # ^ |

Это моё решение !!! И оно проходит в дорешивании....

→ Ответить

14 лет назад, # ^ |

← Rev. 3 →

Значит системные тесты оказались слабые и взломы всё ещё не включаются в них.

Мне больше интересно как это решение прошло (обошло) мой первый взлом. Не должно же было. Тут же квадрат.

→ Ответить

Lepetrandr

14 лет назад, # ^ |

на вашем тесте решение отрабатывает спокойно линейку, так как в вашем тесте вообще нет двух рядом стоящих одинаковых символов и delete никогда не вызывается. а вот на тесте [ab]49999 + [ba]49999 + c оно будет работать действительно за квадрат, и меня тоже смущает факт что это решение работает не дольше 770мс на систестах.

→ Ответить

14 лет назад, # ^ |

Да! Да! Да!
Там конечно было вот точно как у вас!

→ Ответить

Lepetrandr

14 лет назад, # ^ |

← Rev. 2 →

1. В систестах я вашего теста не наблюдаю, хотя взломотесты всегда добавляются. Во всяком случае в задаче B 41ый тест мой. Возможно, жюри решили не перегружать задачу А кучей огромных тестов участников.
2. В вашем тесте не хватает девятки. На 4999 оно действительно имеет право работать квадрат.
3. По-моему, напрашивается вывод, что жюри зачем то пропускает очевидно неверное решение по задаче A. Либо мы чего то не знаем о процедуре delete.
UPD: на тимусе оно как не странно получает TLE (задача 1654)

→ Ответить

14 лет назад, # ^ |

По-моему Codeforces ещё не научилось добавлять взломтесты...

Видимо вы угадали 41й тест. :)

→ Ответить

14 лет назад, # ^ |

====================
Нет, взломы действительно добавляются. На всякий случай. Но мало и вручную. Т.е. это пока не автоматизировано.

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

А я видел подобное решение и ломал ровно этим же тестом. И... программа работает за 50мс. Как так?
Upd. нет, там все нормально, извините.

→ Ответить

14 лет назад, # ^ |

Такое ощущение, что после перепосылки у Ministr решение не тестировалось на взломах.

Поэтому его три раза ломали.

→ Ответить

14 лет назад, # ^ |

Отписался тут.

→ Ответить

SkorKNURE

14 лет назад, # |

+13

Возможно этот вопрос уже поднимался, однако: куда делись графики рейтинга на станицах? Сделано ли это специально, чтобы не давать участникам лишней информации? Когда вернут? :)

→ Ответить

Skiminok

14 лет назад, # ^ |

Наверное, это одна из фич, которые отключили на время контеста, чтобы сервер не перегружать.

→ Ответить

sdryapko

14 лет назад, # ^ |

+12

Это сделано для того, что бы облегчить нагрузку на cf во время контеста. Я так думаю

→ Ответить

kasyankrak

14 лет назад, # ^ |

"Как вы уже успели заметить — система функционирует в несколько урезанном варианте. Мы решили перестраховаться и выключили на время контеста некоторую функциональность. После окончания раунда все вернется на место."

По моему это как-то намекает - )

→ Ответить

ifsmirnov

14 лет назад, # ^ |

Вроде бы это сделано для снижения нагрузки на сервер во время контеста с большим числом участников. Сейчас много фич отключено.

→ Ответить

14 лет назад, # |

-22

По ходу соревнований сдал четыре задачи без бревен и шел неплохо. Но в конце меня взломали по второй задаче. Я думал, что это фейл дня. Но во время систеста у меня упала первая задача из-за того, что я конкатенировал stl-строки. Всего-то надо было переписать на массив чаров... Зато перепосланная на 498 баллов вторая задача зашла. Как результат, можно считать, что я сдал первую задачу, но не сдал вторую (первая моя посылка по второй все равно бы не прошла систест из-за еще более глупой ошибки). Справедливость восстановлена...

→ Ответить

SkorKNURE

14 лет назад, # |

← Rev. 2 →

Спасибо, не заметил.

Вот только не понимаю людей, минусующих посты с такими вопросами. Ну да это их проблемы...

upd: комментарий к этому

→ Ответить

P___	14 лет назад, # \| 0 What about rating? :) → Ответить

14 лет назад, # |

I am not able to reply to petr's post. is it a bug?

→ Ответить

14 лет назад, # ^ |

+37

You don't have required rating to answer Petr, LOL. =)

→ Ответить

14 лет назад, # ^ |

Lol. Actually I am able to post it but after publishing it is shown as a blank comment.

My comment was:

As top 500 will be selected from overall ranking table. then how is it easier for div 2 users ?

Or you are just considering the fact that hacking is easier in a Div 2 room ?

Correct me if I am wrong.

→ Ответить

Petr	14 лет назад, # ^ \| +13 Yes, I was referring to the fact that hacking is usually much easier in a div 2 room (if the same contestant were to hack there). → Ответить

Shafaet

14 лет назад, # ^ |

For div 1 contestants its easy to hack div 2 coder's code. But its not as easy for div 2 coders.

→ Ответить

14 лет назад, # ^ |

If I'm a new but experienced contestant (or I created new account), I can get much-much points from hacking.

But I thought it was obvious.

→ Ответить

tracyhenry

14 лет назад, # |

-12

The server was too slow, I can't submit any problem for 50 minutes. Anyway, good problemset.

→ Ответить

Parhomets

14 лет назад, # |

← Rev. 3 →

В задаче B во время контеста получил "Неправильный ответ на претест 5" (посылка 428332), но на своём компьютере программа выводила правильный ответ. Заменил "while (cin.get(ch)) s.push_back(ch);" на "while (cin.get(ch)) if (ch!='\n') s.push_back(ch);", то есть если следующий символ во входном файле не равен новой строке - считываем его, в результате "Полное решение". Отсюда делаю вывод что в претесте 5 в строке есть символ новой строки, а это противоречет условию задачи.

→ Ответить

zurg	14 лет назад, # ^ \| ← Rev. 2 → 0 да, таже проблемы была → Ответить

geka666

14 лет назад, # ^ |

у меня та же проблема :(

→ Ответить

14 лет назад, # ^ |

Каждая строка текстового файла всегда заканчивается символом перевода строки. На Codeforces это правило всегда четко выполняется. Данная задача не исключение. Пятый тест не был особенным, просто ваше решение так отработало.

В этой задаче я бы считывал данные как getline(cin, s) - это надежный и кросплатформенный способ.

→ Ответить

goo.gl_SsAhv

14 лет назад, # ^ |

"слудючий символ" - Чумачечая весна? Мда, попса влияет на наше сознание, по крайней мере у меня проассоциировалось...

→ Ответить

logicmachine

14 лет назад, # |

My solution of problem B (#427173) had WA on test 8.
But, it returned correct answer on custom test with input of test 8.
Why did such a thing happen?

→ Ответить

14 лет назад, # ^ |

I ran your solution in custom testing and it outputs "1" as mentioned in juding protocol.

→ Ответить

logicmachine

14 лет назад, # ^ |

Oops. Sorry, I misunderstood interpretation of test result.
Thanks.

→ Ответить

14 лет назад, # |

Баг: точка в графике рейтинга подписана как

Открытый турнир Яндекса 2011<BR>Квалификация 1

→ Ответить

zurg	14 лет назад, # ^ \| +3 в контакте так же выглядит, если щелкнуть "мне нравится" → Ответить

geka666

14 лет назад, # |

а в задаче B по условию может быть перевод строки в тесте?

→ Ответить

geka666

14 лет назад, # ^ |

по условию

>>Входные данные

>>Входные данные содержат единственную строку s.

как мне кажется не должен содержать, но

#include <cstdio>

#include <cstdlib>

int main(){

char c=getchar();

while(c!=EOF){

if (c=='\n') return 1;

c=getchar();

}

puts("1, 2, 3, ..., 10");

return 0;

}

получает runtime 1 o_O

→ Ответить

14 лет назад, # ^ |

Конечно, каждая строка текстового файла заканчивается символом перевода строки. Тест 5 не был особенным. Все тесты имеют вид "некоторая-строка\r\n".

→ Ответить

14 лет назад, # ^ |

Строка может заканчиваться переводом строки. Т.е. файл может заканчиваться /n+EOF, в принципе и должен. Где-то говорили, что это признак хорошего стиля тестов.

→ Ответить

Ferlon

14 лет назад, # ^ |

Более того, если даже задача - парсер и во входе допустимы пустые строки, которые надо как-то нетривиально обрабатывать, то, скажем, файл с текстом <something>+/n+EOF надо обрабатывать как содержащий одну строку - <something>. Этот факт был со скорбью и негодованием мною уяснён экспериментально в одном из первых раундов Codeforces.

→ Ответить

http://acm.timus.ru/problem.aspx?space=1&num=1654&locale=ru

14 лет назад, # |

Никому ничего не напоминает?)

→ Ответить

pank.dm

14 лет назад, # ^ |

эээ..
Может быть задачу B? :)

→ Ответить

14 лет назад, # ^ |

Очень может быть :-)

→ Ответить

Lepetrandr

14 лет назад, # ^ |

Мне больше напоминает задачу A =)

→ Ответить

denys.astanin

14 лет назад, # ^ |

я тоже сразу ее вспомнил

→ Ответить

ryuzmukhametov

14 лет назад, # ^ |

← Rev. 2 →

D мне напомнило
http://acm.timus.ru/problem.aspx?space=1&num=1445

→ Ответить

unprost

14 лет назад, # ^ |

D еще похожа на http://acm.timus.ru/problem.aspx?space=1&num=1832

→ Ответить

ryuzmukhametov

14 лет назад, # ^ |

кстати, как она решается? :)

→ Ответить

14 лет назад, # ^ |

Выберем наименьшее a, не делящее n. Оно будет не больше 13. Тогда первой половиной ответа будут символы i%a+'a', второй - i%a+13+'a'.

→ Ответить

14 лет назад, # ^ |

А можно поподробнее ;)

→ Ответить

14 лет назад, # ^ |

i-ый символ ответа равен i%a если i<=n/2 и i%a+13 иначе. Это работает, т.к. если a не делится на n, то на него также не будет делится никакой делитель d числа n. А это означает что для любых j, j+d соответствующие символы будут различны.

→ Ответить

14 лет назад, # ^ |

Да, с етим вроде мне понятно, мне не ясно почему наименьшее a, не делящееся n будет не больше 13. ведь 2*3*5*7*11*13 = 30030. < мах_n = 300000.

→ Ответить

14 лет назад, # ^ |

Да, но НОК (1,2 ... 13)=360360.

→ Ответить

14 лет назад, # ^ |

Действительно, виноват, не подумал. Хорошее решение. Не подскажете еще какие-то похожые задачки.

→ Ответить

http://acm.timus.ru/problem.aspx?space=1&num=1249

14 лет назад, # ^ |

← Rev. 2 →

_____________________________________________________

Похожие - значит у которых много решений, среди которых есть как минимум одно изящное? :) Тогда наверное вот эти:

http://acm.timus.ru/problem.aspx?space=1&num=1614

http://acm.timus.ru/problem.aspx?space=1&num=1744

http://mirror.codeforces.com/problemset/problem/65/E

→ Ответить

http://codepad.org/hdom99Ce

14 лет назад, # ^ |

Спасибо ;)

→ Ответить

chenchen1024

14 лет назад, # |

Can anyone help me to figure out why his code for A

Runtime error on test 12

→ Ответить

14 лет назад, # ^ |

Try test:

abc

→ Ответить

chenchen1024

14 лет назад, # ^ |

Thanks a lot, I am too careless

→ Ответить

A.K.Goharshady

14 лет назад, # |

← Rev. 2 →

+19

Hope to see no more morning-contests :)
It's really hard to wake up before 11:00

→ Ответить

Leonid

14 лет назад, # ^ |

Yeah, had to wake up 6AM to make it (UK time).

→ Ответить

yandry

14 лет назад, # ^ |

+17

I did not sleep at all :) The contest started at 1.00am in Cuba.

→ Ответить

sajad22

14 лет назад, # ^ |

-12

به آریو برزن:

شما میباس صبحها بری مدرسه!!!

نه اینکه تو خونه بخوابی

از خودم یاد بگیر:D

→ Ответить

unprost

14 лет назад, # ^ |

← Rev. 2 →

不是每個人都明白你寫什麼。可能會更好地使用英語進行交流：）

→ Ответить

havaliza

14 лет назад, # ^ |

Haha...!
It'd be nice to have a auto-translate option for comments in non-English. Using Google Translate API maybe.

→ Ответить

A.K.Goharshady

14 лет назад, # ^ |

← Rev. 2 →

Come on guys. stop writing in Persian and Chinese. This is not nice really. Imagine what happens if everyone wants to write comment in his own native language? Do you enjoy that really?

@Sajad: Call me Amir :) , I don't go to school. It's a waste of time :D

→ Ответить

ZiyaoWei

14 лет назад, # ^ |

Don't panic there:) the Chinese above is something like this:

"Not everybody understands what you are saying here. If using English, maybe we could understand each other better this way."

So you see, just a little in-joke for Chinese speaking people:)

→ Ответить

Perlik

14 лет назад, # ^ |

you are cuban pepper))

→ Ответить

Creed

14 лет назад, # ^ |

← Rev. 2 →

NO NO NO! He is pepper from KUBAN!!!

→ Ответить

Perlik

14 лет назад, # ^ |

← Rev. 3 →

you're certainly right)

→ Ответить

14 лет назад, # |

epic fail

Научите меня читать

→ Ответить

denys.astanin

14 лет назад, # ^ |

только я такой особенный или у кого-то тоже возникли непонятки с формулировками в Б?

после каждой запятой шел ровно один пробел (если запятая является последним символом строки, то это правило к ней не применимо),
перед каждым многоточием был ровно один пробел (если многоточие начинает строку, то это правило к нему не применимо),
других пробелов быть не должно.

при тесте "... ," ответ должен быть "...,", а я возвращал "... ,"

немного не ясно почему, ибо про разделение чисел пробелами сказан, а про разделение знаков - нет. понимаю, что сам виноват, но все же неприятно из-за этого схватывать WA

→ Ответить

14 лет назад, # ^ |

Ну я тоже сперва примерно с этим тупил, и не проходил первый sample

но:

других пробелов быть не должно.

→ Ответить

denys.astanin

14 лет назад, # ^ |

*посыпая пеплом голову

да-да.

→ Ответить

sajad22

14 лет назад, # |

← Rev. 2 →

→ Ответить

Connector

14 лет назад, # |

Мне кажется или произошла очередная инфляция рейтинга?

→ Ответить

Perlik

14 лет назад, # ^ |

мне тоже так показалось, особенно у 2-ого дивизиона. наверное это потому, что многие фиолетовые и оранжевые ниже многих зеленых и синих.

→ Ответить

mnlm	14 лет назад, # \| +3 can anyone tell me how to solve the problem E. although it has tag of tree and dp, but i think it is not a tree, how can we to solve it with tree dp. → Ответить

14 лет назад, # ^ |

← Rev. 3 →

1). Lets choose some person and walk to its' friend, to a friend of a friend and so on. Obviously, at some point we will receive a cycle. So, generally, our graph ( nodes=people, edges=friendship) is divided into cycles with som "tails" whom which you can go into the cycle by edges.

2). Let's traverse every edge. Cycle remains cycle and from some nodes on a cycle we now can go to some other nodes, possibly from one node to few different nodes. So actually our figure is a cycle with oriented trees that "hang" on the nodes of cycle.

3).For each tree compute the following DP:

F(i,0) = maximum number of pairs we can choose from subtree of i we we don't use i in any pair.

F(i,1) = the same if we match i with some of its descendants.

Obviously, F(i,0)=sum(max(F(Child i,0), F(Child i,1))) for each child of i.

Obivously, F(i,1)=max(F(i,0)-max(F(Child i,0), F(Child i,1))+F(Child i,0)+1) for each child of i. (We loop through all children of i and try to pair i with that child).

4). Now we have two options: to match last node of a cycle with first one, and not to match. In both cases we then delete our edge from last to first node and we get a chain. We perform almost the same DP on this chain:

G(i,0) = F(i,0)+max(G(i-1,0),G(i-1,1)) - we don't match i-th node with anything.

G(i,1) = max(F(i,1)+max(G(i-1,0),G(i-1,1)), F(i,0)+1+G(i-1,0))

For G(i,1) we have to options: we either match our node with some node in its subtree (first value in max) or match it with previous node in cycle and add F(i,0).

In case if we match 1-st and last node, G(0,0)=-infinity, G(0,1)=1+F(0,0) and the answer is in G(n-1,0), because n-1-th vertex can not be matched with previous node as it is already matched with the first one.

In case if we don't, G(0,0)=F(0,0), G(0,1)=F(0,1) and answer is max(G(n-1,0), G(n-1,1)).

Also, to make it easier, I wrote about DP that just returns maximum number of pairs but I hope it is obvious how to turn in to DP that returns maximum number of pairs|maximum number of boy-girl pairs.

Hope this helps!

PS. Solution below is better because it is easier and uses only one DP instead of two.

→ Ответить

mnlm	14 лет назад, # ^ \| ← Rev. 2 → 0 thank you very much! → Ответить

14 лет назад, # ^ |

← Rev. 2 →

>> S. Solution below is better because it is easier and uses only one DP instead of two.

In such case your approach has to be more general than approach formulated below.

If no, than your approach should be just more complicated and doesn't solve more general class of such problems ? Can you clear it ?

→ Ответить

2222	14 лет назад, # ^ \| +10 Each connected component in the graph has exactly one cycle. Pick any edge from the cycle and remove it from the graph, now we should consider two cases: a picked edge is in the answer and it isn’t there. Both cases can be easily solved with dp on tree. → Ответить

mnlm	14 лет назад, # ^ \| 0 you answer is also clear → Ответить

14 лет назад, # |

-8

Раскажите пожалуйста как решать задачу Е.

По существу, я так понимаю, что она идейно очень похожа на вот ету http://mirror.codeforces.com/contest/70/problem/E. Очень бил би благодарен за хорошое обєснение, возможно нє только етой задачи(Е. По парам.), но и самого принципа. Да и еще парочку задач разной сложности чтобы ето закрепить. :)

→ Ответить

14 лет назад, # |

Перенесу обсуждение сюда.

var
 s : ansistring;
 i, n : longint;
begin
    readln(s);
    n := length(s);
    for i := n - 1 downto 1 do if (s[i] = s[i + 1]) then delete(s, i, 2);
    writeln(s);
end.

Это код посылок 427555 и 427592 с соревнования (от Ministr).
Код абсолютно одинаков. Разница в том, что первая посылка получает
Превышен предел времени на взломе 1 [взломы], а вторая Полное решение [претесты].

Подумал-подумал и решил проверить это решение на систестах в дорешивании. Результат:
Delphi: Превышен предел времени на тесте 12, 1000 мс
FreePascal: Полное решение, 770 мс

Теперь мне хочется прогнать этот код во фри на сервере с тестом [ab]x49999 + [ba]x49999 + c. К сожалению сейчас это сделать невозможно (ограничение на ввод - 20kb).

→ Ответить

14 лет назад, # ^ |

Оно, конечно, не совсем то, но допиши код генерации теста в саму прогу. Я думаю, что медленнее от этого она точно не станет, но при этом останется в TL.

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

Уже сам проверил. На delphi работает ~12 секунд. Как-то нехорошо вышло.
UPD. На fpc - 3,5. Код здесь.

→ Ответить

14 лет назад, # ^ |

← Rev. 7 →

UPD2. Так там 400к символов. Пост выше игнорировать наверное.

А вот этот код с 200k символами работает на fpc за 840 ms.

И 3050 мс на Дельфях.

Так что шанс сдать этот квадрат видимо был. о_О

Интересно что за тест был 2й и 3й, которые его поломали.

UPD. Да, оба не умеем считать)))

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

~~Тут всего 100Кб из 200 разрешенных условием.~~
UPD. Считать не умею.

→ Ответить

14 лет назад, # ^ |

Более того, если вызывать delete в конце строки(особенно от последнего символа) то получится что-то похожее на линию.

Для этого нужно просто обрабатывать данные по мере считывания.

→ Ответить

14 лет назад, # ^ |

Мы сейчас говорим конкретно про это решение. Оно квадратичное в худшем случае как не крути. :)

А точнее даже не об этом решении, а о том, как оно проходило взломы и было снова взломано.

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

Такой вот тест:

ab*35000+ba*35000+cd*30000 работает 1110мс.

код

→ Ответить

nep1965

14 лет назад, # ^ |

var s,b:ansistring;

i:longint;

begin

readln(s);

b:=s[1];

for i:=2 to length(s) do

begin

if (b<>'') and (s[i]=b[length(b)])

then delete(b,length(b),1)

else b:=b+s[i];

end;

writeln(b);

end.

Мое решение, которое не обращается к несущестующему символу. Памяти ест вдвое больше, зато не падает на aaabbbcc

→ Ответить

14 лет назад, # ^ |

Если считывать посимвольно - лишней памяти не потребуется.

→ Ответить

nep1965

14 лет назад, # ^ |

Согласен.

→ Ответить

pernay

14 лет назад, # |

При участии вне конкурса во второй квалификации, влияет ли она на рейтинг?

→ Ответить

14 лет назад, # ^ |

MikeMirzayanov

Да, все раунды будут рейтинговыми. Более того, во всех них сможет принять участие любой желающий. Если участник не квалифицирован на этот раунд, он будет участвовать вне конкурса, но рейтинг участника будет пересчитан в соответствии с совмещенной таблицей результатов участников в конкурсе и нет. Вероятно, исключением станет финальный раунд, поживем-увидим.

→ Ответить

14 лет назад, # ^ |

Да, так уже было на Manthan.

→ Ответить

hust.elt

14 лет назад, # |

+11

Hi!

I don't know why I can't register Qualification 2.

It said that I had already qualified into the competition, and let me choose whether I want to register as OUT OF COMPETITION participant. I choosed "Yes", but it didn't work, I still can't register this competition.

Anyone can explain this and help me? Thanks a lot!

→ Ответить

14 лет назад, # ^ |

← Rev. 2 →

+11

you are in list of registered

→ Ответить

hust.elt

14 лет назад, # ^ |

← Rev. 2 →

+13

Thanks very much, RiaD-WaW!

Well, Actually I found my name in registrant list, but it didn't show register completed information in contest list. Maybe it's a bug, I think.

→ Ответить

watashi

14 лет назад, # ^ |

I just met the same problem. I think it's a trivial bug.

→ Ответить

hust.elt

14 лет назад, # ^ |

Watashi...Orz...Orz...Orz...Orz...Orz...

I saw you in FZ, and I sat opposite to you, lol......

→ Ответить

14 лет назад, # |

Кстати, видимо впервые более 1000 человек участвовали в контесте.

→ Ответить

yeputons

14 лет назад, # ^ |

Не-не-не. А как же раунды 56, 58, 60-66, 68, 71?

→ Ответить

14 лет назад, # ^ |

Зарегистрировались != участвовали

→ Ответить

yeputons

14 лет назад, # ^ |

Тогда, видимо, да.

→ Ответить

Horuka

14 лет назад, # |

Что то мне подсказывает, что количество участников второй квалификации перевалит за 2000=)

→ Ответить

14 лет назад, # ^ |

Не дай Бог, а то снова отсылать задачи буду минут по пять. :-)

→ Ответить

14 лет назад, # ^ |

По-моему это только на пользу проекту, может из названия быстрее исчезнет греческая буква (хоть она и не мешает)...

→ Ответить

zendo

14 лет назад, # ^ |

делаем ставки, господа?

→ Ответить

zendo

14 лет назад, # ^ |

← Rev. 2 →

→ Ответить

14 лет назад, # ^ |

2000-ый зарегестрировавшийся - erepb1991

→ Ответить

Horuka

14 лет назад, # ^ |

Оп=). Правильное предсказание.

Будем держать кулаки за сервак.

→ Ответить

caustique

14 лет назад, # |

Дайте все-таки уточнить.
При регистрации на вторую квалификацию мне сказали, что я регаюсь вне конкурса, потому что уже квалифицировался в первый раунд.
Значит ли это, что раунд не повлияет на мой рейтинг или все-таки повлияет?

→ Ответить