Форум DL

Мой профиль

Сегодня решал второй день сборов. Всё было лёгким, кроме последней задачи. Она была очень противной в реализации, было относительно много случаев, в которых можно было сделать ошибку (именно поэтому у меня 0 баллов на первой посылке). Но почему же я писал её больше 3-ёх часов? Как я уже сказал, задача была противной, и я где-то пол часа думал, как бы мне её хорошо написать, чтобы не допустить ошибки в коде. Этот подход сработал (почти, кроме первой посылки), но у меня, чёрт, TL!!! Я прочитал разбор, решение как у авторов... Но почему оно не проходит!!??
Я не знаю... Это какое-то проклятье. Пишешь быстро, не проходит, пишешь хорошо, долго, вдумчиво, красиво - получаешь TL. Я зол. Не знаю на кого, наверное, стоит на себя, но я пока не понял, что я сделал не так. Решение у меня довольно хорошее, разве что можно было бы заменить ДО на структурах на ДО на массиве, или на Фенвик по префсумкам, но от этого решение станет только уродливее, а как выяснил мой большой опыт, кроме асимптотики, очень важна красота. Когда я писал суфф. масс. за O(n*log(n)), но с большим кол-вом некрасивых обращений к памяти (типа d[pos[a[i]]), у меня не проходило по TL, но как только я написал его же, но с доп. сортировкой, вместо такой работы с памятью, всё прошло (такая работа с памятью нужна была для сортировки подсчётом (или как она называется, когда в массив количества cnt[a[i]]++, а потом проходимся по cnt, и собираем отсортированный массив a)).

P. S. Я узнал, что Миша писал через Фенвика с преф. суммами

Мой профиль

Надо прекратить писать "я всё делал хорошо", если задача не сдана.
Надо разобраться, что сделано плохо.
И СДАТЬ вчерашнюю и сегодняшнюю задачи методами Миши и взять эти методы на вооружение.
Ещё можно завтра спросить у Миши, почему он писал как писал он, а не так, как писал ты.

Надо прекратить писать "противной в реализации", потому что это влияет на твоё кодирование.

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

"У природы нет плохой погоды"

26.11.2024 10:55:25 26.11.2024 10:55:50 Брель Михаил Программирование - профессионалы (лич. 2024-2025) A. Дела по дому 100 Все тесты успешно пройдены source.g131 DelTA4 at NIT0 Win10
26.11.2024 10:49:22 26.11.2024 10:49:47 Брель Михаил Программирование - профессионалы (лич. 2024-2025) B. Возвращение домой 100 Все тесты успешно пройдены source.g131 DelTA4 at NIT0 Win10
26.11.2024 10:43:42 26.11.2024 10:44:27 Брель Михаил Программирование - профессионалы (лич. 2024-2025) C. Прогулка по Бруклину 100 Все тесты успешно пройдены source.g131 DelTA4 at NIT0 Win10
26.11.2024 10:30:29 26.11.2024 10:31:12 Брель Михаил Программирование - профессионалы (лич. 2024-2025) D. Взлом компьютера 100 Все тесты успешно пройдены source.g131 DelTA4 at NIT0 Win10
26.11.2024 10:28:47 26.11.2024 10:29:03 Брель Михаил Программирование - профессионалы (лич. 2024-2025) D. Взлом компьютера 0 Не пройдены тесты: 6-106 source.g131 DelTA4 at NIT0 Win10

Мой профиль

Я разобрался, почему моё решение не проходило. Это какой-то трэш. Я почти всегда писал #define nl '\n'. nl - это new line, т. е. вместо cout << a << '\n'; Я пишу cout << a << nl;
НО почему-то, в моих дефайнах на олимпиаде было #define nl endl, а как мы знаем, endl раз в 8 медленнее '\n'. Вот оно и не проходило.
Какой можно сделать из этого вывод? Не знаю, тщательнее проверять дефайны перед олимпиадой

Мой профиль

Я решил D второго дня. Вот выводы:

1. Если можно писать Фенвиком, пиши Фенвиком. Всё равно его писать легко, а мучаться с подстраиванием не сложнее, написания ДО.
2. Рёбра бора писать на массивах, а не на map <char, ссылка>, так быстрее
3. При дебагинге не комментировать строки, чтобы проверить что долго работает (какую закомментил, и стало работать быстро, та и была медленной, это может сломаться в каких-то случаях), а по отдельности ставить clock-и, чтобы замерять время каждой строки

Мой профиль

Четверг. Решал сборы. За час 20 минут решил 3 задачи. Последняя оказалась сложной. там была сумма Минковского, которую я не знал, писал неполное решение, результат - 57 баллов.

Мой профиль

А теперь знаешь сумму Минковского?
Для Республики и IOI наверно и не нужно.
А вот для ВКОШП может пригодиться.
Не в этом году так в последующие.

Мой профиль

Да, весь день разбирался

Мой профиль

Пятница.
Первые 4 задачи я решил за 2.5 часа. Прочитал 5-ую, не увидел, что не обязательно дерево связано рёбрами, направленными вниз. Это понял я довольно быстро, начал думать, что делать, но идеи не приходили. Я очень устал за последние девять олимпиад (пят., субб., субб., воскр., пон., вт., ср., если её можно назвать олимпиадой, чт., и сегодня). Мозги уже не варили, поэтому решил взять неполные баллы. Результат - 29 баллов.

Мой профиль

Ну усталость есть усталость.
После отдыха надо разобраться, как надо решать задачу, а по возможности и сдать в Р/О.

И хорошо отдохнуть перед воскресной олимпиадой.

Мой профиль

Понедельник.
Задачки были прикольными. Над B я сидел больше часа, там было много случаев, но зато сдал с первой попытки. C была вообще лёгкой, на алгоритм Манакера, просто надо было аккуратно написать. А вот D уже интересная. Думал где-то час над фулом, но понял, что нужно сначала сдать неполным решением, а потом оптимизировать. Написал решение за O(n^4*k^2), и на удивление получил 74 балла. Придумал, как соптимизировать до O(n^3*k^2), но не успел докодить. Как решать на фул, пока не знаю, почитаю разбор

Мой профиль

Вторник.
Первые 3 задачи (если можно считать С на 98 баллов, не знаю почему, было бессмысленно выяснять на олимпиаде, надо было решать D) решил за 3:20 часа:минут. Прочитал D, придумал решение для t=1, стал думать над полным, но не учёл, что оно работало только для делящихся на m. Решил написать, потом оптимизировать, и не прогадал: в моём решении была ошибка. Исправить её не успел: как-то запутался. Почему? Это была прикольная/сложная ДП-шка, какая и была вроде-бы в пятницу. Почему-то в них я теряюсь, и делаю ошибки. Сейчас я дорешал эту подгруппу, у меня 49 баллов. Над фулом надо ещё чуть-чуть подумать

Мой профиль

Четверг.
Наконец-то я закрылся! И даже с плюса. Первые 3 задачи были вообще лёгкими, их я сдал за пол часа (извините, я чутка проспал). Последняя была обычной таской на битовый бор с двумя операциями, только надо было рассчитать асимптотику и аккуратно реализовать. Что у меня и вышло. Хотя, да, долговато я её писал. 2:40 - это много, но и задача была противной. Одним словом надо ускорятся и не опаздывать

Мой профиль

Отлично.
Если есть силы-желание хорошо бы долги дорешать.

Мой профиль

А ещё почитай разбор похоже авторское решение другое.
Какое легче писать? Придумывать?

Мой профиль

Пятница.
Первые 3 задачи я сдал меньше, чем за час. Прочитал четвёртую, ограничения показались маленькими (900), поэтому подумал, что куб зайдёт. Попытался запихать, но не получилось. На 3-ем часу придумал нормальное решение, но подумал, что оно вряд-ли пройдёт (т. к. медленное решение летело не по времени, а по не времени (WA, RE, ML, я не знаю)), но попытавшись ещё, и подумав над новым решением, понял, что оно скорее всего пройдёт, и с первой попытки сдал.
Вывод: меня запутали ограничения: я подумал, что оно будет работать быстро, а оно слетало по WA. Одним словом, была какая-то ошибка, которую я не смог найти, или вообще нельзя было исправить, написал новое решение и оно зашло. Надо просто быстрее переключаться между решениями