OpenCup Stage 6 - Grand Prix of Azov Sea

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

← Rev. 2 →

Если |x1-x2| = |y1-y2|, то эта позиция проигрышная для первого иначе для второго. Т.е. чтобы победить надо после своего хода образовывать квадрат, это можно сделать двумя способами, но оптимальных из них будет один (оставляю как можно меньше пространства второму игроку), т.е. стратегия для победителя однозначная. Стратегия для проигравшего -- как можно больше оставить простор для себя, то есть по возможности приближаться, если нет, то отдаляться. Если приблизиться на несколько клеток, то и простор будет быстро кончаться, поэтому все ходы приближения/отдаления будут на соседние клетки. А там уже считается.

→ Ответить

Seyaua

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

← Rev. 2 →

Совсем не так решали эту задачу. Решим сначала такую задачу: кто выигрывает и за сколько ходов, если у нас есть доска n*m и ладьи стоят в противоположных углах. Это мы решали динамикой d[i][j]. Тогда пересчет не очень сложный - ведь из состояния d[i][j] можно попасть в состояния d[2][j], d[3][j], ..., d[i-1][j], и d[i][2], d[i][3], ..., d[i][j-1]. Тогда сразу можем определить кто выигрывает для такой доски. А если мы хотим найти число ходов, то тогда надо заметить следующий факт. Что если у нас есть доска N*M и наши ладьи находятся в углах какой-то ее поддоски n*m, то ответом будем число d[n][m]+x. Где x - это удвоенное манхэттенское расстояние от ладьи проигрывающего игрока до угла доски N*M (такой угол ровно один). После этого легко пересчитывать динамику и легко решить исходную задачу - ведь выигрывающий игрок зависит от числа d[n][m], а количество ходов находим по приведенной формуле. Все это иллюстрирует следующая картинка:

На картинке стрелочками изображено расстояние, которое нужно удвоить и добавить к ответу. Красный кружочек - это ладья человека. В данном случае это расстояние отмеченное стрелочками равно 3 и тогда x=6. Стрелки направлены именно в таком направлении, так как для такой игры человек проигрывает - это следует из того, что d[4][4]=8. Итого d[4][4]=8, поэтому общий ответ - это 8+2*3=14.

→ Ответить

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

Почему совсем не так? Просто вы считали динамикой то, что можно было вычислить за О(1).

→ Ответить

Seyaua

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

Ну возможно похоже, но в процессе решения даже не возникло мыслей насчет того, что выигрышность позиции зависит от истинности выражения |x1-x2| = |y1-y2|. Поэтому мне показалось, что это совсем разные идеи :)

→ Ответить

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

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

→ Ответить

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

спасибо, пофиксил

→ Ответить

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

А мне интересно, как в H ловить разницу между "три точки на одной прямой" и "три точки почти на одной прямой", если там координаты до миллиарда. Мы, сравнивая углы, умножали расстояние по одной координате на полное расстояние - думаю, если вместо этого делить, всё равно ничего не получится. 18 знаков double держит плохо. Попытался написать "#define double long double" - никаких изменений почему-то.

→ Ответить

Gerald

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

Можно было написать в целых числах.

→ Ответить

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

-22

С квадратами расстояний? И длинную арифметику ещё типа?

→ Ответить

cerealguy

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

+16

Векторным произведением

→ Ответить

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

-9

ВНЕЗАПНО. Никогда так не делал. Мда, век живи - век учись...

→ Ответить

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

Не знаю, с этим проблем не было, но почему не хватает:

(x2-x1)*(y3-y1)==(x3-x1)*(y2-y1) т.е. максимальное значение 4*10^18?

→ Ответить

Commandos

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

Именно, аккурат в long long влезает, я правда только на дорешивании сдал :(

→ Ответить

winger

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

Там все влезает в long'и

→ Ответить

Jokser

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

Интересно решение задачи K.
И как можно было быстро решить А? Я решал так: 2-мя бинпоисками находил отрезок минимальной высоты и длины, в который влезает и a и b. Далее сокращал высоту, переходом a в ярус, в котором сидит b. И снова находил границы, и так пока a и b не станут равны.

→ Ответить

Commandos

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

← Rev. 4 →

Задача А - переводим оба числа в их двоичное представление (предварительно отняв по единице). Дальше бежим со старших разрядов, если цифры в числах не совпадают - меняем все цифры на противоположные в любом из двоичных представлений. Количество таких изменений есть ответ.

→ Ответить

Jokser

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

Спасибо. Я понял самый первый вариант, так что мог не исправлять :) Я тоже рассматривал решения с переводом в двоичную систему, но до такого что-то не допер.

