10898 - Combo Deal

All about problems in Volume 108. 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
New poster
Posts: 2
Joined: Mon Aug 29, 2005 7:40 am

10898 - Combo Deal

Post by confused »

im getting TLE
my algo is as follows:
#assume in each case there are 6 items in combos. if a combo has less than 6 items then the remainings are 0. for example a combo with 3 items:
2 1 2 455
will be treated as
2 1 2 0 0 0 455

#treat each individual item as combo item. if item 1 costs 100 cents then treat it as
1 0 0 0 0 0 100
if item 3 costs 400 cents then treat it as
0 0 1 0 0 0 400
and so on....

#then i used a table with 6 dimension tab[10][10][10][10][10][10] and done something like "coin change" (0/1 knapsack)

this algo is of O(N^6)*(individuals + combos) ,N=10 and generates TLE. how its possible to solv it 00.000 sec....plz help
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of


Post by wook »

your algorithm and coding-technique is exact equal to mine.

i used also table[10][10][10][10][10][10], and dynamic programming

but my algorithm gots AC in 2.568 sec

so, if your source code is right, i think you won't got TLE.

however, the access like


is too slow :

a[132640] is more faster.

we can convert item's stat into 6-digited integer number;

i think (yet i didn't write code with this method) it will be more faster.
Sorry For My Poor English.. :)
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »


During contest I used the same algo as yours. This gave me Accepted in 0.8 sec, slightly less than the 1-second time limit.

Now I recoded my program and get Accepted in 0.03 sec. In my new program I used top-down approach, since it's obviously faster under the problem constraints. Think about that. :wink:

Btw, I think this line in prob description might also give you some idea to optimize your program:
Buying a combo is cheaper than buying its items individually.
Have fun~~

P.S. For those whose runtime exceeds 1 second (time limit during contest), please consider revising your code. It will get TLE during actual contest......
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

Post by Larry »

I did it naively memoization like you described and it runs in 0.5 seconds. I don't clear values for each query, only for each different set..
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

Post by oulongbin »

hi ,i think this problem could easily to be solved by backtracking.
New poster
Posts: 2
Joined: Mon Aug 29, 2005 7:40 am

Post by confused »

i have got acc at last :) using a linear array and some modification in 0/1 knapsack part. thanks everyone.
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

Post by tRipper »

I don't really think this is a hard problem. I've tried both bottom-up approach and memoization but the result is the same - WA. I just don't see the reason why.. Is there any tricky input?
Here's my source: a straightforward memoization

Code: Select all

    cut after AC
Last edited by tRipper on Mon Sep 26, 2005 9:03 pm, edited 1 time in total.
If I am out of my mind, it's all right with me.
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

There are more test cases than just one! :wink:
Problem statement wrote:The input contains several test cases, each of them with a menu and several orders.
Just put a while loop around the code.
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

Post by tRipper »

You are right, thanks. I don't read problem statements carefully enough. AC now
If I am out of my mind, it's all right with me.
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 10898 - Combo Deal

Post by jddantes »

What is the recommended way to scan doubles and typecast to int?

For example, if I'm reading 9.14, and I want it to be 914, I would do: scan as double, multiply that double by 100, then typecast to int.

Code: Select all

double f;
cin >> f;
int i = (int) f;
For this problem, I think one can do "%d.%d" to be safe, but I was wondering if the above approach is safe, precision-wise.

EDIT: This problem already gives it in cents, so I don't need to do the conversion. Still wondering what the safe way is, though.
Post Reply

Return to “Volume 108 (10800-10899)”