Page 1 of 1

10898 - Combo Deal

Posted: Mon Aug 29, 2005 8:05 am
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

algo

Posted: Mon Aug 29, 2005 9:52 am
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

a[1][3][2][6][4][0]

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.

Posted: Mon Aug 29, 2005 12:00 pm
by Observer
Hi,

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

Posted: Mon Aug 29, 2005 3:54 pm
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..

Posted: Tue Aug 30, 2005 5:15 am
by oulongbin
hi ,i think this problem could easily to be solved by backtracking.

Posted: Tue Aug 30, 2005 2:59 pm
by confused
i have got acc at last :) using a linear array and some modification in 0/1 knapsack part. thanks everyone.

Posted: Sun Sep 25, 2005 11:42 am
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

Posted: Mon Sep 26, 2005 2:45 am
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.

Posted: Mon Sep 26, 2005 9:02 pm
by tRipper
You are right, thanks. I don't read problem statements carefully enough. AC now

Re: 10898 - Combo Deal

Posted: Thu Jun 18, 2015 8:35 am
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;
f*=100;
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.