codeforces задача короткий код

Codeforces задача короткий код

Эта задача решается за один проход по всем группам. Решение можно представить следующим кодом:

Эта задача решается жадно. Будем стараться максимальные цифры ставить как можно раньше. Алгоритм можно описать так:

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

Чтобы быстро выполнять проверку, нужно было для всех диагоналей, строк и столбцов сохранить массив частичных сумм. И далее, проверять запросом на сумму, лежит ли в данном отрезке на соответствующей линии хотя бы одна черная точка.

Полезные соображения, помогающие значительно сократить реализацию описанного выше:

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

Вертикальные раскраски выглядят следующим образом:

acbcbd.
bdadac.
acbcbd.
bdadac.
acbcbd.
bdadac.
.

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

Горизонтальные раскраски выглядят аналогично, только повернуты на 90 градусов. Конечно, бывают раскраски, которые одновременно и горизонтальные и вертикальные, но для решения задачи, это не имеет никакого значения.

Давайте научимся проверять, существует или нет, корректная вертикальная раскраска, удовлетворяющая шаблону заданному во входных данных. Это достаточно просто. Достаточно просто перебрать, какие цвета и на каких вертикалях находятся. А затем проверить, что такую раскраску действительно можно составить.

Аналогично нужно проверить для горизонтальных раскрасок.

Источник

Codeforces задача короткий код

Спешу познакомить вас с авторскими идеями решений задач сегодняшнего раунда. Авторы разбора первых пяти задач — HolkinPV и gridnevvvit, разбор последних двух задач написан мной.

В этой задаче нужно было рассмотреть несколько случаев и выбрать лучших ответ. Это можно было сделать так:

Эта задача решается жадным образом. Отсортируем все экзамены по неубыванию даты фактической сдачи (то есть по a i ), при равенстве по неубыванию даты досрочной сдачи (то есть b i ). Рассмотрим экзамены в получившемся порядке и будем поддерживать текущий ответ. В первую очередь будем стараться сдать очередной экзамен досрочно (если это не нарушит условие задачи, то есть если никакой предыщий экзамен мы не сдавали позже досрочной даты этого экзамена). В противном случае сдадим этот экзамен в дату его фактической сдачи. Обновим текущим ответ выбранной датой сдачи этого экзамена.

Сделаем два наблюдения.

Во-первых, посмотрим на посылки как на отрезки [$in_i, out_i$]. Верно следующее утверждение: если коробка i оказалась в какой-то момент времени сверху коробки j (не обязательно непосредственно сверху), то .

Во-вторых, представим, что на платформе находятся какие-то посылки. Оказывается, что все, что нам нужно знать про этот набор посылок, чтобы понимать, можем ли мы положить что-то сверху, это “остаточная прочность” всех этих посылок. Остаточная прочность определяется так: для каждой посылки из набора остаточная прочность равна прочности этой посылки за вычетом суммарного веса всех стоящих на ней. Для набора посылок остаточная прочность считается как минимум из остаточных прочностей посылок в наборе. Таким образом, новую посылку можно положить, если ее вес не превосходит остаточной прочности уже имеющихся коробок.

Будем называть приезды машин на парковку событиями.

Авторское решение использует принцип разделяй и властвуй. Давайте напишем рекурсивную функцию, которая принимает подтаблицу, границами которой являются r 1, r 2, c 1, c 2 ( r 1 ≤ r 2, c 1 ≤ c 2 ), а также список всех событий парковки, которые происходят в этой подтаблице. Задача функции — рассмотреть то, как меняются максимальные пустые квадраты в этой таблице по прошествии этих событий, и попытаться обновить ответы для некоторых событий.

Осталось только научиться искать максимальный квадрат в двух гистограммах. Это можно сделать с помощью метода двух указателей. Поставим первый указатель в начало. Будем двигать второй указатель до тех пор, пока в гистограммах есть такой квадрат: квадрат со стороной k имеется, если (минимум на отрезке в первой гистограмме) + (минимум на отрезке во второй гистограмме) — 1 >= k. После того, как это свойство нарушилось, двигаем первый указатель. Для того, чтобы находить минимум за O(1), авторское решение для каждой гистограммы заводит очередь с поддержкой минимума за O(1). Таким образом, поиск максимального квадрата осуществляется за линейное время.

