Search found 44 matches

by makbet
Mon Oct 11, 2004 11:21 pm
Forum: Algorithms
Topic: Does STL use Boyer-Moore?
Replies: 2
Views: 1408

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.
by makbet
Mon Mar 08, 2004 10:23 pm
Forum: Algorithms
Topic: Hungarian method
Replies: 1
Views: 1695

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-...
by makbet
Sat Jan 31, 2004 2:19 pm
Forum: Volume 102 (10200-10299)
Topic: 10280 - Old Wine Into New Bottles
Replies: 15
Views: 6411

Use dijkstra's algorithm to solve this.
by makbet
Tue Jan 27, 2004 3:57 pm
Forum: Volume 102 (10200-10299)
Topic: 10299 - Relatives
Replies: 57
Views: 14071

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...
by makbet
Thu Jan 22, 2004 1:48 pm
Forum: Algorithms
Topic: LIS, better then O(n^2)?
Replies: 16
Views: 11836

Not so large.
Length of word * size of alphabet.
Of course I meant all words it can be transformed into in one step.
by makbet
Mon Nov 24, 2003 7:47 pm
Forum: Algorithms
Topic: perfect matching in bipartite graphs
Replies: 0
Views: 974

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...
by makbet
Mon Oct 13, 2003 4:07 pm
Forum: Algorithms
Topic: Reverse Problem.....can somebody give me hints.
Replies: 4
Views: 2280

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 :P.
by makbet
Sun Sep 14, 2003 2:19 pm
Forum: Algorithms
Topic: find if one rectangle fits into another
Replies: 2
Views: 2200

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 ...
by makbet
Tue Sep 02, 2003 5:56 pm
Forum: Other words
Topic: An Important Request !!!!!!!!!!
Replies: 14
Views: 2954

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...
by makbet
Mon Sep 01, 2003 4:35 pm
Forum: Algorithms
Topic: LIS, better then O(n^2)?
Replies: 16
Views: 11836

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...
by makbet
Sun Aug 10, 2003 10:32 am
Forum: Algorithms
Topic: Who know Maximal Matching Problems O(n) solution?
Replies: 4
Views: 2328

Go find it yourself, it's called
Hopcroft-Karp's.
by makbet
Fri Aug 08, 2003 12:17 pm
Forum: Algorithms
Topic: Can anyone suggest an algorithm for this Clock Synchro Prob?
Replies: 4
Views: 2044

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.
by makbet
Fri Aug 08, 2003 11:47 am
Forum: Algorithms
Topic: Who know Maximal Matching Problems O(n) solution?
Replies: 4
Views: 2328

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)
by makbet
Sun Jul 27, 2003 6:03 pm
Forum: Algorithms
Topic: Muliple shortest Path Problem
Replies: 4
Views: 2270

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...
by makbet
Sat Jun 07, 2003 8:51 am
Forum: Algorithms
Topic: Negative cycle in graph
Replies: 11
Views: 4608

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? :wink:

Go to advanced search