Search found 26 matches

by Joe Smith
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...
by Joe Smith
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 ...
by Joe Smith
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...
by Joe Smith
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...
by Joe Smith
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".
by Joe Smith
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]...
by Joe Smith
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...
by Joe Smith
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...
by Joe Smith
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!
by Joe Smith
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...
by Joe Smith
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".

Go to advanced search