ИОИП - Codeforces

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

← Rev. 2 →

я также писал, только получил 94 почему-то

→ Ответить

kuzmichev_dima

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

у меня тож сначала было 94. Добавил проверку на то, что в каждой из трех частей, на которые разбили, >=1 элемент и получил 100

→ Ответить

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

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

хотя вроде проверял

→ Ответить

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

Такое бывает когда есть 0. У меня тоже первая посылка на 94.

→ Ответить

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

кстати, поздравляю с 400 :)

→ Ответить

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

А это уже интересно. Где висят результаты?

→ Ответить

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

← Rev. 2 →

хм

мне сообщил об этом Riad-WaW

извиняюсь если нагнал

→ Ответить

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

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

→ Ответить

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

значит слухи уже передались :)

→ Ответить

ostroumov

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

Результаты показывали на разборе в Питере. Кстати, поздравляю!

→ Ответить

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

жутко лень было на основном туре ИОИП ? О_о

или просто на интернет-олимпиаде?

→ Ответить

agul	13 лет назад, # ^ \| 0 На интернет-олимпиаде. Я вообще сначала забыл про нее, вспомнил через 2 часа после начала. Ну и вот) → Ответить

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

кто-нибудь знает, как делать D на 100?

→ Ответить

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

Решение D на 100 баллов

Понятно, что любая тоговая конфигурация - группы подряд идущих единичек, разделенные одним нулем. Заметим, что при такой конфигурации мы приходим в группу, наступая обязательно на первый ее элемент, а уходим, наступая на последний. Кроме этого, переход между группами осуществляется ровно одним способом (перепрыгиванием через ноль). Пусть у нас есть P групп, длина i-й группы Li, количество способов ее пройти Bi. Тогда произведение всех Bi есть количество способов пройти через все группы от начала к концу, а сумма всех Li + P - 1 - суммарная длина всех групп (+P-1 берется потому, что в конце всех групп, кроме последней, стоит замыкающий ноль).

Получаем, что произведение всех Bi = k, а сумма всех Li + P = n + 1. Теперь надо найти любой такой набор групп.

Заметим, что Bi - это числа Фибоначчи. Преподсчитаем всевозможные Bi до 10^18 (их всего 87). После этого искомое разбиение на группы можно найти рекурсивным перебором.

→ Ответить

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

спасибо, классное решение

→ Ответить

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

Только мне показалось, что С сложнее,чем D? Или это так и задумывалось?

→ Ответить

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

Не тебе одному. В Москве сотен по С нет. Хотя трудно сказать, какая задача сложнее в плане решения. В С оно почти на поверхности, зато фиг напишешь потом. В D же перебор пишется за несколько минут.

→ Ответить

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

У меня тоже не честное решение. Но я верю что оно даже может работать всегда.

→ Ответить

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

Ты думаешь, что в D перебор, который я описал, не всегда будет работать на данных ограничениях? Или ты про С говоришь?

→ Ответить

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

Про С. У меня разбор случеев + бфс + всякое шаманство.

→ Ответить

IlyaLos

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

Павел, а можно подробнее как решать С?

По соревнованию: я его дико слил, не набрав даже 200 баллов, всё из-за того, что по тупости не мог решить В, вроде алгоритм верный, но набирает только 56 баллов. После этого опустил руки, ибо шансы даже на 3й диплом исчезли. В конце понял, как решать D, но похоже понял не до конца (успел набрать только 24 балла) или скорее времени не хватило.

Да, и что за случай такой в А из-за которого у многих (в том числе и у меня) задача набирает 90 баллов? Решал проверкой на 2 предела: первый момент, когда джедай лидирует и первый момент когда ситх лидирует.

→ Ответить

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

По поводу А: не знаю. Сам решал методом промоделировали первую 1100 дней, если ничего хорошего не вышло, то говорим что ситх всегда круче.

По поводу B: Знаю только из-за чего бывает 94, что писал выше. Правильных решения 2 - бинпоиск и два указателя. На самом деле это одно и тоже. 56 могу предположить что потеряли long long или что-то еще такое.

C: Нормальное решение такое. Посчитали расстояние от всего до конца (бфсом из конца по обратным ребрам). Нашли кратчайший путь по числу поворотов. и Бинпоиском ищем оптимальную по минимальной длине. по поводу как проверять. Хороший вариант от Саши Тимина. Будем считать динамику d[x][y][i][j] x,y - позиция. i - по чему мы в нее пришли (по аллее или по улице) j - сделали ли мы уже шаг. Тогда если шага не делали то будем ходить на С, иначе на 1. Вроде авторское решение - что-то похожее.

→ Ответить

kuzmichev_dima

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

Если решение действительно такое сложное, то странно, что мой просто bfs+восстановление пути набирает аж 84

→ Ответить

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

← Rev. 2 →

А бфс+востанавление пути + перебор путей из трех отрезков набирает от 92 до 100, в зависимости от реализации.

UPD: А просто перебор путей длины три набирает 76. Что не плохо против 80-90 которые получало правильное решение с багами.

→ Ответить

IlyaLos

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

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

По поводу А. Ваше решение действительно проще моего. Почему-то я не подумал, что решится в течении 1000 ходоов.

В С думал написать ширину с восстановлением пути, но уже не хватило времени - слишком долго шаманил над В.

→ Ответить

agul

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

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

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

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

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

→ Ответить

Nikolai

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

← Rev. 2 →

Да, С явно сложнее.

UPD: Это к верхнему посту.

→ Ответить

agul	13 лет назад, # \| 0 Кто-нибудь в курсе, когда будут результаты? → Ответить

ostroumov

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

Станкевич обещал сегодня вечером.

→ Ответить

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

а поконкретнее время не уточнил?

просто уже довольно поздний вечер, а я по-прежнему каждые 5 минут обновляю страницу :)

→ Ответить

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

в этом посте появился ярый минусовщик?

→ Ответить

DimaPhil

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

← Rev. 2 →

Кстати, почему по D не проходит такое решение:

Заметим, что k - число Фиббоначчи. Тогда пусть fib[m]=k. Если m>k, то решений нет. Иначе, заметим, что поставив 0 в n-1 позицию, количество способов добраться до клетки n будет fib[n-2], а если поставить в n-2 позицию, то fib[n-3]. Получаем, что мы умеем получать количество способов fib[n], fib[n-2], fib[n-3], ...(fib[n-1] вроде не получить). Ну и после этого выставляем 0.

UPD. Оно получает 58 баллов.

→ Ответить

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

>Заметим, что k - число Фиббоначчи.

Вот по этому.

→ Ответить

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

Наверное потому, что k может и не быть числом Фибоначчи ;)

n = 7, k = 4

1110111

→ Ответить

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

← Rev. 3 →

что-то многовато 58 баллов для такого решения. разве что в тестах было много ответов Impossible ?

что маловероятно, так как мое решение прошло на 46, писал на 40 + крайние случаи + обрывал перебор маски когда выполнилось 10^7 операций и выводил Impossible

→ Ответить

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

В Саратове один человек послал вывод Impossible. По его словам это получает 28.

→ Ответить