→ Ответить

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

← Rev. 3 →

Только поясню почему именно так: если представить наши числа как бинарные строки (спускаясь от корня к переулку, если влево то 0, иначе 1), то операция зеркального отражения будет эквивалента инвертированию любого суффикса в строке...

→ Ответить

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

← Rev. 2 →

Главное наблюдение в задаче K следующее.

Пусть у нас есть 2n команд с рейтингами L₁, L₂, ..., L_2n, причём L₁< L₂< ...< L_2n(никаких регионов пока нет!). Тогда разбиение этих команд на пары будет оптимальным, если каждая команда среди первых n попадает в пару с одной из последних n команд. Общее число таких разбиений, следовательно, равно n!

Таким образом, легко понять, во-первых, существует ли разбиения с учётом географической специфики, во-вторых, существует ли разбиение с номером K. Само же разбинение, если оно существует, получить уже просто.

→ Ответить

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

Ты не учитываешь "...каждая пара разбиения должна состоять из команд одного региона...", т.е. порядковый номер числа в исходном массиве выбранного из первых n чисел должен иметь такую же четность как порядковый номер числа выбранного из последних n чисел. В связи с этим общее количество вариантов будет не n!, а (n/2)!^2.

→ Ответить

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

← Rev. 2 →

Я говорил об основном наблюдении, в упрощённой формулировке. Формулировку уточнил, спасибо.

Если n - это то самое n, которое в условии задачи, то количество оптимальных пар с учётом региона равно или (n / 4)!^2, или нулю.

→ Ответить

_jte_

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

← Rev. 3 →

все еще очень упрощается тем, что все номера будут различны попарно.

→ Ответить

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

Нельзя разбить на две группы по четности (по крайней мере я себе это не представляю), потому как порядок следование чисел в нашем конечном списке заранее не определен.

→ Ответить

Di735

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

← Rev. 2 →

Можно по-подробнее, почему разбиение будет оптимальным, только если пары будут образованы м/у элементами правой части массива и левой(по n шт)

а именно при исходном массиве 1 2 2 2 2 2 2 3

чем не оптимально разбиение 7 4 5 2 3 8 1 6 // спасибо )

→ Ответить

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

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

→ Ответить

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

← Rev. 2 →

Поробую объяснить.

Давай определим сначала ~~значение нашего~~ максимальноего значение. Понятно что это делается жадно беря самое минимальное и самое максимальное число в пару. Т.е. если я отсортирую свой список, то пару будут (1,N), (2,N-1) ... (N/2, N/2+1). Как видим изначально для каждого из первой половины сопоставлено число из второй.

Теперь давай рассмотрим две пары (a,b) (c,d). Понятно что c < b, так как если это не выполняется, то я могу улучшить ответ сделав пары (a, c) (b,d) /* ответ в данном случае улучшиться на 2*(L[c] - L[b]) */ (тоже самое можно сказать про a < d). Такую пару пар я могу превратить в другую пару не потеряв в сумме ничего. (a,b) (c,d) и (a,d) (c,b) эквивалентны, то есть в общую сумму добавляют одинаково. Таким образом между любыми двумя парами я могу обменивать второй элемент, т.е. для каждой из первой половины выбрать любого из второй.

→ Ответить

pank.dm

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

А правда ли, что J решалась потоком?
И если да, к какому потоку сводилась задача?

→ Ответить

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

← Rev. 2 →

Она решалась максимальный поток минимальной стоимости.

~~Чуть позже здесь будет краткий разбор.~~

→ Ответить

Seryi

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

+10

Я разберу :-)

1. Проведём дуги из истока к помещениям (cap = ti, cost = 0).

2. Проведём дуги из помещений в вершины-ограничители (cap = wi, cost = 0).

3. Проведём дуги из помещений и вершин ограничителей в вершины-минуты (cap = 1, cost = число_людей_в_эту_минуту_в_этом_помещении). Само собой, что дуги из помещения проводятся в минуты только если нет ограничений в эту минуту, иначе - проводятся из ограничений.

4. Проведём дуги из минут к стоку (cap = 1, cost = 0).

