Насколько распространена ситуация при которой несмотря на то что ты сдал решение одновременно или раньше, твой соперник выше тебя на рейтинге, за счет того что его код работает быстрее или/и требует меньше памяти.(При условии что оба кода проходя все тесты) На каких платформах и турнирах такая ситуация и насколько она вероятна? Имеет ли вообще хоть какой то смысл оптимизировать решение если асимптотика решения остается неизменной?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.04.2024 15:11:25 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been translated by IcantComeUpWithOrigName (original revision, translated revision, compare)
Автокомментарий: текст был обновлен пользователем IcantComeUpWithOrigName (предыдущая версия, новая версия, сравнить).
Спасибо за ответ. А часто такое бывает: "код проходит претесты почти впритык к TL". Лично я такого не видел, но с другой стороны я и задач не так много решил.
Как правило, в претестах на Codeforces включают тесты с максимальными входными данными, чтобы +- точно проверить, проходит ли решение участника TL. Но если вы отправляете решение, и максимальное время выполнения на претестах близко к TL, это значит, что существует вероятность, что системные тесты оно не пройдет.
Причины две. Во-первых, в систестах может попасться тест, на котором программа работает чуть-чуть медленнее, и вы получите TL. Кроме того, система измеряет время выполнения программы с некоторой погрешностью (до 10, редко 15%) — и одно и то же решение, близкое к TL, может сначала пройти тест, а при втором запуске — нет (чистый рандом).
As long as both solutions pass all the test cases, efficiency does not matter in competitive programming. The one who submitted earlier doing fewer mistakes will get the better rank.
In general, you want your code to be as easy to code as possible so that it is only as efficient as it needs to be. Don't bother trying to make something linear if it would require a bunch of thinking and you can just mindlessly binary search for the answer anyway.
That said, when it gets to harder problems, occasionally you will either need to optimize your solution to lower the constant factor (which is always annoying), or do some nonsense to get rid of log factors, such as using an RMQ to answer queries in O(1) instead of a segment tree in O(log(n)).
In practice, the latter usually happens when your logic is already built on top of some other log factor, for instance you are doing something for each power of 2, or you are binary searching something, et cetera.
That was the smoothest segue into self-promotion I've ever seen xD. +1
(On a more serious note that video is very educational and helped me understand RMQ) :D
Execution time and memory don't matter on Codeforces as long as they're below the limits. It's the same for all other contests that I know of.
In (Uva) currently named onlinejudge.org, there is a rank list based on the efficiency for each problem.