Сегодня прошел очный тур иоип. Предлагаю обсудить задачи и баллы за дипломы.
Сегодня прошел очный тур иоип. Предлагаю обсудить задачи и баллы за дипломы.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
Можно, пожалуйста, ссылку на результаты?
http://neerc.ifmo.ru/school/ioip/standings-2012.html
А известно, со скольки баллов призеры/победители?
Предварительно — около 250/300.
А сколько всего людей участвовало? Вернее сколько будет учитываться при выдаче дипломов?
Смилуйтесь до 246. Обидно очень ;(
По закону невозможно более 35%.
Спасибо за ответ. Освободили хоть от томного, и как уже ясно, бессмысленного ожидания.
А те результаты, которые на нирке, это полные, или только Питерские?
Полные, конечно. В них ведь есть участники из всех регионов России и других стран — вряд ли бы они все приехали в Питер.
в эти результаты не добавятся люди, которые не приехали?
Интересно получится зацепиться за диплом с моими 254..
Довольно хорошо вписались)Мои поздравления)
Какие идеи по решению С? Мое решение на 68 баллов: посчитать все числа(<= макс запроса) с помошью бора смотреть был ли запрос.
Преподсчитать сколько то чисел фибоначчи и бинарный поиском для каждого запроса правда не знаю возможно ли это на 100 сдать. Слышал что кто то по моему за такое 82 набрал
учитывая что запрос до мегабайта это примерно 10^6-10^7 символов, считать надо примерно столько же чисел
А я хранил полностью числа поэтому не влезал по памяти..
Предпосчитать 5 * 106 чисел фибоначчи по нескольким простым модулям
А как это делается "по нескольким простым"?
Выбирается k простых, после этого для каждого простого независимо считаются Fi mod pk. Также каждый запрос считаем по модулю всех простых. Ну и нужно для каждого запроса узнать, есть ли в множестве фибоначчиевых остатков такое же множество остатков как и в запросе.
Век живи, век учись.. Спасибо
а как, собственно, это узнавать?
Отсортировать и двоичный поиск или хэш-таблица. Или даже просто для каждого запроса с числом n, отдельно вычислять примерно 5·n чисел фибоначчи.
UPD: с числом длины n
Наверное, с числом длины n?
Да, ошибся
то есть, если есть по каждому простому остаток, то есть соответствующий и по произведению?
Не совсем понял, что вы имели в виду второй частью предложения
Ну типа что если найдется остаток по каждому простому, то найдется нужный остаток и по произведению простых?
Ну это да, только я не понял зачем нам нужен остаток по модулю произведения?
хм, видимо я совсем туплю. можете с начала и поподробнее тогда рассказать решение?:)
Каждому числу x можно сопоставить k чисел, x mod pi. Так вот, возьмем первые 5000000 чисел фибоначчи, им сопоставим такой кортеж из k остатков. Со всеми запросами проделаем точно так же. Теперь осталось по запросу определить, есть ли такой же кортеж в множестве тех фибоначчиевых чисел, которые мы посчитали.
спасибо) а пруф?:)
Не знаю, не думал над этим. Интуитивно понятно, что должно работать:)
Я на 68 баллов написал просто в лоб: пока влазит по памяти, просто HashSet на Яве, на 30000 BigInteger, я их отдельно считаю, а потом проверяю, есть ли введенное число в хеше)
Аналогично. Сначала попробовал HashSet, потом переделал в ArrayList с бинарным поиском на каждом запросе. 68 баллов.
Можно было просто считать 5000000 чисел Фибоначчи, закрывая глаза на переполнение типа, отсортировать получившийся массив, далее просто считываем число как строку, переводим в число опять же закрывая глаза на переполнение и бинпоиском ищем есть ли число в заранее посчитанном массиве. 100 баллов.
класс)) у меня уже при 300000 числах (правда, я длинку писал) вываливалась ошибка о нехватке памяти) красивое решение)
та же проблема и я не знал что с этим делать
По сути это похоже на верное решение, просто все считается по модулю 2^64. Можно было, конечно, именно этот модуль завалить...
Я бы условия задач почитал
http://neerc.ifmo.ru/school/io/today/problems-20120325.pdf
Тогда осталось выяснить как решать D
там фишка в том, что чтобы проверить похожи ли два квадрата K x K нужно занулить у каждого верхнюю строку и левый столбец, и тогда у них должны быть одинковые подквадраты (K-1) x (K-1). на контесте я успел только на 60 для каждого в лоб посчитать с мапом. на сотню хэшами за куб вроде можно, но я не дописал
да, можно, могу выложить код, если надо)
UPD там суть была в том, чтобы занулить текущую рассматриваемую строку, а потом посмотреть на квадраты, для которых верхняя строка находится в ней. (Очевидно, что в большой таблице мы можем инвертировать строку и столбец, от этого ничего не меняется). Считаем хеши снизу, теперь для каждого квадрата смотрим левый столбец — единички в нем задают строки, которые надо инвертировать. Тогда хеш от строки квадратика — это либо хеш отрезка, префиксы которого посчитаны, либо его хеш его инвертированного, который считается очень просто.
я решала так (100 вышло): — посмотрим, что не меняется от описанных операций. можно сделать то, что сказал diogen (у меня тоже первой мыслью было), но можно использовать более продуктивную штуку — xor квадратов 2х2 — превращаем исходную таблицу nxn в (n-1)x(n-1) таблицу xor-ов — теперь нужно просто решить задачу об одинаковых квадратах (k-1)x(k-1), я для этого использовала хеши + суффмассив
У меня с задачей С такая история (я сам дурак, но всё таки).
На моих условиях первое число во входных данных — 10, а не 8. Поэтому я подумал, что раз грядки создаются новая каждый день, а N — "количество исследуемых грядок", то нужно проверять является ли число числом фибоначчи до f[N]. 2 часа сидел, не мог понять почему тупое решение набрало 34, а длинка с бинпоиском и хешами — 12...
Такого неудачника надо поискать ещё, просто пи***, ну правда...
Я пол часа искал багу в А которая была на 80 из-за кривых тестов
Ты хотя бы диплом получишь, а я из-за такого глобального тупняка — нет(
В Питере только у меня была эта опечатка?
Нет, не только у Вас. Например, у меня тоже. Но в проверяющей системе во время тура приходило сообщение об этой опечатке. Заглядывать иногда во вкладку messages бывает полезно)
Да уж, epic fail.
У меня тут возник вопрос. На контесте я просто написал на вторую задачу переборное решение на 65 баллов. А потом по дороге домой сел переписать его с LinkedList'ом на Яве. Вопрос, собственно, такой: будет ли полностью работать такое решение: http://pastebin.com/PvxJXzTB
Можно скачать архив контеста и протестировать тестером тимуса.
Ещё можно вообще без структур: пока можем ставим максимальный элемент вперёд, если не можем — сдвигаем текущий на нужное место и дальше оставшиеся в порядке возрастания на незаюзанные клетки.
А кто-нибудь может скинуть презентацию с разбором?
Еще любопытный факт, что в задаче С если считать по модулю 2^64, можно было просто считывать число функцией scanf(она считывает число по модулю), ну а дальше бинпоиском по хэшам, как тут говорилось(ну лично я кидал хэши в мап)
почему первая задача была столь несерьезной?
вторая задача была ещё проще по моему
Ну как сказать, несерьезной... Некоторым (и мне тоже) пришлось с ней повозиться) Недолго относительно.
А на вторую вместе с прочтением у меня ушло 6 минут.
Когда будет точно известна разбаловка на дипломы?
очевидно не раньше окончания апелляций, т.е. не раньше 28 марта
По задаче D очень странные тесты. Решение, обрабатывающее случаи k=1,2,n, а иначе выводящее a*(а–1)/2, где а — это общее количество квадратов, получает 70 баллов
ничего себе
Аппеляция закончилась вроде как.. Когда результаты?
Кстати, интересно, сколько всего апеллирующих оказалось?
Я апеллировал, мою отклонили с формулировкой "Всё равно такое решение (_задача D, printf("0");_) не набирает много баллов и не повлияет на ваш диплом".
16 баллов набирает))
Да, я знаю, поэтому и апеллировал. Если бы зачли, поднялся бы на 29 мест.
Как было написано в памятке, не позднее 1 апреля :)
ну мало ли там была шутка, а то первая апреля день несерьезный. а если серьезно просто поскорее узнать хочется :)
Это была не шутка — на рассмотрение апелляций необходимо некоторое время. А вообще, некоторые изменения в результатах уже произошли и еще ожидаются. Но все незначительно и вряд ли коснется дипломов.
Опубликованы окончательные результаты олимпиады.
люди с 300 баллами наверное очень огорчились...
Я за них тоже... К сожалению, по закону округление в меньшую сторону :(
А можно ли это все http://neerc.ifmo.ru/school/ioip/ запилить в тренировки? Удобней просто (имхо).