## Search found 51 matches

Mon May 25, 2009 11:34 am
Forum: Algorithms
Topic: Sorting with a minimal number of swaps
Replies: 3
Views: 5636

### Re: Sorting with a minimal number of swaps

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's try ...
Sun May 24, 2009 5:40 pm
Forum: Algorithms
Topic: Sorting with a minimal number of swaps
Replies: 3
Views: 5636

### Sorting with a minimal number of swaps

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 inversions...
Tue Apr 14, 2009 12:03 pm
Forum: Algorithms
Topic: Computing n choose k mod p
Replies: 3
Views: 8382

### Re: Computing n choose k mod p

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) * ....
Mon Apr 13, 2009 10:08 am
Forum: Algorithms
Topic: 2-d extension of interval trees?
Replies: 3
Views: 2278

### Re: 2-d extension of interval trees?

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.
Mon Apr 06, 2009 5:54 pm
Forum: Algorithms
Topic: shortest paths network
Replies: 2
Views: 1764

### Re: shortest paths network

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].
Mon Feb 09, 2009 11:03 pm
Forum: Algorithms
Topic: Circular String Linearization
Replies: 12
Views: 13298

### Re: Circular String Linearization

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 suffixes...
Wed Jan 21, 2009 10:04 am
Forum: Algorithms
Topic: hortest path from s to t with which includes all subset
Replies: 11
Views: 2421

### Re: hortest path from s to t with which includes all subset

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, ...
Tue Jan 20, 2009 3:00 pm
Forum: Algorithms
Topic: hortest path from s to t with which includes all subset
Replies: 11
Views: 2421

### Re: hortest path from s to t with which includes all subset

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 is no...
Wed Jan 14, 2009 11:28 pm
Forum: Algorithms
Topic: hortest path from s to t with which includes all subset
Replies: 11
Views: 2421

### Re: hortest path from s to t with which includes all subset

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 1...
Tue Jan 06, 2009 9:25 pm
Forum: Algorithms
Topic: hortest path from s to t with which includes all subset
Replies: 11
Views: 2421

### Re: hortest path from s to t with which includes all subset

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 ...
Mon Jan 05, 2009 9:48 pm
Forum: Algorithms
Topic: How many graphs?
Replies: 4
Views: 1280

### Re: How many graphs?

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 Goo...
Sat Dec 20, 2008 10:54 pm
Forum: Algorithms
Topic: RMQ problem
Replies: 3
Views: 1576

### Re: RMQ problem

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 th...
Sat Dec 20, 2008 1:36 pm
Forum: Algorithms
Topic: RMQ problem
Replies: 3
Views: 1576

### Re: RMQ problem

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 ...
Wed Nov 05, 2008 9:34 am
Forum: Algorithms
Topic: given N circles,how many pairs intersect
Replies: 2
Views: 1242

### Re: given N circles,how many pairs intersect

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) ca...
Thu Sep 25, 2008 10:07 am
Forum: Algorithms
Topic: use Bellman ford algo. to find a negative cycle
Replies: 5
Views: 4130

### Re: use Bellman ford algo. to find a negative cycle

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