Поток не может быть больше чем 500 (рабочий день уборщика). Поэтому итоговая ассимптотика - O(500 * E log V) - если посчитаешь максимальное число вершин и рёбер, в ограничения попадает легко.

Остаётся только узнать, получился ли поток максимальным и аккуратно восстановить решение.

→ Ответить

safeasmilk

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

Если несложно, можно для тех, кто в танке: что такое OpenCup, кто (и как) его проводит и где читать правила? ~~Забанили в гугле.~~

→ Ответить

taras.klaskovsky

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

ВНЕЗАПНО opencup.ru :)

Или что-то оттуда неясно?)

→ Ответить

safeasmilk

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

Собственно, неясно, кто проводит. Логотип Яндекса в углу что-то символизирует? :)

И какова роль координатора региона (кроме раздачи паролей): подразумевается очное написание контестов?

→ Ответить

freopen

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

Внезапно пункт 5.1 и 5.1.1.

→ Ответить

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

← Rev. 3 →

-8

Отвечу тогда про "кто проводит". Каждый этап в основном проводится на задачах какого-то локального онсайт-контеста, то есть проводят совместно авторы задач и собственно Snark, также известный под именем Олег Богданович Христенко, из МГУ (вот не знаю, кстати, а есть ли у него с этим сайтом вообще хоть кто-нибудь в помощниках?). Логотип "Яндекса" же символизирует, что сия компания время от времени спонсирует серии маленьких личных контестов, проводящихся на том же сайте, и по их результатам раздаёт каких-то фирменных ~~слонов~~ слоников.

→ Ответить

Gassa

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

Логотип Яндекса на Опенкапе потому, что Яндекс — спонсор Опенкапа. В правилах можно прочесть также, что 1-10 места приглашаются на очный раунд, а там бывают ценные призы победителям.

→ Ответить

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

← Rev. 2 →

Кто как решал задачу F?

Я решал довольно таки неоптимальным способом, удаляя вершины в графе. И потом выводил количество оставшихся ребер.

Как можно было лучше решить?

→ Ответить

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

← Rev. 2 →

Видимо, это любимая классическая задача новичков :) Всё та же конденсация по сильно связным компонентам.

P.S. Так и что, с Вашим удалением вершин прошло всё ж таки?

→ Ответить

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

Да, проходит, но много кода. Я смотрю, народ за 10 минут делал))

→ Ответить

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

← Rev. 2 →

Много? Ну, в моей реализации 65 строк, считая закомментированный дебажный вывод, - это намного меньше? Всё-таки крайне интересно, а как это Вы так хитро удаляли вершины? У меня почему-то было предубеждение, что такого рода решение неизбежно квадратично.

→ Ответить

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

Не могу так сразу сказать алгоритмическую сложность...

Вот код, можете посмотреть http://pastie.org/1723488

→ Ответить

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

Ничего не понял, но на первый взгляд квадрат на логарифм. Видимо, на самом деле что-то как-то клёво амортизируется.

→ Ответить

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

Ну суть в том, что исходный граф постепенно сворачивается в граф из сильных компонент связности.

Потом выводится количество ребер в графе из сильных компонент связности.

А можете показать как выглядит код короткого решения?

→ Ответить

http://pastie.org/1723667

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

Вот. Спасибо, кстати, классный сайт, не знал о нём раньше. И даже регистрации не требуется!

→ Ответить

yarrr

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

Наше:

→ Ответить

yarrr

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

Количество рёбер между разными сильными компонентами связанности.

→ Ответить

Anton_Lunyov

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

← Rev. 2 →

Не знаю номер задачи. Писали контест в Таганроге.
Задача про братьев и землянику.
Зашло у кого-нибудь решение за O(N*M*N*M) на опенкапе?
У меня на онсайте где-то в 1,6-2 раза не укладывалось по времени.
Глупо, конечно, было думать в таком направлении.
Мне как сказали, что там сложность O(N*M*log K), я сразу-же придумал.
Но все-таки если у кого-то зашло, то обидно.
Я уже мог где-то в 3:20 - 3:30 отсабмитить и в самом этапе опенкапа мы заняли бы 3-е или 4-е место, а так только 7-е.

P.S. Я бы и сам проверил именно свое решение, но дорешивание лежит. :)

UPD. Уже заработало. Отправил. Не прошло. Так что никаких шансов на место повыше не было. :)
Но вопрос все равно актуален. Было бы интересно, если кто-нибудь таки запихал такое решение.

→ Ответить