TopCoder SRM 499 - Codeforces

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

← Rev. 2 →

-7

*ворчливо*
Ну конечно, кто-то может, Илья вон, например... А хотя бы просто победы в комнате не хватит? Хотя это надо уже у девушки спрашивать...

→ Ответить

Sammarize

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

Ха, ну даже такой подарок надо уметь преподнести, не так ли?)

→ Ответить

Melamori

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

Некоторые подруги и сами SRM играют. Будем считать, что пост для них и одиноких парней, если уж "уделить внимание" исключает "играть контест" в некоторой системе логических правил. =)

→ Ответить

Melamori

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

+10

Удачи всем! =)

→ Ответить

Kenny_HORROR

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

Интересно как решается 1000. Может кто-нибудь рассказать?

→ Ответить

Egor

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

+13

Понятно, что порядок букв не важен. Построим граф где вершинами будут варианты разбиения k на сумму 4 чисел. Ребрами связаны те, которые можно получить преобразованием. Нам нужно в этом графе (максимум 5456 ребер) надо найти компоненты сильной связности. Далее для каждой компоненты посчитаем ее вес как сумму веса вершин. Вес вершины - количество строк, которые ей соответствуют (произведение 3 цешек). Осталось найти самый большой по весу путь на графе из компонент связности - это уже совсем просто

→ Ответить

Kenny_HORROR

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

Спасибо. Вроде всё понял. =)

→ Ответить

MBabin

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

А почему это будет правильным ответом?

→ Ответить

Egor	14 лет назад, # ^ \| 0 Потому, что куда мы можем дойти? Во все вершины в той же компоненте сильной связности и потом надо выбрать, куда дальше идти. Я понимаю, что это не строгое доказательство, но если немного подумать, то можно придумать конкретную раскраску в столько цветов → Ответить

MBabin

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

Я как раз, как раскрасить и не придумал :)(а из-за того, что над этим думал не успел дописать немного).

→ Ответить

Petr

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

Мне кажется легче придумать, если вспомнить, как мы этот самый весомый путь будем искать. Мы для каждой компоненты x берем f(x)=weight(x)+max(f(y)) по всем y куда есть ребра из x, так?

Соответственно и раскраска получается - мы красим все вершины достижимые из x в цвета с 1 по f(x) следующим образом: компоненту x в цвета с max(f(y))+1 по max(f(y))+weight(x).

→ Ответить

MBabin

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

← Rev. 2 →

Спасибо, и правда не сложно)

→ Ответить

KADR

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

Да, обидно. Накодил такое же еще в первой половине контеста, но до конца так и не нашел баг. При этом все надеялся добить ее и за 550 не садился.

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

→ Ответить

cerealguy

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

Надо взять граф из всех состояний с точностью до перестановки букв и построить конденсацию.

→ Ответить

Nyatl

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

Решал 550, думая что "RETURN" можно ставить только в конце. Написал решение за O(10^6 * n + n^2), не мог его доказать, а потом перечитал условие, а там: "добавлять можно в любое место". Соответственно, пришлось всё переписывать с нуля, но зато понял основные ошибки, которые можно здесь допустить. В итоге - 8 челенжей :E

→ Ответить

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

а где можно посмотреть тест на котором случился эпик фейл?

→ Ответить

Skiminok

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

В Division Summary по своему нику правой кнопкой -> History.

→ Ответить

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

← Rev. 2 →

O_O
А ведь и правда можно. Спасибо, раньше не знал, всегда ждал, пока статистику на сайт не вывесят. Вернее, пока практис-рум не откроют, если речь идёт о систесте.

→ Ответить

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

да, раунд оказался богатым на челленжи =)

основной тест, который проваливали многие 550-ые решения - {1, 2, 3, 2, 1}; правильный ответ 7 =)

→ Ответить

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

Наконец-то я вышел в дивизион 1!

Что ж, второй удачный контест за два дня.

→ Ответить

