Page 1 of 1
10898 - Combo Deal
Posted: Mon Aug 29, 2005 8:05 am
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 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
Posted: Mon Aug 29, 2005 9:52 am
your algorithm and coding-technique is exact equal to mine.
i used also table, 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 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
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.
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
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
hi ,i think this problem could easily to be solved by backtracking.
Posted: Tue Aug 30, 2005 2:59 pm
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
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
Posted: Mon Sep 26, 2005 2:45 am
There are more test cases than just one!
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
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
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
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.