Привет всем. Прошёл первый отборочный тур ИОИП. предлагаю обсудить задачи здесь.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.11.2024 19:13:19 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Уже можно обсуждать?
Да вроде конец.
Не знаю У меня кнопка сабмит работает
у меня вот что. OVER, 300:00 of 300:00
Как решать D на 100?
Ну у меня пока 40. Когда будут резы узнаем 100 или нет. Дп с параметрами номер бита, биты чисел x, y, z и меньше ли x r, меньше ли y r, меньше ли z r,больше ли x l,больше ли y l, больше ли z l.
Заметим, что какая-либо пара x и y однозначно задает z. Переберем в какой позиции x и y начинают отличаться от L или R (это тоже перебираем). Проверим, что сгенерированный префикс z попадает в [L; R]. Будем потихоньку идти и добавлять очередные биты в x и y, поскольку они уже однозначно лежат в интервале [L; R], нужно проверять z. Будем пересчитывать количество способов получить текущую позицию. Если новый бит у z однозначно определяет, что z лежит в интервале [L; R] добавим в ans 2^(кол-во оставшихся бит) * (кол-во способов попасть в данную позицию), если же нет, то префикс z все еще совпадает с префиксом L или R, продолжаем генерировать последовательность. O(log^3).
Результаты уже появились. Ссылка на архив тестов и решений жюри не корректна :( Как решать С на 100?
Где появились?
http://neerc.ifmo.ru/school/io/archive/20140118/standings-20140118-individual.html
Так, а кому писать если меня там нет?
Это не они
Это видимо результаты тех, кто писал вне конкурса.
-
Я решал С так. Я не уверен что на 100, т.к. сделал маленькие массивы но идея такая Будем хранить в сете числа которые написаны на квадрате Найдем минимум потом дфс находим такие числа которые на 1 меньше текушего (если рассматриваем в бфс чисор то выкидываем его из сета), заходим в них рекурсивно итд Запоминаем максимальную глубину дфса
-
еще нужно заметить что нужно красить уже посещенные вершины, чтобы в них дважды не заходить
Можно заметить, что при обработке клеток, начиная с самой маленькой, никаких дфсов/бфсов не нужно. Можно просто завести массив, в котором будет храниться ответ для каждой клетки, изначально все ответы равны 1. Тогда, при обработке с самой маленькой, мы будем смотреть на соседние, и если они на единицу меньше текущей, то в ответ текущей будем записывать максимум из текущего ответа и ответа для соседней + 1. Очевидно, что, если из данной клетки переходов в меньшие нет, то для неё ответ равен 1, иначе меньшие соседние клетки мы уже обработали. Получаем быстро пишущееся решение за O(n*m*log(n*m)).
С другой стороны, если использовать дфс/бфс в решении, то можно не сортировать клетки, а просто запускать обход из тех клеток, где мы ещё не были. В обходе всё почти так, как и у вас, только мы для каждой посещённой вершины запоминаем ответ. В итоге получаем решение за O(n*m).
Заметим, что у нас есть несколько ациклических графов. Несложно посчитать такую динамику:f[i][j] — это максимальный по длине путь, заканчивающийся в клетке i,j. Код под спойлером.
Ваше решение прошло на 100? Просто у меня идея похожая, но только 60. Вот я бы хотел узнать почему мое решение неправильное. http://pastebin.com/vSB4XbXK
Да, 100.
я решал БФСом, реализация оказалась простой.
вот код
Эммм... Сначала релаксируется текущая динамика, а только потом, если мы еще не посчитали dp[newx][newy], считаем?
Так или иначе мог быть stack overflow.
А у всех задачи протестировались? У меня до сих пор нет
где вы смотрите?
в PCMS2
У меня тоже нет....
Мое решение один в один совпадает с Вашим и тоже получило 60 баллов :(
Если ваше решение совпадает один в один то вас должны были дисквалифицировать)))
Контест какой-то баянистый был...
Первая задача — элементарна.
Вторая задача — фигню надо писать.
Третья задача — стандартный алгоритм.
Четвертая задача — стандартное ДП.
Это был отборочный раунд, которые традиционно легче обычных контестов. Ждём тебя на следующих личных олимпиадах.
Привет всем.
Сейчас опубликованы все материалы, включая предварительные результаты первого отбора. Такая задержка связана, в основном, с проверкой на списывание и дисквалификацией тех, кто ее не прошел.
Результаты
Какой проходной балл?
Решение про проходной балл еще не принято. Как только, так сразу опубликуем.
Добавьте, пожалуйста, кто-нибудь тренировку по Первому отборочному туру ИОИП.
Спасибо. :)
Поддерживаю
Проверю, правда ли что там трабла с размером массива или с чем то другим