Hi Rebecca :)

Скорее всего да. Хотя нужно было авторам , написать про это и другое;)

Такой же комментарий чуть ниже, но на английском, получил +2=)

Двойные стандарты.

Да, 500-1000-1500-2000-2500!

we'll have standard points distribution in both divisions.

I thought about same thing but got lots of negative votes. Does it mean people pronounce it another way?

I wish you not to change opinion after round :)

The third is the charm, right =)

That peter50216 solved all the problems gains me some belief about a rated round :)

I Like PvP!!!

first from the end or from the beginning?

at least 1 problem

Видимо, Вы, так как оригинальное название другое :)

Боюсь представить, что бы про тебя сказал Фрейд =)

мне тоже так показалось.

Ну заметим, что еси уж мы цифру перекладываем, то так, как нам нужно.

Посмотрим, сколько можно не перекладывать: это кол-во чисел от начала a, которые содержаться в правильно порядке(возможно с чем-то между) в b

Можно убрать в какой машине едешь. Если прекомпьютишь кратчайшие пути на любой одной машине, то это измерение не нужно. Получается N^4.

В я урезал степень на единицу, чтоб было все же не 800 миллионов операций, а в 60 раз меньше. 800 миллионов у меня без считывания и вывода в запуске корячились полторы секунды.

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

60^5 (правда еще с логом каким-то) я выломал.

===Она решалась четырехмерной динамикой? d[s][t][k][m]

Мне кажеться трехмерной. F[s][t][k]

нам не важно с какой машины стартовать. Мы делаем предпосчет MinD[i][j] какой машиной оптимально ехать из i в j.

F[s][t][k] = Min( Min( MinD[s][i] + F[i][t][k-1] ) , — едем с пересадкой в городе i F[s][t][k-1] та же задача но с к-1 пересадкой }

По поводу А — у меня такое же решение зашло, проверь, может где в реализации косяк?

I don't know yet if this solution is correct. Binary search by q. Lets Check if we can get to t from s using q steps: Starting bfs, from all marked verticies,storing DSU, go to the no more than q step from each. If we get to vertex, where we was, check, if dist[current]+dist[vertex where we was]+1<=q, than join their sets in DSU. Finally, if set[s]==set[t], than we can use current q.
P.P.S. Correct, simple bug..

4 3 2 1 4 1 2 3 4 Вроде как

It seems that you are only counting the ones with equal diagonals. Those with unequal diagonals are also possible.

(x,y) (x+1,y) (x-1,y) (x,y+2) is not a rhombus: 3 vertex on one line.

Вот, это тоже самое (вроде)

Как ты сдал это решение, не понимая его? :)

It reopens every contest by someone

Let's open! I've created array of 100010 elements instead of 200010 (thx Edvard (**fixed**) for hack =) )

Let me in: I tried to hack really wrong solution A div 2, but failed to find 3 numbers a,b,n: n-a % b != 0, n-b % a != 0, n % (a+b) == 0.

Me too, too! Since I'm naive, I believed k ≤ 1000 is important, and iterated 1000 times instead of 60 in B. Never again will doubt myself on these things. >_<

I made a tiny silly mistake in problem D (div2), but it was accepted the pretest. In stead of f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[1][k][v]), it was f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[i — 1][k][v])... It was too late when I realised the mistake 5 minutes after the contest finished. It was failed the system test.

I tried to hack this code 2 times during contest but it passed somehow! (Div2 A)

http://codeforces.net/contest/189/submission/1673396

It ran for 18sec in my PC to produce output of this case: 4000 2 2 2

Да, в общем так и надо было.

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

First, precalc time(i,j) = min time for moving from i to j without changing car. Second, use dynamic: time2(i,j,k) = min time for moving from i to j with changing car <= k times. Base: time2(i,j,0) = time(i,j). Step: time2(i,j,k+1) = min(time2(i, j, k), min_l(time2(i,l,k) + time2(l, k, 0)) (not sure, that first argument in external min is necessary). When you go from i to j, you change car last time in city l, and move from i to l with changing car <= k times, and from l to k without changing car.

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

Самое интересное — я не сдал С, а меня просят кинуть код на нее.

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

I used binary search.

смотри выше

Number of fixed points = max {i| b[:i] is subsequence of a}

for the every element a[i] in first array:

Consider all numbers that are to the left in first array... = set A
Consider all numbers that are to the right in second array...= set B (after a[i])

if(A ^ B != {empty}) this is bad for our element (i.e a[i])

That yields that starting from a[i] to the a[n] all elements must be affected, giving us the answer n-i

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

Не один. АС 0.86 секунды.

Не один. 390мс.

Нет. У меня, в теории n^2 log^2 n, но AC за 1750мс.

Мне перестала нравиться эта задача...

У меня вроде такое же решение.

Идея -- бинпоиск по ответу, а в проверке Форд-Беллман с очередью (как предлагает Burunduk1 здесь)

Я хотел написать такое решение, но почему-то был на 100% уверен, что оно получит TL и не стал его писать.

I think your Floyd algo is wrong

replace

                    timer[i][j][k] = min(timer[i][j][k], timer[i][j][f] + timer[i][f][k]);      

to

                    timer[i][k][f] = min(timer[i][k][f], timer[i][k][j] + timer[i][j][f]);      

My code was wrong on test 11 because of this line: f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[i — 1][k][v]... I resubmitted the code after replacing it by f[i][u][v] = min(f[i][u][v], f[i — 1][u][k] + f[1][k][v] and got accepted.

все вопросы к Burunduk1, его цитата)

Yeah! I spent some 20 minutes during the contest trying to analyze the time complexity, but didn't get anywhere :(

Any help on how to do it?..

нееееееееееееееееееееееееееееееет..........

[спойлер]

I think it's slow because intended solution is O(n^4), while yours is O(k*n^3).

Your solution runs in about 1000*60*60*60 operations. But "correct" solution should do about 60*60*60*60 operations. So it will be really hard not to get TL even if you use int. But if you use long long you will obviously get TL.

Thanks for replies. Somehow I didn't realize that computing Ks >n is pointless.

pfff... Левит? обычный поиск в ширину:)

А какое там честное? Мне вот witua объяснил довольно простое решение, которое точно (n+m)*log(n), а не как у Левита, черт знает что:) :) Сначала посчитаем BFS расстояния от каждой вершины до ближайшего гида (это можно сделать в одном обходе графа), потом будем бинарить по ответу, а в бинарке проверять достижимость обычным DFS. Вся идея в том, что если мы идем по путях между вершинами длиной не более k, то это аналогично тому, что мы идем по вершинах, которые не дальше чем за k/2 от ближайшего гида (только еще надо поставить гида в конечную вершину).

По С я во время контеста думал, что доказал, что мы из каждой вершины релаксацию не более 2 раз будем делать, а вот сейчас понял, что ошибся в доказательстве. Мне кажется, там оценка получается похожая на

Unable to parse markup [type=CF_TEX]