Search found 51 matches

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Go to advanced search