## Search found 31 matches

Wed Oct 01, 2003 7:06 pm
Forum: Volume 105 (10500-10599)
Topic: 10549 - Russian Dolls
Replies: 19
Views: 8010
Well, I don't want to give too much away. It's fun to figure these things out for yourself. Your first crack at a solution to this should be the head-on approach. Analyse the problem logically -- create some functions or relations, and define them in terms of each other. If you can reduce the proble...
Tue Sep 30, 2003 3:12 pm
Forum: Volume 105 (10500-10599)
Topic: 10549 - Russian Dolls
Replies: 19
Views: 8010
Nice algorithm, konsept! Another excellent problem with a variety of viable solutions. So far I'm aware of three essentially different solutions (not including heuristic exponential ones -- you shouldn't be able to get away with that!), with time and space complexities between O(N^2) and O(N^3) incl...
Wed Jul 16, 2003 6:03 pm
Forum: Volume 105 (10500-10599)
Topic: 10529 - Dumb Bones
Replies: 15
Views: 10954
If you have a situation A_B and you attempt to place a domino into the gap, then the following things may occur: * with probability Pl, the placed domino will fall left, taking out not only itself but the entire group A * with probability Pr, the placed domino will fall right, taking out not only it...
Tue Jul 15, 2003 5:35 pm
Forum: Volume 105 (10500-10599)
Topic: 10529 - Dumb Bones
Replies: 15
Views: 10954

### dem speedy bones

The O(N^2) DP way is fine given the limit N <= 1000 as specified. During the actual Waterloo contest I solved it that way, as I imagine everybody who competed at UVA did. It's (mathematically) interesting to look at the continuous version of this problem (taking the limit as N goes to infinity). Unf...
Mon Jun 02, 2003 2:34 pm
Forum: Algorithms
Topic: Negative cycle in graph
Replies: 11
Views: 4702
See my comment near the end of the thread on 10449: http://acm.uva.es/board/viewtopic.php?t=2306 for a simple modification to Bellman-Ford which will identify exactly the nodes on negative-weight cycles in total time O(VE). Dijsktra doesn't work, even for finding cycles reachable from a given source...
Wed May 21, 2003 12:23 am
Forum: Volume 104 (10400-10499)
Topic: 10457 - Magic Car
Replies: 20
Views: 10907
The are strong similarities between this problem and 10486 "Mountain Villages". A good algorithm for one is likely to translate into a good algorithm for the other. Personally, I'm a huge fan of union-find (disjoint-set-forest) techniques, so that's what I used for this and for 10486. It worked spec...
Fri May 16, 2003 2:52 pm
Forum: Volume 1 (100-199)
Topic: 101 - The Blocks Problem
Replies: 635
Views: 43703
Before asking this question, perhaps you should think about whether you could arrive at such a situation using the instructions available.
Fri May 16, 2003 2:43 pm
Forum: Volume 104 (10400-10499)
Topic: 10421 - Critical Wave
Replies: 17
Views: 5392
DM, I think there is some confusion in your code with the use of 'd', 'next', and len[2]. len[0] and len[1] don't seem to represent consistently either an 'upper' or 'lower' path, instead they depend on the value of .next, which may be rewritten on another pass. You may end up writing two different ...
Thu May 15, 2003 10:03 pm
Forum: Volume 104 (10400-10499)
Topic: 10438 - Meta Editor
Replies: 17
Views: 11650
"a b a" does not reduce because there is an intervening "b" between the duplicated "a". Reduce duplicated sequences if and only if there are no intervening words. "a b c a b c a b c" --> "a b c" "a b c d a b c" --> "a b c d a b c" (intervening "d" prevents collapse of "a b c") See above for further ...
Thu May 15, 2003 6:37 pm
Forum: Volume 104 (10400-10499)
Topic: 10421 - Critical Wave
Replies: 17
Views: 5392
little joey, I think your problem may be that your program only keeps track of one of the 'upper path' and 'lower path' for each point. In this way, it can lose track of the path which falls behind but will eventually become optimal. You need to keep track of the upper path and the lower path separa...
Thu May 15, 2003 12:40 am
Forum: Volume 104 (10400-10499)
Topic: 10421 - Critical Wave
Replies: 17
Views: 5392
Input:

Code: Select all

``````5
0 0
0 1
0 2
0 3
0 4``````
Wed May 14, 2003 11:57 pm
Forum: Volume 1 (100-199)
Topic: 100 - The 3n + 1 problem
Replies: 1394
Views: 191166
Here's an example of what I/O timings can tell you: I recently looked at problem 10011. The top two times on the ranklist are 0:00.221 and 0:00.482. Submitting an I/O shell which reads the input and outputs "0.000" gives me the following timings: cin >> double: 1.113 s scanf double: 0.484 s scanf fl...
Wed May 14, 2003 9:46 pm
Forum: Volume 1 (100-199)
Topic: 100 - The 3n + 1 problem
Replies: 1394
Views: 191166
If you are interested in getting fast times on UVA you are in for a bunch of work. First, unless you're worried about your submission accuracy (a reasonably futile concern -- the large number of underspecified problems require some degree of trial and error), I suggest the following: Submit a progra...
Wed May 07, 2003 4:46 pm
Forum: Algorithms
Topic: bridge in O(E) time?
Replies: 10
Views: 4059
I think most of this confusion is stemming from the close relationship between O(V+E) and O(E). For all practical purposes, they're the same, so sometime you'll see O(V+E) referred to as O(E) (which is technically a bit sloppy). The only way in which O(E) can be less than O(V) is if a graph has an a...
Tue May 06, 2003 6:01 pm
Forum: Volume 1 (100-199)
Topic: 175 - Keywords
Replies: 13
Views: 3776
After a bunch of investigation, I think I have found some of the ambiguities which are causing many of us problems. First, to answer your specific question, we are indeed intended to consider all possible pairings, not just adjacent keywords. The big issue is that the judge's input contains duplicat...