Page 1 of 1

11372 - Arranging a Contest

Posted: Sat Dec 29, 2007 7:07 pm
by Observer
I would really love to hear what you feel about this task. I thought it is an easy task, but the statistics seem to show otherwise.

Posted: Sat Dec 29, 2007 7:12 pm
by Monsoon
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
by Observer
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
by sohel
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
by jah
Could you post some test case, I don't know what's wrong with my code.

Posted: Sat Dec 29, 2007 11:13 pm
by fpavetic
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
by Darko
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
by rio
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
by Darko
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
by black.phoenix
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.
Could you give an explanation about this "brute-force" method.
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
by sonyckson
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
by sohel
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
by Giorgi
Observer wrote:I would really love to hear what you feel about this task. I thought it is an easy task, but the statistics seem to show otherwise.
I think algorithm is very easy , but my brute force solution is more than 300 lines and I was writing it about 1 hour...

Re: 11372 - Arranging a Contest

Posted: Thu Dec 03, 2009 8:31 pm
by serur
I say, there may be at most 4 dp-problems, at most 3 math, at most 3 graph, and at most 2 "other" problems. So it is enough if we choose <=2 problems of each type for each difficulty level, indeed arriving at <= 24 problems among which to choose. This problem is more about common sense than programming. Is this what monsoon meant when referring to it as TC-like?