webmaster написав:
є дві команди, які зробили всі 10 задач KNU1 TNU "Akai"
6 команд, які зробили по 9 задач NTU "KhPI" IF DonNU_United НТУУ КПI 1024 КНУ Exploitless TNU "TTL300" LNU United
2 команди, що зробили по 8 задач VNTU [wRabbits] MSUSB "MSUSB1"
Через технічні проблеми змагання було трошки продовжено і команда, як виявилось, NTU "KhPI" IF здала свою 10у задачу і вийшла на 2 місце.
Автор
RE: Півфінал Всеукраїнської студентської олімпіади з програмування 2010
webmaster написав:
Переглянув трохи таблицю із результатами, а виявилась дуже цікава штука: команда "WEST * Lviv Schools Malyata (Glova, Gerasymiv, Pryshchenko)" зробила перший успішний сабміт на задачу І на шостій хвилині змагання і це серед всіх 170 команд учасників і серед 568 успішних сабмітів.
Ми не перші. Ми другі. Має бути ще хтось з часом 0:06 на цій задачі, мені лінь шукати, але я її заацептив не першим, а другим. З.І. додумався скористатись вмонтованими можливостями браузера, контрол-файнд показав, що це NORTH КНУ BZFlags.
Взагалі задачі певно полінились для нас скласти - скільки серед них свічених? Якраз цей сабміт за рахунок того, що Віталій швидко побачив ту задачу, і виділив її, як просту, а я точно знав, як вона пишеться, бо вона є навіть на російськомовних серверах, мовчу вже про англомовні, і тому зразу сів кодити. Така сама історія з задачкою на границю функції, яка стандартна до тупості (особливо такий конкретний випадок) і теж є в неті - як в математичних збірниках, так і в збірниках з програмування. І боулінг теж світився навіть на 2 контестах в російськомвній мережі (але я його ніколи не писав раніше, тому вбив дуже багато часу і штрафну спробу).
І повний перебір для одержання суми 0, який доручили писати Віталієві, я теж бачив, єдиний прикол в тому, що я бачив таке саме (і в плані обмежень, і в плані того, що чудити зі стрічкою і як її виводити), але треба було вивести лексикографічно найменший розв'язок, а не всі.
Про першу задачу навіть говорити нема бажання... Це зараз я зрозумів її суть, і те, чому там може проходити перебір. А на контесті ми були в шоці, Павло все не міг просунути стандартний для всіх задач такого типу алгоритм Евкліда, який вперто валився на одному з тестів (десь можна завантажити тести? Мені аж самому цікаво стало, що там за інпут такий дивний, здається, в 58ому тесті), і Віталій згадав про повний перебір тільки тоді, коли ми десь при -9 критично оцінили список тих, хто заацептив ту задачу
Ще з С натупили неслабо, останню годину вбили на реалізацію, бо я всіх переконав, що мій метод простий і зрозумілий, а десь так хвилин через двадцять виявилось, що він навіть для мене не надто простий, а у інших таке чомусь не пишеться
G - на контесті наш затупізм полягав в тому, що через не дуже круту матпідготовку ми просто не вшарили умову задачі. Шукати в такому випадку НСД алгоритмом Евкліда з довгою арифметикою - це взагалі-то дуже цікавий метод, але я не представляю, як його можна втиснути в такі обмеження. А виявилось, що задача така сама, як є і на Контестері (якщо мені правильно потім пояснили умову), тільки не пропустить наівного лобовика - можна б зробити бінарний пошук з використанням довгої арифметики і швидкого обчислення чисел Фібоначчі.
Про свіченість задач поскладніше сказати нічого не можу, бо я таких ще в житті не розв'язував - ще встигну в майбутньому А тому й не переглядав дуже задачі такого рівня, і не бачу з ходу явно типові і нагло свічені в плані казки вправи.
Таке питання: коли буде наступний контест, в якому школярам можна спробувати свої сили командно? Знаю, що щось там вимальовується в Сумах, але це трошки далеко + я ще не знаю, як там воно співпаде з моїми екзаменами й іншими освітніми дрібницями за часом... І є ДеКодед, але він взагалі десь біля ЗНО
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Автор
RE: Півфінал Всеукраїнської студентської олімпіади з програмування 2010
Організатори прагнуть проводити кожного року кращий та масштабніший фестиваль ніж попередній. 2009 році фестиваль дійшов до межі, коли організаторам вже дуже важко було організовувати фестиваль, так як фестиваль організовуються студентами. Наступний фестиваль відбудеться у 2011 році,під час цієї 2-ох річної перерви організатори, переважна більшість з яких вже не буде студентами, та до яких долучаться професіонали, створять відповідні умови для щорічного зростання масштабів фестивалю та його актуальності.
LeBron написав:
Про першу задачу навіть говорити нема бажання... Це зараз я зрозумів її суть, і те, чому там може проходити перебір. А на контесті ми були в шоці, Павло все не міг просунути стандартний для всіх задач такого типу алгоритм Евкліда, який вперто валився на одному з тестів (десь можна завантажити тести? Мені аж самому цікаво стало, що там за інпут такий дивний, здається, в 58ому тесті), і Віталій згадав про повний перебір тільки тоді, коли ми десь при -9 критично оцінили список тих, хто заацептив ту задачу
Можливо ви використовували тип int (хоча можливо воно і на long long може впасти). В розширеному алгоритмі Евкліда, числа які він находить можуть бути досить великими. Сам стикався з такою проблемою на одній олімпіаді, здавалося все працює, якісь числа повертав але вони були неправильні через те, що в int не влазили.
Автор
RE: Півфінал Всеукраїнської студентської олімпіади з програмування 2010
kobra написав:
Можливо ви використовували тип int (хоча можливо воно і на long long може впасти). В розширеному алгоритмі Евкліда, числа які він находить можуть бути досить великими. Сам стикався з такою проблемою на одній олімпіаді, здавалося все працює, якісь числа повертав але вони були неправильні через те, що в int не влазили.
Всяке може бути... Але ми ніби все писали в int64, longint'ами у нас були хіба що один чи два лічильники для циклів. При обмеженнях до 10000 НСК буде, зрозуміло, в межах 100 мільйонів, тобто як не крути, але алго Евкліда мав би повертати числа, набагато менші за 2^63.
Я більше схиляюсь до думки, що помилка була десь в пошуку пари з найменшою сумою, або ж десь щось неправильно відкидалось при пошуку "крайніх" невід'ємних розв'язків.
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Автор
RE: Півфінал Всеукраїнської студентської олімпіади з програмування 2010
Birthday(s):
