Search found 44 matches

by danielrocha
Thu Oct 06, 2005 9:00 pm
Forum: Algorithms
Topic: Mincost Maxflow - help!
Replies: 7
Views: 2932

nnahas , I would like to thank you again for your help. As you can see here http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:10594:50 we've been able to correct code the algorithm. As for anyone who's having difficulties with this algorithm, I have one suggestion: follow the pseudo-code in the abo...
by danielrocha
Tue Oct 04, 2005 4:24 pm
Forum: Algorithms
Topic: Mincost Maxflow - help!
Replies: 7
Views: 2932

Still...

I've read about 200 times each of these .pdfs, but I can't quite understand the algorithm :oops: My code is something like this: 1. Run a Dijkstra and set the initial "potencial" value on the nodes to -d[i], where d[i] is the minimum distance from the source node to the node i. 2. Run a BF...
by danielrocha
Mon Oct 03, 2005 3:30 am
Forum: Volume 1 (100-199)
Topic: 134 - Loglan-A Logical Language
Replies: 45
Views: 5578

Spaces after the period

I would just like to warn everyone who's trying to solve this problem that there are spaces after the period. Since this is not clearly stated in the input specification I think it should be mentioned here.
by danielrocha
Mon Oct 03, 2005 3:27 am
Forum: Volume 1 (100-199)
Topic: 134 - Loglan-A Logical Language
Replies: 45
Views: 5578

Spaces after the period

I would just like to warn everyone who's trying to solve this problem that there are spaces after the period. Since this is not clearly stated in the input specification I think it should be mentioned here.
by danielrocha
Sat Oct 01, 2005 10:14 pm
Forum: Algorithms
Topic: Mincost Maxflow - help!
Replies: 7
Views: 2932

Thank you!

Thank you so much for the links nnahas. They seem to be exactly what I've been looking for. I'm gonna read them and if I have any other problems I'll post here.

Thanks again
by danielrocha
Sat Oct 01, 2005 12:37 pm
Forum: Algorithms
Topic: Mincost Maxflow - help!
Replies: 7
Views: 2932

Mincost Maxflow - help!

Hello everyone, For the past few weeks I've been trying to code an algorithm for the Mincost Maxflow problem, but I've had a lot of problems. I see this problem as been very interesting, as there are a lot of problems that can be solved by it (10594, 2691, 10888, 10746 come to mind). I was hoping yo...
by danielrocha
Mon Sep 05, 2005 7:54 pm
Forum: Volume 8 (800-899)
Topic: 868 - Numerical Maze
Replies: 21
Views: 15173

Just to make it clear: the last cell to be visited MUST BE the end of a sequence. This bothered me when I was solving this problem. I'm not sure if there are inputs where there are no solutions but my AC problem prints just an empty line.
by danielrocha
Fri Aug 12, 2005 4:27 pm
Forum: Algorithms
Topic: Can lift-to-front be slower than Edmonds-Karp?
Replies: 2
Views: 1076

Thank you very much for your reply, I never realized that the number of augmenting paths was usually << |V|.

Guess I should have spent my time improving my Edmonds-Karp algorithm :-?
by danielrocha
Fri Aug 12, 2005 6:19 am
Forum: Algorithms
Topic: Can lift-to-front be slower than Edmonds-Karp?
Replies: 2
Views: 1076

Can lift-to-front be slower than Edmonds-Karp?

I've recently finished my implementation of a "lift-to-front" max flow algorithm, following the ideias described in CLRS (2nd edition). I think I understood the algorithm, and my code works (I've tested with some problems, like 10330 and 820 - both AC). But there's one problem: it's incred...
by danielrocha
Sun Jun 19, 2005 3:54 pm
Forum: Volume 101 (10100-10199)
Topic: 10158 - War
Replies: 23
Views: 9996

It is indeed a problem about "Disjoint Sets". I'll give you a small clue: at any given time a person X can be enemies with only one (or zero) group of friends Y. Never more than that.
by danielrocha
Thu Oct 21, 2004 12:20 pm
Forum: Volume 107 (10700-10799)
Topic: 10740 - Not the Best
Replies: 23
Views: 13627

Some ideas

Hello sozu, Thank you for the test case. As I said in my previous post, a zero-sized loop could be even worse :) 4 4 1 4 10 1 2 0 2 3 0 3 1 0 1 4 10000 I tried some ideas like only inserting a node K times in the queue, but that didn't work. Could someone give some references to Kth shortest paths a...
by danielrocha
Wed Oct 20, 2004 10:04 pm
Forum: Volume 107 (10700-10799)
Topic: 10740 - Not the Best
Replies: 23
Views: 13627

Help me!

I'm using a very naive algorithm: a simple BFS + priority queue (without checking if a node has been visited, always inserting in the queue). However, my algorithm doesn't seem to work. I was getting TLE, but now I'm getting WA. I realized that there can be zero-weighted cycles, which can cause my a...
by danielrocha
Mon Oct 11, 2004 8:09 pm
Forum: ACM ICPC Archive Board
Topic: Wrong input (prob. 2045)
Replies: 0
Views: 674

Wrong input (prob. 2045)

I'm not sure this is the correct place to put this message, since this is a Regionals Archive problem, but I couldn't find a better place. There's a mistake in the judge's input of problem 2045 - Closest Common Ancestors. The problem states that: "The tree description is followed by a list of p...
by danielrocha
Tue Sep 21, 2004 12:04 am
Forum: Volume 107 (10700-10799)
Topic: 10710 - Chinese Shuffle
Replies: 19
Views: 5106

It's ok..

Your output is correct (although you skipped the first input number). Try these numbers:

Code: Select all

341
561
-1
The output should be:

Code: Select all

341 is a Jimmy-number
561 is a Jimmy-number
by danielrocha
Wed Sep 15, 2004 9:30 pm
Forum: Volume 101 (10100-10199)
Topic: 10100 - Longest Match
Replies: 95
Views: 23132

Output

Input: 12 12 12 12 this is a test this is is a a test 76.67 67 67 67 76 asd a s d c f a d c as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2 as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2 a s d r t g .;.;[ .;.;[ Output: 1. Length of longest match: 2 2. Length of longest match: 4 3. Len...

Go to advanced search