Контест закончился, давайте пообсуждаем. Как решать C?
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | adamant | 157 |
| 6 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | djm03178 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 13.11.2024 04:56:55 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Задача C решается с помощью meet-in-the-middle. Подсчитаем сколько различных троек после конкатенации по модулю дадут каждый из остатков. Ну и вспомогательную информацию для формулы включений/исключений, чтобы отсечь повторы. В общем-то даже без прекалька зашло.
Или можно динамикой (наибольшее добавленное число баллов, уже добавленное подмножество 6 чисел, остаток). Идём в порядке увеличения баллов.
а как подможество чисел храниться?
Маской размера 6 бит. Сами числа нам не важны, только их позиции.
Еще можно перебрать перестановку 6 чисел и искать строго возрастающую последовательность баллов двумерной динамикой.
Я вначале писал meet-in-the-middle но не завелось, и мы сдали с перебором перестановок. можешь дать код посмотреть?
Могу: http://pastebin.com/Z4RcGM1D
КАК(!!!????) решалась Е?
разве не так
Задача имеет решение для всех K, даже нечётных =)
Странно. Для нечетных выводил
-1— Accepted.Even integer K.
Аа, понятно. Я не прочитал это :)
для K=2 ответ
4
rev 1
rev 2
out 1
out 1
Разделим на 2 кучки, в первой K штук, во второй (N — K). В данной задаче N = 18 Пусть в первой перевернутых X штук, тогда во второй — K — X Перевернем все в первой, получим, что в ней K — X перевернутых, и получено решение.
Для этой задачи надо было бы сделать нормальный семпл, мы тоже подумали, что размеры кучек должны быть одинаковыми. Потом третий участник прочитал задачу, и она была сразу же сдана.
а можно рассказать немного подробнее о дополнительной информации, которая нам нужна для включений-исключений? просто идея сначала все остатки подсчитать которые получатся из троек, довольно стандартная для таких задач, мне кажется избавиться от повторов посложнее как то.
Как решались A и B? Можно ли пропихнуть в G двумерную динамику с перебором подмасок за что-то типа n^2.5? Что пропихивается в I, а что нет? Кто-нибудь писал двумерное Фурье?
B — очень просто
Тогда такие задачи не надо давать в соревнованиях по программированию.
Для них более подходят соревнования по интернет-поиску.
А как предполагалось сдавать задачу в харькове, где не локальных компах нет интернета, вообще не понятно.
Мы решали по-другому. Предпосчитали значения для n <= k + 1 и отвечали на каждый запрос за O(k), используя формулу интерполяции.
Правда все равно пришлось попихать, зашло только когда дооптимизировали до 2k взятий по модулю на запрос.
Расскажи подробнее, пожалуйста.
Нам надо посчитать что-то вроде \sum value[i] * \frac {\prod{n — j}}{\prod{i — j}} (codeforces съедает формулы)
Знаменатель — это +-произведение двух факториалов, числитель — это const(i) / (n-i). Только не будем делить по модулю на каждой итерации, а будем считать ответ как дробь и в конце один раз поделим.
Наш код
Ну она честно решается — предпросчитываем коэффициенты многочленов и отвечаем за O(k) на запрос. Что такого полезного для задачи по приведённой ссылке на wiki (и при этом не выводящегося на бумажке за 5-10 минут) — непонятно.
Ээ, не понял. На кубке запрещено пользоваться Интернетом, какая разница есть инет на локальных компах или нет?
Если бы можно было пользоваться интернетом, мы бы сегодня часа полтора-два точно сэкономили.
все слегка покраснели ;)
Лично я не имел в виду, что кто-нибудь воспользовался интернет-поиском. Просто считаю неправильными задачи типа "знаешь формулу — решил", "иначе — нет".
Но, если эту задачу можно решить не зная DP для чисел Бернулли, то нет вопросов. Вот только интересно, а авторы действительно подразумевали решение без чисел Бернулли? Или, действительно, это тривиально выводится?
Выводится несложно, Вася Астахов вот например рассказал:
Пусть P_k(n) — это сумму k-ых степеней от 1 до n. Тогда P_k(n)-P_k(n-1)=n^k. Продифференцируем обе части: P'_k(n)-P'_k(n-1)=k*n^{k-1}=k*(P_{k-1}(n)-P_{k-1}(n-1)). Откуда P'_k(n)=k*P_{k-1}(n)+C, и надо всего лишь найти два коэффициента.
Можно чуть поподробнее? Не понятен переход от P’k(n)-P’k(n-1)=kn^{k-1}=k(P{k-1}(n)-P{k-1}(n-1)) к P’k(n)=k*P{k-1}(n)+C.
Ну пусть f(x) и g(x) два многочлена таких, что f(x)-f(x-1)=g(x)-g(x-1) для всех целых x. Тогда нетрудно заметить, что f(x)=g(x)+C (пусть C=f(0)-g(0), тогда f(1)-g(1)=f(0)-f(0)+f(1)-g(0)+g(0)-g(1)=f(0)-g(0)+(f(1)-f(0))-(g(1)-g(0))=f(0)-g(0)=C, и так далее.
На разборе рассказывали про числа.
Давайте не будем идеализировать людей. 80% участников будут читерить если есть возможность. Поэтому почти бессмысленны на таких соревнованиях задачи про вывод формул для известных последовательностей и не любые гуглящиеся факты.
Ну таких задач в идеале просто не должно быть... как на opencup так и в Петрозаводске...
Если мне не изменяет память, то на разборе рассказывали только про то, что числа Бернулли фигурируют в формуле, но нигде дальше их не использовали. Правда, авторы предполагали, что можно сгенерить табличку и вывести закономерность.
Можно без вики если расписать как суму спадающих факториальных степеней а потом взять интеграл (дискретный)... тогда все что нужно — O(K) на запрос и препроцес чисел стирлинга (это можно легко заметить если попробывать порасписывать степени через спадающие факториальные)
В I мы писали двумерное Фурье.
В G перебор подмасок с некоторыми нетривиальными оптимизациями прошел.
Если я правильно вспомнил что такое G, то там нужна динамика по дереву с состоянием количество вершин в корневой компоненте. Это однозначно задает все подмножества которые есть в поддереве из единственности разложения в двоичную запись. А дальше только не ходить по недостижимым состояниям и решение летает. Впрочем, если не заметить единственности и то все равно летает, если лениво и только по достижимым ходить.
В I команда ИжГТУ находила 10.000 прямоугольников с максимальной суммой, и потом считала сумму по маске в этих прямоугольниках.
В задаче B я писал многочлен Лагранжа. 20 секунд на локальном компьютере.
В I я сдал обычное Фурье посчитанное от всех строк исходной и строк образца... Правда оно еле влезло в ТЛ =/.
Зачем в I двумерное Фурье? Одномерного достаточно — нужно произведение \sum a_{i,j} x^{im+j} и \sum b_{i,j} x^{mn — (im+j)} (где m — ширина большого поля).
А можешь пояснить что ты имеешь в виду под двумерным Фурье? Это обычный Фурье только для полинома получающегося из таблицы выписыванием строк сверху вниз?
Нет, это F[x,y]=sum(a=0,N-1){sum(b=0,M-1){A[a,b]*exp(-2*PI*i*(x*a/N+y*b/M)}} (надеюсь, можно что-то разобрать). Это, конечно, эквивалентно тому, чтобы сначала применить преобразование к каждой строке, потом — к каждому столбцу (или наоборот). http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Multidimensional_DFT . Этой штукой можно делать двумерную свертку, реверснув столбцы и строки одной из преобразованных матриц и поэлементно перемножив (ну то есть все как в одномерном случае). Правда (как я здесь узнал), свертку можно получить и просто дописав к матрицам кучу нулей и перемножив полиномы, полученные выписыванием строк подряд. В этой задаче и дописывать нули не надо было: они уже были дописаны во второй матрице где надо.
Мне показалось, что константа у двумерного фурье хуже, чем у одномерного. Я прав или нет? Размеры матриц n у тебя были 2^10 или 2^11? Я использовал одномерное фурье, размер массива был 2^(21). Три преобразования. Тебе как я понял нужно 6 * n одномерных преобразований, так?
Что одномерное, что двумерное, это ровно N M log_2(NM) "бабочек", то есть константа одинаковая. Двумерное должно быть быстрее, потому что более локально обращается к памяти (только к одной строке каждый раз). Но не в этой задаче: тут для двумерного преобразования наверно понадобились бы матрицы размера 2^11, и получилось бы в 2 раза больше операций. Сам я эту задачу не писал, я тут диванный аналитик :)
Кто решал задачу N не с помощью теоремы Ловаса? И вопрос на засыпку: что такое вполне случайный граф?
Определение вполне случайного графа так и не обнаружилось, зато выяснилось некое важное свойство таких графов. Для вполне случайных графов заходит обычный Кун. Вы конечно можете возразить, что это свойство не графов, а тестов, но разве в див-2 такое возможно?)
Зато история с массовыми ok'ами по этой задаче проясняется)
Вот интересно, а что сдавали в D? Я написал следующее: нумеруем все элементы в соответствии с первой разностью арифметической прогрессии (т.е. 0 получает номер 0, A — номер 1, 2A — номер 2,... kA — номер k, потом 1 — номер k+1, и т.д.) и в соответствии со второй. Получаем у каждого элемента по 2 координаты, строим на них как на точках квадродерево. Нам приходят запросы "+1 в вертикальной полосе" и "сумма в горизонтальной полосе", они делаются за sqrt(n) обычным способом. Казалось бы, n * sqrt(n), но оно ни в какую не лезет в ТЛ на сервере (видимо, из-за мелкого кеша). У кого-нибудь получилось такое сдать? Или есть более быстрое решение?
Сдали за n sqrt(n) log(n), отдельно рассматривая случаи, когда A и B маленькие, и когда хотя бы одно из чисел большое.
А чем случаи "A и B маленькие" и "хотя бы одно из чисел большое" особенные? И что у вас за n sqrt(n) log(n), тоже квадродерево?
"A и B маленькие" — заводим lcm(A,B) деревьев, отвечаем на запросы за B / gcd прибавлений на отрезке и A / gcd сумм на отрезке соответственно.
"Одно из чисел большое" — заводим (меньшее из чисел) деревьев, запрос одного типа — это запрос к одному дереву, на запрос второго типа отвечаем в лоб.
Ну видимо за n sqrt(n) log(n) можно решать разбивая запросы на sqrt(n) блоков. В каждый момент храним актуальную информацию до текущего блока и запросы которые уже были в текущем блоке. Мы подумали, что это не пройдет и не стали писать. Команда Saratov SU 1: Bondarenko, Matov эту же идею использовали только избавились от log(n)
Ааа, я понял, что все делали, спасибо. Не знал, что у квадродерева настолько большая константа, что оно тупняку сливать будет...
Будем рассматривать три возможные нумерации фотографий:
1) исходную
2) такую, чтобы все запросы на +1 были на отрезке (то есть чтобы элементы, которые были на расстоянии A, оказались рядом)
3) аналогично с B.
Во второй нумерации будем хранить sqrt-декомпозицию, позволяющую добавлять на отрезке и узнавать в точке. Третью нумерацию разобьем на отрезки по sqrt(n). Для каждого из них будем поддерживать сумму. Предподсчитаем для каждой пары (отрезок в третьей нумерации, префикс во второй нумерации) количество общих элементов. При запросе на изменение, надо добавить 1 на отрезке во второй нумерации и добавить к каждому отрезку в третьей нумерации размер его пересечения с отрезком запроса. При запросе на сумму, сложим ответы для всех целиком попадающих в отрезок отрезков в третьей нумерации и добавим сумму остальных элументов, пройдя по ним и посмотрев значения в sqrt-декомпозиции. O(N sqrt(N)). Фух, в голове намного проще, чем текстом :)
Сначала вместо sqrt-декомпозиции использовал дерево отрезков, и было O(N sqrt(N) log(N)), не смог запихать.
После таких контестов появляется желание вообще не писать Opencupы. Такое ощущение, что авторов заставили сделать хоть какие-нибудь задачи и дать на контест.
Меня наоборот улыбнули истории про Иру :D Да и задачи вроде интересные были =)
Я бы не стал называть интересными задачи B и E, а также то что в I ограничения 800 (хотя может у авторов решение быстрое решение без Фурье)
B — прикольная задача, проверяет факт "в команде есть математик". А в хороших командах всегда нужен математик :)
А что не так с I? Два прямых и один обратный Фурье для многочленов размера миллион — это же очень быстро, укладывается в ТЛ с большим запасом.
В B же есть нормальное решение, которое может придумать и не особо продвинутый математик, cerealguy его описал.
По-моему нормальные решения придумывает как раз математик:)
"Продвинутости" не требуется, нужен человек, который умеет придумывать нетривиальные вещи. У cerealguy в команде как раз с этим всё в порядке :) Наверное, можно запихать и что-то совсем безыдейное, но с математиком она решается быстро и без проблем.
С I не так то, что она совсем неинтересна участникам, которые ранее встречали точно такую же задачу (с другой легендой, конечно). Она дает таким значительное преимущество.
В I четвертая степень заходила при желании (за O((N*M)^2)). Мы запихали решение, которое представляет собой полный перебор позиций, ускоренное в 8 раз.
Такой вопрос а как получается многочлен размера миллион. Я сдал в дорешивании и у меня получилось 800 * 800 * 2 и плюс ближайшая степень двойки. Всего 2^21 = 2097152.
Ну надо перемножить два многочлена, каждый размера 800^2, что меньше миллиона. Фурье конечно приходится делать для 2^21, т.к. результат имеет размер больше миллиона.
Ну я первый многочлен раздваивал, чтобы учесть всевозможные сдвиги, поэтому получилась длина 2 * 8002. А можно как то без раздваивания первого?
Зачем первый раздваивать? Первую матрицу выписываем прям по строкам, вторую — дополняя строки нулями до ширины первой. Вот если были бы разрешены сдвиги, при которых вторая матрица вылезает за границу первой, нужно было бы 2 * 800^2.
Да и Е вроде была на идею.
Идея детская, на самом деле.
Я вообще сдал эту задачу после того, как мне пришла смс от подруги. Тут я и вспомнил, что пару месяцев назад она рассказывала мне головоломку, где в темной комнате монеты подкидываются вверх, несколько из них падает орлом вверх. Нужно разделить (комната темная, ничего не видно) монеты на две кучки так, чтобы в каждой лежало равное количество монет орлом вверх. Вот такая вот удача :)
И я вспомнил эту же головоломку о разделении монеток на 2 кучки с равным количеством повернутых орлом вверх монеток в тёмной комнате :)
Оказывается, Е тоже боян.
E точно боян, мне ее пару лет назад на собеседовании давали
Подскажите, пожалуйста, идею решения задачи M — MySpace( div.2 ). Пытались решить её многие, и почти у всех, наверное, был вердикт TL. И только 4 удачных сабмита на весь дивизион.
Мы сдали за N*sqrt(N)*С, где C — обращение к мапу.
Идея предельно простая и выше уже обсуждалась: разобьём запросы на блоки размером sqrt(N).
Тогда вначале каждого блока мы можем пересчитать ответ за линию для всех остатков деления на A и на B.
Тогда при запросе суммы мы уже знаем ответ для всех запросов, которые были до текущего блока запросов, а из этого блока мы можем легко добавить, пробежавшись по этим запросам и взяв из мапа сколько у нас элементов с указанным остатком деления на B пересекаются с остатком деления на A из запроса на добавление.
Фигня, конечно, но зашло. Код: http://pastie.org/3465337
Сдал в дорешке за n*sqrt(n). Рассмотрим 4 случая. Если A, B > sqrt(n) все просто. Если A > sqrt(n), будем бегать через A и плюсовать у встречаемых ост по % B. Если B > sqrt(n), будем хранить для каждого ост по % A, сколько раз его плюсовали, ответ на запрос суммы — пробег с шагом B, суммируя кол-во плюсов у ост по % A. Если A, B < sqrt(n), то найдем для каждого ост по % A, сколько раз встретится каждый ост по % B, если начнем бежать с шагом A от него. Тогда обновление — пробег по массиву встречаемых ост и суммирование кол-ва их встреч.
Кто подскажет как решались F, J?
F — попробуем получить наше число как OR отдельных битов, использующихся в нём. Для получения i-ого бита возьмем все числа, которые его содержат, и возьмем их AND. В результате получится маска, которая содержит i-ый бит и возможно что-то еще. Если это "что-то еще" полностью содержится в числе (является его подмаской), смело берем его. Если это верно для всех битов числа — Yes, иначе — No.
I wonder how checker works on problem E.
Heard of Nim?
The problem won't change much if you replace K with 18 — K. According to the constraints (K <= 18, output length <= 2^9+36) a simple brute force checker should suffice: binom(18,9)*2^9 ≈ 25 millions, a factor of 18 being avoided by bit hacks
to slowww