OpenCup - Codeforces

→ Обратите внимание

До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Artishok

OpenCup

Автор Artishok, 14 лет назад, По-русски

Порешал сегодня OpenCup... Задача T, и поиск причины почему не работает скушала весь моск... Ничего не понимаю...Не подскажете тест 24

opencup

Artishok
14 лет назад
70

Комментарии (70)

Написать комментарий?

gen	14 лет назад, # \| +12 Не по вопросу, но: как можно было допустить столько грамматических ошибок в переводе? Некоторые задачи просто невозможно было читать. Задача F в этом плане лучшая, например, "On the table N heaps of stones are" (master Yoda says). → Ответить

vilcheuski

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

← Rev. 2 →

Для Пети я увеличивал максимальное число на количество повышений уровня. Тогда ответ равен сумме квадратов чисел. А для Васи я каждый раз увеличивал минимальное число. И потом искал произведение.

→ Ответить

Artishok

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

Самое грустное в этом, что делал тоже самое... Но почему ломается, не пойму :(

→ Ответить

vilcheuski

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

← Rev. 2 →

Хочешь, скину тебе своё решение на эл.почту. У меня тоже были проблемы с этой задачей. Был WA 18

→ Ответить

Artishok

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

[email protected] - скинь, пожалуйста :)

→ Ответить

vilcheuski

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

Читай в своей переписке. Отослал туда.

→ Ответить

freopen

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

Как решать H?

→ Ответить

cmd

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

← Rev. 2 →

Разобьем девочек по классам эквивалентности по строкам им соответствующим.

И посчитаем количества.

Тогда получаем cnt[i] - это количество таких девочек, что они дружат с мальчиками из множества i.

Затем, посчитаем новый массив ncnt[i] - количество таких девочек которые в подмножестве друзей имеют i.

Тогда ответом будет сумма binomial(ncnt[i], L) для всех i в которых ровно K мальчиков.

Сложность получается что-то вроде: O(3^M)

→ Ответить

Vashegin.Roman

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

Для каждой девочки заводим маску мальчиков. Считаем скока раз каждая маска используется...
Перебираем маски мальчиков, где их ровно K и для каждой такой маски находим величину All_girls - равную сумме количеств тех масок, которые поглощают маску мальчика.
дальше суммируем к ответу C из All_girls по L. Как-то так.

→ Ответить

e-maxx

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

Или просто bitset :-p

Если подробнее, то научимся быстро находить маску всех девочек для выбранной маски мальчиков. Для этого предпосчитаем bitsetы девочек для всех возможных первых половинок маски мальчиков, а также для каждой возможной второй половинки - итого порядка 2^8 bitsetов.

→ Ответить

freopen

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

Я делал так: завел маски для каждого мальчика и перебираем наборы мальчиков. Причем девочек группируем в группы по ~23 девочки и объединяем желания мальчкиков посредством &&. Затем считаем количество единиц предподсчетом для всех масок из 23 девочек. На моем компьютере работает около секунды - а на сервере TL38. Кто нибудь смог затолкать такое решение?

→ Ответить

winger

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

У меня были группы по 32 и Integer.bitCount

→ Ответить

ilyakor

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

Ну у нас прекрасно зашло с stl'евскими bitset'ами (только &&-ить их надо конечно в процессе рекурсивного перебора мальчиков, тогда время работы будет 2^15 * 100000 / 32, а не 2^15 * 15 * 100000 / 32).

→ Ответить

Edvard

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

Почему 2^15 когда можно перебрать только маски с K битами. А их максимум C(15, 8) ~ 3500

→ Ответить

ilyakor

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

Ну да, это я просто очень грубо сверху оценил, чтобы понять, что точно должно успевать.

→ Ответить

Edvard

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

Да мы но мы не толкали мы просто STLим bitsetом воспользовались. Он работает заметно быстрее (видимо они группируют по 32 бита)

→ Ответить

vilcheuski

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

А как правильно делать задачу М(восстановление количества очков). У меня WA 20.

→ Ответить

Artishok

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

я перебирал строку (0,1,2,3,4,5,6,7,8,9,-) и смотрел, может ли такая быть.. для каждой строки из заданных считаем кол-во строк, подходящих из этих строк.. учитываем, что "-" может быть только на 1 позиции и если "-" на 1 позиции, то 0 на 2-ой позиции не может быть. ну.. и 0 на 1-ой тоже не может быть.. потом произведение количеств - ответ на задачу.

