11566 - Let's Yum Cha!

All about problems in Volume 115. 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
Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:

11566 - Let's Yum Cha!

Post by Naani » Sun Dec 28, 2008 12:44 am

I am having hard time understanding the problem statement. From what i understand,

1) There are N+1 persons in total including you.
2) Each person can spend $x at max.
3) Each person spends the same amount of money(I don't understand what 'same amount of money to within one dollar' means).
4) Each person has a favor index for each type of dim sum.
5) Each person can have at most 2 dishes(Both may be of same type) and a maximum of 2 dishes of a particular type of dim sum can be ordered.

6) Tea charge is (N+1)*T dollars total or T dollars for each person. In addition to this, a service charge of 10% of combined cost of dishes and tea charge is charged. The total cost should not be more than the total amount of money the group
could spend.

7) We are asked to maximize the mean favor value of all the persons in the group(essentially total favor value).

Someone please elaborate on points 3 and 6.
I am signing an important document!

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11566 Let's Yum Cha!

Post by Robert Gerbicz » Sun Dec 28, 2008 1:09 am

Naani wrote:I am having hard time understanding the problem statement. From what i understand,
This problem's description is really sucks, if you understand it you can solve it less than 5 minutes.
You have lots of misinterpretaions, the problem in pseudocode is the following:

Code: Select all

max(i=1,K,order[i]*sum(j=1,N+1,fun[i,j]))/(N+1)
subject to 
0<=order[i]<=2 and integers (for i=1..K)
sum(i=1,K,order[i])<=2*(N+1)
let Q=sum(i=1,K,order[i]*cost[i])+T*(N+1) then Q+ceil(Q/10)<=(N+1)*x


Where cost[i] is the cost of the i-th meal
you order exactly order[i] from the i-th meal
fun[i,j] is the i-th meal's favour index of the j-th people
you pay altogether P=Q+ceil(Q/10), and this should be at most (N+1)*x.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11566 Let's Yum Cha!

Post by baodog » Tue Dec 30, 2008 1:25 am

Hi,

Any tricky datasets? I keep get wa. Thanks. Here is some of my IO.

Code: Select all

3 10 5 2
6 7 5 6 9
10 9 10 10 8
3 10 5 2
6 7 5 6 9
10 9 10 2 8
3 10 5 2
6 7 5 6 9
10 2 1 3 8
9 9 3 2
4 7 5 6 9
10 2 1 3 8
0 0 0 0

Code: Select all

16.00
14.00
13.50
10.20
Here is my code. It's just simple memorization. Thanks.

Code: Select all

Thanks! Fixed stupid bug!
Last edited by baodog on Tue Dec 30, 2008 10:22 am, edited 1 time in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11566 Let's Yum Cha!

Post by Robert Gerbicz » Tue Dec 30, 2008 9:37 am

In this line there's a mistake:

Code: Select all

    if(x % 10 == 0) return x; else return (x/10)+1;

kengood
New poster
Posts: 7
Joined: Fri Oct 31, 2008 6:25 am
Location: Hong Kong

Re: 11566 - Let's Yum Cha!

Post by kengood » Tue Dec 30, 2008 12:19 pm

more testcases for someone:

Code: Select all

3 9 3 2
4 7 5 6 9
10 2 1 3 8

3 10 5 2
6 7 5 6 9
10 9 10 10 8

3 100 1 2
1 10 10 10 10
2 10 10 10 10


9 4 3 2
4 2 0 0 0 0 0 0 0 0 0 
10 1 0 0 0 0 0 0 0 0 0

3 10 5 2
6 7 5 6 9
10 9 10 10 8
3 10 5 2
6 7 5 6 9
10 9 10 2 8
3 10 5 2
6 7 5 6 9
10 2 1 3 8


3 10 0 3
6 0 0 0 0
10 9 10 10 8
7 10 10 10 10


5 10 0 1
10 1 1 1 1 1 2

5 100 0 10
10 0 0 0 0 0 1
10 0 0 0 0 2 3
10 0 0 0 0 0 0
10 0 1 2 0 0 0
10 0 10 4 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 10 0 0 0
10 0 0 0 5 0 1
10 0 0 0 0 5 5


5 100 0 10
10 0 0 0 0 0 1
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 1


9 100 20 10
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8

9 100 20 12
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
7 5 2 5 8 4 8 1 4 8 1
3 2 3 7 10 3 4 9 3 7 9

9 100 20 20
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
6 7 0 9 4 9 8 9 5 4 9
7 1 7 1 6 2 8 9 2 8 8
8 1 7 7 7 1 5 5 8 1 2
5 4 10 1 8 6 10 2 9 0 8
3 5 0 10 4 3 6 5 8 2 6
1 7 7 7 2 0 1 1 5 0 5
2 0 7 6 2 6 3 8 7 9 2
5 6 4 7 9 0 5 2 1 6 3
2 7 7 5 9 6 4 8 4 3 0
3 2 3 7 10 3 4 9 3 7 9
0 0 0 0
output:

Code: Select all

17.00
16.00
40.00
0.20
16.00
14.00
13.50
38.50
2.33
16.00
0.67
96.60
104.00
112.60
enjoy your tea~

Azrael
New poster
Posts: 1
Joined: Sat Dec 27, 2008 4:12 pm

Re: 11566 - Let's Yum Cha!

