10898 - Combo Deal

[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

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

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

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

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

[oulongbin]

hi ,i think this problem could easily to be solved by backtracking.

[confused]

i have got acc at last using a linear array and some modification in 0/1 knapsack part. thanks everyone.

[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

[Martin Macko]

There are more test cases than just one!

The input contains several test cases, each of them with a menu and several orders.

Just put a while loop around the code.

[tRipper]

You are right, thanks. I don't read problem statements carefully enough. AC now

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