11372 - Arranging a Contest

[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.

[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...

[Observer]

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.

[sohel]

The dimension that I used for dp was ::
int dp[201][7][3][3][3][2][2];

Is there any better way?

[jah]

Could you post some test case, I don't know what's wrong with my code.

[fpavetic]

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?

[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?

[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

[Darko]

Yes, I realized later that only 12 of each are relevant, so it can be easily brute-forced.

[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.

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?

[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.

[sohel]

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.

[Giorgi]

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...

[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?