Search found 22 matches

by nibbler
Tue Sep 13, 2005 12:52 pm
Forum: Algorithms
Topic: dfs sequence
Replies: 3
Views: 1154

I'm sure I already read something about min cost matching on this forum, try searching
by nibbler
Fri Jul 08, 2005 1:50 am
Forum: Algorithms
Topic: Usaco- Contact (IOI'98) .... I get "Time Limit exceed
Replies: 2
Views: 1440

If you don't get any help here, you can try the usaco forum
by nibbler
Tue May 31, 2005 11:05 am
Forum: Volume 106 (10600-10699)
Topic: 10679 - I Love Strings!!
Replies: 101
Views: 48681

This is not Boyer-Moore, this is Quick search algorithm
http://www-igm.univ-mlv.fr/~lecroq/stri ... CTION00190
Notice the O(n*m) running time
by nibbler
Thu May 26, 2005 8:36 pm
Forum: Volume 6 (600-699)
Topic: 694 - The Collatz Sequence
Replies: 46
Views: 15991

why don't you post your code?
by nibbler
Thu May 26, 2005 12:03 pm
Forum: Algorithms
Topic: Algorithm For String Matching
Replies: 5
Views: 1559

KMP is O(N+M), which is worst case optimal. Boyer-Moore variants also have O(N+M) worst case, but their best case can be down to O(M+N/M), which is much better. If you are searching for more then one pattern, use Aho-Corasick. Is there a particular problem that you are trying to solve?
by nibbler
Sun May 22, 2005 2:24 pm
Forum: Algorithms
Topic: Lines and a point
Replies: 4
Views: 1016

This is something like usaco fence4 problem. general idea of my solution was to keep line segments that are visible so far, to add one new at a time, checking those you examined so far: if part of a line segment is not visible, we can break it in two ( or less ) visible parts and continue checking r...
by nibbler
Mon May 02, 2005 3:21 pm
Forum: Algorithms
Topic: RMQ (Range Minimum Query), who r u?
Replies: 4
Views: 1713

I solved Cave Cows 2 like this: divide the segments into groups of 50, and preprocess the min of every group. Example querry: what is min from 117 to 873? Compute "manually" min from 117 to 150, then you now mins from 150-200, 200-250, ... , 800-850, then manually from 850-873 again. Maximal time to...
by nibbler
Tue Apr 19, 2005 9:56 pm
Forum: Algorithms
Topic: Help on a USACO problem
Replies: 3
Views: 1168

I used similar method, only I used binary search to limit the maximal path length and then maximal flow to see if all the cows can get to shelter. I had a nasty bug so actually won no points on it, but later I had 10 test cases on time, and the rest was TL. In fact, no one solved this problem comple...
by nibbler
Mon Apr 18, 2005 5:29 pm
Forum: Algorithms
Topic: n-queens problem
Replies: 15
Views: 3576

search() calls itself several thousand times and you run out off stack, I haven't studied why. pozdrav ;)
by nibbler
Mon Apr 18, 2005 5:13 pm
Forum: Algorithms
Topic: quentions about a knapsack problem
Replies: 2
Views: 1021

Try this, it is O(N*M) #include <cstdio> #include <vector> using namespace std; int main() { int N,M,cnt=0; scanf ("%d %d",&N,&M); vector <int> weight(N),amount(N), V(M+1), R(M+1); for (int i=0;i<N;i++) scanf ("%d %d",&weight[i],&amount[i]); V[0]=1; for (int i=0;i<N;i++) { int w=weight[i],a=amount[i...
by nibbler
Thu Apr 14, 2005 11:33 pm
Forum: Algorithms
Topic: want to learn about "Hash"
Replies: 6
Views: 1339

to start off, try rabin karp string matching algorithm
by nibbler
Tue Oct 05, 2004 7:11 pm
Forum: Volume 107 (10700-10799)
Topic: 10703 - Free spots
Replies: 26
Views: 9038

i got accepted without the additional newlines, like D-DY first output.
by nibbler
Sun Sep 26, 2004 7:15 pm
Forum: Volume 6 (600-699)
Topic: 681 - Convex Hull Finding
Replies: 60
Views: 20683

I used Grahm's scan and got WA. With almost identical code I passed convex hull problem on USACO. I've checked test cases posted above, works fine. Anyone has an idea about where the error might be? Any new test data? // FINDING THE COMPLEX HULL USING GRAHM'S SCAN #include <cstdio> #include <vector>...
by nibbler
Sun Aug 15, 2004 8:52 pm
Forum: Algorithms
Topic: Maximal suffix
Replies: 2
Views: 1305

Maximal suffix

Problem: given a text determine lexicographically maxiaml suffix of a string in O(n). For example: cacbca has the max suffix cbca. I read that this can be done with technique similar to one used in KMP, using the maximal suffix and at the same time a prefix of a word, but I don't know how to impleme...
by nibbler
Wed Jul 28, 2004 3:10 pm
Forum: Algorithms
Topic: Cowcycles... A VERY hard problem!
Replies: 4
Views: 2265

you don't need any pruning at all, test cases are that simple.

Go to advanced search