Post by Azrael » Wed Dec 31, 2008 4:33 am

Problem, indeed, has quite a tricky statement :) I got AC, but I still do not understand about "(to within one dollar)" :)
During contest I used knapsack-style DP and got WA. Now I found bug and here it is:
For calculating maximal sum, which friends can spend on dim sums, I used next statement:

Code: Select all

int maxmoney = floor(double(x * (N + 1)) / 1.1) - (N + 1) * T;
Just a small fix and AC:

Code: Select all

int maxmoney = floor(double(x * (N + 1)) / 1.1 + 1e-6) - (N + 1) * T;
:roll:

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

Re: 11566 - Let's Yum Cha!

Post by Observer » Sat Jan 03, 2009 5:55 am

Azrael wrote:Problem, indeed, has quite a tricky statement :) I got AC, but I still do not understand about "(to within one dollar)" :)
:roll:
Oh for that part, I just copied from the problem statement of 10137 - The Trip...

The problem statement wasn't meant to be confusing. The tea charge and service change issues are real in many Chinese restaurants.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11566 - Let's Yum Cha!

Post by brianfry713 » Fri Jul 19, 2013 12:35 am

Input:

Code: Select all

3 9 3 2
4 7 5 6 9
10 2 1 3 8

3 10 5 2
6 7 5 6 9
10 9 10 10 8

3 100 1 2
1 10 10 10 10
2 10 10 10 10


9 4 3 2
4 2 0 0 0 0 0 0 0 0 0 
10 1 0 0 0 0 0 0 0 0 0

3 10 5 2
6 7 5 6 9
10 9 10 10 8
3 10 5 2
6 7 5 6 9
10 9 10 2 8
3 10 5 2
6 7 5 6 9
10 2 1 3 8


3 10 0 3
6 0 0 0 0
10 9 10 10 8
7 10 10 10 10


5 10 0 1
10 1 1 1 1 1 2

5 100 0 10
10 0 0 0 0 0 1
10 0 0 0 0 2 3
10 0 0 0 0 0 0
10 0 1 2 0 0 0
10 0 10 4 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 10 0 0 0
10 0 0 0 5 0 1
10 0 0 0 0 5 5


5 100 0 10
10 0 0 0 0 0 1
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 0
10 0 0 0 0 0 1


9 100 20 10
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8

9 100 20 12
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
7 5 2 5 8 4 8 1 4 8 1
3 2 3 7 10 3 4 9 3 7 9

9 100 20 20
9 2 4 10 1 9 1 5 9 6 4
1 3 5 5 5 5 6 3 10 4 9
4 2 2 1 0 8 3 3 4 8 1
4 7 10 3 1 1 7 6 8 8 1
4 6 3 2 2 9 2 6 7 1 8
10 8 9 7 1 3 7 4 9 9 7
7 3 5 1 2 1 8 2 4 4 4
6 6 2 7 2 3 5 0 5 4 7
7 10 5 3 6 2 7 4 4 7 7
7 5 2 5 8 4 8 1 4 8 8
6 7 0 9 4 9 8 9 5 4 9
7 1 7 1 6 2 8 9 2 8 8
8 1 7 7 7 1 5 5 8 1 2
5 4 10 1 8 6 10 2 9 0 8
3 5 0 10 4 3 6 5 8 2 6
1 7 7 7 2 0 1 1 5 0 5
2 0 7 6 2 6 3 8 7 9 2
5 6 4 7 9 0 5 2 1 6 3
2 7 7 5 9 6 4 8 4 3 0
3 2 3 7 10 3 4 9 3 7 9
0 0 0 0
AC output:

Code: Select all

17.00
16.00
40.00
0.20
16.00
14.00
13.50
38.50
2.33
16.00
0.67
96.60
104.00
112.60
Check input and AC output for thousands of problems on uDebug!

Rocker3011
New poster
Posts: 6
Joined: Mon Feb 17, 2014 12:21 am

Re: 11566 - Let's Yum Cha!

Post by Rocker3011 » Mon Sep 01, 2014 11:57 pm

hello i am having quite troubles to solve this problem, i believe i am missing some key data, i readed the various test datas on this section and very few of them give me wrong answer, the problem is that all are really long, so i really cant quite understand why my answer is not optimal.

This is my code:

Code: Select all

AC
silly mistake, remember that the number of dishes actually counts on the memoization :3

damien_g
New poster
Posts: 8
Joined: Sun Oct 05, 2014 5:53 pm

Re: 11566 - Let's Yum Cha!

Post by damien_g » Mon Dec 22, 2014 7:18 pm

This problem is really difficult (while the main idea of the knapsack behind it is still simple).

I spent a lot of time on it, but it's AC now ! :)

If you have difficulties, look at Azrael's answer (the 1e-6 trick).
Without it, my code gives WA, but with it it's finally AC.
This damn floating point precision !

Try this, at least if your answers to the I/O brianfry provided are all right.

abhisek104
New poster
Posts: 1
Joined: Sun Feb 15, 2015 11:30 am

Re: 11566 - Let's Yum Cha!

Post by abhisek104 » Wed Feb 15, 2017 1:29 pm

I really can not understand the problem statement. Can any one please tell me what it's trying to say and how the sample output is 16.00

An explanation of how that output came is really appreciated

Post Reply

Return to “Volume 115 (11500-11599)”