Codeforces Round #101 (Div. 2) Разбор Задач.

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

141A - Веселая шутка

Для решения этой задачи достаточно посчитать для каждой буквы: a_c - количество вхождений буквы c в первые две строки инпута, b_c - количество вхождений буквы c в последнюю строку инпута. Ответ на задачу "YES", если для $\text{[math]}$ , иначе "NO".

141B - Классики

Переберем "уровень" 0 ≤ i ≤ 10⁶ , в который предположительно должен попасть камешек, попутно поддерживая наименьший номер квадратика на этом уровне. Далее понимаем, сколько на этом уровне квадратиков один или два. Далее одним или двумя (если на уровне два квадратика) ифами проверяем, попал или нет камешек в соответствующий квадратик, если попал выводим ответ. Если мы не нашли ни одного квадратика, в который попал камешек, выводим "-1".

141C - Очередь

Отсортируем пары (name_i, a_i) по возрастанию a_i. Если существует такой индекс 0 ≤ i < n, что a_i > i, тогда ответ "-1". Иначе ответ существует. Будем идти по массиву отсортированных пар слева направо, поддерживая вектор результата res. Пусть на текущей итерации h_i = n - i, тогда текущего человека нужно поставить в текущий вектор на позицию a_i. В C++ это можно сделать одной строчкой: res.insert(res.begin() + a[i], man);

141D - Трамплины

Сгенерируем взвешенный ориентированный граф всевозможных переходов. Вершины графа - это важные точки на прямой Ox, т.е. точки 0, L, x_i - p_i, x_i + d_i. Ребра графа - это возможные переходы, т.е. либо переход из точки x_i - p_i в точку x_i + d_i, либо переход из вершины в соседние вершины (соседние, в том смысле что мы берем следующую и предыдущую важные точки на прямой). Веса у таких ребер соответственно p_i + t_i и x_v + 1 - x_v, x_v - x_v - 1. В переходах нужно учесть, что нельзя забегать за старт, просто не добавляя такие переходы.

Далее на этом графе нужно найти и вывести кратчайший путь из вершины 0 в L. Это можно сделать, например, алгоритмом Дейкстры для разреженных графов.

141E - Большая чистка

Перефразируем условие задачи: нужно найти покрывающее дерево графа, такое что в нем ровно половина ребер помечено буквой S.

В таком дереве всегда будет n - 1 ребро, поэтому если n - четное, ответ "-1".

Давайте удалим из данного нам графа все S-ребра. Пусть теперь в нем будет cnt компонент. Чтобы сделать редуцированный граф вновь связным, нужно добавить минимум cnt - 1 S-ребер, поэтому если cnt - 1 > (n - 1) / 2, ответ "-1". Найдем cnt - 1 S-ребер, которые обязательно придется добавить в граф, чтобы он стал связным, если cnt - 1 < (n - 1) / 2, то будем пытаться добавить в это множество ребер другие S-ребра, так чтобы не получилось цикла по S-ребрам. Все это нужно делать по аналогии с алгоритмом Краскала нахождения минимального по весу остова. Если мы смогли получить множество S-ребер из (n - 1) / 2 элементов, такое что в него входят обязательные cnt - 1 ребер и нет циклов по ребрам, тогда ответ существует. Теперь нужно добавить в это множество (n - 1) / 2 M-ребер так, чтобы получилось покрывающее дерево. Это нужно сделать также по аналогии с алгоритмом Краскала.

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

Показать архивные | Написать комментарий?

oversolver

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

← Rev. 2 →

кстати, задача Е?

upd: нет, не она

→ Ответить

hydrastuff

Вопрос по задаче Е, в ответе же может быть больше n-1 ребра, если еще добавлять петли? Или я что-то не так понял?

Polichka

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

Нет, не может. Если есть петля, то существует 2 пути из вершины в себя:стоять на месте и идти по петле.

Идти по петле же не простой путь?

Gerald

Ну а должен быть ровно один путь, к тому же он должен быть простым. На это третий семпл.

Написано должен быть ровно один простой, и не важно сколько не простых.