Источник

Codeforces задача короткий код

В этой задаче нужно было догадаться, что существует только 3 корректные тройки:

В задаче нужно было аккуратно выписать формулу. Оптимальное решение укладывает шарики по два в ряд, пока это возможно. А потом сверху кладет еще один шарик, если это возможно. Основная хитрость и сложность была именно в последнем шаге.

В этой задаче можно было как считать количество хороших расстановок, так и из общего числа вычесть плохие расстановки. В любом из решений нужно было уметь считать динамику по маскам, состояние (j, mask) — j — номер текущего полностью заполненного столбца, mask — маска того, что находится в последнем столбце (также этот прием называет динамикой по профилю). Это по сути известная задача о паркете (замощения поля доминошками). Как решать классическую задачу о паркете, можно узнать на известном сайте e-maxx.ru.

Чтобы получить само решение задачи я поступал так. Пробовал к клетке с кружочком приписывать с четырех сторох доминошку, после этого все три клетки закрашивал в черный цвет и считал общее количество способов. Однако, чтобы не учитывать один ответ несколько раз, нужно использовать формулу включения исключения для этих четырех направлений. Это также известный прием, который позволяет правильно считать ответ для многих задач и не учитывать один ответ несколько раз.

Задачу можно было решать несколькими методами. Самый простой из них — корневая оптимизация. Разобьем запросы на sqrt(m) блоков. Каждый блок будем обрабатывать отдельно. Перед тем как обработать блок одним обходом в ширину посчитаем кратчайшие расстояния от красных вершин до всех остальных. Далее, чтобы выполнить запрос на вывод ответа из текущего блока нужно взять значение полученное обходом в ширину и обновить его расстояниями до красных вершин из текущего блока, которые покрасились до текущего запроса.

Расстояния между вершинами dist(u, v) на дереве можно было считать, используя предпосчет для lca.

Источник

Codeforces задача короткий код

In problem D, can anyone explain how to decide the number of times to perform iterations.?

Help needed in task B Can someone please tell,why m would be arbitarily large if we have no positive difference.

But according to the editorial if a = <9,7,5,3>m should be arbitrarily large as all the negative differences are same and no positive difference exists.but why?. I haven’t understood this part.Can you please help me?

For problem C, I think Testcase 2 is wrong. For the following problem: n = 2, m = 7 2 1 2 1 2 1 2 1 2 1 2 1 This is case 33 in 2nd testcase and according to my algorithm the answer is NO which is clearly correct but judge prints Wrong_Answer.

For problem C, I think Testcase 2 is wrong. For the following problem: n = 2, m = 7 2 1 2 1 2 1 2 1 2 1 2 1 This is case 33 in 2nd testcase and according to my algorithm the answer is NO which is clearly correct but judge prints Wrong_Answer.

Not author solutions, but fun solution D, E:

Solution E: Let’s look at the element with the minimum height in the array, and look at the 2 segments into which it divides the array. Note that we must take the beauty of this element in the answer, and that the two segments into which the array is divided are independent, so we can solve the answer for them independently. The only difference from the original problem is that we can remove the array suffix / prefix for free.

can you please explain what you mean by doing dijkstra?

Thanks, nice explanation.

In problem D editorial, It is easy to find it using the bad pairs set. How exactly?

Simple circular linked list solution for Div2 D can be optimised to O(N).

AT the time of deletion just manage deletion in a circular linked list plain algorithm one use of set can also be transformed to queue with just a few changes.

All the elements should be less than m, because a(I) = ( a(i-1) + c) %m and a(1) = s % m You can check the solution (m, c) before printing (3+1)%5!= 7 #wa

only the first element should be less than m ig.

Problem G very nice and interesting! Below is my explanation of the editorial.

