## 10280 - Old Wine Into New Bottles

Moderator: Board moderators

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

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

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

### 10280---Old Wine into New Bottles TLE

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

Retired from SJTU Accelerator 2004

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
Use dijkstra's algorithm to solve this.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
why djisktra? i did not see that way.
thanks,

titid
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
isnt it a subset sum problem?

regards,
titid
Kalo mau kaya, buat apa sekolah?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
i'm not sure there exist DP algo which solve this prob in reasonable time. can anyone give another hints?
Kalo mau kaya, buat apa sekolah?

lghmf
New poster
Posts: 3
Joined: Fri Apr 15, 2005 3:55 pm

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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
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.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

### 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% ).

chengouxuan
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?

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re:

Got acc!
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 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.
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

just_yousef
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 ??