USACO help

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
New poster
Posts: 6
Joined: Fri Nov 12, 2004 2:33 am

USACO help

Post by h_s_potter2002 »

I need help with one of the test cases with the problem inflate.

Here's the problem description if anyone needs it:
Score Inflation

The more points students score in our contests, the happier we here at the USACO are. We try to design our contests so that people can score as many points as possible, and would like your assistance.

We have several categories from which problems can be chosen, where a "category" is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the USACO staff how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest.

The input includes the length of the contest, M (1 <= M <= 10,000) (don't worry, you won't have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 <= N <= 10,000.

Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is worth (1 <= points <= 10000); the second tells the number of minutes a problem from that category takes to solve (1 <= minutes <= 10000).

Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points.
Line 1: M, N -- contest minutes and number of problem classes
Lines 2-N+1: Two integers: the points and minutes for each class

300 4
100 60
250 120
120 100
35 20

A single line with the maximum number of points possible given the constraints.
SAMPLE OUTPUT (file inflate.out)


(Take two problems from #2 and three from #4.)
Here is the test case I am having trouble with. Since it's really long and complicated, it's hard for me to try and figure out how it works.

Code: Select all

minutes problems
1000 20

points minutes
40 11
333 336
2172 356
1958 537
9499 701
4443 275
6983 109
416 565
8155 166
7644 686
9596 828
4268 220
8396 953
8109 924
6048 452
5998 662
7201 550
4062 114
6713 122
4911 475
thanks for your help

and btw, does anyone know what happened to

New poster
Posts: 1
Joined: Tue Nov 16, 2004 1:29 am

Post by countersixte »

I'm getting an answer of 62887. Is this the correct answer for this case?

New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Post by cypressx »

U must use DP to calculate the best way to use t minutes for all t from 0 to to the end of the time interval.

New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

Post by tRipper »

I'm having trouble passing time limit on this one. I use bottom-up DP solution with time complexity O(mn). How do I speed this up? Is there a way to trade time for space?

New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

Post by yaro »

My O(nm) solution passed all test cases (it worked 2.12 second at worse).
You should optimize your code to get it accepted.

New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

Post by tRipper »

How can you pass all test cases when the time limit is 1 s? My improved solution runs for about 1.25s on the last case, but that's still not enough

New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

Post by yaro »

1s? When I was doing USACO training it was 5 seconds.
O(nm) is the model solution, but it is smartly improved so that O(nm) occurs only in the worst case.

Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

the 1s test case limit becomes a bottle neck for some much harder optimization problems, such as cryptcowgraph, which is just a pain.

Post Reply

Return to “Algorithms”