Задача A
Так как на первом месте должен стоять солдат с максимальным ростом, то логично поставить на первое место самого левого солдата с максимальным ростом, чтобы минимизировать время (число обменов). Исходя из таких же соображений на последнее место поставим самого правого солдата с минимальным ростом. Таким образом количество обменов это номер самого левого солдата с максимальным ростом - 1 + n - номер самого правого солдата с минимальным ростом. И если самый левый солдат с максимальным ростом стоит правее самого правого с минимальным ростом, то из этой суммы нужно вычесть один.
Задача B
Переберем все точки, в которых сидят генералы, и посчитаем количество не покрываемых никакой окружностью. Пусть xa < xb и ya < yb, если это не так, то просто поменяем xa и xb, ya и yb местами. Тогда генералы сидят в точках: (xa, y), (xb, y), (x, ya), (x, yb), где xa ≤ x ≤ xb и ya ≤ y ≤ yb. При подсчете ответа нужно аккуратно посчитать генералов, которые сидят в точках (xa, ya), (xa, yb), (xb, ya), (xb, yb), чтобы не учесть их дважды.
Задача C
Посчитаем количество каждой из букв во второй строке и сохраним это, например, в массив a[1..26]. Для первой строки для префикса длины, равной длине второй строке, (это первая подстрока) посчитаем в массив b[1..26] количество каждой из букв. Знаки вопроса в массиве b не будем учитывать. Если для всех i выполняется b[i] ≤ a[i], то значит это хорошая подстрока. Далее перейдем ко второй подстроке: вычтем из массива b первый символ: b[s[1] - 'a' + 1] – и прибавим n + 1 символ, если n --- длина строки p: b[s[n + 1] - 'a' + 1] + + . Если какой-либо из этих символов вопрос, то для него прибавление или вычитание делать не нужно. Далее повторяем выше рассмотренную проверку и переходим к следующей подстроке. Повторяем эти действия, пока не переберем все подстроки строки s длины n.
Задача D
d[i] --- минимальные расстояния от вершины s до вершины i, посчитанные с помощью алгоритма Дейкстры.
Далее переберем все ребра графа, и для каждого из них посчитаем количество точек, не совпадающих с вершинами, лежащих на них, находящихся на расстоянии l от вершины s (причем l - минимальное расстояние от этих точек).
Рассмотрим ребро (u, v):
если d[u] < l и l - d[u] < w(u, v) и w(u, v) - (l - d[u]) + d[v] > l, то прибавим к ответу точку, лежащую на этом ребре на расстоянии l - d[u] от вершины u;
если d[v] < l и l - d[v] < w(u, v) и w(u, v) - (l - d[v]) + d[u] > l, то прибавим к ответу точку, лежащую на этом ребре на расстоянии l - d[v] от вершины v;
если d[v] < l и d[u] < l и d[u] + d[v] + w(u, v) = 2 * l, то прибавим к ответу точку, лежащую на этом ребере на расстоянии l - d[u] от вершины u и l - d[v] от вершины v.
Также если d[i] = l, то прибавим к ответу вершины.
Задача E
Рассмотрим каждого спортсмена в отдельности. Очевидно, что мы можем по координатам спортсмена понять: какие клетки на побочной диагонали являются ближайшими к нему, они образуют "отрезок" на побочной диагонали. Выпишем для каждого спортсмена эти отрезки.
Выберем спортсменов так, чтобы каждому из них мы могли сопоставить ровно одну клетку на побочной диагонали из его "отрезка", и каждой клетке на побочной диагонали соответствовал не более, чем один спортсмен. Понятно, что спортсмены смогут дойти до "своих" клеток, не побывав с кем-либо на одной клетке. Осталось максимизировать количество выбранных спортсменов. Таким образом переформулированная задача решиется жадно.
Чтобы в D не рассматривать случаи, можно было на каждом ребре (u,v) добавить вершину между u и v на расстоянии l - d[u] и l - d[v] (пара проверок, чтобы новые вершины не совпали и существовали) и запустить Дейкстру ещё раз.
>> ... посчитанные с помощью алгоритма Дийкстры.
Поправьте, пожалуйста.
Never mind.
After sorting the left endpoints of the segments, you loop through them, and use a priority queue (heap data structure) to repeatedly select the next non-intersecting segment with the leftmost possible right endpoint.
By the way, the editorial's question marks are not displaying properly.
UPD. Большой вопрос под спойлером. Уже решён.
Ой.... блиииин! Вот из-за тупого косяка задача провалена :(
Спасибо!
UPD. Удалил лишь условие в третьем if`е (d[t1[i]]==d[t2[i]]) и AC... Эх :(
Ну на самом деле это практически очевидно.
А Е решалась так: сортируем полученные интервалы, затем пробегаем по точкам от 1 до n и для каждой точки берём по одному отрезку, если таковые есть под данной точкой - стандартная задача, похожа на вот эту http://e-maxx.ru/algo/covering_segments . А я вообще делал эту задачу иначе :) Закинул n точек в set, отсортировал точки по рядам затем по столбцам и для каждого интервала (l,r) находил максимальную точку из оставшихся, которая лежит в этом интервале (методом lower_bound), и удалял её.
UPD. Под спойлером доказательство на пальцах. Лучше читайте ниже..
во-первых заметим, что спортсмены, которые стоят на разных диагоналях (параллельных побочной) никогда не окажутся в одной клетке, т.к. если идти по кратчайшему пути, то каждый раз спортсмен должен переходить на более близкую к последней диагональ.
Теперь рассмотрим спортсменов и их пункты назначения на некоторой диагонали. Понятно, что и спортсмены и их пункты назначения будут идти в одинаковом порядке на диагоналях, иначе они обязательно пересекутся. Теперь каждый спортсмен идет до нужного столбца влево, потом вверх. Очевидно, что если они будут двигаться таким образом, то пути не пересекутся
Может кто-нить заметит в чем проблема?
В дейкстре косяк где-то: http://codeforces.me/contest/144/submission/1083533
Thanks a lot.
Very sad that its impossible to get Accepted on problem B with Ruby.
http://codeforces.me/contest/144/submission/1078267
Интересно, он все-таки валится или нет?
В разборе задачи D прибавляем к ответу точку по 3 условиям
d[u] < l и l - d[u] < w(u, v) и w(u, v) - (l - d[u]) + d[v] > l. Но зачет 3 -е условие, что оно дает?
Предположим d[i]=7, d[j]=3 a[i,j]=9 l=10. Почему я не могу из i отложить 3 и добавить его в ответ???
Третьим условием мы проверяем корректность точки отстающей от u на расстояние l - d[u].
l - d[u] - расстояние от точки до u;
w(u, v) - (l - d[u]) - расстояние от этой точки до v;
w(u, v) - (l - d[u]) + d[v] - расстояние, если идти в искомую точку из s в v и по ребру (u,v);
w(u, v) - (l - d[u]) + d[v] <= L - это значит, что проходя через v мы можем прийти в точку по более короткому пути и она нам не подходит!
Can somebody help me with this (code) problem (C) ?Are you talking about the cases that only have one line?
I think maybe because the string in the first line is so long that the system can only show a small prefix of it. then the whole input file remained is ignored.
eg.
xxxxxxxxxxxxxxxxxx
yyyyyyyyyyyyyyyyyy
zzzzzzzzzzzzzzzzzz
aaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbb
will looks like
xxxxxxx...
In Codeforces, large test case displays first 256 characters only, after which they show ellipsis (...)
Thank you,after 5 years SyFy can at last live happily.
Hello, I wrote the solution of this problem in java but it is giving me wrong answer on test 4 on codeforces, even though its output is correct, if anybody figured out what is the bug please share his/her foundings, thank you. ~~~~~~~~~~~~~~~~~~~~~~ import java.util.*;
public class Arrival_of_the_General144A {
i really stucked, thank you for this :)