TCO12 Algorithm Квалификационный раунд 1B

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

← Rev. 2 →

+10

Когда пытаюсь зарегаться в арене пишет

Registration in this competition is by invitation only

Что это такое? Хотя на tco я зареган...

→ Ответить

SkyHawk

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

Может быть дело в том, что участвовать могут только те, кто ещё не отобрался в первый раунд?

→ Ответить

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

Может вы имели ввиду кто не прошёл во второй из 1A? Так я там не участвовал..

→ Ответить

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

← Rev. 2 →

+35

Блин :( По ходу нужно не меньше чем за день быть зареганным на tco :( А я сегодня зарегался :( Нафига так делать...

UPD. так и есть http://community.topcoder.com/tco12/algorithm-rules/

In order to compete in Online Rounds 1A and 1B, individuals must be registered for the Tournament at least 24 hours prior to the start of that Online Round.

Блин, ну это гавно :( какие проблемы брать список зареганных онлайн :(

→ Ответить

olpetOdessaONU

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

А как регаться на ТКО? Что-то я такого не помню по прошлому году. В арене не нашёл, на сайте тоже.

→ Ответить

Anarivu

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

← Rev. 2 →

http://community.topcoder.com/tco12/ там на лесенке, если ты еще не зарегистрировался, должна быть соответствующая кнопка

→ Ответить

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

Вот сколько лет как ТопКодер ввел это правило, сколько люди на него жалуются, столько я не понимаю: какие проблемы почитать правила турнира? Или хотя бы зарегиться сразу, когда можно — за месяц ведь регистрация открывается? Нет, какая-то сложность в этом должна быть, не зря же столько людей не справляются, но вот какая?..

→ Ответить

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

← Rev. 3 →

+20

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

→ Ответить

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

+10

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

А вы на каждый контест перечитываете правила соревнований? Может и перед каждым кф раундом перечитывать.. может, они там заменились, но я же подтверждаю что прочитал их. Вобщем это совсем не очевидное правило является очень глупым. Я считаю, если это возможно, правила должны быть логичными, а тут совсем не видно смысла и логики.

→ Ответить

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

+14

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

На кф раундах правила я не перечитываю по ряду причин: 1) я в них не участвую, 2) каждый отдельно взятый раунд не настолько важен, как TCO, 3) правила существуют в виде ссылки на блог пост, изменения в котором показываются в "прямом эфире", за которым я слежу независимо от раундов.

→ Ответить

DAle

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

← Rev. 3 →

Я вообще согласен, что это правило довольно специфическое и желательно, чтобы его не было. Но с другой стороны, мало ли какие причины побудили это правило ввести, может быть есть необходимость. Справедливости ради, в письме, которое присылается до соревнования, о регистрации на TCO за сутки написано явно.

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

→ Ответить

Edvard

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

Думаю все просто любят делать все в последний момент. Мне это тоже нравится, но на TCO я заранее зарегался))

→ Ответить

Edvard

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

Раз уж речь зашла о марафонах, то у меня такой вопрос: чтобы участвовать в марафоне нужно просто открыть задачу или нужно что-нибудь послать?

→ Ответить

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

Что-нибудь послать (example test или full submission).

→ Ответить

Edvard

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

А можете вкратце объяснить в чём разница между example test и full submission? Я ни разу не писал марафон хочу TCO Marathon написать. Кстати я правильно понимаю что будет 3 TCO Marathon раунда из каждого 4 человека выходит на онсайт?

→ Ответить

I_love_Tanya_Romanova

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

+20

Да, правильно. 3*4.

Баллы за фулл отображаются в итоговой таблице; итоговому тестированию подлежит тоже именно фулл-сабмит.

