
Search found 27 matches
- Sun Apr 27, 2003 11:25 pm
- Forum: Other words
- Topic: Online Judge Server is down?
- Replies: 6
- Views: 1609
- Sun Apr 27, 2003 7:14 pm
- Forum: Other words
- Topic: Online Judge Server is down?
- Replies: 6
- Views: 1609
- Tue Mar 04, 2003 9:32 pm
- Forum: Volume 101 (10100-10199)
- Topic: 10160 - Servicing Stations
- Replies: 20
- Views: 13929
Is this NP? How to solve efficiently?
Hi people,
I'm trying to solve this problem and it appears to be NP (dominating seT). I've implemented a recursive solution using backtracking, but it is giving time limit.
Anyone could help?
Regards!
I'm trying to solve this problem and it appears to be NP (dominating seT). I've implemented a recursive solution using backtracking, but it is giving time limit.
Anyone could help?
Regards!
- Thu Nov 07, 2002 12:33 am
- Forum: Volume 103 (10300-10399)
- Topic: 10369 - Arctic Network
- Replies: 45
- Views: 25168
Exactly. Prim's MCST does not work. For those wanting to see a BS solution, look at Waterloo. Regards... Here's a counterexample to Prim. 1 3 6 0 1 0 2 0 4 0 5 0 7 0 8 The output should be 1, but Prim will give 2. Let's say you start with 0,1. You will connect it to 0,2. Then the closest point is 0,...
- Wed Nov 06, 2002 3:52 pm
- Forum: Volume 101 (10100-10199)
- Topic: 10181 - 15-Puzzle Problem
- Replies: 38
- Views: 21181
- Tue Nov 05, 2002 4:43 pm
- Forum: Volume 103 (10300-10399)
- Topic: 10369 - Arctic Network
- Replies: 45
- Views: 25168
Re: 10369 - Arctic Network
The MCST does not solve this problem. It appears as if you did so. I first compute the distance and add a corresponding edge between each pair of outposts. That is, I construct an undirected graph where edge weights are those distances. Then I apply Kruskal algorithm until P-S edges are added and pr...
- Tue Nov 05, 2002 4:35 pm
- Forum: Volume 102 (10200-10299)
- Topic: 10260 - Soundex
- Replies: 30
- Views: 11712
Re: 10260,HELP!
This is a problem from Waterloo. Maybe you could find something helpful there. Regards! I don't know why I always recieve WA . :cry: Could someone give me some data? thanks!! :) Here is my code : //@BEGIN_OF_SOURCE_CODE #include <stdio.h> void main(){ char array[25]; int i=0; int printbuffer=0,temp=...
- Tue Nov 05, 2002 4:28 pm
- Forum: Other words
- Topic: About ACM forum
- Replies: 1
- Views: 1683
Re: About ACM forum
maybe this has already been answered, but there is the
http://www.ioiforum.org
http://www.ioiforum.org
Archangel wrote:Does anybody know any other ACM forum ??
- Tue Nov 05, 2002 4:21 pm
- Forum: Volume 102 (10200-10299)
- Topic: 10221 - Satellites
- Replies: 34
- Views: 14200
Re: 10221 a easy problem,but why wrong answer?
try using pi = acos(-1). Also there is no a>360 in the input. What happens if a > 180? Try using cos instead of sin to determine chord. Regards! #include<iostream.h> #include<math.h> #include<stdio.h> #define pi 3.1415926535897932384626433832795 void main() { double arc,chord; char ch[4]; long s; do...
- Tue Nov 05, 2002 4:17 pm
- Forum: Volume 101 (10100-10199)
- Topic: 10181 - 15-Puzzle Problem
- Replies: 38
- Views: 21181
Hi, how can I use this information? I've implemented A* with the Manhattan Distance heuristic and it still gives time limit. Your help is welcome :) Regards! Read description for problem 652. Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable versi...
- Mon Nov 04, 2002 1:12 am
- Forum: Volume 8 (800-899)
- Topic: 827 - Buddy Memory Allocator
- Replies: 6
- Views: 6640
827 - Buddy Memory Allocator
Is there any trick with this problem? Does anyone have an interesting input?
Thanks a lot!
Thanks a lot!
- Mon Nov 04, 2002 1:11 am
- Forum: Volume 8 (800-899)
- Topic: 825 - Walking on the Safe Side
- Replies: 38
- Views: 21503
Where can you find judge's input? Have u got the input for problem 827 - Buddy Memory Allocator, too?Picard wrote:i've solved it generaly (i still think the problem description allow longer minimal pathes), but now i checked the judge's input and found no minimal path longer as width+height-2
Thanks a lot!
- Wed Oct 30, 2002 3:36 am
- Forum: Volume 1 (100-199)
- Topic: 188 - Perfect Hash
- Replies: 9
- Views: 5499
Re: 188 perfect hash - huh?
you must use long long. but the initial value for C must be the minimum of the vector, not 2. I don't understand why I'm getting WA here. The problem desc. says exactly what to do and it works on all the input i've tried. Can anyone see the problem? (I know my split function is fine, and i added the...
- Mon Oct 28, 2002 7:24 pm
- Forum: Volume 3 (300-399)
- Topic: 307 - Sticks
- Replies: 56
- Views: 19062
Hi all! What's the idea behind the dynamic programming? Thanx a lot! :D My solution worked with an array with 100000 elements. So there are no more than 100000 parts in the input. But how do you store the used solutions? I think this is your problem. I used another array of 100000 elements to memori...
- Mon Oct 28, 2002 7:10 pm
- Forum: Volume 102 (10200-10299)
- Topic: 10234 - Frequent Substrings
- Replies: 25
- Views: 9403
Efficient Implementation?
How could we solve it in O(length(s))? What's is the time complexity of your algorithm?
Thanx!
Thanx!