http://e-maxx.ru/algo/strong_connected_components

Задаёшь сильносвязанный компонент состоящий из одной точки — начало, потом делаешь DFS и каждый раз, когда натыкаешься на точку в компоненте — добавляешь в компонент весь путь. Если после этого процесса остались точки — повторяешь для второго компонента.

Но я провалил один из тестов, так что где-то логика (или реализация) подкачала.

You just have to sum L — c + 1 to ans on each iteration that finds a value greater than t. The pseudocode:

answer := 0
L := 0
for v in values do
  if v > t do:
    if L >= c do:
      answer := answer + L - c + 1
    end
    L := 0
  else do:
    L := L + 1
  end
end

// Test for last L
if L >= c do:
  answer := answer + L - c + 1
end

By the way, I don't get what you mean by "without any tricks".

А разве нельзя на первом прогоне просто поотрезать куски слева и справа по (m) (сколько влезает в машину), пока не останется мало заключенных в центре, и уже центр прошерстить поосновательней? За крайними всё равно ездить и если убирать по m с каждой стороны, то общая дистация всегда будет расстояние между крайними умножить на два.

I did that solution, but it failed — probably some corner case. I'll investigate today. I think you should cut m items from each head and tail until you have just a few criminals left.

There is also an elegant solution by Vladyslav that I could not understand. Any idea on how this works ?

My solution for E: If we simplify the problem for m = 1, then (one) best location is the [n/2]-th criminal's position (if n is even there are multiple best locations). If we move it by one point further from any direction, we would be farther from n/2 + n%2 criminals and closer to n/2 criminals..

Does something change when m is higher? Not at all.. We want to collect the furthest criminals together (so the total distance we travel is smallest), so we just look at the positions 0, m, 2*m and n-1, n-1-m, n-1-2*m (until these two sequences cross each other) and so on and we solve the problem for these positions and m = 1.., so the solution is still the same..

when we know the position of the police station it is easy to calculate the result. Even easier is to notice, that there is equal amount of points when we turn the car and start returning on the left and right from the police station and noticing that right — middle + middle — left == right — left, so we can calculate right — left for the interesting points (sequences 0, m, 2*m, ... for left and n-1, n-1-m, n-1-2*m, ... for right) until they meet..

i think that the hint stated in this short editorial is actually for a harder version of this problem which does not occur on a straight line but on a tree, there we have to calculate "how many nodes am i getting closer to" and "how many am i getting farther from " by traversing this path for each path (using two DFS for example), calculating total distance from every node to root of the tree and then traverse through each path and re-calculate the total distance from it by looking at the pre-calculated information. On a straight-line we know how many nodes we are getting closer and farther from so we can minimize it (by placing the optimal position to the middle straight forward)

My solution works with ternarySearch , in fact when you fix a point for example if x = -10^9 the answer is very huge , if x = 10^9 then the answer is very huge , then we can see a function that decrease first then increase.

You can see Yeputon's picture.

Tutorial for ternarySearch

My solution

In the contest my solution fails in test 10 because i have overflow in my variables lo , hi. I fix it and i got accepted.

По-моему там целый диапазон, где можно ставить.

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

Дополнение — тест слишком длинный, не помещается в экране "Посылка"

It looks like you use hashing modulo 2⁶⁴. That isn't reliable: Anti-hashtest

Fist you have to learn Strongly Connected Components SCC

Wiki

There have two famous algorithm that solve :

-Kosaraju Algorithm

-Tarjan Algorithm

MySolution (I used Tarjan)

Knowing SCC then the solution is pretty easy , for every SCC choose the nodes with the min cost.

I used the same algo and it passed with good timing

this is my code: 6533487

I solved using Kosaraju's Algorithm for SCC. Here is my solution — https://mirror.codeforces.com/contest/427/submission/85106512

suffix automaton

easy

Thank you a lot for great clue. I think this was the only solution which worked for Python. I am still wrapping my head around the whole thing. It is not "easy" :) I finished course on Automata at Coursera website and I had previous exposure to Knuth–Morris–Pratt algorithm, so I think I was ready for the idea, but it is still difficult.

This is solution in Python: 6546632

Now I want to rewrite the whole thing as reasonably convenient class and add it to my toolbox. Thank you a lot!

Can you explain how to solve this problem with suffix automaton?

Probably because Scanner is slow. You can see this for more information: http://acm.timus.ru/help.aspx?topic=java&locale=en

It's my first time here. I am used to topcoders.com where the programming language doesn't really matter. Numbers are chosen in a way that the only thing that counts is whether you got the right algorithm or not. I wish that codeforces.com will use the same strategy. It's pretty sad as you mentioned to see solutions refused because they require a split second more.

I had exactly the same problem.

The way test 112 is different from any other is that m = 1, so basically you "cut" away prisoners by 1. My program had two indices, i and j going from different directions and meeting in the middle.

Test 112 was the only case where left index overrun right index — after main cycle left index ended up being larger then right index. I didn't check for that and in final "adjustment" was just adding final distance between i and j. When i overrun j I ended up actually subtracting last distance from solution.

Again — this happened only in case 112. If you algorithm is different, then my hint is still — think where it can breakdown if m = 1.

Ну вот и прошла z-функция, правда с костылем.

Thank you very much, your answer really helped me, Just one question, I did this problem in java, and was using int, but some answers were wrong(I'm guessing overflowing), then changed to long and it was fine, why is this ?, int are supposed to be 2^32 which is greater than 10^9 , Sorry if my question is really dumb, I dunno much about these things...

Tarzan — :)

Same here :[

Fixed! :)

We can sort the suffixes of both strings using a single suffix array (on the string s₁#s₂#). Note that later we can recognize which string does each suffix belong to: if its index is less than |s₁| (0-based), than it belongs to s₁, if its index is greater than |s₁|, it belongs to s₂.

Now suppose there is some string t that is a unique substring of s₁ and a unique substring of s₂. Let's think of the corresponding prefixes of s₁ and s₂ where this string starts. Since only they have the common prefix t, they have to be adjacent in the suffix array, let's say at p[i] and p[i + 1]. Also, the longest common prefix of p[i - 1] and p[i] is less than |t|; and the longest common prefix of p[i + 1] and p[i + 2] also is less than |t|.

So, this leads to a solution: iterate over all adjacent positions in the suffix array, p[i], p[i + 1]. Calculate:

x = lcp(p[i - 1], p[i]),

z = lcp(p[i], p[i + 1]),

y = lcp(p[i + 1], p[i + 2]).

Then each prefix of p[i] with length of at least max(x, y) + 1 and at most z is unique in both s₁ and s₂. So if max(x, y) + 1 ≤ z, we can update the answer with max(x, y) + 1.

Check out my submission: 6538270.

You can use std::pair;

It is correct because if you change point to the left, you make result better for left side, but you make worse for right side, and vice-versa;

My solution: 6556865

EP, you are right

you still have "ep" being unique on each string.

Just increase your INF by adding 2 ,3 more 9s & you will get AC (:

Count only the number of nodes with minimum cost.