Egor	14 лет назад, # \| 0 Ну вот как обидно. Упало по стеку, причем если бы убрать один параметр в рекурсии ненужный - проходило бы... → Ответить

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

а зачем вообще передавать в рекурсию ненужные параметры? =)

→ Ответить

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

+17

ух, я получил уже -2 за этот комментарий! =) видимо, многие считают, что передавать ненужные параметры в рекурсию нужно... ;)

→ Ответить

Egor	14 лет назад, # ^ \| +5 Ну, потому что prewritten code и общий фреймворк с дфс коллбеком. Видимо надо не поленится и развернуть его без рекурсии → Ответить

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

а, prewritten code, понятно всё =)

у меня, к сожалению, нет вообще prewritten code в топкодерской заготовке, поэтому с такими проблемами я ещё не сталкивался

→ Ответить

Egor	14 лет назад, # ^ \| 0 А у меня не в заготовке - отдельно распихано → Ответить

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

под заготовкой я подразумеваю несколько файликов с алгоритмами

если говорить о заготовке в другом смысле этого слова, то пихать всё в один файл неразумно, ибо штрафы за unused code, а каждый раз удалять все ненужные алгоритмы - лучше заготовку вообще не иметь тогда =)

→ Ответить

taras.klaskovsky

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

А что за штрафы за unused code?

→ Ответить

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

ну когда много неиспользуемого кода у тебя - дефайны неиспользуемые, код потоков, fft, ещё какой-нибудь фигни в простой задаче - то тебя предупреждают, что могут отнять, кажется, 75% баллов за задачу

это средство защиты от обфускации

→ Ответить

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

наверно, за тем же, зачем и допускать иные ошибки в решении

→ Ответить

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

← Rev. 2 →

омг, глупость-то какая

когда я пишу код, я знаю, зачем мне нужна та или иная переменная; почему размеры массивов именно такие и т.п.

если ошибка из-за невнимательности или кривоты рук - это одно, а unused variable - это совсем другое

UPD ага, а вот и ответ, почему так случилось: prewritten code

→ Ответить

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

а вот у меня unused variable часто появляется из-за невнимательности и кривых рук)

→ Ответить

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

ну это печально =/

→ Ответить

SergeyLazarev

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

Впервые решил 2 задачи. И снова стал желтым. Ура=)

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

→ Ответить

steiner

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

Да, у меня тоже прошло однопроходное решение. Челленджили неудачно несколько раз.

→ Ответить

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

у нас было двое синих в комнате с ~1200 рейтингом, оба написали жадину за 10 минут

у каждого 6-7 defend'ов =)

→ Ответить

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

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

→ Ответить

Egor	14 лет назад, # ^ \| 0 Заметим, что они были об этом не в курсе :) → Ответить

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

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

→ Ответить

Sammarize

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

В третьем раунде TCO 2010 был ещё более впечатляющий троллинг) Больше половины участников очень быстро сдали красивое, простое и неправильное решение 250той =)

→ Ответить

iensen

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

← Rev. 5 →

В смысле совсем O(N)?А в чем идея?

Я писал так:

Для первой строки need[0]=lines[0].

Для последующих строк ясно,что мы либо строим их с нуля либо копируем какую то часть с предыдущей.То есть need[i]=min(abs(j-length[i])+1),j=0..lines[i-1].

Ответ-need[0]+need[n-1]

UPD:need[0]+need[1]+..need[n-1]

Получается O(N*Max(Length)).

Правда как всегда сделал тупой баг:забыл +1 для '\n' в случае когда строка строится с нуля и получился очередной epic fail:)

→ Ответить

SergeyLazarev

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

int res = lines[0];

for (int i=1; i<lines.length; i++){
res++;
if (lines[i] > lines[i-1])
res += lines[i]-lines[i-1];
}

→ Ответить

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

да, крутая задача

все ждали tricky dp, а тут "на тебе!" =)

→ Ответить

