Авторами были предложены различные варианты решения. Порисовав примеры, можно заметить, что если полукони не встретятся за один ход (причем не важно, если они встретятся на "плохой" клетке), то они не встретятся никогда. Это следует из ограничений на размеры поля и самих вариантов движения полуконя. Поскольку клетки, где изначально стояли полукони, считаются хорошими, то мы можем считать, что попав в одну клетку (пусть даже и плохую) за первый ход, полукони могут вместе перейти в одну из начальных позиций, и там уже встреча состоится. Таким образом, достаточно проверить, смогут ли полукони встретиться за один ход.
Обратим внимание на то, что число грязных ступенек ≤ 3000. Для того, чтобы решение существовало, необходимо проверить, что ступенька с номером 1 и ступенька с номером n чистые, а также что в отсортированном массиве не встречается больше двух подряд идущих ступенек. Отсортируем массив, и проходом по нему узнаем нет ли трех подряд идущих номеров грязных ступенек, а также проверим, не являются ли ступеньки 1 и n грязными.
Количество выполнений функции swap — это количество инверсий во входной перестановке. Несложно заметить, что менять местами имеет смысл только такие элементы ai, aj, что i < j и ai > aj (иначе количество инверсий только увеличится). Пусть di, j — количество таких элементов перестановки с индексами от 0 до i включительно, которые строго меньше j. Тогда при обмене элементов c индексами i и j количество инверсий станет равным old - 2 * (di, ai + dj, aj - di, aj - dj, ai) - 1, где old — количество инверсий в исходной перестановке. Достаточно перебрать все пары элементов и выбрать из них те, которые позволяют минимизировать количество инверсий. Доказательство этой формулы оставим читателю в качеству упражнения.
Если исходный граф состоит менее чем из q компонент связности, то решения не существует. В противном случае, очевидно, выгодно сначала добавлять ребра, которые будут соединять разные компоненты, а затем ребра в пределах одной компоненты. Первый этап можно выполнять жадно: каждый раз брать две компоненты, текущий вес которых минимален, и соединять их ребром, объединяя в одну компоненту. Для этого, например, все компоненты связности текущего графа можно хранить в структуре set. Для выполнения второго этапа достаточно найти любую компоненту, состоящую более чем из одной вершины (т.к. петли запрещены), и добавить все оставшиеся ребра между любыми двумя её вершинами. Если какое-то действие выполнить невозможно (например, были добавлены все ребра, а количество компонент связности все равно больше требуемого), то решения также не существует.
Асимптотика — O(n + m + plogn).
Представим данную задачу как задачу нахождения максимального потока минимальной стоимости. Построим следующую сеть. Истоком будет 1-ый резервуар, стоком — n-ый резервуар. Каждая труба из резервуара u в резервуар v в сети будет представлена двумя дугами из вершины u в вершину v — первое ребро будет иметь пропускную способность cuv и стоимость 0, второе — бесконечную пропускную способность и стоимость 1. Таким образом, ответом на задачу будет величина максимального потока в этой сети стоимости не более чем k. Ее можно найти стандартным алгоритмом увеличивающих путей.
UPD1. Добавлен разбор задач A и B. UPD2. Добавлен разбор задачи C.
can you give an explanation/proof for the fact used to solve problem A? (if semiknights cannot meet in the first step they cannot meet later)
Bruteforce?
I recommend you to draw the usable (or reachable) cells of the chess board from (1,1), you will realize that there are just a few valid cells to meet, and even less taking into account the invalid (#) cells.
I think the fact you find just hold when n is small. I recommand you to find a way to solve the problem no matter how large n is(of course not too lager). During the hack, I find a solution that calculate the position of two knights difference Mod 4. And I think that is the point to the problem. If (a[0] — a[1]) % 4 != 0 || (b[0] — b[1]) % 4 != 0, ans is no. else yes. Sorry for my poor English.
yes, I thought this way too. It's quite obvious. If two knights can meet each other, afterwards we can think about them as an unit entity and move this entity to the initial position of any of two knights by reverse sequence of moves of this knight. Because this position is available for meeting, we are just about to check if one knight can reach the initial position of the second knight — your conditions just check it right.
I don't understand problem A. You say that "If (a[0] — a[1]) % 4 != 0 || (b[0] — b[1]) % 4 != 0, ans is no. else yes."
But these knights can move: "2 squares forward and 2 squares to the right, 2 squares forward and 2 squares to the left, 2 squares backward and 2 to the right and 2 squares backward and 2 to the left."
So ..., a knight at (4,1) can jump to (6,3). In the following example, the two knights meet and ((x1-x2)%4==2 && (y1-y2)%4==2)==true
Every step knight leaves the position where he is.
OK, thanks. I get it: they move at the same time
Can someone please explain the solution to C again? Some of the accepted solutions appear to be using BIT tree to solve the question. What's the logic behind it? Thanks.
Here is the logic i used for problem C
let's name the array A
for any value at index i ... The number of swap function calls related to this number is equal to the number of values greater than A[i] in the segment A[:i] ...
So for every index i ... I store the number of values greater, and smaller than A[i] in every segment A[:j] (0 <= j < N)
Now when I change the position of some value to an index greater than its intial index ... The total number of swaps decreases (or increases) by the factor Bigger[i][j]-Bigger[i][i] + Smaller[i][i] — Smaller[i][j], where i is the initial index and j is the new index , We will need to reverse that expression in case of moving from j to i
Now i try every possible swap between 2 elements (i,j where j>i) calculating the change due to change of position of A[i] and change of position of A[j], and take the swap with the best benefit.
and also if you are computing number of swap before swapping on of those pairs you have to increase your ans by one because you are counting the number of change in swap of that pair twice in this formula.
Regarding Question E: Does mincost maxflow also allow us to find the maximum flow within a particular cost ? [ I am concerned as to how would I find this statement: "answer is the maximum flow with cost not greater than k" ]
+1
In this problem, we are trying to solve the "minimum cost flow" problem, rather than the "minimum-cost max-flow". This more general solution is useful here because we can fix a flow amount and check whether the cost goes over K. So some people used binary search with the "min-cost-flow" algorithm, rather than just using the min-cost-max-flow algorithm (which is a special case). The binary search thing works here because the cost increases with flow (this might not always be the case).
Alternatively, if I recall correctly, if you use an "augmenting path" based approach for solving the min-cost max-flow problem, each time you augment the flow by an augmenting path, you actually have the minimum cost for that specific flow amount. I don't remember a direct proof of this, sorry. But it may be useful to think about how one might solve the minimum-cost flow problem using a minimum-cost max-flow algorithm.
So, in my solution, I first augmented as much as possible without any cost. And then I augmented by 1 flow unit at a time, keeping track of the cost used so far. Once it became greater than K, I stopped and returned the previous answer. This also worked because the cost increases with flow (i.e.: there is never a time where you increase the flow but the cost goes down). That's definitely not true in general though.
Instead of augmenting by 1 you can augment by min((k-costsofar)/cost_for_reaching_sink,maxflow).
[del]
[del]