Code Jam: кто за сколько решит задачку из первого раунда

[creative]

Есть задачка:

http://code.google.com/codejam/contest/ ... d?c=544101

Вкратце правила следующие:

1. Скачать оба набора входных данных (small и large).
2. Скормить их своей программе.
3. Загрузить файлы с выходными данными.

Задание будет выполнено, если система примет эти выходные данные.

Мне интересно за сколько времени решите Вы, так как несмотря на простое задание я очень долго тупил почему мои выходные данные от large система не принимает. Только потом разобрался.

P.S. В борьбе против собственной тормознутости...

[allchemist]

Да ну это скучно

Присоединяйтесь к Google AI Challenge, это веселее

[venco]

creative в сообщении #354982 писал(а):

Мне интересно за сколько времени решите Вы

<15 минут

[creative]

venco в сообщении #355147 писал(а):

<15 минут

Мда, мне есть к чему стремится...

ОК, попробую решить вторую:

http://code.google.com/codejam/contest/ ... 44101#s=p1

Но теперь мне сначала интересно Ваше время решения вот этой задачи, чтобы при решении я стремился, чтобы моё время хотя бы на порядок не превышало Ваше.

[venco]

creative в сообщении #355161 писал(а):

Но теперь мне сначала интересно Ваше время решения вот этой задачи, чтобы при решении я стремился, чтобы моё время хотя бы на порядок не превышало Ваше.

~18 минут.

[Dandan]

нажимаешь на full scoreboard, ставишь галочку Time Submitted и смотришь кто за сколько времени сделал из участников во время контеста. Там же можно и скачать решения

[creative]

Dandan в сообщении #355327 писал(а):

нажимаешь на full scoreboard, ставишь галочку Time Submitted и смотришь кто за сколько времени сделал из участников во время контеста. Там же можно и скачать решения

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

[creative]

venco в сообщении #355263 писал(а):

creative в сообщении #355161 писал(а):

Но теперь мне сначала интересно Ваше время решения вот этой задачи, чтобы при решении я стремился, чтобы моё время хотя бы на порядок не превышало Ваше.

~18 минут.

Уже 8 часов прошло, вообще не представляю как её решить (т.е. даже до кодирования не дошёл)! Кажется это на неделю или больше размышлений о том, как гарантировать минимальный cost (по условию задачи), если не смотреть готовые алгоритмы.

По сути я намертво уже 8 часов как застрял на том как гарантированно удовлетворить условию:

$min\left\{ k\ :\ k=\sum\limits _{j=1}^{N}|a'_{j}-a_{j}|\ \wedge\ \forall2\leq j\leq N(a'_{j}-a'_{j-1}\leq M)\right\}$

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

У меня вопрос: Вы сами придумали решение этой задачи или же вспомнили подобную типовую задачу из прошлого опыта?

P.S. Я про эту: http://code.google.com/codejam/contest/ ... 1#s=p1&a=1

[venco]

Задача на применение метода динамического программирования (Dynamic Programming), а именно усложнённый вариант поиска расстояния Левенштейна (Levenshtein distance).
Метод полезно знать и уметь применять.

[creative]

venco в сообщении #364142 писал(а):

Задача на применение метода динамического программирования (Dynamic Programming), а именно усложнённый вариант поиска расстояния Левенштейна (Levenshtein distance).
Метод полезно знать и уметь применять.

За сколько времени Вы смогли бы решить эту задачу "с нуля", то есть изобретая её решение?
Просто именно с таким подходом я пытаюсь решать эти задачи, может быть это слишком жёстко.

Т.е. реально ли решать за 20 минут подобные задачи изобретая решение с нуля (оставляя в стороне вопрос о практичности данного подхода)?

[venco]

creative в сообщении #364151 писал(а):

За сколько времени Вы смогли бы решить эту задачу "с нуля", то есть изобретая её решение?

Не зная метод DP - может и не решил бы. Ну или изобрёл бы DP сам. DP - это не решение специфической задачи, а технология, применимая на огромном классе задач, типа рекурсии.
Знание же конкретного применения DP для расстояния Левенштейна помогает мало, т.к. задачу усложнили существенно.

[creative]

venco

Понятно, буду вкуривать "INTRODUCTION TO ALGORITHMS, Second Edition" ("Алгоритмы: построение и анализ") дальше.