Ну а сэмплы... Во-первых, на них можно тестировать "в процессе" доработки (ведь там время между сабмитами всего 15 минут, а не 2 часа, как на фулл), во-вторых — это некая возможность "не раскрывать карты". Т.е. если фулл не отличается принципиально от сэмплов (а такое не всегда бывает, — например, бывает так, что сэмплы полностью из открытой инфы состоят и т.д... и, скажем, обученная на той же инфе генетика просто летает на сэмплах... но так далеко не всегда), то можно предположить, что результат из сэмплов примерно так же перенесется и на фулл — тогда у вас есть инфа о возможном результате, а у супротивников нету (до момента вашего сабмита на фулл, который может быть даже за 5 минут до конца матча).

Ну и сэмплы — это сэмплы))) как в АСМ, с той лишь разницей, что тут они автоматически делают матч рейтинговым. Т.е. реально на сэмплах можно проверить, корректно ли работает решение (не падает в их системе и т.д.).

→ Ответить

http://apps.topcoder.com/forums/?module=Thread&threadID=687316&start=0

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

← Rev. 2 →

+20

Мне как райтеру этой задачи это намерение кажется крайне похвальным :-)

Example test прогоняется на 10 тестах из условия (с известными сидами), по нему дается подробная информация (время выполнения, скор, вывод в cerr/cout, если решение его пишет, и текст ошибок, если есть). Full submission прогоняется на 100 тестах с неизвестными сидами и выдает только общий скор по ним (в данном случае сумму). Кроме того, только full submission изменяет место в ранклисте (по скору на этих 100 тестах).

Да, правильно.

→ Ответить

Tranvick

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

← Rev. 2 →

Всех выкидывало в начале каждые минут 5, или у меня в самый подходящий момент что-то с модемом?

→ Ответить

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

Меня не выкидывало, моего друга тоже.

→ Ответить

imslavko

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

и почему ява зависает во время челендж фазы?

→ Ответить

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

Как решать Medium?

→ Ответить

helThazar

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

Сортируем по возрастанию (убыванию).

Считаем динамику d[i][j] — минимальное количество времени, чтобы сделать задания с iго по jый. d[i][j] = min( max(d[i][k-1], d[k][j])+split ) для всех i+1<=k<=j. Дно динамики d[i][i] = work[i].

→ Ответить

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

Впервые вижу, чтобы базу называли дном :)

→ Ответить

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

+17

Пишем Хаффмана =)

→ Ответить

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

Ой, и правда. Как до этого догадываться надо?

→ Ответить

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

-8

Ну смотришь на структуру ответа, пытаешься что-то посвопать с чем-то... и понимаешь... да это же Хаффман )) самое забавное, что почти у всех в таком решении написан max хотя он никому не нужен...

→ Ответить

fetetriste

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

← Rev. 3 →

+14

Доставать (из кучи) два минимальных времени a и b и возвращать туда max(a,b)+splitCost, пока не останется один элемент. Это и есть ответ.

→ Ответить

safeasmilk

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

← Rev. 2 →

Должен же кто-то первым поныть

Догадался под конец до такого решения, но не успел отладить. :(

→ Ответить

Alex_KPR

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

ого, красиво! с ходу не очевидно, что это — правильно, надо подумать

я писал бинпоиск по ответу

→ Ответить

gen

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

Тоже писал, но забыл поразмножать лис после совершения работ. Свалится... );

→ Ответить

Alex_KPR

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

а зачем их размножать после завершения работ?

→ Ответить

gen

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

А, я почему-то сейчас подумал, что у работ задано время начала. :D Тогда, наверное, можно их поразмножать перед началом всех работ.

→ Ответить

witua

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

← Rev. 2 →

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

→ Ответить

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

я бинпоиск написал

→ Ответить

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

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

Напоролась, кстати, на то, что KawigiEdit использует одни и те же глобальные переменные для всех тестов без очистки: первые два примера прошли хорошо, на остальных получалась ерунда. Потерянное время на этом + поначалу я этой задачи испугалась и пошла читать Hard = почти одинаковые баллы за первые две задачи.

→ Ответить

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

+36

Я думал, намного будет... Намного легче будет это все. И очень сложные задачи, просто очень сложные задачи! Я думал, намного легче это все будет. Сколько раз здесь решал — было намного легче, но на этот раз как-то не удалось. Во-первых, народу много, задачи — трудные...

