Page 1 of 1

### 11372 - Arranging a Contest

Posted: Sat Dec 29, 2007 7:07 pm

Posted: Sat Dec 29, 2007 7:12 pm
I think it should be very easy to people who starts in TC. At TC there are often tasks similar to this. But when someone starts only in acm-style contests these type of tasks are rare...

Posted: Sat Dec 29, 2007 7:18 pm
Monsoon wrote:I think it should be very easy to people who starts in TC. At TC there are often tasks similar to this. But when someone starts only in acm-style contests these type of tasks are rare...
I can't comment on that. I'm not a Topcoder member.

Posted: Sat Dec 29, 2007 8:20 pm
The dimension that I used for dp was ::
int dp[201][7][3][3][3][2][2];

Is there any better way?

Posted: Sat Dec 29, 2007 10:08 pm
Could you post some test case, I don't know what's wrong with my code.

Posted: Sat Dec 29, 2007 11:13 pm
jah wrote:Could you post some test case, I don't know what's wrong with my code.
are you sure you are finding lexicographically smallest solution?

Posted: Sun Dec 30, 2007 12:05 am
I tried to use a [200][3][3][3][3][2][2] table, but, without actually printing a result, I got RTE. I am guessing that was a MLE or something. I guess there is no Java reference solution so we cannot really compare results, right?

For me the order of difficulty was ADCBEF.

What was the intended solution?

Posted: Sun Dec 30, 2007 1:34 am
I think the intended solution is:

Chose which categories to take the 2 hard problems,2 easy problems and the 2 extra problems.
It could be done with O(4^6) without any tables.

-----
Rio

Posted: Sun Dec 30, 2007 12:56 pm
Yes, I realized later that only 12 of each are relevant, so it can be easily brute-forced.

Posted: Sun Dec 30, 2007 7:52 pm
I think the intended solution is:

Chose which categories to take the 2 hard problems,2 easy problems and the 2 extra problems.
It could be done with O(4^6) without any tables.
Darko wrote:Yes, I realized later that only 12 of each are relevant, so it can be easily brute-forced.
The dimension that I used for dp was ::
int dp[201][7][3][3][3][2][2];

Is there any better way?
How does the DP works? You try recursively and store in dp the answer for a subproblem after it has been solved. But what the dimensions mean? Are they the following?

201 - problem to be used
7 - number of problems already solved
3 - number of hard problems
3 - number of easy problems
3 - number of DP problems
2 - number of graph problems
2 - number of math problems

How is the algorithm to solve this problem using DP?

Posted: Sun Dec 30, 2007 8:17 pm
I can tell you my approach that is similar.
You will never use more than 2 problems having the same difficulty and category ( this is the important step ), because you will never need 2 problems having the same difficulty as the problem statement says.

You have 3 difficulty levels, and 4 category's for each one. So you have 12 pairs, and as you wont need more than 2 problems for each pair, you will have to take at most 24 problems ( you will choose trying to get the higher indexed problems, and the most convenient at the lexicographical order ).
When you have this (at most ) 24 problems, you can do a simple brute force, for example choosing 2 Easy problems, 2 Medium's, and two Hard's.

As you have at most 8 problems for each difficulty level, this can be done in less than 8^6 calculations. Eric.

Posted: Sun Dec 30, 2007 9:18 pm
black.phoenix wrote: How does the DP works? You try recursively and store in dp the answer for a subproblem after it has been solved. But what the dimensions mean? Are they the following?

201 - problem to be used
7 - number of problems already solved
3 - number of hard problems
3 - number of easy problems
3 - number of DP problems
2 - number of graph problems
2 - number of math problems
Yes.

### Re: 11372 Arranging a Contest

Posted: Sat Jan 05, 2008 1:14 am