The first part of solution is trivial. Let’s discuss the second part. The first solution in my mind is binary search, but it costs too much queries.

The editorial uses a different idea, which is similar to a famous problem: «egg dropping problem». The idea is:

Thanks a lot for the great explanation!

Here is my code for question-C, i don’t know what’s wrong here, like my code is not passing pretest-2(giving correct answer for first few testcases,wrong for some and then again correct for rest). But when i tried running those testcases individually, all of them are giving correct answers. idk howz that even possible since i’ve not used any global variable. Can someone help me with this please?

has a bug. If ans == false but x > 0, then you break the loop, and skipped some test data, so when you read next text case, you may read wrong data which belongs to previous test case.

how will that give an incorrect answer? since while taking all m arrays input, previous gets cleared.

I updated the comment, your code skipped some test data. If you skipped some test data, when you are solving next test case, you may read wrong data(it’s belong to previous test case).

okay,i got you!! thank you so much for helping.

I used a dynamic programming approach for 2C, I have neatly commented so that you can understand my approach, I still, however, am getting a run time error on tc 3, if you could help me figure it out it would be of great help.

my submission p.s. i know I’m going to get downvoted but I really need to get this itch itched thanks 🙂

Thanks for the clear editorial(but a little slower), the contest is really good in general, I really enjoy it!:-)

Hope there will be more nice contests like this one on Codeforces.

Like the title says I used a dynamic programming approach for 2C basic diplomacy, I have neatly commented so that you can understand my approach, I still, however, am getting a run time error on tc 3, if you could help me figure it out it would be of great help.

my submission p.s. i know I’m going to get downvoted but I really need to get this itch itched thanks 🙂

My solution in E( almost the same as the author’s)

Final asymptotics O (nlogn) My code for more information: 110848133

Heh, I feel like problem E from ARC 115 (contest that took place

2 hours before this one) is very similar to problem E here.

Can someone plz tell the 29th query of 2nd Test of Problem B

Thank you for sharing this approach.

I just found the aspect of «reversing Floyd-Warshall» too intriguing not to share it. Also, the code is quite short.

That’s a funny paper XD. I like this idea a lot, and so I tried to understand why it worked. Turns out my proof is a bit unlike Floyd Warshall.

Источник

Codeforces задача короткий код

Hello, Codeforces!

Welcome to the ICPC Communication Routing Challenge powered by Huawei!

This challenge edition is very special, as it will be happening in conjunction with the ICPC World Finals! For those who are not participating in the finals — ICPC and Codeforces are offering a unique chance to compete during a 4-day Challenge Marathon and win amazing prizes from Huawei!

ICPC Challenge Marathon (open to public, unrated): October 9-13, 2021, 00:00 UTC:

This time we’re delighted to provide you with a future-oriented topic – routing algorithms for next-generation communication. During this Challenge we will provide you with a super-large inter-satellite optical network to properly plan message paths, to reduce communication latency and improve resource utilization. However, finding the optimal path in a network with limited resources is an NP-hard problem. Considering the physical constraints of optics and circuits, our algorithm faces greater technical challenges:

We hope that these satellite communications challenge questions can help you understand the problems that Huawei’s software algorithm researchers face every day. All the best.

Prizes

For 3-hours onsite ICPC World Finals Challenge Huawei will provide prizes to the winners in 2 groups of participants:

Group 1: TOP 30 ICPC World Finalists, who participate individually:

Group 2: TOP 9 ICPC World Finals Coaches and Co-Coaches, who participate individually:

For 4 days online Challenge Marathon, Huawei will provide prizes to TOP 30 individual participants:

* The 1st place winner will get additional bonus in amount of 5000 USD. If the bonus cannot be transferred to the winner due to any reason, it may be replaced by a prize of the same value.

If the allocated Huawei Challenge prize cannot be delivered to your region for any reason it may be replaced by another prize of the same value (if no legal restrictions), at the discretion of the sponsor.

By participating in this Challenge, you agree to the Challenge Rules and Conditions of Participation

Источник