### 11372 - Arranging a Contest

Posted:

**Sat Dec 29, 2007 7:07 pm**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.

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=41&t=26747

Page **1** of **1**

Posted: **Sat Dec 29, 2007 7:07 pm**

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

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

I can't comment on that. I'm not a Topcoder member.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...

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?

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

are you sure you are finding lexicographically smallest solution?jah wrote:Could you post some test case, I don't know what's wrong with my code.

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?

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

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.

Could you give an explanation about this "brute-force" method.Darko wrote:Yes, I realized later that only 12 of each are relevant, so it can be easily brute-forced.

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?The dimension that I used for dp was ::

int dp[201][7][3][3][3][2][2];

Is there any better way?

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.

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

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

Posted: **Sat Jan 05, 2008 1:14 am**

I think algorithm is very easy , but my brute force solution is more than 300 lines and I was writing it about 1 hour...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.

Posted: **Thu Dec 03, 2009 8:31 pm**

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?