10280 - Old Wine Into New Bottles

[cyfra]

Hi!

I wonder how it is possible to solve this task....

Because DP will need too much memory (1,000,000) litres = (1,000,000,000) mililitres and it is too much.

And I wonder if there is any good algoritm that can solve this task fast ..

Thanks in advance

[hujialie]

Hi.
I am in difficulty solving this problem, keep
receiving Time Limet Exceeded.Can anyone
give a hint?

Thanks in advance.

[makbet]

Use dijkstra's algorithm to solve this.

[titid_gede]

why djisktra? i did not see that way.
thanks,

titid

[titid_gede]

isnt it a subset sum problem?

regards,
titid

[Observer]

The first line of input contains two integers: the amount of wine to be bottled (in litres, between 0 and 1,000,000) and the number of sizes of bottles (between 1 and 100). For each size of bottle, one line of input follows giving the minimum and maximum capacity of each bottle in millilitres. The maximum capacity is not less than 325 ml and does not exceed 4500 ml. The minimum capacity is not less than 95% and not greater than 99% of the maximum capacity. You may assume that an unlimited number of each bottle is available.

After reading the input description, I have a feeling that the information bolded above may help us to deal with large cases. (Notice the great difference between 1,000,000,000mL[max. vol. of wine] and 4500mL[max. capacity of a bottle])

Can anyone who got accepted in this problem verify this for me? Thanks!

[titid_gede]

i'm not sure there exist DP algo which solve this prob in reasonable time. can anyone give another hints?

[lghmf]

how solve it ?

i'd try to think DP...but it's hard to me..

if i use my DP algo, It'll exceed memory and time limit..

because the amount of wine to be bottled is 1000 000 000 ml..

[little joey]

Say, you have a bottle that can contain a minimum of 950 ml and a maximum of 1000 ml.
What are the minimum and maximum amounts you can store in 2 bottles? And in 19 bottles? And 20?
Do you notice something when looking at the numbers?

[minskcity]

Why does that help? I mean, even if for all bottles min_capacity == max_capacity, it's Subset-Sum on 10^9... Could you give more hints?

[little joey]

But min_capacity is never equal to max_capacity (see the description) and that's why this problem is solvable. Did you work out the example I gave? It should provide you with all the information you need.

[sonyckson]

I havent code it yet, but I think its also solvable ( althougth not too efficient ) with max = min...

If you have <= 5000 bottles ( each with no empty space, just giving you the integer amount of wine they can take ), and you consider a matrix mat[5000], you can get
in O(n^2) which amounts of wine mod 5000 you can get. And if im not mistaken thats enough to see with all the bottles how much litres you can
get ( without passing the limit ).

You can considrer having <= 5000 bottles, because each bottle has a maximum of 4500 litres, and then you can not have bottles with size > 4500...
so if you have a bottle with min= 4000 and max = 4005, you can consider having 6 different type's of bottle's: 4000, 4001, 4002, 4003, 4004 and 4005.

Im not sure about all this, and seeing the best times, there should be better solutions ( considering the fact that little joy said about 99% ).

[chengouxuan]

how to solve it using dijkstra's algorithm?

[lighted]

Got acc!

Say, you have a bottle that can contain a minimum of 950 ml and a maximum of 1000 ml.
What are the minimum and maximum amounts you can store in 2 bottles? And in 19 bottles? And 20?
Do you notice something when looking at the numbers?

This gave me idea of dealing with large cases.

The maximum capacity is not less than 325 ml and does not exceed 4500 ml. The minimum capacity is not less than 95% and not greater than 99% of the maximum capacity.

This gives constraints of large cases.

A little math to find bound of large cases which we can calculate in O(1).
Smaller amounts can be calculated by DP.

[just_yousef]

Can You Please provide some test cases ??