Только что завершилась олимпиада. Предлагаю здесь обсуждать задачи. Интересуют решения задач G,J,H,E. Тыкни здесь!
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 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
Время на сервере: 25.11.2024 21:29:59 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
В E(Футбольные поля) достаточно проверить, чтобы площади и множества длин ребер совпадали.
ооп. А если множество одно, а последовательности длин разные?
Считаем длины сторон первого многоугольника, сортируем их. Тоже самое делаем и для второго. Если массивы сортированных длин совпадают и площади одинаковые, то многоугольники совпадают.
3 0 5 1 8 4 7 5 0 6 3 2 1
Вроде бы тут YES.
Сдвинул второй треугольник на вектор (-2,-1), получилась одна точка в (0,0). Потом отразил относительно y=x, затем относительно y=-x. Еще сделал параллельный перенос. Треугольники совпали.
Возможно, но все равно построить многоугольники такие можно наверное.
У нас зашла даже без проверки площади. Считаем длины ребер у одного, потом у другого. Если одну можно получить из другой циклическим сдвигом, то ответ YES, иначе NO. Тоже хотел бы узнать как делать G.
Получается, если во входном файле вам дан квадрат и ромб с такой же стороной, не являющийся квадратом, у вас выведет YES?
Видимо, да. А можете предложить тест такой, просто если они не совпадают, значит у одной фигуры (у ромба, если конкретнее) будет какой-то угол не 90гр. И тут уже вопрос стоит в том, можно ли подобрать такой тест, чтобы координаты при этом были целочисленные.
Да, я вот тоже составил подобный тест только что(: Абсолютно с вами согласен. Если честно, то мы и сами были удивлены, когда она зашла. У нас была написана только часть задачи про ребра, но времени оставалось мало и мы решили хоть что-нибудь заслать.
Я почти уверен, что существует какой-нибудь контрпример и к решению с проверкой равенства площади. Весьма странно, что организаторы не предугадали подобные эвристические решения
UPD. Ну вот, ниже уже привели контрпример
да организаторы нирк уже задолбали делать слабые тесты, в который раз уже после контеста валятся решения, прошедшие тесты. я слышал байку, что в предыдущем году на вкошпе тоже были слабые тесты
На прошлом ВКОШПе в задаче А проходило неправильное решение, но в Барнауле против таких тесты подобрали.
Это очень вряд ли. Тесты на всех площадках идентичны.
Тогда в архиве на сайте не все тесты, потому что тест, который валит неправильное решение имеет больший номер, чем количество тестов в архиве. И о том, что проходило неправильное решение уже писалось ранее.
А кто-нибудь может это доказать (хотя бы нестрого)? Мы делали весьма хардкорно: перебирали перестановку из отражений, применяли их к многоугольнику и находили вектор, который соединяет центры масс, проверяли, что он подходит. Это еще и в лонг даблах не заходит, только целочисленно.
Можно было получать вектор по левым нижним точкам. Тогда вещественная арифметика совсем не нужна.
Можно тупо перебрать все сочетания видоизменений и смотреть, равный получился или нет, причем с разными обходами.
Мы также делали, там всего 8 случаев видоизменений, довольно компактно получается.
пффф, тест:
4
0 4
4 7
7 3
3 0
8 1
13 1
13 6
8 6
ответ НО (если я не ошибся), насколько я понимаю, ваше решение выдаст YES? мне кажется, или он валит всякие площади, длины сторон, углы и периметры
H. У меня так какой-то баг, но она зашла после грязного хака. А так решение, вроде, правильное: Посчитаем бфсом уровень темноты в каждой клетке. Сделаем бинпоиск по ответу, т.е. по наибольшей темноте. Для фиксированной наибольшей темноты рассмотрим все клетки в которых темнота больше этого значения. Рассмотрим их диагональный boundig-box, если он покрывается ромбиком радиуса равного наибольшей темноте, то надо понижать уровень, иначе — повышать. Потому переберем центр ромбика и проверим.
Одно из авторских решений — такое как у вас, другое за O(площадь прямоугольника). Оно основано на том, что "диагональный bounding-box" можно за быстро пересчитывать при добавлении некоторых клеток, которые нужно осветить, а также уменьшения допустимого ответа (можно пересчитывать за O(кол-во добавленных клеток)). А если начнем перебирать ответ с суммы длин сторон, и будем отнимать по единице каждый раз (до того момента, пока существуют клетка такая, что поставив в нее лампочку, осветим необходимые клетки), то всего будет обработано O(площадь) клеток.
А что за "грязный хак"?
У меня получался в бинпоиске какой-то ответ (радиус этого ромба). Я пытался его получить, перебирая центр ромба. На четвертом тесте я не выводил ничего, то есть, не находил нужный центр. Я решил увеличивать ответ на 1, пока что-то не найду. Зашло.
На самом деле это вполне обоснованный хак... Если я правильно понимаю, то хватило бы увеличить ответ на 1 один раз — тогда точно найдется такая клетка. Просто в поиске bounding-box'a может получиться (если искать его вводя ограничения на сумму и разность координат), что вроде бы на нем клетка должна быть, но ее там нет из-за разной четности суммы и разности, например. Ну и очевидно, что если увеличить ответ на один, то такая клетка точно найдется.
ааа. Да, понял, точно.
Пожалуйста, залейте в тренировки, хотелось бы написать в виртуале. Желательно и базовую и усложненную.
G. Ленивая динамика [t2][t3][mask], где t2 — количество слоев из двух блоков, из которых можно удалить один блок, t3 — количество полностью заполненных слоев, mask — маска последнего слоя. Мы можем вытащить блок из t2 слоя, либо t3 слоя, либо последнего и поставить на последний слой, либо создать новый слой.
наше решение Е (казалось бы верное), на мой взгляд не особо сложное: заметим, что такими операциями можно получить многоугольник повернутый на 0, 90, 180 или 270 градусов относительно своего начального положения, который, возможно, будет отражен. сначала зададим стороны многоугольников набором векторов, затем, оринетируем оба многоугольника в одном направлении (можно, например, против часовой стрелки), переберем угол поворота второго многоугольника и проверим, что второй многоугольник (или его отражение) является циклическим сдвигом первого. циклический сдвиг можно проверить префикс функцией.
Как-то сложновато. Верно, но сложновато. Можно просто перебрать все повороты второго многоугольника (их 8). Теперь для первого и рассматриваемого найти минимальные вершины (самые нижние левые), а дальше просто пройтись двумя форами, проверяя на соответствие координаты вершин, по часовой и против часовой стрелки. Хотя, может, профессионалу мой способ покажется менее рациональным и удобным, не знаю, не знаю :) UPD. Тьфу, выше уже было такое решение. Ну да ладно)
Я эту задачу вообще случайно сдал: решаю по монитору, вижу, что все Ф сдают, читаю (потом оказалось, что это Е) понимаю, что может все не так уж и просто, но раз люди за 5-10 минут сдают, значит эвристики с площадью, периметром, углами должны работать. Пишу, сдаю, потом несколько секунд удивляюсь, что задачу Ф я так и не сдал, но зато получил первый успешный сабмит по Е :)
Скачав архив тестов, обнаружил что в задаче G были тесты где N = 1000, в то время как по условию N не превосходит 700. На моем решении не сильно отразилось, но неприятно узнавать вот такие сюрпризы. Если бы сразу не забил бы массив с запасом, очень долго бы искал почему RE/WA.
збс
Ты не прав.
Надо создавать массивы длины N.
кто-нибудь из авторов контеста или таргетов может сказать, как решать J?
Разбить треугольное поле на n диагоналек.
Посчитать динамику dp[i][j] — количество способов покрыть поле, таких что мы уже покрыли последние i диагоналей (три на предыдущей картинке), причем мы уже пробовали ставить на первые j побочных диагоналей. N^2 состояний, каждое считается за O(N) (надо перебрать сколько мы покрыли до этого). Можно заметить, что нам нужно сумму по всем переходам посчитать, это можно с помощью частичных сумм на одной из диагоналей или ее же считать прямо при итерации по второй размерности динамики. Итого получится O(N^2)
А как задачу B решать?
Подвесим дерево за какую-нибудь вершину. Посчитаем динамику: downSq[v] сумма квадратов путей до всех вершин вниз, чтобы ее пересчитывать понадобится down[v] сумма путей до всех вершин вниз. Тогда просто
где w(vc) — вес ребра, count(c) — количество вершин в поддереве c
Формула может быть немного неправильная, если что исправьте, главная идея, что если к элементу прибавить d, то квадрат изменится на 2 * d * val + d ^ 2.
Потом пройти вторым поиском в глубину и пересчитать те же самые динамики наверх. И сложить.
В Codeforces::Тренировки были добавлены:
Как А и Д решаются?
D. Сортировка, но чуть-чуть необычная. Рассмотрим две произвольные строки s1 и s2. a1=s1+s2, a2=s2+s1. Если a1<a2, то строка s1 будет раньше чем строка s2, иначе позже.
A. f[i][j][k] = можно ли дойти до клетки (i,j) и не показаться на всех снимках с 1 по k. Если можно, то храним откуда пришли. Ну а потом восстановление ответа.
Спасибо! Сейчас решаю виртуал, сдам в дорешке.
Кто нибудь решал задачу ф с базовой? Засылаю на сервер, RE5, но локально проходит все тесты. Да, наверняка мой косяк, потому что проблемы подобные возникают у многих и они находят баг, но я уже бессилен. Если кто-то сдаст ее именно на сервере кф, напишите пожалуйста, буде еще раз смотреть код тогда. Спасибо. UPD Всё, спасибо, сдал, используя dsu.