21 и 23 января пройдет региональный этап Всероссийской олимпиады школьников по информатике. По результатам этапа будет составлен общий рейтинг по России, лучшие в этом рейтинге пройдут на заключительный этап Всероссийской олимпиады школьников в Казань.
У меня возникло несколько вопросов, связанных с проведением этапа:
- Есть ли какое-то положение, регламентирующее проведение пробного тура? По сути, в нашем регионе (Новосибирская область) уже второй год подряд пробный тур проводить не собираются, и это печально.
- В сентябре ходили слухи, что на региональном этапе добавят подгруппы тестов, но токенов (т.е. возможность узнать результат тестирования моей программы на всех тестах прямо во время тура) не будет. Насколько это правда сейчас?
Кроме того, предлагаю здесь задавать свои вопросы.
Здесь же можно обсудить задачи этапа, но не раньше, чем в 16:00 17:00 (MSD), т.к. только в это время заканчивается этап во всех субъектах Российской Федерации.
P.S. Возможно, я где-то ошибся. Напишите об этом, и я исправлю.
UPD: Архив с условиями, тестами и решениями первого тура.
UPD: yeputons поднял дорешивание на своем сервере.
Результат тестирования во время тура узнавать это круто! А то прошлом году из-за перевода строки не прошла задача С первого тура,но претестирование сделали только ко 2ому дню олимпиады.
Еще раз повторю, что такой возможности (тестирование во время тура), скорее всего, не будет.
Не у всех второй этап пройдет 23 января.
К сожалению, gamedeveloper прав. И так по всем предметам
Кстати, это есть нарушение Положения о проведении всероссийской олимпиады. Надо бы об этом сообщить В.М. Кирюхину, чтоб местным чиновникам раздали по серьгам!
Нет, Паш. "Требования" как были очень скользки на тему языков, так и остались. Тут сначала рекомендуется сделать две группы языков, и лишь потом указывается, какие языки основная группа должна содержать. И как это трактовать, если жюри решает не делать две группы языков?
Думаю, что вся информация по региональному этапу, которая есть в открытом доступе находится здесь, в частности методические рекомендации.
Хм. Видимо да. В общем, я про Калининград. Исправил.
нетуда
Вопрос по положению. Пункт 5.8 Проверка и оценивание всех представленных участниками на проверку решений олимпиадных задач осуществляется либо после окончания тура, либо во время тура, если используемая жюри среда проведения соревнований позволяет это делать. Если полная проверка производится во время тура, то могут ли участники сдать задачу повторно? Я не нашел, чтобы это было четко прописано.
Все нашел Результаты проверки на полном комплекте тестов могут сообщаться участникам только после окончания тура.
Проверка во время тура не подразумевает показ результатов. Она нужна для ускорения показа результатов после тура, потому что проверить много посылок, из которых еще куча работает непонятно сколько это дело не очень быстрое. Перепосылать можно. Обычно сколько угодно раз в разумных пределах, этот вопрос лучше задать местным организаторам.
UPD: Поставьте пожалуйста нормальный шрифт(кнопка очистить формат). Очень неприятно смотрится неожиданное увеличение внутри текста.
На семплах можно и самому проверить.
Ой, прошу прощения. Только сейчас нашел.
Она показывает TL/WA. Этого достаточно.
А система, это та в которой ответы на вопросы в трех разных местах и не дублиуются?
Составили письмо, отправили, практически без реакции.
Что значит "нарушение рекомендаций"?
2) Ну вот подготовить на местах что то.
Я так и не услышал ответ на свой вопрос...
Надеюсь, что ничего не нарушу, если скажу, что мне показалось, что с ограничением в 100000 символов задача 3 была бы интересней. А вот задача 4 реально очень интересная. Восхищаюсь людьми, которые могут придумывать такие задачи.
Зато впервые появился сервер. А не то что раньше было.
upd: да, в Татарстане теперь PCMS вместо "оставьте файлы в этой папке". Ура!
Помогите пожалуйста понять, почему задача С тайм-аутится на 3 тестах?
вот код:
http://pastebin.com/pDzHyWx0
может потому что в 33строке ты присваиваешь k = i + 1, а потом смотришь st[k], при i = st.size() - 1 вникуда обратишься45 строка while (st[k] >= 'a' && st[k] <= 'z'), ты не смотришь, что вышла за длину строки
К сожалению, если это(и новое) исправить, то все равно остается 85( в архив отправила).
вот исправленный код
То бишь там: BGGBGGBGGBGG.....потом оставшиеся B...и оставшиеся G... ?
я лично, подумал, что это хоть гарантировано работает, а жадину я могу не придумать или придумать, но быстрее это напишу, и напишу это минут за 30 (а вышло вон как)
если a > 1000 && b > 1000 то выводи -1 -1)
cin >> a >> b;
if (a <= 1000 && b <= 1000) решение на 100;
else return -100500;
у нас в области чувак взял на 50 из за того что написал integer.
UPD а минусовать то за что? у меня то нормально с результатами.
Как я умудрился пройти примеры...
/*ушёл топиться*/
Мне вот не нравится, что кто-то правит баллы за первые 2 задачи в сторону увеличения. Видел, что человек вбивал 50 за первую. А потом кто-то другой прошёлся по нескольким ячейкам и выставил большинству 100 за первые 2.
А ты где писал?
По техническим причинам таблица была скопирована в новую. Сейчас добавление работает в режиме отписаться на другой странице и перенести теми у кого есть права в общую таблицу. Дальше посмотрим.
Желающие получить доступ к редактированию gmail в личку. Люди, которые знаю как адекватно заносить результаты без возможности такого бреда и готовые это сделать туда же.
как решалась C на 100? :D
Я вот слажал на 60 -_-
все....
пора на пенсию :D
я вообще не перебирал. -__-
У меня вообще само решение со стеком было, мда.
1 RE, 1 TL
Можно, кстати, быстрее делать, причем реализация только на 2 строчки вырастет. Будем пытаться заменить только на символ '/' и символы, которые встречались нечетное число раз в исходной строке (таких не более 2-х), причем пытаться заменить будем только их.
Неправильно написал брут в D(как так?). По моим подсчетам тупое решение с заплатками на случаи 0 или n набирает 66 баллов. Что писали, те кто получили 60 баллов и более?
Могу достать архив на любую задачу.
Поднял дорешивание.
17:00 прошло поэтому выкладываю тесты. http://dl.dropbox.com/u/13007864/region2012/day1.zip Спасибо пользователю afix за предоставленные тесты. Надеюсь поможет. В архиве также есть чекер и решения жюри.
Спасибо за выложенные тесты нужно говорить не пользователю afix, а мне.
Я думаю, что 520 может не хватить, потому что многие полностью решили первые три задачи.
===
Так, ну вроде бы можно начать обсуждение (17:07)
Скажите пожалуйста как решалась восьмая на 100?
Код
В моей реализации, если все образцы и наборы начинаются с одной буквы, то каждый раз проверяются все строки из набора (квадрат).
Что-то типа O(n log(n) k), где k - количество строк, начинающихся с той же буквы, что и текущий образец.
Да и сортировка строк за O(n log(n) log(50)).
Можно сортить хеши, и не понял про проверку за квадрат.
2 строки же сравниваются бинпоиском по хешам.
Короче, моё решение делает так:
- отсортим оба набора
- идём по образцам (допустим мы сейчас в s[i]) и поддерживаем указатель L - до него уже не может быть подходящих нам строк, так как они меньше s[i-1] уже
- бинпоиском ищем первую и последнюю строку начинающуюся с такой же буквы, что и s[i] (пусть это l и r)
- проверяем все строки из словаря между l и r на совместимость с s[i]
- L присваиваем l
Пример в прошлой правкеСложим эти паттерны в бор и для каждой вершины будет насчитывать ответ (просто к добавлению в бор добавить один if для проверки, является ли префикс супрефиксом и один инкремент, если да).
Потом умеет отвечать на запросы онлайн для длину запроса - нашли вершину в боре, вывели ответ, который в ней уже посчитан.
http://www.e-maxx.ru/algo/prefix_function
http://www.intuit.ru/department/algorithms/advancedalgo/9/
Префикс
Z - функция
Бор
Из алгоритма её построения явно вытекает, как узнать, какие префиксы - супрефиксы.
Бор. Суффиксные ссылки тут не нужны, просто в каждой вершине появлятеся счётчик answer.
Классная задача.
ммм делал так же 55 баллов, вот код, может у меня бор кривой
или может потому что у нас сервер медленныйи где вообще можно дорешать задачи?P.S. вопрос исчерпан... проблема была в мэпе
А у меня вот такой короткий асимптотический ад набрал сотню. http://ideone.com/rd6Hw
читаем 1й и 2й наборы в стринги. потом проверяем для каждой строки из 1го набора какие в нем есть супрефиксы (в лоб с помощью метода substring, ага) и для всех найденных в мапе (map< string, int >, конечно же) делаем ++. теперь идем по 2му набору и выводим ответы, которые лежат в мапе.
прошу прощения за повтор, не особо вчитывался в комментарии
530 баллов, учитывая 0 за 2-ую.
Надо же так зафейлиться...
>9 - 438
>10 - 495
А учитывая это вообще оверкилл...
Мне одному кажется, что в том гуду было проще?
Или вы не про неё?
Хм... Как можно было не взять по модулю ориентированное расстояние? -_-
P.S. По регламенту первое место автоматом идет на всерос?
Чтобы идти на всерос, надо планку набрать. В том и только том случае, если в регионе нет ни одного, набравшего планку среди всех 3 классов (9, 10, 11) есть возможность послать одного участника с региона (опять же одного на все параллели).
лишь бы проходной балл был 500 по десятым классам :D
Ну или наоборот слишком высоким, чтобы никто не набрал :D
Там вроде как по усмотрению жюри и с согласия министерства, если проходной балл не набрали
Тупое разложение на k множителей набрало 80...
Посмотрим на ai и ai + 1. Посмотрим на их разность. Заметим, что эта разность - произведение всех bi (с учетом предыдущих людей), кроме того, на которое показал i-й работник. Т.о. можно легко восстановить, какое количество блюд было в типе, на который показал каждый работник (и, соответственно, какое количество стало - просто минут один).
А теперь пускаем жадник - поддерживаем текущее состояние (есть еще неизвестные), если такое число уже есть, уменьшаем его, если нет - добавляем новое.
В конце, если произведение не равно a1 надо его добавить на любое из оставшихся мест. А остальное забить единицами.
Начинал думать в таком духе, но побоялся опять сумничать получить 0 по В и заслал перебор)
Пусть n[i] = a1 * a2 * ... * aj * ... ap. Тогда n[i - 1] = a1 * a2 *... * (aj - 1) * ... ap. Значит, n[i] div (n[i] - n[i - 1]) = x = aj. Последовательно рассматриваем все n[i]. Получаем таким образом x. Если среди множителей, наличие которых мы уже успели распознать, есть x, тогда просто в текущем массиве множителей мы уменьшаем его на один. В противном случае мы узнали новый множитель, содержащийся в n[i - 1] (а раз мы не распознали его до этого, то он содержится и в n[1]). Запоминаем его для ответа и для массива текущих множителей. В конце выводим этот массив. Если количество распознанных множителей меньше k, то делим n[1] на все множители, получаем оставшийся, записываем и его, остальное можно забить единицами. Как-то так, хотя я понимаю что мой текст очень непонятен)
Разве у вас разбора не было?
Зная отношение n[i] к n[i + 1] мы можем найти, какое у нас кол-во вариантов выбора одного из блюд. Оно будет равно n[i] div (n[i] mod n[i + 1]). Не знаю почему, но у меня получилась такая формула. А дальше будем поддерживать два массива, допустим firstdiv и curdiv. В firstdiv будем хранить предполагаемое изначальное разложение, а в curdiv - текущее. Дальше проще написать кусок кода(сорри за паскаль).
for i:= 1 to m - 1 do begin
divisor:= n[i] div (n[i] + n[i+1]);
position:= find(divisor); // линейный поиск элемента divisor в массиве curdiv
if position = 0 then begin //не нашли
inc(c);
firstdiv[c]:= divisor;
curdiv[c]:= divisor - 1;
end else dec(curdiv[position]);
end;
А дальше выводим firstdiv,посчитав произведение ненулевых элементов этого массива. После этого выводим n[1] div p и выводим единички пока i <= k.
P.S. Да, я не умею объяснять.
Наверно был, но я про него не слышал..
Хм. странно, я написал тупой перебор вариантов разложения на множители и для каждого варианта запускал перебор вариантов увеличений(т.е. конечно уменьшений количества блюд, просто запускал с конца). Вроде ничего сложного, меня больше напрягает что у меня на 8ой WA#4 а не TL.
UPD. http://pastebin.ru/TrMpyWNt вот код если интересно
ну оно как бы вероятностное. =) а решение жюри должно быть строгим.
решение жюри без бора и хешей вообще.
http://codeforces.com/blog/entry/3704#comment-76014
Хэши мне не нравятся, мне проще и очевиднее бор написать.
А вот целые числа в седьмой - нечего было делать последние три часа. Решил чуть улучшить код, чтобы не было проблем даже в теории :)
Содержательная часть решения с бором занимает меньше 15 строк.
А корень извлекается из числа до 10^30, можно написать бинпоиск и длинку. Согласен, немного читы, но только один раз.
там же встроенная длинная арифметика. если число вылезает за пределы типов данных, пайтон делает длинку. причем очень быструю.
Думаю, имелось ввиду, что на C++ это без длинки не сделать. Про питон-то верно.
я думал он говорил про int64 в пайтоне %) которого нету
пайтон, лол)
А правильно говорить "пайтон"? И "си плас плас", наверное.
если уж на то пошло, то "пайс(th)он"
Пишите результаты своих регионов или кидайте ссылки на таблицы.
Так легче будет ориентироваться и понимать, на что рассчитывать.
Ставрополь.
Как бы есть табличка на Google Spreadsheets, там можно ориентироваться.
У нас 1 место-748, 2 - 690 ( на самом деле, Коля требовал -O2 для компиляции, и получил бы 744, если б не наше местное жюри), 3 - <600, точно не помню
UPD а о табличках в нашей области нечего и мечтать ;)
У нас такой же бред был. Сам не пробовал войти, но от друзей слышал, что там доступ в интернет был. Главное, жюри прекрасно знало - они им в первом туре сказали, сказали исправят. Но на втором туре он тоже был.
+: ответил не на тот коммент. ответ к комментарию от kuzmichev_dima (http://codeforces.com/blog/entry/3704#comment-76155)
Красноярский край
Хотелось бы услышать(прочитать) мнение людей насчет олимпиады этого года. А в частности: хоть кому-нибудь кроме меня эта олимпиада показалась более тяжелой, чем в прошлом году??
Люди, подскажите пожалуйста, почему не проходит большую часть тестов(WA) следующее решение задачи 8: 1)Сортируем массив строк с помощью MergeSort 2)Для каждой подстроки-образца с помощью бинарного поиска определяем границы строк, супреффиксами которых является данная подстрока-образец,в отсортированном массиве строк
3
Это не кривые тесты, просто O(n*m) - оценка сверху и выполняется только при определенных тестах. Я думаю, что 85 баллов в данном случае это норм.
upd: и собственно нечего было гнать на мое дерево отрезков которое избавлялось от O(n*m) и получало 100 ))
Где-то слышал, что в Казани.
Мое мнение - по 11ым проход будет в районе 550
Теперь вы можете узреть результаты, которые собрал я.
В задаче 3, вроде, можно выбросить префикс, который является корректным xml, и за это ничего не будет (хотя контрпример <a></a></ba></a>)
В задаче 7 проходят на 100 неточные решения, хотя, кажется, их все можно хорошим тестом заставить работать неправильно (точная проверка требует работы с числами 30+ порядка).
А, и по 8 были слабые тесты, судя по тому какие не оптимальные решения заходили.
UPD: а вернее даже не тесты слабые, а ограничения. длина строк 50 и ограничение на суммарную длину 10^6 сделали свое дело.
Рассмотрим все числа, которые уменьшались по ходу раздачи блюд. каждое число могло либо входить в первоначальный набор, либо быть уменьшенным на 1 другим числом. Тогда жадно расставим, из какого числа могло получиться каждое число. Добавим в набор те, которые ни из какого не получились, потом добьем до нужного количества и произведения. Это завалилось на каком-то тесте с n раза в три больше k.
Решение.
Так вот, можно покрывать граф путями жадно, что я сначала и делал. На тестах, где актуально минимизировать произведение количеств вариантов, то есть n сильно больше k это быстро валится.
На сайте rosolymp появились первые наброски проходных баллов по всем предметам.
"по информатике проходные баллы следует ожидать в районе 450-460 баллов в 9 классе, 500-510 баллов — в 10 классе, 560-570 баллов в 11 классе. Точнее сказать практически невозможно, так как поскольку остается неопределенность в выборе количества участников по каждой параллели (количество может быть от 60 до 90)."
Это, конечно, довольно приблизительно, но в прошлом году предварительный балл оказался очень точным.
Обучающиеся 7–8 классов образовательных учреждений, являющиеся победителями или призерами муниципального этапа Олимпиады по информатике как минимум среди девятиклассников, могут принимать участие в региональном этапе только при наличии соответствующего документа, подтверждающего обучение по предмету «Информатика и ИКТ» в 9 классе в форме экстерната. Вот и все.
Не понял, что именно вы хотели этим сказать.
Это выдержка из "Положения о Всероссийской олимпиаде школьников по информатике".
Не понял, что именно вы хотели этим сказать.
Такого документа, как "Положение о всероссийской олимпиаде школьников по информатике" не существует.
Требования к организации и проведению регионального этапа Всероссийской олимпиады школьников по информатике в 2011/2012 учебном году Обозвал неправильно.
Я так и не понимаю, что именно вы хотели сказать. Да, есть такой документ. Да, в нем написаны такие слова. Да, есть еще "Положение о всероссийской олимпиаде школьников", для которого "Требования" — подзаконный документ.
Да, оргкомитет регионального этапа всероссийской олимпиады школьников в Москве знаком и с "Положением" и с "Требованиями".
И что дальше?
Просто интересно, почему же в Москве среди участников нет восьмых классов?
А в каком регионе они есть?
Пожалуйста, ссылку на протокол результатов регионального этапа.
Я 8 класс. Занял первое место в регионе среди 9 классов. Веселов Иван, Респ. Башкортостан.
А у Вас есть "соответствующий документ, подтверждающий обучение по предмету «Информатика и ИКТ» в 9 классе в форме экстерната." ? :)
А в итоговом протоколе жюри вы записаны, как учащийся восьмого класса или девятого?
А вы изучаете предмет "Информатика и ИКТ" по программе 9 класса в форме экстерната?
С чего вы взяли, что в Москве нет таких же школьников?
Yeap.
А кто-нибудь знает, чем вызван этот запрет для 7-8 классов?
И, как я понимаю, на 1-6 класс он не распространяется? :)
Такая была позиция министерства. По имеющимся у меня слухам, министр ссылался на то, что согласовать участие школьников до 9-го класса в региональных олимпиадах (а это два тура по пять часов) с Роспотребнадзором не получится.
А Роспотребнадзор при чем? Скорее тогда Минздрав должен был возражать?
Ну вы в общем-то не в курсе структуры органов исполнительной власти РФ.
Что такое Роспотребнадзор
Да, конечно, не в курсе. Но, если речь идет о каких-то медицинских противопоказаниях, то я совершенно не понимаю откуда это идет.
Сам постоянно до сих пор читаю в газетах, о том, что первокласнику за компьютером можно находиться типа 10 мин. в день, второкласнику — 15 и т.д. Откуда этот анахронизм? Я, конечно, сам прекрасно помню как у меня перед монитором висел защитный экран, заземленный на батарею. Без заземления нещадно бил током при прикосновении. Но с тех пор уже сколько времени прошло.
Сам-то я всяко не одобряю зависание детей в сетях или играх. Но это уже совсем другой вопрос, и к олимпиадам по программированию, по-моему, он не имеет никакого отношения.
Понятно, что СанПиНы на эту тему — анахронизм. Но увы, они существуют. Поэтому приходится считаться с ними.
И если школе просто игнорировать СанПиНы, то министр образования не может подписывать документы, им противоречащие.
И в этих условиях Россия еще как-то умудряется завоёвывать золото IOI !!! :)
Как всегда, строгость законов компенсируется необязательностью их исполнения :)
Ответ k-va: тогда еще регион не был общим по России, в Питере был теор.тур, отбор был через региональные сборы и никто и не слышал про запрет участия до 9-го класса.
Проходной балл — Информатика — 495, 535, 573.
Источник — http://rosolymp.ru/index.php?option=com_agora&task=topic&id=125&Itemid=4884&p=84