Tuesday, July 10, 2012

UVA 10910 - Marks Distribution

You are a student that has taken a total of N subjects. In order to pass a certain subject, you need a least \(P\) marks of grade. You got a total of \(T\) marks among all your examinations. Your task is to print how many different ways you can distributed those marks among the N subjects in such way you pass all of them.

This problem can be solve with Dynamic Programming. The first thing to note is that we don't need to bother with distributions of grades were one or more grades are less than \(P\). In other words, we can assume that all the subjects start with \(P\) marks. Knowing this we just need to care in how to distributed the remaining \(T - N \cdot P\) marks left. To calculate this we are going to use top-down Dynamic Programming also known as memoization. 

The state of the DP state is simple: (current subject, remaining marks) = total number of configurations. For each subject  recursively we tried all the possible assignments of marks. Because we are counting different configurations the base case return the number 1. We use the variable res to add up all the valid configurations founded by the recursion function.

No comments: