Topcoder SRM 498 - Codeforces

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

← Rev. 2 →

-8

история маленького фэйла :)

благодаря плагину moj я все делаю в MSVS

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

нажал submit и не потрудился посмотреть на сообщения которые вылезли

воткнул в лажу только через 15 минут, увидев результаты комнаты - перед сабмитом я не нажал compile!!

обидно за свои ~40 баллов )

→ Ответить

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

все равно тупейший баг О_о

→ Ответить

caustique

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

Обычно принято тестировать девайсы перед использованием.
Когда изобретешь свой самолет, смотри не взорвись при взлете.

→ Ответить

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

да, теперь понял это )

видимо когда тестил (мало конечно), не отложилось в голове

→ Ответить

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

Ну и как нормально решать 1000? У меня была идея и неотлаженный код.

→ Ответить

ilyakor

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

Ну включения-исключения по количеству плохих шагов. Если все шаги (включая 0,0) - хорошие, то трив. Дальше включения/исключения, надо быть аккуратным с коэффициентами и ещё аккуратным чтобы не словить TL. Надеюсь, у меня прокатит...

→ Ответить

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

Да, именно это писл. Но багов былооооо :)

→ Ответить

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

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

→ Ответить

fetetriste

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

Отдельно по координатам же

→ Ответить

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

Спасибо, кажется, идею уловил... Пойду додумаю.

→ Ответить

Egor	14 лет назад, # ^ \| 0 я правильно понимаю, что в sh first == second для любого элемента, и, соответственно, d[i][j] == 0 для i != j? → Ответить

ilyakor

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

Да, я как обычно стал писать код, не вчитываясь в условие :) d[i][j] == 0 при i != j заодно обеспечивает нормальное время работы.

→ Ответить

Egor	14 лет назад, # ^ \| 0 Я просто не могу понять какого гладиолуса у меня точно такой же код не проходит семпл :) → Ответить

Egor	14 лет назад, # ^ \| 0 Нет, ну то есть он, очевидно, не точно такой же. Ошибку у себя я ищу, короче → Ответить

Egor	14 лет назад, # ^ \| 0 Посеял один из множителей → Ответить

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

Перемудрил я 500 :(

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

→ Ответить

Alex_KPR

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

строка из расстояний у меня ловила TL на макстесте, поэтому я тоже хэш писал ;)

→ Ответить

PavelChadnov

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

у меня 0.2 секунды

→ Ответить

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

Тем не менее меня с моими несколькими хешами it4.kp таки зачеллил :) Подозреваю, что по TL, я не спрашивал.

→ Ответить

natalia

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

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

→ Ответить

it4.kp

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

Нет не ТЛ.
Константа 500 маловата. Причем я специально этот баг и ждал :)
Тест был заранее подобран где величина 792 участвует.

→ Ответить

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

Ага, спасибо. Красиво :)

→ Ответить

dmitrydyatlov

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

Странно. Я тоже хранил расстояния строками (но правда 1 расстояние -> 1 символ строки). На макс тесте было 0.4 сек.

→ Ответить

Egor	14 лет назад, # ^ \| 0 Йа хеш написал. Посчитал, что со строками будет ТЛ → Ответить

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

Java HashMap и полиномильный хэш для массивов.

→ Ответить

mastersobg

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

HashMap<ArrayList<Integer>,Integer> заюзал. :)

→ Ответить

MAK	14 лет назад, # ^ \| 0 Аналогично. Идея с мапом векторов/строк пришла сразу, но была отброшена, как неоптимальная, уступив место замудренной индексации массива. Несколько сбивает с толку стоимость задачи. Если бы она весила 300, я бы уверенно писал вектор. → Ответить

natalia

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

← Rev. 2 →

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

→ Ответить

Ripatti

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

А я так прикинул, что элементов в мапе будет не более 200*200, а добавление/поиск и все такое за не более log(200*200)*50. Перемножим, домножим еще на 10, т.к. stl, получаем 3*10^8 простых операций. А топкодер до 10^9 операций жует.

Ну, потом я все же макстест загнал. Было меньше 0.5 с.

→ Ответить

MAK	14 лет назад, # ^ \| 0 Я тоже понял, что это решение пройдет, но уже на стадии челленджей. На контесте по невнимательности отбросил. → Ответить

Jokser

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

Тоже занимался псевдо-оптимизациями. Потом хотел прикрутить хэширование... В итоге просто забил и написал тупой сорт векторов.

→ Ответить

Edvard

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

Я делал на всякий случай по 2 хешам и нормально прошло

→ Ответить

NALP	14 лет назад, # ^ \| +5 Дай мысленное пять, Эдик =) → Ответить

Edvard

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

Уже дал :-)

→ Ответить

dmitrydyatlov

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

Кстати, похоже у TopCoder будет новый рекорд по числу участников. Сегодня зарегистрировано 2050 человек минус те, кто не решал скорее всего превзойдет предыдущее значение 1891. Может это из-за того, что на Codeforces тоже рекорды пошли? =)

→ Ответить

Alex_KPR

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

+14

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

кстати, Геннадий снова одержал! поздравления!

→ Ответить

Jokser

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

Особо "порадовала" 950 в диве 2 :)

→ Ответить

fetetriste

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

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

→ Ответить

yeputons

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

Как решать 450? Я решал как-то, у меня TL на одном из систестов. Сейчас чуть переделал - теперь на другом :)

→ Ответить

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

Расклассифицируем все камни по их состоянию - вектору расстояний до отмеченных точек.

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

Тогда подсчитаем все существующие на доске состояния, и для каждого - количество камней с таковым состоянием.

Ответ - произведение факториалов количеств по всем состояниям.

Большинство хранило состояние как string или vector<int> в качестве ключа в мапе. Другие считали хеш этого вектора расстояний и записывали его как ключ. И то и то проходит.

→ Ответить

Jughead

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

Блин, реально проще, а я к прямоугольникам переходил(

→ Ответить

yeputons

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

*FACEPALM*
*WALL*
*SAD*
*OTHER_BAD_ACTIONS*
:(
Всё, понял. В лоб при помощи map. Гррр. Перемудрил. Очень. Сильно.

→ Ответить

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

оценил парцелляцию :)))

→ Ответить

NALP	14 лет назад, # \| 0 ну чтоже... у меня примерно +45 к рейтингу... с моей скоростью печати и багами - даже вполне неплохо) хотя место нужно было лучше занимать... вообще, этот раунд удивил задачами, они были необычайно простыми) → Ответить

natalia

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

И, обрати внимание, почти совсем без легенды. Прямо контест твоей мечты :)

→ Ответить

NALP	14 лет назад, # ^ \| 0 шутку оценил) → Ответить

Edvard

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

Контесты без легенд - контесты моей мечты. Сегодня я даже без гуглтранслейта обошёлся

→ Ответить

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

А у меня аргх из-за разницы в компиляторах. В 250 один чувак в комнате обращался к seq[1], не потрудившись посмотреть, что такового может и не быть. В "Студии" это однозначно сегфолт, а вот в g++, оказывается, нет... И причём я далеко не один такой, кто на этом -25 получил.
P.S. Итого +28, ну, тоже ничего.

→ Ответить

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

Я два таких бага видел в комнате, но заметил что в одном из случаев runtime должен выдаваться на любой "YES"-тест и не стал челенжить.

→ Ответить

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

Я ещё подумал, что TopCoder хуже того места, где мы сейчас находимся, из-за отсутствия кнопки "Запуск" и возможности менять код после кодинг-фазы.

→ Ответить

riadwaw

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

и в релизе упадет под мсвс?

→ Ответить

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

В релизе не упадёт.

→ Ответить

riadwaw

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

ну так что никакой разницы..

→ Ответить