OJ Board

mf

I'm just curious :)
I tried to find this problem in online judges, but found only the "easy" version.

Number of inversions is useful if we are allowed to swap only adjacent elements.
Yeah, you're right. It was a wrong move from the algorithm 2) to algorithm 1) :)

Yeah, that works. And let ...

The problem is, given an array A[1..N] of numbers (not necessarily different) output a minimal number of swap operations (you can swap any, not only neighbour, elements) needed to make this array sorted.

If all numbers A were different, then the solution is obvious: 1) count the number of ...

There is another, more "mechanical", but more general, approach. It can be applied to any formula containing factorials over some modulo.

C_n^k = n! / (k! (n-k)!)
Let's learn how to compute n! mod p, but factorial without factors p and so on:
n!* mod p = 1 * 2 * ... * (p-1) * _1_ * (p+1) * (p+2 ...

I think, only (logn)^2.
We create interval tree for X coordinates, where each vertex of this tree is an interval tree for Y coordinates.

You don't even need in pred[], only distances dist[] from vertex s to the others.
After that, calculate for each vertex dynamics: d[v] is the number of shortest paths to v.
Set d[s] = 1.
For each other vertex d[v] = SUM d[p] over all p such that dist[p] + g[p][v] == dist[v].

There are lots of approaches to solve this problem.

First of all, hashes. Indeed, we can compute LCP (longest common prefix) of any two suffixes S[i..] and S[j..] of given string (we can do this be binary search in O(log N), N = S.length). After that we can compare lexicographically any two ...

do u see any easier easy solution if the K =V.
That means to find a shortest path if the graph must pass through all the nodes of a complete graph .
a kind of shortest hamiltonian path ?

I asked this because the problem can be reduced to a hamiltonian path if
we construct a graph complete G1= (V1 ...

thanks for explanations,math is international. what are the wights for the new graph ?
Weights stay the same. That is, if there is any rib a -> b, than in new graph each rib (a,x) -> (b,y) (of course, if the rib exists) will have the same weight.

well very nice imagination you have.
This idea ...

Ok.
Let's have a graph
1 -> 2, 2 -> 3, 3 -> 4, 1 -> 3, 2 -> 4
and the only marked vertex is 2.
So the problem is to find a path from 1 to 4 , visiting vertex 2.

Let's build new graph G' (a 'state graph'), in which each vertex is a pair (v,m), here m can take only two values: 0 or 1 (mask of length ...

I don't think it's a polynomial-solvable problem.
I suggest an O (M 2^K (logN + K)) algorithm (N - number of vertices, M - ribs, K - number of selected vertices). Let's make another graph, with N 2^K vertices, i.e. each vertex is a pair (original_vertex, visited_mask), what means that we stand in a ...

How could the directed graph be connected? I am not familiar with such a term (for example, is graph 1->2 connected or not? you can't go from 2 to 1)

I know the solution for undirected graphs (connected and without loops and parallel edges), it's described on my site (it's in Russian, but I hope ...

Thanks for your reply.

Few questions , if i give you a mask of +-1 , can you tell me where the minimum is ? Why isn't it ambiguous .

if the maks was 1 -1 -1 , the minimum is at position 2, if maks is 1 -1 1, minimum is at position 1 , but if mask is 1 -1 1 -1 ,minimum is at position 1 and 3 . In ...

You misunderstood a bit.
Of course, we find minima in original array, not in +-1 array.
But to find it efficiently, we exploit the fact, that each element a is a[i-1]+-1.
More precisely, we can divide array a[1..N] into blocks of length L=logn/2, and precompute RMQ in each block i between each pair ...

It looks like very hard problem.
Even the following problem, which is a simplification of this one, is very hard: there is a set S of N points on plane, and the query is some circle; we should return number of points from S inside the circle. This problem (which is mentioned in Shamos, Preparata ...

Btw, I've discovered a simpler way to restore the negative cycle after executing the Ford-Bellman.
So, we've got vertex 'firstchanged', and just repeat the following N times: firstchanged = parent[firstchanged].
After that we are surely inside the negative cycle (not in any of its 'tails'), and we ...