→ Ответить

vilcheuski

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

А я про минус забыл:( Спасибо.

→ Ответить

Electronick

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

У меня похожая идея было но почему то на 17 проваливалось пол часа искал причину и всё в пустую!

→ Ответить

Snipx

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

А что насчет S?

ВА 22 было =(

→ Ответить

SergeyLazarev

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

Считаем независимо по каждой из координат. Для каждой координаты перебираем все варианты и считаем количество ходов. Выбираем минимум. Затем складываем ответ для обеих координат. Добавляем к ответу удвоенное количество предметов (чтобы подобрать и положить).

→ Ответить

taras.klaskovsky

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

Можно было ускорить и для каждой координаты выбрать тот вариант, в котором лежит медиана массива

→ Ответить

yarrr

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

А можно поподробнее, если не сложно, не понял идеи :(

→ Ответить

taras.klaskovsky

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

Расстояние у нас независимо по X и Y, т.е. при выборе x-координаты можно считать, что все y-координаты одинаковы(т.к. тут не обычное расстояние, а без корня--|xi-xj|+|yi-yj|) и наоборот

В этой задаче проходил перебор, но можно было просто взять медиану массива, потому что если мы выбрали не медиану, это значит что с одной стороны осталось больше точек чем с другой и если мы подвинемся туда то улучшим ответ на разницу между этими числами, уменьшив расстояние до большей части точек на 1 и увеличив для меньшей на 1

→ Ответить

yarrr

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

Но, если я правильно понял идею, куб же получается, а за куб не заходит.

→ Ответить

taras.klaskovsky

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

← Rev. 2 →

Два раза(для X-координат и Y-координат) перебираем результат от 1 до N, в каждой итерации суммируем расстояние до остальных клеток за O(N) (у нас есть массив x[i]--количество точек с x-координатой i и любой y-координатой, т.к. это не влияет, аналогично y[i]) и выбираем лучший вариант.

→ Ответить

AlexErofeev

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

Как решать B, E, F, G, I?

→ Ответить

Vashegin.Roman

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

← Rev. 6 →

С - динамика по подмножествам. параметры - маска секторов, раунд, но запоминаем ответ только для маски, ну и замыкающие соотношения:
Достигли раунда K+1 и сектора I нет -> 1.0, сектор I есть -> 0.0
Не достигли раунда K+1 и сектора I нет -> 0.0, сектор I есть - пытаемся взять каждый из оставшихся секторов.

F - Функция Гранди.
Найти некоторые закономерности: одна из которых ответы цикличны и периодом x+y
Обозначим:
X = min(x,y)
Y = max(x,y)
А для отрезков [0,Y-1],[Y,X+Y-1] закономерности...
В первом отрезке ответы 0,1 чередуются через X.
Во втором отрезке ответы 1,2 чередуются так же через X (кроме начала), ну и надо проверить с чего начнется второй отрезок на стыке.

G - жадно, НО не даем сразу замкнуть цикл.
Сортируем все ребра по убыванию весов, для каждой вершины храним флаги, были ли входящее и исходящее из нее ребро и вершину начала цепи.
Для очередного ребра смотрим, не было ли у начальной вешин исходящих ребер уже, для конечной не было ли входящих и не будет ли цикла, проверив не является конец ребра началом этой цепи. Ставим ребро, обновляем начало цепи для всех вершин второй подцепи.
В конце замыкаем цикл оставшимся ребром.

А как решать I,K без явы????

→ Ответить

cmd

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

K так:

переберем все простые числа до ~4000 и посчитаем вхождение каждого и поделим все числа на все простые до 4000.

Теперь осталось какое-то число где все простые делители не меньше 4000 -- положим число P. Если P > 1, тогда есть какие-то простые числа в разложении > 4000. Тогда максимальная степень простого числа будет меньше 5. И если степень какого-то простого числа >= 2 в остатке, а у другим отличаться, то как минимум у одного степень будет == 1. Тогда нужно проверить извлекается ли корень 2, 3 и 4й степеней из P если извлекается, то проапдейтить ответ, а если не извлекается, то ответ равен 1.

→ Ответить

Vashegin.Roman

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

Спасибо!

→ Ответить

cmd

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

B можно через FFT попробывать:

Сделаем 4 пары строк, вместо двух:

P[0] = в первой заменим все A на 1, а остальные на 0

P[1] = во второй все C на 1, остальные на 0

и т.д.

Затем посчитаем раздельно для каждой пары P массив Q[i][], где Q[i][j] равно степени похожести, если вторую строку приложить к первой в позиции j.

Затем посуммируем Q[0][j] + Q[1][j] + Q[2][j] + Q[3][j] и надо выбрать такое j, где эта сумма максимальна.

Считать Q[i] можно через произведение быстрое произведение многочленов с помощью FFT (нам нужно скалярные произведения строк для всех сдвигов второй строки).

Получиться O(N*log(N)).

Но надо как-то с TL бороться.

→ Ответить

e-maxx

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

Да, так и сдали, но и правда очень сурово TL выставлен. Хачить пришлось просто Максимально :)

→ Ответить

winger

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

Сколько раз у вас вызывался FFT?

→ Ответить

e-maxx

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

Итого - 12.

4 раза для каждой буквы умножить на 3 вызова для произведения умножения.

Если можно было уменьшить это, то интересно узнать, как :)

→ Ответить

winger

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

12->9 можно сделать за счет того что FFT линеен и сложить результаты можно до invFFT

→ Ответить

fetetriste

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

Ага, у нас тоже 9, но в даблах и std::complex. TL 30.
Вообще можно сделать за 5 fft, может кто-то знает, как?

→ Ответить

Zhukov_Dmitry

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

А ещё можно было делать FFT для N = 2¹⁸, а не для N = 2¹⁹.

Это ещё в 2 раза ускоряет.

Хотя, и так вроде без проблем проходило.

А ещё на этих Харьковских сборах эта задача уже как минимум на третьем контесте даётся в разных вариациях :)

