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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Задача A

Так как на первом месте должен стоять солдат с максимальным ростом, то логично поставить на первое место самого левого солдата с максимальным ростом, чтобы минимизировать время (число обменов). Исходя из таких же соображений на последнее место поставим самого правого солдата с минимальным ростом. Таким образом количество обменов это номер самого левого солдата с максимальным ростом - 1 + n - номер самого правого солдата с минимальным ростом. И если самый левый солдат с максимальным ростом стоит правее самого правого с минимальным ростом, то из этой суммы нужно вычесть один.

Задача B

Переберем все точки, в которых сидят генералы, и посчитаем количество не покрываемых никакой окружностью. Пусть x_a < x_b и y_a < y_b, если это не так, то просто поменяем x_a и x_b, y_a и y_b местами. Тогда генералы сидят в точках: (x_a, y), (x_b, y), (x, y_a), (x, y_b), где x_a ≤ x ≤ x_b и y_a ≤ y ≤ y_b. При подсчете ответа нужно аккуратно посчитать генералов, которые сидят в точках (x_a, y_a), (x_a, y_b), (x_b, y_a), (x_b, y_b), чтобы не учесть их дважды.

Задача 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

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

Выберем спортсменов так, чтобы каждому из них мы могли сопоставить ровно одну клетку на побочной диагонали из его "отрезка", и каждой клетке на побочной диагонали соответствовал не более, чем один спортсмен. Понятно, что спортсмены смогут дойти до "своих" клеток, не побывав с кем-либо на одной клетке. Осталось максимизировать количество выбранных спортсменов. Таким образом переформулированная задача решиется жадно.

import java.util.*; import java.lang.*; import java.io.*; public class CodeForces { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] heights = new int[n]; for (int i=0; i<n; i++) { heights[i] = sc.nextInt(); } int maxE = Integer.MIN_VALUE, minE = Integer.MAX_VALUE; int minP = -1, maxP = -1; for (int i=0; i<n; i++) { if (maxE<=heights[i]) { maxE = heights[i]; maxP = i; } if (heights[i]<=minE) { minE = heights[i]; minP = i; } } // int result = 0; // if (maxP > minP) { // result = maxP + (n - 1 - minP) - 1; // } else { // result = maxP + (n - 1 - minP); // } int result=maxP-1+(n-minP)-(maxP>minP?1:0); System.out.println(result); // Close the scanner sc.close(); } }

import java.util.*; import java.lang.*; import java.io.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] heights = new int[n]; for (int i=0; i<n; i++) { heights[i] = sc.nextInt(); } int maxE = Integer.MIN_VALUE, minE = Integer.MAX_VALUE; int minP = -1, maxP = -1; for (int i=0; i<n; i++) { if (maxE<heights[i]) { maxE = heights[i]; maxP = i; } if (heights[i]<=minE) { minE = heights[i]; minP = i; } } // int result = 0; // if (maxP > minP) { // result = maxP + (n - 1 - minP) - 1; // } else { // result = maxP + (n - 1 - minP); // } int result=maxP-1+(n-minP)-(maxP>minP?1:0); System.out.println(result); // Close the scanner sc.close(); } }

#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; int a[n]; int maxIndex = 0; int minIndex = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; if (a[i] > a[maxIndex]) maxIndex = i; if (a[i] <= a[minIndex]) minIndex = i; } cout << maxIndex - 1 + (n - minIndex) - (maxIndex > minIndex ? 1 : 0); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }

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

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

pavel.savchenkov

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

← Rev. 3 →

Чтобы в D не рассматривать случаи, можно было на каждом ребре (u,v) добавить вершину между u и v на расстоянии l - d[u] и l - d[v] (пара проверок, чтобы новые вершины не совпали и существовали) и запустить Дейкстру ещё раз.

→ Ответить

Kh.Madi

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

+23

Легче пару проверок сделать и не запускать Дейкстру =)

iama

>> ... посчитанные с помощью алгоритма Дийкстры.

Поправьте, пожалуйста.

Melamori

← Rev. 2 →

Never mind.

Hohol

Что поправить?

shevchen

http://www.forvo.com/word/dijkstra/

Уже поправлено.

Petar

Thank you for the contest and fast published tutorial :-)

zzzzxk89

Actually I'm confused by how to greedy in Pro E... I have worked out the convertion, but didn't know how to solve the "segment" problem. THX

random.johnnyh

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.

Got it，THX very much

AndreySiunov

UPD. Большой вопрос под спойлером. Уже решён.

Так точка не обязательно на середину должна попадать, если она одна. Пример: до одного конца ребра расстояние 1, до другого 3, длина ребра 4.

