## Search found 26 matches

Thu Jul 04, 2002 11:20 pm
Forum: Volume 103 (10300-10399)
Topic: 10313 - Pay the Price
Replies: 42
Views: 19468
You wrote : Actually, with this formula ways[i,j] is the ways in which the biggest coin is *less than* or equal to j... not just equal. That's all you need, I'm not sure I understand the problem you're having. I mean that, 1. Ways[i,j] - is the number of ways to pay i dollars using coins less or eq...
Thu Jul 04, 2002 5:00 pm
Forum: Volume 103 (10300-10399)
Topic: 10313 - Pay the Price
Replies: 42
Views: 19468
Formula Ways[i,j]=Ways[i,j-1]+Ways[i-j,j] is known by almost everybody (as I think). Although I wanted to use this formula in the contest, but I have a big problem: This formula only count the ways in which the biggest coin is equal to j; but how can I count the ways in which the number of coin is ...
Thu Jul 04, 2002 3:40 am
Forum: Volume 103 (10300-10399)
Topic: 10313 - Pay the Price
Replies: 42
Views: 19468
Joe, are you sure you solve it in O(n^2)? Because I thought my algorithm is O(n^3), but my program is faster than your program. Did you also sum up the values of the matrix and store them? Yes, I only have an NxN array which I memoize on, and each value is computed from other values in O(1) time, s...
Tue Jul 02, 2002 9:11 pm
Forum: Volume 103 (10300-10399)
Topic: 10313 - Pay the Price
Replies: 42
Views: 19468
I just wonder how the program can work less than 2 seconds. My program work 29.530 seconds and get Accepted. But I have no idea how to optimaze it. Can anyone give me a hint to make a good fast program? P.S. I use DP. My algorithm is O(n^3). May be exist a algorithm O(n^2 (log n))? If your algorith...
Fri Jun 28, 2002 10:18 pm
Forum: Volume 103 (10300-10399)
Topic: 10302 - Summation of Polynomials
Replies: 29
Views: 15219

### Hint

mido wrote:Well a friend just mentioned that any number type can only be accurate upto some length after which there will be some zeroes inputted automatically. Oh well.
gcc (which is what UVA uses) has a "long long" data type which supports integers up to 2^64. So does Java's "long".
Wed Jun 19, 2002 6:21 pm
Forum: Volume 103 (10300-10399)
Topic: 10304 - Optimal Binary Search Tree
Replies: 24
Views: 12555
I think that's a wrong interpretation. For example, let i=3 and j=7 and let root[3,6]=4 and root[4,7]=6. Then we try 4 to 6 as root[3,7]. We might end up with 5, even though it is not the root of any of the two subproblems. I wasn't very specific; what I meant was the nodes to the left of root[3,6]...
Tue Jun 18, 2002 5:42 am
Forum: Volume 103 (10300-10399)
Topic: 10304 - Optimal Binary Search Tree
Replies: 24
Views: 12555
Can anybody explain exercise 15.5-4 of CLRS to me? I don't ask for a solution, I just can't understand the first sentence. This "always" and "for all" and stuff is weirdly mixed... (Later the same day) Found it out myself. The hint means that in order to find root[i,j] you only have to try all node...
Mon Jun 17, 2002 6:36 pm
Forum: Volume 103 (10300-10399)
Topic: 10304 - Optimal Binary Search Tree
Replies: 24
Views: 12555

### 10304 - Optimal Binary Search Tree

How did people get their solutions to run so fast? I used the obvious O(n^3) dynamic programming algorithm; is there something better? My first two attempts used memoization and were too slow, so I switched to iterating over the array, eliminating all function calls, and my submission just barely ra...
Mon Jun 17, 2002 6:26 pm
Forum: Volume 103 (10300-10399)
Topic: 10308 - Roads in the North
Replies: 30
Views: 9784
shahriar_manzoor wrote:There can be inputs with zero cities!!!
Oops, I guess I can't read.

Thanks!
Mon Jun 17, 2002 2:49 am
Forum: Volume 103 (10300-10399)
Topic: 10308 - Roads in the North
Replies: 30
Views: 9784

### 10308 - Roads in the North

Am I wrong in assuming the graph is a tree? I interpret the statement "there is only one route from a village to a village that does not pass through some other village twice" as meaning there are no cycles, and it says there's only 1 component. If this is right then it's easy, just dfs, but I'm get...
Wed Jun 12, 2002 10:07 pm
Forum: Volume 103 (10300-10399)
Topic: 10301 - Rings and Glue
Replies: 50
Views: 16338

### 10301 - Rings and Glue

The problem says to output the answer in a gramatically correct sentence.

When X=0, the expected answer is "The largest component contains 0 ring.". This is gramatically incorrect, and should be "0 rings".