11372 - Arranging a Contest

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

11372 - Arranging a Contest

Post by Observer » 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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » 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...

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » 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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » 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?

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Post by jah » Sat Dec 29, 2007 10:08 pm

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

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

Post by fpavetic » 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?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » 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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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.

black.phoenix
New poster
Posts: 8
Joined: Sun Aug 06, 2006 3:07 am

Post by black.phoenix » 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.
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?
You do not know whether the path is easy or hard unless you walk through it.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » 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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » 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.

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Re: 11372 Arranging a Contest

Post by Giorgi » Sat Jan 05, 2008 1:14 am

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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 11372 - Arranging a Contest

Post by serur » 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?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Post Reply

Return to “Volume 113 (11300-11399)”