Региональный этап ВСОШ по информатике

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
7	cnnfls_csy	3569
9	ecnerwala	3494
10	Um_nik	3396

№	Пользователь	Вклад
1	Um_nik	164
2	maomao90	160
3	-is-this-fft-	159
4	atcoder_official	158
4	awoo	158
4	cry	158
7	adamant	155
8	nor	154
9	TheScrasse	151
9	maroonrk	151

Всем привет. Недавно был региональный этап всош по информатике и хотелось бы сказать пару слов по поводу него. Первый день я написал плохо, потому что не успел оптимизировать дп в с1, но каково же было мое удивление, когда я узнал, что задача засылалась буквально рандомом. То есть некоторые участники написали полностью тупое решение и оптимизировали его рандомом. Тогда я смирился с этим и подумал, что второй тур будет лучше.

Во второй день ситуация не лучше — я хоть и написал на 300+, но в задаче С2 на фулл загоняли куб при ограничениях в условии на квадрат.

Теперь вопрос, который я хочу задать — действительно ли олимпиады такого уровня должны проверять удачу участников? То есть у меня хороший балл, но люди, которые зарандомили задачи, могут знать и уметь меньше меня, но при этом выйти на заключительный этап всош. Даже если какой-то участник загнал рандом в задачу, у другого то же самое решение может не зайти из-за его невезения. Ладно отжиг — этот алгоритм действительно работает в подавляющем большинстве случаев и понятно, как, но почему из-за того, что тесты на задачи слабые, некоторые участники, достойные выхода на заключительный этап, не выходят на него? В моем понимании, оба тура олимпиады в сумме проверяли везение участника больше, чем знание алгоритмов, подразумевающихся в официальных решениях, и умение их реализовывать.

Комментарии (17)

Написать комментарий?

infrapolar

8 месяцев назад, # |

Можешь скинуть ссылку на подобные решения?

→ Ответить

Bobrovin

8 месяцев назад, # ^ |

Решения не будет, но точно знаю что заслали и точно знаю алгоритм. Задача с1: перебираешь битмаски, сжимаешь массив получившихся строк, шаффлишь массив и считаешь преф суммы 50 раз. Это решение заходит на 100, хотя контртест строится довольно просто, насколько я знаю

-16

Это пиздец. Они не построили тест, имеющий один ответ, содержащий половину столбцов. Это же типа просто поставить в одной строке степени двойки, а в остальных 9999999.

kanao_enjoyer

+18

Поплачь

← Rev. 2 →

+17

Без негатива, кстати

sergeev.PRO

+44

Только что скинули решение, которое заходило на 100. Держи ссылку: https://pastebin.com/yvKYL7qb

-6

Я построил стресс-тест, валющий это решение.

Тест

15 15
131 131 131 131 131 131 131 131 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 131 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 131 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 131 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 131 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 131 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 4 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 64 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 2 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 8 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 16 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 32 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 33 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 131 131 131 131 131 131 131 131 
131 131 131 131 131 131 131 131 131 131 131 131 131 131 131 
126

nizamoff

-21

Ты не прав. Без негатива. Мяу

exhausted

+20

в чем же он не прав друг? тесты действительно были ужасные и заходило то что не должно, в C1 рандом а в C2 куб, кажется такого быть не должно. возможно слово "везение" нужно заменить на "умение загонять то что не должно заходить", это максимум. понятно что сильные участники и так прошли, но кто-то загнал то что не должно заходить из-за слабых тестов и поэтому прошел, забрав проход у людей с таким же баллом(кроме того что у них не зашел куб на 100), только наифавшим больше подгрупп в D

azureglow

-9

Мое решение в С2 набирает 100 на московском еджаджа, и 39 на липецком потому что там куб. Решение в С1 с митмом и анордеред сетом набирает 100 на мск, и 71 на липецком. Также тли на кф были меньше чем на других платмформах. Кажется слово везение тут подходит лучше всего

-12

Если решение с вероятностью 99.99% отработает любой тест за приемлиемое время, а построить стресс-тест для него сложно, то почему его должны валить? Те же хеши тоже являются по сути рандомом. Участник же догадался, что рандом здесь поможет.

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

ты считаешь что авторы не смогли бы отсечь перебор за 2^30 * 15? мне кажется они не пытались особо, можно было бы сделать n и m на 1 больше и tl поднять в два раза, при этом перебор бы уже работал намного хуже. или сделать отрицательные числа и тогда легче было бы намного строить тесты на которых перебор работает долго или неправильно

куб в C2 я тоже не понимаю как не смогли отсечь, даже если там условно n^3 / 27 то это все равно 5e9, я не понимаю как такое смогли допустить, сделали бы n <= 7000 и подняли бы ml в два раза то уже было бы намного лучше, 1.5e10, уже даже с рандомными тестами это бы не зашло

-45

Ты не прав. С негативом

xfloud

Автор не прав

sunsh1ne

+30

Ты не прав

PUFL

Хочется добавить, что кажется, что в С1 можно было просто добавить отрицательные числа, что уже поломало бы многие решения с отсечениями и рандомом.

Еще С2 странно выглядит из-за разбала 40/69/100, при том, что 69 от 100 отличается лишь небольшой идеей. Логичнее было бы сделать 69 условными 80 и придумать какую-нибудь подгруппу на 60.

Блог пользователя Bobrovin