10280  Old Wine Into New Bottles
Moderator: Board moderators
10280  Old Wine Into New Bottles
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
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
10280Old Wine into New Bottles TLE
Hi.
I am in difficulty solving this problem, keep
receiving Time Limet Exceeded.Can anyone
give a hint?
Thanks in advance.
I am in difficulty solving this problem, keep
receiving Time Limet Exceeded.Can anyone
give a hint?
Thanks in advance.
Retired from SJTU Accelerator 2004

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
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])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.
Can anyone who got accepted in this problem verify this for me? Thanks!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
10280 Old Wine Into New Bottles , help me, please..
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..
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
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
Re: 10280  Old Wine Into New Bottles
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% ).
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% ).

 New poster
 Posts: 10
 Joined: Wed Dec 15, 2010 12:32 pm
Re: 10280  Old Wine Into New Bottles
how to solve it using dijkstra's algorithm?
Re:
Got acc!
A little math to find bound of large cases which we can calculate in O(1).
Smaller amounts can be calculated by DP.
This gave me idea of dealing with large cases.little joey wrote: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 gives constraints of 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.
A little math to find bound of large cases which we can calculate in O(1).
Smaller amounts can be calculated by DP.
Last edited by lighted on Fri Jul 25, 2014 3:42 pm, edited 1 time in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

 New poster
 Posts: 50
 Joined: Tue Dec 17, 2013 11:01 pm
Re: 10280  Old Wine Into New Bottles
Can You Please provide some test cases ??