Я правильно понимаю, что по мнению авторов ГП Азова слон не является шахматной фигурой?
UPD: Официально объявлено, что Гран-при внезачетный
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
38:18:14
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
38:18:14
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 03:16:46 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Является
Ну, судя по тому, что тупое решение со слоном получает WA 8, а без него — TL 10 — таки нет
Какой у вас ответ на 7 3 1 1?
у AC решения — 18
upd. больше не AC =(
А правильный ответ — 19. Клетка 7, 3 достижима слоном минимум за 3 хода
А не 20 правильный?
Да, правильно, я ручками посчитал не запуская и ошибся
По-моему, вообще 20 -- клетка 5, 3 тоже достижима слоном минимум за 3 хода.
Спасибо...
хм, 3хN вроде поле было, только не помню какое...
да, такого теста не было, были только 3х3 с тремя способами расстановки...
У моего решения и стресса — 20. Моё решение на авторских тестах заходит.
А покажи свое решение. Мы пробовали правильное решение написать, но там адовейший адец :(
У меня O(N + M) и ад, я делил доску по меньшей стороне и решал как две отдельные доски, где фигура на меньшей стороне. Для каждого X по большей стороне я как-то вычислял кол-во хороших клеток на нём. Долго дебажил, чтобы сошлось со стресс-тестом.
У Миши с Пашей О(1). Проверенно стрессом на досках до 20х20 и 40х10
Есть подозрение, что на opencup тесты не последней версии.
Да, Олег уже написал
Да, там очень неприятно писать, но я думаю, что есть команды, которые сдавали по другому.
Давайте посчитаем количество клеток ans, до которых все фигуры доходят за четное количество ходов. Тогда ответ будет N * M - ans. Разобьем доску на 4 части диагоналями, которые проходят через клетку (X;Y). Для каждой части, если посмотреть в какие клетки доходит туда слон за четное количество ходов, можно увидеть, что там будет образовываться период. Т.е. некий кусок достижимых, потом недостижимых, потом достижимых и так дальше. Можно посчитать сколько в куске, домножить на количество таких кусочков и прибавить ещё остаток. Если посмотреть какие именно клетки подоходят в куске, то там получиться два прямоугольника + арифметическая прогрессия. Сложнее считать в остатке, т.к. эти прямоугольники могут превратиться в прямоугольник + прогрессия. Сложность O(1).
Исходник
Является. Как конь, ладья и король, этого достаточно.
А как решалась задача А?
Заметим, что ответ не превышает 26*2. Так как каждую букву можно ввести и сразу удалить. Построим бор на всех подстроках длинны до 52. И намутим что-нибудь в этом боре.
Например будем рассматривать все возможные пути в боре. Предположим, что текущий путь мы введём в самом конце, а значит его не надо будет удалять. Такой путь, который можно будет не удалять очевидно только один. А значит за остальные мы не получим никакого бонуса, значит, что всё, что не покрылось полностью единственным неудаляемым путём имеет смысл покрыть вводя по одной букве и удаляя её. То-есть ответ это длинна пути + 2*(кол-во букв, непокрытых полностью этим путём). В процессе обхода бора будем поддерживать сколько букв у нас полностью покрыто. Для этого мне потребовалось хранить число строк проходящих через каждую вершину и строить в процессе обхода префикс функцию. Так как когда мы при обходе бора проходим через некоторый символ мы можем добавить его к покрытым только если он не был покрыт раньше префиксом текущего слова. Тоесть первое вхождение этого символа больше длинны префикс функции для текущей позиции
Как решались А и К?
Мы весь контест паттерны в слоне искали :( Это явный повод для unrated-раунда.
Полностью согласен. Без слона эта задача ни о чем
В задаче F решение за MN проходило ?
У меня не прошло. Только за KM.
Разве 10^9 простых операций так много на 15 сек ?
На моем ноуте решение за NM работало порядка 10 секунд, но получало TL23. Решение за KM работало меньше 3 секунд и тоже получало TL23, потому что большие массивы не влазили в кэш.
у меня NM на 29 падало.
У нас в решении был двумерный массив частичных сумм. Поменяв размерности массива местами мы стали попадать в кеш и решение ускорилось больше чем в 10 раз (было почти 8 секунд стало 0.74)
Оказалось, что Пашка перепутал. MK на самом деле
Что-то типа MK logN я насчтал у себя, хотя наверно меньше все же.
NM проходило. Код
Решение К: Заметим что поведение показателей степеней схоже с поведением для биномиальных коэфицентов, странные перепады происходят из-за делимости факториалов. Переберём функции подобные Cij, каждый раз смотря сколько чисел в таблице показателей степеней совпало. В итоге получается что есть функция которая ведёт себя абсолютно так же на двойках и тройках:
Показатель степени простого числа p в n! считается легко: это сумма по всем целым k: n / pk
А я сдал предпосчёт. По модулю 2200234002 посчитало за 10 минут. А как доказать, что та функция правильно себя ведёт? Как вообще можно анализировать такие функции, кроме как считать и искать закономерности?
У меня тупое решение без модулей на Java считает пару минут. Доказательства нет, я проверял 1000х1000. Эта штука была найдена случайно, из-за схожести таблицы показателей с факториалами. Там всё завязано на эллиптические функции, недавно появилось доказательство целочисленности.
Можно поподробнее, как сдавать предпосчет, если в условии 0 <= n,m <= 1000, и, стало быть, порядка 10^6 возможных тестов?
Хм, АСы же вроде не забирают..
Да, поэтому ГП, судя по-всему, будет незачетным
А как поведут себя организаторы в Таганроге?
Ну то есть сдав говно, которое другие не стали писать из-за того, что оно не правильное, можно выиграть онсайт соревнования?
А может там никто слал эту задачу? Где-нибудь есть ранклист?
Здесь есть монитор, но он заморожен.
В Таганроге не было реджаджа... он не нужен... наверное...
Покажите код по B (про XOR) и D (про маршруты), пожалуйста, интересно где набажили.
B D
А какая у Вас идея в B? Мы писали бинпоиск по answer^X.
разобьем как в Дереве отрезков на отрезки длины 2^n, таких, что первое число кратно 2^n. Пусть a1,a2 лежит в A, b1,b2 в B. тогда a1^X < b1^X => a2^X < b2 < X
то есть отрезки — целые группы. Ну дальше все понятно — сортим, выкидываем отрезок, уменьшаем К, если в нем меньше К элементов.
Найти на отрезке Кый элемент легко. Это "Общее начало""число, которое в xor'е c концом X дает K-1"
UPD: Отрезков не больше лога
UPD: Наверно не понятно из того, что говорил. Отрезки имеют вид START0000...START1111
D
Авторское по B. Lottery
В задаче H.(Numismatists)(у див2 она Е).Что будет худшим случаем для числа 6? Мне казалось что обратный но тогда можно
за 7 ходов,хотя проходит решение которое выводит 8...
Из 651432 нельзя получить 652143.
Из 651432 уже не получается 652143, вроде как.
Там на первое, из 2^k мест, ставится минимальный элемент.
Хочется еще отметить, что в условии задачи Е не были перечислены шахматные фигуры и правила, по которым они ходят. На наш вопрос "Какие шахматные фигуры могут быть" нам ответили "все", что весьма невнятно. Например, вообще непонятно про пешек, мы долго ломали над ними голову. После разбора второго теста (который немаленький) все, правда, стало понятно. Однако в итоге обнаружился неприятный баг со слонами.
Мнение мое личное и многих участников из нашего сектора (в том числе видавшего виды бывшего координатора задач на Codeforces RAD): в подобных задачах нужно подробно пояснять, какие есть фигуры и как они ходят. Не все acm-щики играют в шахматы. Участники не должны использовать все свое воображение, чтобы додуматься, чего хотели авторы задачи. А такие условия вызывают массу вопросов и недовольства.
Когда мы принимали решение по условию этой задачи, учитывалось, что турнир командный, а задача сама по себе сложная, и очень маловероятно, что все 3 участника будут не знакомы с правилами шахмат. Я при этом погуглил другие задачи про шахматы и убедился, что многие авторы опускают эту информацию, особенно когда речь идёт о всех фигурах — в этом случае описание ходов занимало бы пол страницы минимум.
То, что подразумевались все фигуры — это на наш взгляд очевидно. Просто представьте себе, что бы с нами сделали участники, если бы учитывались только некоторые :)
По ходам всех фигур, кроме пешки, сомнений на наш взгляд быть не может. Про пешку — согласен, стоило написать подробно, учитывая, что там может быть разное понимание условия (как по самим ходам, так и по направлениям). С другой стороны, насколько я понимаю, единственное понимание, которое влияет на ответ задачи — это разрешение хода на две клетки и хода наискосок одновременно. Но при отсутствии других фигур на доске такое понимание условия довольно сомнительно, и к тому же противоречит семплу, который и правда можно было сделать и поменьше.
Добавлю, что на онсайте на вопрос о ходах пешки командам давался подробный ответ. Если бы такой же вопрос был задан на Кубке и передан нам координатором, мы бы поступили также.
Я не знаю, что подразумевалось в задаче, но замечу, что в шахматах пешки не считаются фигурами.
К счастью, наше условие при этом остаётся корректным :)
Вообще, в таком случае я готов забрать свои слова об отсутствии необходимости перечисления фигур назад. Честно говоря, лично я просто не знал этого факта)
При этом английское piece пешку включает, а русское "фигура" — нет. И проблемы не только с двойным ходом, но еще и с превращением в ферзя
При превращении в ферзя без двойного хода ответ не меняется, потому что все клетки, достижимые такой пешкой, достижимы ферзём (а также ладьёй и слоном) за 1 ход и уже включены в ответ.UPD: всё что выше некорректно, на самом деле такая пешка покрывается королём.
Не совсем. Пусть пешка на свой четный ход дошла до последней горизонтали. Тогда все клетки, достижимые оттуда ферзем (а среди них есть, например, клетки того же цвета, то есть самые интересные) будут достижимы "пешкой" за нечетное число ходов. Если же она дойдет за нечетное число ходов, то почти все клетки доски будут достижимы за нечетное число ходов (кроме тех, что достижимы с позиции превращения ферзем/конем)
Только сейчас дошло, что под превращением в ферзя подразумевалась именно замена фигуры. Мы вообще забыли про такой вариант, когда составляли условие.
Надо чаще играть в шахматы :)
Легче вставить рисунок ;) как и кто ходит.
Верно — это было бы оптимально) Как-то не подумали.
А как решалась задача J? Я решил ее с помощью 2-х RMinQ и одного RMaxQ. Думаю, я один такой) поэтому хотелось узнать решение попроще.
Мы для каждого числа считали p[i] — расстояние до предыдущего такого же и затем d[i] — количество предыдущих p[j], совпадающих с нашим p[i]. Кроме того, дерево отрезков с максимумом из i — p[i]. Затем в онлайне отвечали на запросы. Может быть, можно как-то проще, если в оффлайне.
Я почти также. Вначале посчитал массив b[i] — номер индекса следующего числа равного i. Также составил массив d[i] — расстояние до предыдущего такого же. Потом с помощью дерева отрезков (RMinQ по b) нахожу p. Это будет min(l,r)-l. Затем если min(l+p,r) == max(l+p,r)==p (RMinQ и RMaxQ по d), то вывожу 1, иначе 0). Так что ваше решение на одно дерево отрезков меньше:D уже лучше)
Решение попроще за O(N + M): В одном массиве B[i] будем хранить позицию, до которой мы можем двигаться вправо от i, пока все a[j] на пути будут различны. Это легко вычисляется как min(B[i + 1], следующее вхождение a[i]). Это позволит за O(1) найти размер блока из уникальных, обозначим его len. Затем найдем сколько от каждого числа a[i] двигаться влево до такого же, пусть это массив C. Надо быстро определять, чтобы все значения в C[l + len, r] = len. Заведем еще массив D, D[i] = (C[i] != C[i — 1]). Проинтегрируем его. Теперь все C[l + len, r] = len, если (D[r] — D[l + len] = 0) & (C[l + len] = len).
А подскажите пожалуйста как решалась H? Я сдал 6 задач, а эту не сдал, хотя её очень активно решали. Задача "Нумизматы", про хитрую сортировку монет.
Мы так рассуждали: если мы делаем операции и не трогаем самую старшую монету, то мы эти же по сути операции могли сделать и без присутствия старшей монеты. Если же трогаем, то порядок всех остальных монет не меняется. Поэтому справедливо, что для n монет ответ — минимальное количество ходов в худшем случае, если было бы только n - 1 монет + за сколько мы можем опустить самую старшую на своё место (а это либо 1, либо 2 хода).
Можно еще посмотреть для маленьких и сделать рекурсивную формулу,
,
А завтра OpenCup будет?
А то и snarknews.info, и opencup.ru всю неделю лежат...
Должен быть. И кстати они работают и не лежали вроде как.
Да. И у меня opencup.ru работал все те разы, что я пытался на него зайти
И прямо сейчас работают?
А у меня тогда что за ерунда, не открываются через 2-х разных провайдеров. Или опять какие-то чисто белорусские проблемы =(
Да, и сейчас доступны, но см. коммент Ильи снизу
И opencup.ru, и snarknews.info доступны с очень ограниченного диапазона ip. В частности, из Германии вроде ниоткуда недоступны. Даже vpn не спасает. Похоже, "умный" хостер всё ещё думает, что opencup ддосят, и поэтому блокирует доступ почти отовсюду.
Очень "весело"...
В общем, проблема лечится vpn'ом на российский сервер. Но надеюсь, snarknews разберётся с хостером.