Да и по монитору видно, кто сдавал её в первые полчаса контеста..

→ Ответить

winger

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

Изначально у нас был FFT по простому модулю. Если же делать его в комплексных числах, то можно замутить следующий трюк:
Возьмем p[i]=(a[i]=='a'?1:0)+I*(a[i]=='c'?1:0) и q[i]=(b[blen-i-1]=='c'?1:0)+I*(b[blen-i-1]=='a'?1:0). Тогда мнимая часть их свертки будет равна сумме совпадений по 'a' и 'c'.

Объединив эти два трюка, получим всего 5 вызовов FFT

→ Ответить

MBabin

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

B - отдельно для каждого символа сделать строку из 0 и 1 (1 если это этот символ и 0 иначе) потом расстояние между 01-строками для каждого сдвига второй строки можно считать через быстрое умножение многочленов (через FFT)

→ Ответить

frost_nova

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

а как преодолеть ТЛ?

→ Ответить

e-maxx

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

Нам пришлось писать FFT нерекурсивно и без доп. памяти, переписать на свой complex, вместо double использовать float, и максимально оптимизировать всякие мелочи.

→ Ответить

frost_nova

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

у нас работал 4.1 секи на флотах =(

→ Ответить

e-maxx

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

← Rev. 2 →

Последние, самые жесткие оптимайзы - это предпосчитать все bitreversы и cos/sin заранее, перед вызовом этих 12 FFT. Также обращаться не по a[i] / a[i+len], а хранить два указателя на элементы массива и двигать. Каждый из этих хаков давал немного, но в итоге мы довели до 2.65 сек на своей машине.

→ Ответить

pank.dm

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

ппц.
всегда "очень радуют" задачки, в которых необходимо использовать неассимптотические оптимизации.

→ Ответить

winger

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

Ее можно спокойно сдать без них

→ Ответить

pank.dm

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

А, ну тогда задача ок.
Не видел ваш пост про 9 fft, когда писал.

→ Ответить

Edvard

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

Макс как вам такое ваще в голову приходит? (я про указатели)

→ Ответить

e-maxx

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

Да это известный хак - а что ещё делать, когда другие способы ускорения кончаются :)

→ Ответить

Edvard

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