Egor	14 лет назад, # ^ \| +8 Одно только не понятно - какого хрена 550? Ведь ДП тоже не очень трики, прямо скажем → Ответить

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

чтобы порвать шаблон окончательно ;)

→ Ответить

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

← Rev. 2 →

Есть кой-какое подозрение. Все нормальные люди в нашей комнате, насколько я смотрел, раз уж писали ДП, то с масштабированием по числу пробелов и, соответственно, с вообще не жалко какой сложностью. И только Ферлон догадался писать за 50*10⁶, поэтому если б он всё же с какими-то неимоверными вывертами это дописал (в возможности чего он уже сомневается), то ему и ему подобным уникумам 550 было бы справедливой наградой %)

→ Ответить

Gassa

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

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

→ Ответить

Medium

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

а какое там дп нормальное?

→ Ответить

SkorKNURE

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

Можете объяснить идею ДП по 550, реализованную у Петра, JongMan'а и еще у 50-100 человек из дивизиона (dp[50][50][50])? Хочу убедиться что правильно понял...

→ Ответить

NALP

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

← Rev. 2 →

Лично у меня было так: d[l][r][value] - минимальное количество действий, нужных, чтобы привести в порядок отрезок с l по r, если l-ое значение у нас сейчас имеет значение value. Понятно, что важных значений у нас всего 50, а не 10^6.

А дальше нам нужно выбрать некоторые значение из (l, r], которые получатся копированием l-ого элемента, пока мы будем его делать такми как нужно (то есть мы как бы изменяем наш l-ый элемент с value до lines[l], а во время этого иногда нажимаем RETURN). Это можно делать тупой вложенной динамикой, но тогда получится плохая асимптотика. *Если непонятно, почему мы так действуем, могу потом объяснить подробнее.*

А будем откусывать по последнему нашему RETURN'у и переход следующий:

d[l][r][value] = min( 1 + |value - nval| + d[l][i - 1][nval] + d[i][r][nval]), где мы перебираем i в отрезке [l + 1, r] и nval в отрезке [value, lines[l]] (ну или [lines[l], value], смотря удаляем мы или прибавляем пробелы)

Замечу, что у меня не прошло изза маленькой тупой баги. Сдал в дорешивание

→ Ответить

SkorKNURE

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

>> ... если l-ое значение у нас сейчас имеет значение value ...

Спасибо. Значит я правильно понял :-)

→ Ответить

SergeyLazarev

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

Но додумался я до этого, к сожалению, только под конец. А до этого тоже ДП придумать пытался. А могло бы быть очков на 100-150 побольше...

→ Ответить

iensen

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

Точно,копируем не какую то часть а максимально-возможную:)

→ Ответить

Fcdkbear

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

А почему только 0 и n-1 суммируются?

→ Ответить

iensen

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

← Rev. 2 →

ignore

→ Ответить

Fcdkbear

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

Спасибо, но мне не ясно почему ответ need[0]+need[n-1] а не сума всех need[i] (i от 0 до n-1)

→ Ответить

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

Поведайте пожалуйста, как решалась 3 задача 2 дивизиона?

→ Ответить

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

← Rev. 2 →

Главное ограничение в условии - то, что все слова одинаковой длины. Поэтому нам надо выбрать все пары слов из массива такие, что front[i]=reverse(front[j]). При этом если существует несколько слов одинаковых слов надо выбирать слово с максимальной стоимостью. Я для этого использовал map<string, priority_queue<int>>, в котором хранил каким словам соответствуют какие стоимости.

→ Ответить

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

Спасибо, а как просматривать такие случаи {"xyx","xyx","xyx","zzz","zzz","zzz"} {5,7,2,1,6,4}?

→ Ответить

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

Здесь в мапе бы хранилось:

"xyx": 7,5,2

"zzz": 6,4,1

У меня был отдельный цикл, в котором я сравнивал front[i] и reverse(front[i]). После работы этого цикла осталось бы:

"xyx": 2

"zzz": 1

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

→ Ответить