11079 - What's the Time?

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

Moderator: Board moderators

Post Reply
Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

11079 - What's the Time?

Post by Nazmul Quader Zinnuree »

Input will be terminated with N=0 and K=0.
The people who solved it. did you consider it? The sample does not say so.
How to solve it? I'm getting TLE, but no reason to get it. it may be WA. Someone plz clarify whether it is just some math or anything other to solve it?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: 11079

Post by sclo »

Nazmul Quader Zinnuree wrote:
Input will be terminated with N=0 and K=0.
The people who solved it. did you consider it? The sample does not say so.
How to solve it? I'm getting TLE, but no reason to get it. it may be WA. Someone plz clarify whether it is just some math or anything other to solve it?
I haven't solved it yet, but i think you have to simulate for lcm of periods, then find how many periods are needed, then solve for the time. It shouldn't tle because that number shouldn't be too big. Some optimization may be needed.

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree »

First, I simulate for the first period & for the last period. which loops for at most 30000. I think it must be done. coz, situation may change in every second in a period. Then, if it is possible to reach, then O(1) calculation, to get the time.

only three cases may occur:
i. reached within the first period.
ii. never reach.
iii. reached after a some period, but within the next one.

I matched all the cases.

Second, is there such a input so that

Code: Select all

desired amount < initial amount
?

Thanks.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

I think you should loop for at most 55440 (lcm of (p * 2)), because each period consists of actually 2 * p seconds before it repeats.
Then, my solution would handle such cases where the desired amount is smaller than the current amount. In this case I simply switch desired amount with current amount and change the sign of all capacity values, so then it becomes an equivalent problem with desired amount > current amount.

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree »

Thanks Adrian,
I have worked to minimize my time. & now I'm getting WA after 5.660 sec. So, would you please give me some tricky samples?

EfEr
New poster
Posts: 5
Joined: Thu Sep 22, 2005 8:56 pm
Location: Bucuresti, Romania
Contact:

Post by EfEr »

Adrian, I see you solution to this problem is the fastest. Did you use the approach of simulating over the LCM of the periods? I can't make it to run in the time limit.
Thanks.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

I don't understand sample case 2

Post by fh »

I don't understand sample case 2:

The input is

2 0
3 4
3 -3
100

Which mean there are:
1 inlet that will give 4 units in 3 secs and then idle 3 secs, etc..
1 outlet that will subtract 3 units in 3 secs and then idle 3 sec, etc..

So :
in time = 6, the processing unit will have 1 unit
in time = 12, the processing unit will have 2 unit
in time = 18, the processing unit will have 3 unit
in time = 24, the processing unit will have 4 unit
...
in time = 199, the processing unit will have 33.1667 unit

The minimum time according to the output is 199, but when you see above, in time = 199, the processing unit only has less than 34 unit (not even close to the desired amount 100).

Can anybody explain the sample case 2? how to get 199?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

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

Post by little joey »

No, your interpretation is wrong:
3 4 means the inlet will give 4 units per second during the first 3 seconds and then be idle for 3 seconds
3 -3 means the outlet will take 3 units per second during the first 3 seconds and then be idle for 3 seconds

So in each in each 6 second period:
during 1st second: gain is 4 -3 = 1 unit
during 2nd second: gain is 4 -3 = 1 unit
during 3rd second: gain is 4 -3 = 1 unit
during 4th, 5th and 6th second: idle

So the tank gains 3 units in every 6 second period.
After 198 seconds it has gained 198/6 * 3 = 99 units, and in the next second an additional one to make 100.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

[quote]Now a peculiar incident can occur
I code, therefore I am.

Post Reply

Return to “Volume 110 (11000-11099)”