ИОИП 2012 - Codeforces

http://neerc.ifmo.ru/school/ioip/standings-2012.html

12 лет назад, # ^ |

→ Ответить

x1te

12 лет назад, # ^ |

А известно, со скольки баллов призеры/победители?

→ Ответить

12 лет назад, # ^ |

Предварительно — около 250/300.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

А сколько всего людей участвовало? Вернее сколько будет учитываться при выдаче дипломов?

→ Ответить

FreddyKrueger

12 лет назад, # ^ |

Смилуйтесь до 246. Обидно очень ;(

→ Ответить

12 лет назад, # ^ |

По закону невозможно более 35%.

→ Ответить

FreddyKrueger

12 лет назад, # ^ |

Спасибо за ответ. Освободили хоть от томного, и как уже ясно, бессмысленного ожидания.

→ Ответить

ilona

12 лет назад, # ^ |

А те результаты, которые на нирке, это полные, или только Питерские?

→ Ответить

12 лет назад, # ^ |

Полные, конечно. В них ведь есть участники из всех регионов России и других стран — вряд ли бы они все приехали в Питер.

→ Ответить

12 лет назад, # ^ |

в эти результаты не добавятся люди, которые не приехали?

→ Ответить

12 лет назад, # |

-7

Интересно получится зацепиться за диплом с моими 254..

→ Ответить

Venom

12 лет назад, # ^ |

Довольно хорошо вписались)Мои поздравления)

→ Ответить

12 лет назад, # |

Какие идеи по решению С? Мое решение на 68 баллов: посчитать все числа(<= макс запроса) с помошью бора смотреть был ли запрос.

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

учитывая что запрос до мегабайта это примерно 10^6-10^7 символов, считать надо примерно столько же чисел

→ Ответить

12 лет назад, # ^ |

А я хранил полностью числа поэтому не влезал по памяти..

→ Ответить

12 лет назад, # ^ |

Предпосчитать 5 * 10⁶ чисел фибоначчи по нескольким простым модулям

→ Ответить

12 лет назад, # ^ |

А как это делается "по нескольким простым"?

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

Век живи, век учись.. Спасибо

→ Ответить

12 лет назад, # ^ |

а как, собственно, это узнавать?

→ Ответить

12 лет назад, # ^ |

← Rev. 3 →

Отсортировать и двоичный поиск или хэш-таблица. Или даже просто для каждого запроса с числом n, отдельно вычислять примерно 5·n чисел фибоначчи.

UPD: с числом длины n

→ Ответить

12 лет назад, # ^ |

Наверное, с числом длины n?

→ Ответить

12 лет назад, # ^ |

Да, ошибся

→ Ответить

12 лет назад, # ^ |

то есть, если есть по каждому простому остаток, то есть соответствующий и по произведению?

→ Ответить

12 лет назад, # ^ |

Не совсем понял, что вы имели в виду второй частью предложения

→ Ответить

12 лет назад, # ^ |

Ну типа что если найдется остаток по каждому простому, то найдется нужный остаток и по произведению простых?

→ Ответить

12 лет назад, # ^ |

Ну это да, только я не понял зачем нам нужен остаток по модулю произведения?

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

Каждому числу x можно сопоставить k чисел, x mod p_i. Так вот, возьмем первые 5000000 чисел фибоначчи, им сопоставим такой кортеж из k остатков. Со всеми запросами проделаем точно так же. Теперь осталось по запросу определить, есть ли такой же кортеж в множестве тех фибоначчиевых чисел, которые мы посчитали.

→ Ответить

12 лет назад, # ^ |

спасибо) а пруф?:)

→ Ответить

12 лет назад, # ^ |

Не знаю, не думал над этим. Интуитивно понятно, что должно работать:)

→ Ответить

dark.wizard

12 лет назад, # ^ |

Я на 68 баллов написал просто в лоб: пока влазит по памяти, просто HashSet на Яве, на 30000 BigInteger, я их отдельно считаю, а потом проверяю, есть ли введенное число в хеше)

→ Ответить

Kelang

12 лет назад, # ^ |

Аналогично. Сначала попробовал HashSet, потом переделал в ArrayList с бинарным поиском на каждом запросе. 68 баллов.

→ Ответить

igor.silin

12 лет назад, # ^ |

Можно было просто считать 5000000 чисел Фибоначчи, закрывая глаза на переполнение типа, отсортировать получившийся массив, далее просто считываем число как строку, переводим в число опять же закрывая глаза на переполнение и бинпоиском ищем есть ли число в заранее посчитанном массиве. 100 баллов.

→ Ответить

dark.wizard

12 лет назад, # ^ |

класс)) у меня уже при 300000 числах (правда, я длинку писал) вываливалась ошибка о нехватке памяти) красивое решение)

→ Ответить

12 лет назад, # ^ |

та же проблема и я не знал что с этим делать

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

rem_digga

12 лет назад, # |

Я бы условия задач почитал

→ Ответить

http://neerc.ifmo.ru/school/io/today/problems-20120325.pdf

12 лет назад, # ^ |

→ Ответить

12 лет назад, # |

Тогда осталось выяснить как решать D

→ Ответить

diogen

12 лет назад, # ^ |

там фишка в том, что чтобы проверить похожи ли два квадрата K x K нужно занулить у каждого верхнюю строку и левый столбец, и тогда у них должны быть одинковые подквадраты (K-1) x (K-1). на контесте я успел только на 60 для каждого в лоб посчитать с мапом. на сотню хэшами за куб вроде можно, но я не дописал