← Rev. 3 →

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

afix

+11

А как же пути вида 1-2-1-2?

О да, пожалуй, это еще один путь. Ну все равно это не отменяет правильного понимания условия.

Я ошибся, везде в комментариях я имел ввиду конечно же третий семпл, а не второй.

Lepetrandr

Ну это хорошо, что фразу ровно один простой путь вы понимаете именно так. Но было бы неплохо удостовериться, что незнакомые с условием люди поймут ее так же (в чем я сомневаюсь лично). Я нашел как минимум два варианта как ее понять:
1) из всех путей (соединяющих две вершины) ровно один должен быть простым (а значит, мы можем использовать и петли)
2) должен существовать ровно один путь, и он должен быть простым (петли использовать не можем)
Если бы не третий семпл, без клара бы не обошлось однозначно.

Kostroma

а я, например, сразу понял условие как 1), и даже не думал о другом понимании. не имею привычки разбираться с семплом, если, как мне кажется, я понял условие

salikhov_ayaz

Разве путь из вершины в саму себя считается простым? Судя по условию нет, т.к. в нём есть две одинаковые вершины.

Смотрите семплы, они являются частью условия.

the_killah

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

ibra

ТАКУЮ ерунду я на С послал(АС кстати), что вообще...

Как я до такого простого решения не додумался! туплю..

pavel.savchenkov

А у меня решение в В, не проверяющее попадание на границу в половине случаев прошло претесты...
Сижу теперь, как дурак с А и С только...

BelovP

В чем заключается 19 тест к задаче В?

aropan

можно же смотреть какой тест:

Ввод
5 -4 2
Вывод

0
Ответ

-1

спасибо за оперативный разбор

задача Е хорошая, но, имхо, условие не было полноценно понятным

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

Hohol

Действительно, любопытно.

_dangerous_

← Rev. 4 →

Отсортируем пары (namei, ai) по возрастанию ai. Если существует такой индекс 0 ≤ i < n, что ai > i, тогда ответ "-1"

почему, если не выполнилось это условие, не найдется другого варианта построить ответ

Потому что если это выполняется, то для любого a[j] (j>i) это тоже выполняется(если числа в a[] различны), "сдвигать" массив a[] мы тоже не можешь, так как это не улучшит ситуацию.

А если после a[i] идут равные ему, то сдвиг a[i] ничего не изменит.

daftcoder

Пусть на текущей итерации h_i = n - i, тогда текущего человека нужно поставить в текущий вектор на позицию a_i.

Текущий вектор... Я один ничего не понял? Может кто-то чуть подробнее объяснить как это работает и почему это правильно?

noxwell

Заведем вектор q, куда будем складывать людей в порядке очереди. Т.к. высоты отсортированы по убыванию, то проходя по массиву, высота текущего элемента будет явно меньше предыдущих. Когда a_i=0, мы просто складываем элементы в вектор q в порядке убывания высоты (заметь, у них наибольшая высота из всех элементов). Из этого следует, что если положить в вектор q элемент на место a_i,то впереди у него гарантированно будет a_i элементов, больше него, что соответствует условию.

Кажется, я уловил идею. Спасибо!

По-моему проще для понимания так:

заметим, что можно обойтись числами [1..n] и каждое мы возьмём 1 раз
заведём структуру данных, из которой можно извлечь k-е по убыванию число с удалением его (можно и массив пометок просто) и запихаем в эту структуру все числа от 1 до n
отсортируем пары по неубыванию a[i]
идём от от n до 1 циклом и h[i] присваиваем a[i]+1 по убыванию число из тех, что ещё не было

double

Гениально! Решение задачи B в четыре строчки 1023920

А ведь задача B не только как в разборе перебором решалось, можно было найти решение за константное время =)

sdryapko

Не за линейное, а за константу

Да, именно это и имелось ввиду =)

А ведь задача B не только как в разборе перебором решалось, можно было найти решение за O(1) =)

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

Та же история, только моя ошибка всплыла на систестах.

DamianS

It would be nice to see a proof why does such an algorithm work for problem E.

niyaznigmatul

It's easy to prove as well.

If this algorithm outputs -1 then there are three ways:

1) odd number of edges in the tree, that works correct

2) ( $\text{[math]}$ ) then there doesn't exist $\text{[math]}$ edges of first color that doesn't make a cycle

3) You can't connect the graph with second type of edges, then you can't connect it at all, so it's correct

So if output is -1, then answer doesn't exist.

Why if output is not -1, then answer exists and correct?

So you get cnt components, then you add cnt - 1 edges of second type, then you just add remaining second type edges (all counted as $\text{[math]}$ ), that all second type edges doesn't make a cycle.

But you say there are the cycles that contains, two types of edges, when cycle appears you just remove one first type edge from the cycle. So the graph that you built is correct and it contains everything asked in the problem statement.

This is not complete, there is also another situation when you output -1. Let's say: we added all M-edges and got a spanning tree (none of your 1), 2), 3) conditions applies), but there is still a possibility for the answer to be -1.

Ah.. Yes

I have to change 3)

You can't connect graph with second type of edges or you can't get $\text{[math]}$ second type of edges that doesn't make a cycle.

Then it's -1 and it's correct.

Ok, but it is not clear if the algorithm checks this condiction correctly. I mean it chooses some S-edges which make the M-forest into a spanning tree and then until there are less then (n-1)/2 s-edges it adds new s-edges in such a way that no s-cycle appears. But why the success of such a procedure doesn't depend on the chosen (at the beginning) s-edges? Etc., etc. It's not as obvious as you say.

OK, what you say it's mistake when answer exists, but algorithm doesn't find it. And it's 3). (it outputs -1)

Firstly, if you can't connect the components, but the answer exists.

So if you add all the s-edges, then the components will stay the same, so if you can't connect the graph, then you can't connect it at all.

Secondly, if you have $\text{[math]}$ m-edges, that doesn't make a cycle, you certainly will find and add them, because you firstly connect components, it doesn't matter what edges to connect with, since it's matroid (there will always exist and edge, that doesn't make a cycle, if there's larger set of edges, that doesn't make a cycle)

so you just add the edges one by one until there are $\text{[math]}$ m-edges. so you get m-edges set and s-edges set, you can remove some edges from s-edges set to get the tree.

Ok, now it looks much better. The keyword here is "matroid". Thank you.

azicon

Подскажете, можно ли узнать 19 тест по задаче В? Могу ли я выставить свое решение в комментариях, чтобы пользователи нашли ошибку?

maslowmw

Посмотри свою посылку

http://codeforces.com/contest/141/submission/1021215

А вообще тест такой 5 -4 2

iama

Тесты уже открыты.

looool

can someone explain solution for problem C ?

sorry, but it is very unclear from the tutorial

OK, lets do it in English.

Make vector q, where we will place people in right order, that will be an answer. Sort input people by decreasing of a, give them height from n to 0, place them in array m and go from begining of this array to the end. When m[i].a=0, just place them in vector q by decreasing of h. Notice, that they are the highest people. It means, that if we place some element in vector q on place ai, before him will be ai people, higher than he, that meets the problem.

AlexanderBolshakov

Я в С написал такую логически корректную ересь: сортируем пары по возрастанию a_i, заполняем массив ответов единицами и для каждого a_i выполняем следующее: в промежутке [0..i) увеличиваем на 1 все ответы, отличные от единицы, а также крайние правые a_i - a_i - 1 единиц. Если a_i - a_i - 1 = 0, то ничего не увеличиваем :). Вот код, логика в нем соответствует описанию, но реализована несколько иначе.

BaJIuK

Спасибо за разбор! правда D, E слишком долго кодить! Идеи крутые :)

mmhatred

Решается ли задача D жадным алгоритмом?
Я отсортировал все трамплины по увеличению x+d, затем пока позиция < L проверял, как добраться до точки x_i + d_i быстрее - используя трамплин или без него. Из-за неправильного условия решение не прошло 7 претест. Прошло бы оно системное тестирование?

goo.gl_SsAhv

