## Search found 44 matches

Mon Oct 11, 2004 11:21 pm
Forum: Algorithms
Topic: Does STL use Boyer-Moore?
Replies: 2
Views: 1431
I remember trying to solve this problem with STL on some Russian contest (acm.timus.ru or acm.sgu.ru), and I got time limit exceeded. I think all I found about the topic was that the average complexity of their algorithm is linear. So probably the worst case is not linear. I'm not sure though.
Mon Mar 08, 2004 10:23 pm
Forum: Algorithms
Topic: Hungarian method
Replies: 1
Views: 1724
hungarian method is generally for finding perfect matchings in bipartite graphs. Given a semi-matched graph, you find an augmenting path, that is, a path that starts and ends with an unmatched vertice, and all the edges alternate between matched/unmatched. So you have: unmatched->matched->unmatched-...
Sat Jan 31, 2004 2:19 pm
Forum: Volume 102 (10200-10299)
Topic: 10280 - Old Wine Into New Bottles
Replies: 15
Views: 6575
Use dijkstra's algorithm to solve this.
Tue Jan 27, 2004 3:57 pm
Forum: Volume 102 (10200-10299)
Topic: 10299 - Relatives
Replies: 57
Views: 14650
This program seems to work correctly for all inputs that I found here or made up. But I constantly get WA Thanks for any help [c]#include <stdio.h> #include <math.h> int prime[100000]; int pl=0; int sito(){ char p[100000]; int i,j; p[1]=1; p[2]=0; for (i=2;i<=100000;++i) if (!p ) for (j=2;j*i<100000...
Thu Jan 22, 2004 1:48 pm
Forum: Algorithms
Topic: LIS, better then O(n^2)?
Replies: 16
Views: 11937
Not so large.
Length of word * size of alphabet.
Of course I meant all words it can be transformed into in one step.
Mon Nov 24, 2003 7:47 pm
Forum: Algorithms
Topic: perfect matching in bipartite graphs
Replies: 0
Views: 994

### perfect matching in bipartite graphs

I'm looking for a fast algorithm that finds a perfect matching in bipartite graphs. I know of algorithms of complexity O(V*E) and O(sqrt(V)*E) that find maximum matching, but they don't satisfy me. I know that there exists an algorithm O(E*logE) for perfect matching. If anyone knows it or at least k...
Mon Oct 13, 2003 4:07 pm
Forum: Algorithms
Topic: Reverse Problem.....can somebody give me hints.
Replies: 4
Views: 2320
This task is from the recent IOI.
As far as I recall, nobody scored
a perfect 100 on it, so for the
optimal algorithm you'd have to ask
somebody very smart .
Sun Sep 14, 2003 2:19 pm
Forum: Algorithms
Topic: find if one rectangle fits into another
Replies: 2
Views: 2227
You have to notice, that there are only 2 possibilities to fit it. One is that the two rectangles' sides are parallel to each other, and this case is easy. The other one is a bit complicated: You have to rotate the smaller rectangle, so that two opposite corners touch the bottom and top side of the ...
Tue Sep 02, 2003 5:56 pm
Forum: Other words
Topic: An Important Request !!!!!!!!!!
Replies: 14
Views: 3033
Sometimes having someones source code is useful when you want to test your program against random-generated test cases. I think some people practice this. Another thing is that people often send their buggy code to the forum, asking what's wrong in it. Then someone tells them exactly where's the bug...
Mon Sep 01, 2003 4:35 pm
Forum: Algorithms
Topic: LIS, better then O(n^2)?
Replies: 16
Views: 11937
My way to solve this problem was to build a directed graph ( if a can be transformed into b then add edge va->vb ). It's easy to notice that in such graph O(E) = O(V). Finding the longest route in a directed acyclic graph is O(V+E)(in this case = O(V)). Now about constructing the graph. Several appr...
Sun Aug 10, 2003 10:32 am
Forum: Algorithms
Topic: Who know Maximal Matching Problems O(n) solution?
Replies: 4
Views: 2362
Go find it yourself, it's called
Hopcroft-Karp's.
Fri Aug 08, 2003 12:17 pm
Forum: Algorithms
Topic: Can anyone suggest an algorithm for this Clock Synchro Prob?
Replies: 4
Views: 2081
Gauss-jordan would be OK here if you were to find ANY solution. Unfortunately you have to find the one with minimal number of moves :wink: there are 4^11= 2^22 different positions, you can aply bfs here. Such graph would be very specific, so I don't know how quick this would be. I think still to slow.
Fri Aug 08, 2003 11:47 am
Forum: Algorithms
Topic: Who know Maximal Matching Problems O(n) solution?
Replies: 4
Views: 2362
Are you talking about normal or bipartie graphs? In the first case
O(n^3) is probably the best you can get. In the second case the fastest known algorithm is O(sqrt(V)*E)
Sun Jul 27, 2003 6:03 pm
Forum: Algorithms
Topic: Muliple shortest Path Problem
Replies: 4
Views: 2309
This can be done using dijkstra. When you relax an edge u->v and d[v]== d[u]+ d[u->v] then you add u to a list of 'fathers' of v. When d[v]> d[u]+ d[u->v] then you do the same, but first you clean the list. Now having such lists in all vertices, you can easily build multiple paths between 2 given on...
Sat Jun 07, 2003 8:51 am
Forum: Algorithms
Topic: Negative cycle in graph
Replies: 11
Views: 4695
The algorithm which uses dijkstra works alright when you have
bi-directional edges. But in this problem the edges are directed. Maybe I'm still missing something?