→ Ответить

12 лет назад, # ^ |

← Rev. 4 →

да, можно, могу выложить код, если надо)

UPD там суть была в том, чтобы занулить текущую рассматриваемую строку, а потом посмотреть на квадраты, для которых верхняя строка находится в ней. (Очевидно, что в большой таблице мы можем инвертировать строку и столбец, от этого ничего не меняется). Считаем хеши снизу, теперь для каждого квадрата смотрим левый столбец — единички в нем задают строки, которые надо инвертировать. Тогда хеш от строки квадратика — это либо хеш отрезка, префиксы которого посчитаны, либо его хеш его инвертированного, который считается очень просто.

→ Ответить

iroro

12 лет назад, # ^ |

я решала так (100 вышло): — посмотрим, что не меняется от описанных операций. можно сделать то, что сказал diogen (у меня тоже первой мыслью было), но можно использовать более продуктивную штуку — xor квадратов 2х2 — превращаем исходную таблицу nxn в (n-1)x(n-1) таблицу xor-ов — теперь нужно просто решить задачу об одинаковых квадратах (k-1)x(k-1), я для этого использовала хеши + суффмассив

→ Ответить

12 лет назад, # |

← Rev. 3 →

У меня с задачей С такая история (я сам дурак, но всё таки).
На моих условиях первое число во входных данных — 10, а не 8. Поэтому я подумал, что раз грядки создаются новая каждый день, а N — "количество исследуемых грядок", то нужно проверять является ли число числом фибоначчи до f[N]. 2 часа сидел, не мог понять почему тупое решение набрало 34, а длинка с бинпоиском и хешами — 12...
Такого неудачника надо поискать ещё, просто пи***, ну правда...

→ Ответить

12 лет назад, # ^ |

Я пол часа искал багу в А которая была на 80 из-за кривых тестов

→ Ответить

12 лет назад, # ^ |

Ты хотя бы диплом получишь, а я из-за такого глобального тупняка — нет(

→ Ответить

12 лет назад, # ^ |

В Питере только у меня была эта опечатка?

→ Ответить

Malinovsky239

12 лет назад, # ^ |

Нет, не только у Вас. Например, у меня тоже. Но в проверяющей системе во время тура приходило сообщение об этой опечатке. Заглядывать иногда во вкладку messages бывает полезно)

→ Ответить

12 лет назад, # ^ |

Да уж, epic fail.

→ Ответить

dark.wizard

12 лет назад, # |

У меня тут возник вопрос. На контесте я просто написал на вторую задачу переборное решение на 65 баллов. А потом по дороге домой сел переписать его с LinkedList'ом на Яве. Вопрос, собственно, такой: будет ли полностью работать такое решение: http://pastebin.com/PvxJXzTB

→ Ответить

12 лет назад, # ^ |

Можно скачать архив контеста и протестировать тестером тимуса.
Ещё можно вообще без структур: пока можем ставим максимальный элемент вперёд, если не можем — сдвигаем текущий на нужное место и дальше оставшиеся в порядке возрастания на незаюзанные клетки.

→ Ответить

12 лет назад, # |

А кто-нибудь может скинуть презентацию с разбором?

→ Ответить

PeaceDeath

12 лет назад, # |

Еще любопытный факт, что в задаче С если считать по модулю 2^64, можно было просто считывать число функцией scanf(она считывает число по модулю), ну а дальше бинпоиском по хэшам, как тут говорилось(ну лично я кидал хэши в мап)

→ Ответить

loo

12 лет назад, # |

-6

почему первая задача была столь несерьезной?

→ Ответить

12 лет назад, # ^ |

вторая задача была ещё проще по моему

→ Ответить

12 лет назад, # ^ |

Ну как сказать, несерьезной... Некоторым (и мне тоже) пришлось с ней повозиться) Недолго относительно.

А на вторую вместе с прочтением у меня ушло 6 минут.

→ Ответить

d_i

12 лет назад, # |

Когда будет точно известна разбаловка на дипломы?

→ Ответить

12 лет назад, # ^ |

очевидно не раньше окончания апелляций, т.е. не раньше 28 марта

→ Ответить

12 лет назад, # |

← Rev. 2 →

По задаче D очень странные тесты. Решение, обрабатывающее случаи k=1,2,n, а иначе выводящее a*(а–1)/2, где а — это общее количество квадратов, получает 70 баллов

→ Ответить

12 лет назад, # ^ |

ничего себе

→ Ответить

12 лет назад, # |

Аппеляция закончилась вроде как.. Когда результаты?

→ Ответить

afix

12 лет назад, # ^ |

Кстати, интересно, сколько всего апеллирующих оказалось?

→ Ответить

12 лет назад, # ^ |

Я апеллировал, мою отклонили с формулировкой "Всё равно такое решение (_задача D, printf("0");_) не набирает много баллов и не повлияет на ваш диплом".

→ Ответить

12 лет назад, # ^ |

16 баллов набирает))

→ Ответить

12 лет назад, # ^ |

Да, я знаю, поэтому и апеллировал. Если бы зачли, поднялся бы на 29 мест.

→ Ответить

12 лет назад, # ^ |

Как было написано в памятке, не позднее 1 апреля :)

→ Ответить

12 лет назад, # ^ |

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

→ Ответить