"Мсье знает толк в извращениях" (с) - это о моем решении задачи D

Ну почему я не догадался построить граф? А вместо этого выдумал какую-то дикую фигню с эмуляцией движения слева направо и с помощью дерева отрезков справа налево. Я раз 5 переписывал решение, причем восстановление пути появилось только в третей версии, когда я наконец нашел ответ :) Прежде чем писать, надо хорошо подумать, это сэкономит время, а не потратит. В B тупой баг - забыл унарный минус. Хорошо хоть раунд для меня нерейтинговый.

constkir

В задаче E Большая чистка у меня прошло решение с наихудшей сложностью n^3. Я начал его писать около часа ночи, когда был искренне убежден, что 10^3=100 ;) Дописал только утром, и оно прошло. Мое решение должно было умереть на случае, когда все домики соединены длрожками и Дед Мороз хочет их чистить один.

А как решалась бы С, если надо было бы найти решение с минимальное суммой h[i]?

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

superstar

There are n - 1 edges in this tree, because of it if n is even then the answer is "-1".
That would normally be correct, but here we can have roads that start and end at the same hut, so we can add such a road without changing the connectivity, can't we?
2 2
1 2 S
1 1 M
For this case, isn't the solution to clear both roads?

flashmt

~~"between any two huts should exist exactly one simple path along the cleared roads". That case results in 2 paths from 1 to 2. Hence, we can't clear roads which connect the same hut.~~

UPD: I misunderstood it. Your opinion seems correct based on the problem statement.

ItsLastDay

I think, there is a path 1-1 which is not simple, therefore answer is -1.

There are always paths that are not simple: 1-2-1. Edges are bidirectional

The problem statement states that there is exactly 1 simple path. 1-2-1 is not simple so we don't need to count it.

Ye, that was my point. 1-2-1 and 1-1 are not simple paths so they do _not_ invalidate the conditions.

Either the author of the problem meant to say something else or the official solution is just wrong. I am betting on the second possibility.

When I read that you can have a road starting and ending at the same hut, I was sure that this was added just to make it a little more tricky. Otherwise, what's the point?

gzz

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

I think the roads which begin and end in the same hut are useful to adjust one nearly right answer to a right one.

for example, if I got S=10 M=9, and one road 2->2 is M, I can choose this road so that S=M=10.

between any two huts should exist exactly one simple path along the cleared roads

and the rule above is satisfied, too. because 2->2 is never used, for when it's used nd 2 appeared twice. so whether to choose 2->2 is not important.

To conclude, the solution for problem E is wrong || the problem statement needs change.

Fox235

все задачи понял, кроме 3. поясните ~~дураку~~, что и как... не врубаюсь

заметим, что можно обойтись числами [1..n] и каждое мы возьмём 1 раз

заведём структуру данных, из которой можно извлечь k-е по убыванию число с удалением его (можно и массив пометок просто) и запихаем в эту структуру все числа от 1 до n

отсортируем пары по неубыванию a[i]

идём от от n до 1 циклом и h[i] присваиваем (a[i]+1) по убыванию число из тех, что ещё не использовано как h[i]

Код

Например a[] = 0 0 1 1 2:

1 2 3 4 5
_ _ _ _ 3
3 - (a[5]+1 == 3-е) число из имеющихся
1 2 3 4 5
_ _ _ 4 3
4 - 2-е из оставшихся
1 2 3 4 5
_ _ 2 4 3
1 ~~2 3 4~~ 5
_ 5 2 4 3
1 ~~2 3 4 5~~
1 5 2 4 3

На С можно было спокойно поставить ограничение 10⁵ - вот решение за nlogn.

UPD. Ошибочка: решение работает за nlogn, я не учел сложность сортировки.

nk.karpov

Можно, но зачем?

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

savinov

Подскажите пожалуйста, какая итоговая сложность получилась в E, просто я решил совсем по-другому и у меня N^2 + M, и работает оно быстрее всех уже сданных

В решении Е из разбора итоговая сложность как у алгоритма Крускала, т.е. O(m * log(m)), что вполне может работать медленнее Вашего решения.

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