→ Ответить

safeasmilk

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

Учитывая, что у подавляющей части топ600 не меньше двух задач, гм, апостериорная сложность контеста вполне ок.

→ Ответить

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

Какая пафосная фраза. Впечатлило.

→ Ответить

Jokser

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

-10

Надо было 1000-ку открывать, раз 500 не пошла. По мне она проще чем 500.

→ Ответить

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

Честно говоря, мне лень читать правила.

Сколько человек в следующий раунд проходит?

→ Ответить

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

-14

вроде 1000

→ Ответить

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

Нее, 1000 не может быть.

Я по первому не прошел, хотя был выше 1000ого места.

→ Ответить

ilya.korovin

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

← Rev. 2 →

600 * 3 = 1800

то есть 600 с каждого отборочного

→ Ответить

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

Да, что-то похожее на правду. Спасибо.

→ Ответить

imslavko

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

Ура! Две задачки прошли :). Я во второй писал дп по префиксу и кол-ву лис, которые у нас есть.

Объясните 1000? Почему-то я весь контест верил в паросочетание минимального веса

→ Ответить

shevchen

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

← Rev. 3 →

Идея в том, что один из рядов можно не трогать.

Допустим, будем менять первый ряд. Посмотрим на последний своп (a, a + 1) во втором ряду в оптимальной стратегии; не будем его делать, а вместо этого в конце свопнем те же элементы первого ряда.

Тогда можно по очереди выбирать, что поставить на i-е место в первом ряду. Состояние — текущая позиция, а также уже взятые элементы первого ряда.

→ Ответить

Ripatti

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

+15

я писал дп на масках

сначала поверим, что оптимальный способ свапанья следуюший:

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

ок, теперь сама dp[mask] — наименьшее количество свопов, где mask — подмножество вершин 2 доли, которые мы потом подвинем до упора влево.

пересчитываем так: для mask находим количество единичек ones и пробуем соединить ребром вершинку номер ones из 1й доли со всеми вершинками, что в маске mask во 2й доле и аккуратно считаем сколько свапов надо (исходя из dp для масок после выкидывания этой пары и, собственно, пары). из всех возможных "соединений" выбираем минимум.

ответ в dp[11..111]

→ Ответить

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

отлично, 500 прошла, 250 упала!

→ Ответить

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

а на чем упала?

→ Ответить

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

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

мне сразу показалось странным, что я ее первый в комнате сдал((

еще и -25, так еще и в 600 не попал(

→ Ответить

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

У меня прошла только первая (и единственная отосланная), +2 челленджа, так что мне повезло :)

→ Ответить

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

-6

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

→ Ответить

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

Офигеть, сколько решений первой упали...

Я аж на 130 мест поднялся после систеста.

→ Ответить

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

Да с первой задачей что-то странное, я прочитал, сразу написал, посабмитил — смотрю — первый в комнате ее сдал на 243.44. (и больше ничего не решил...)

А в итоге у лидера комнаты она упала, а MikeMirzayanov, занявший в этой комнате второе место, сделал ресабмит в самом конце. И вроде там негде ошибиться.

→ Ответить

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

есть там где ошибиться например тест пять единичек неправильно обработать... написав проверку криво если i и k-1-i равны...

→ Ответить

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

+21

Я давно заметил, что 95% решений на каждом контесте пишутся под веществами...

→ Ответить

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

+26

а успешность зависит от того, под каким именно веществом ты был :)

→ Ответить

phantom11

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

← Rev. 3 →

Can someone please explain me the intution of Prob 500.I saw a solution of Yarin which is as follows:

Collections.sort(a);
while(a.size()>1)
{
a.set(0,Math.max(a.get(0),a.get(1))+hammerCost);
a.remove(1);
Collections.sort(a);
}

But I cannot figure out why this happens??Would be grateful if someone explains the reason....

→ Ответить