F надо было найти отдельно для каждой кучки функцию Гранди и поксорить всё если 0 то выиграл второй иначе первый. Сложность была в том как быстро считать функцию Гранди. В итоге после 40 минут просмотра этих чисел мы получили примерно следующее (точно не помню уже):

int calc(int n, int x, int y)

{

if (x > y)

return calc(n, x, y);

if (n >= x + y)

return calc(n % (x + y), x, y);

if ((n / x) & 1)

return 1;

if (n >= y)

return 2;

return 0;

}

по мойму это написали

→ Ответить

Ripatti

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

Прошу прощения за некропостинг...
Я только что затолкал B за квадрат без фурье на хаках с масками%)

→ Ответить

Urbanowicz

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

Мы тоже так пытались толкать на контесте, на пару секунд превышали. В чем у тебя фишка?

→ Ответить

Ripatti

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

Ну, общее решение какое - во первых, я все переделал в 32-битные маски для каждой буквы. Потом перебираем сдвиги и для каждого из них считаем маску сколько букв совпало, подсчитываем число бит и находим сдвиг, где это количество наибольшее.

Главное неудобство - посчитать быстро число единичных битов в 32х битной маске. Я использовал хак, описанный здесь:
http://graphics.stanford.edu/~seander/bithacks.html
(искать по строке "The best method for counting bits in a 32-bit integer v is the following").

Но это все давало где-то 8с на моей машине на макстесте.

Главная фишка была в уменьшении этих подсчетов - для каждого куска длины 32 мы находим маски совпадающих букв (4 штуки - отдельно по каждой букве), потом их ксорим (несложно доказать, что единички в этих масках не пересекаются), и только потом применяем bit count. Это уменьшило число подсчетов в 4 раза, время выполнения до 4,5с на моей машине и принесло ОК в дорешивании.

→ Ответить

it4.kp

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

А если предпосчитать ответ для всех масок из 16 бит, разве не быстрее будет?

→ Ответить

Ripatti

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

← Rev. 2 →

Пробовал и так. На моей машине это на 0.5-1.0 с медленнее работает. Видимо из-за лишних обращений к памяти.

UPD. Вот сейчас протестил:
4,7с - хак без прекалка
5,3с - 8-битные маски
5,5с - 16-битные маски

Хотя с 16-битными масками в дорешивание тоже прошло. У меня комп старенький уже.

→ Ответить

Urbanowicz

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

← Rev. 2 →

Этот "бест-метод" точно работает быстрее, чем 16-битный прекальк? Операций меньше, а таблица прекалька маленькая, в кеш влазит.

Не успел.

→ Ответить

SergeyLazarev

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

Как P решить? Пытался подобрать правильный ответ - не успел:)

→ Ответить

taras.klaskovsky

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

Перемножение всех простых чисел до пока влазят(чуть меньше 11 тысяч)+2

Мы сдали с 44 попытки :D

→ Ответить

SergeyLazarev

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

Да, видел, жесть:)

→ Ответить

ZumZoom

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

Просто человек, отпостивший выше, подбирал 11-й тест дихототомией... 43 попытки были потрачены ни на что, а потом внезапное озарение и полное переписывание дали +44...

→ Ответить

diogen

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

мы просто сгенерировали много (1200, 1000 не хватило) простых чисел, и взяли их произведение +2, это число и есть ответ на все тесты. это решение похоже на доказательство того факта, что простых чисел бесконечно много.

→ Ответить

ilyakor

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

Как решали A? Понятно, что можно было через диаграмму Вороного/триангуляцию Делоне, но в таком случае почти всех сдавших надо дисквалифицировать, т.к. prewritten code запрещён =) Ещё я слышал, что там очень слабые тесты и заходил квадрат, но не все же сдавшие догадались попробовать затолкнуть квадрат?

→ Ответить

winger

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

+10

kd-дерево очень быстро работает на таких задачах. Несмотря на то что в худшем случае будет O(n^2), тесты против такого решения очень сложно придумать.

→ Ответить

Edvard

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

А что такое kd-дерево?

→ Ответить

winger

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

http://en.wikipedia.org/wiki/Kd-tree
btw, в статье написано что Nearest-Neighbour ищется за O(sqrt(n)) для двухмерного пространства, а для случайных тестов и вовсе за O(log(n))

→ Ответить