Ой.... блиииин! Вот из-за тупого косяка задача провалена :(

Спасибо!

UPD. Удалил лишь условие в третьем if`е (d[t1[i]]==d[t2[i]]) и AC... Эх :(

Rubanenko

" Понятно, что спортсмены смогут дойти до "своих" клеток, не побывав с кем-либо на одной клетке. " - достаточно неформальное доказательство, не так ли?:)

И как именно "жадно" решалась Е?

+12

Ну на самом деле это практически очевидно.

А Е решалась так: сортируем полученные интервалы, затем пробегаем по точкам от 1 до n и для каждой точки берём по одному отрезку, если таковые есть под данной точкой - стандартная задача, похожа на вот эту http://e-maxx.ru/algo/covering_segments . А я вообще делал эту задачу иначе :) Закинул n точек в set, отсортировал точки по рядам затем по столбцам и для каждого интервала (l,r) находил максимальную точку из оставшихся, которая лежит в этом интервале (методом lower_bound), и удалял её.

pva701

но допустим жадность придумать несложно, но вот как доказать (более четко), что пути спортсменов не пересекуться

UPD. Под спойлером доказательство на пальцах. Лучше читайте ниже..

forest

+15

1. Спортсмены стартующие с разных диагоналей не пересекаются - очевидно.

2. Рассмотрим всех спортсменов на какой-то фиксированой диагонали в порядке возрастания y ( x убывают в этом случае), отсортируем конечные точки на побочной диагонали в том же порядке возрастания y и сопоставим спортсменам - очевидно при таком разбиении пути не пересекутся, если спортсмены сначала будут ходить только по вертикали, а потом только по горизонтали

NuM

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

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

wistful23

Никак не могу найти ошибку в своем решении на задачу D 1083266 (
Может кто-нить заметит в чем проблема?

yarrr

В дейкстре косяк где-то: http://codeforces.net/contest/144/submission/1083533

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

UPD: Ну да, точно нельзя: http://codeforces.net/contest/144/submission/1083539

_{Спасибо! Да, явная ошибка. Самое забавное, что я когда-то сдавал такую реализацию (85837), поэтому особо не искал ошибку в дейкстре.}

shadowac

I still don't know about the solution to the Pro-E "segment" problem.Could you explain it more clearly?
Thanks a lot.

SyFy

Very sad that its impossible to get Accepted on problem B with Ruby.

Here is my code, may be some optimizations?

kolya37

Seems like you are iterating the whole grid... of course it'll get TLE.

Try to iterate only cells of the frame of the rectangle.

rminuv372

How to prove the correctness of problem A.

I simulate 2 times.

The solution is a greedy approach which is proved by contradiction. Consider the best case and assume it's not the one that your algorithm produces and then come up with a contradiction to prove its correctness.

mage

У одного человека из моей комнаты увидел алгоритм Дийкстры с queue вместо priority_queue http://codeforces.net/contest/144/submission/1079923

Дийкстру так можно писать?

Furko

Если я не ошибаюсь, то это уже ширина:)

Ширина для графа, где ребра имеют вес?

JKeeJ1e30

Поиск в ширину с апдейтами

Fefer_Ivan

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

Kostroma

это и есть, примерно, алгоритм Левита?

Да.

Нет! Ширину намного легче заламать чем алгоритм Левита.

dalex

Алгоритм Левита - это чит над вышеописанным методом, который кладет вершину не в конец очереди, а в начало, если ее до этого обрабатывали.
http://codeforces.net/contest/144/submission/1078267
Интересно, он все-таки валится или нет?

это намного его ускоряет?

Я не знаю. Я ему не доверяю и пишу Дейкстру

Вообще-то, да. Но всё равно есть тесты которые ламают это.

Можно, только работать будет за O(VE).

Хм, в этой задаче V до 10^5, а Е до V^2 . И 60-й тест там с V = 10^5, E = 10^5.

Значит, в тестах очень мало случаев, когда одна и та же вершина обновляется много раз.

Есть соблазн попробовать написать генератор, чтобы заваливать такие решения :)

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

PavelKunyavskiy

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

Dima_qwer

В разборе задачи 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 и добавить его в ответ???

← Rev. 5 →

Третьим условием мы проверяем корректность точки отстающей от 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) ?~~

Something strange starts from test #13 (look at input params).

From problem statement:

The first line is non-empty string s, consisting of no more than 10⁵ lowercase Latin letters and characters "?". The second line is non-empty string p, consisting of no more than 10⁵ lowercase Latin letters.

PS.

Got Accepted, but the question remains.

gzz

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

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...

zodiacleo

In Codeforces, large test case displays first 256 characters only, after which they show ellipsis (...)

I_Love_Tina

Thank you,after 5 years SyFy can at last live happily.

yimao

Hello! I want to know why the Pro-D could use Dijkstra to solve? That the complexity of Dijkstra is O(v^2), isn't it ? And this time , |V| <= 10^5.

thanks, Happy new year ~!~

ant.ermilov

We can improve complexity to O(V × logE) using data structures to extract minimum in O(logn), for example, prority queue based on either binary heap or sorted set.

bucephalus370

12 месяцев назад, # |

PROBLEM A I don't understand, what my mistake is, i'm getting wrong Answer on test case 4, everytime! I implemented everything according to the Tutorial only.

Can Any1 help me?

stillc

12 месяцев назад, # ^ |

Well, good job! you almost got it. Now, what did you miss? as we iterate through the array we need to get the first occurance of the max height and the last occurance of the min height. This is to decrease the time required to place the soldiers in their respective positions. Here's the accepted code:

Thank You! That was impressive! I really did forget about that case!

user71661773

11 месяцев назад, # |

Hi, I just started j hope this isn’t a stupid question but any idea my code doesn’t work?

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