10280 - Old Wine Into New Bottles

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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

Post by cyfra » Mon Jun 24, 2002 4:30 pm

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
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

10280---Old Wine into New Bottles TLE

Post by hujialie » Mon Jan 19, 2004 3:37 pm

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

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet » Sat Jan 31, 2004 2:19 pm

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

Post by titid_gede » Sun Feb 01, 2004 10:53 am

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

Post by titid_gede » Fri Mar 12, 2004 5:43 pm

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

Post by Observer » Tue Apr 13, 2004 6:41 pm

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

Post by titid_gede » Fri Apr 30, 2004 12:13 pm

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

Post by lghmf » Fri Apr 15, 2005 6:13 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Apr 16, 2005 9:13 am

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

Post by minskcity » Tue Jan 17, 2006 8:18 pm

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?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Jan 17, 2006 8:26 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

Post by sonyckson » Sat Nov 14, 2009 3:54 am

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

Post by chengouxuan » Sat Feb 19, 2011 10:31 am

how to solve it using dijkstra's algorithm?

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

Re:

Post by lighted » Tue Jul 08, 2014 2:58 pm

Got acc! :lol: :lol: :lol:
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

Post by just_yousef » Fri Jul 25, 2014 2:29 pm

Can You Please provide some test cases ??

Post Reply

Return to “Volume 102 (10200-10299)”