Page 1 of 1
10671 - Grid Speed
Posted: Thu Jun 17, 2004 6:03 am
by Examiner
I have some difficulty with the second sample test case. My program reports it is possible to travel, and I have to agree!
My diagram looks like this
Code: Select all
8) 20 /--<--S
7) 10 |
6) 20 |
5) 10 |
4) 30 T--<--/
3) 20
2) 20
1) 10
10 20 20 30 10 20 10 10
1) 2) 3) 4) 5) 6) 7) 8)
Going along the route indicted above at maximum speed takes
- time
= 2 / 30 * 60 * 6 + 2 / 20 * 60 * 2
= 24 + 12
= 36,
10 <= time <= 39.
It seems possible to travel within the time limits. Anything wrong? Is it because the vertical time limits are put in reverse order?
Posted: Thu Jun 17, 2004 10:06 am
by Adrian Kuegel
Your diagram is wrong.
The values of the horizontal streets are given first, then the values of the vertical streets.
Code: Select all
8) 10 /--<--S
7) 10 |
6) 20 |
5) 10 |
4) 30 T--<--/
3) 20
2) 20
1) 10
10 20 20 30 10 20 10 20
1) 2) 3) 4) 5) 6) 7) 8)
so your route needs 48 minutes.
10671 - Grid Speed
Posted: Sun Aug 01, 2004 3:57 pm
by Ghost77 dimen
I think it is an ordinary dp problem, pass it without further doubt.
What I'd like to ask here is how to reduce the memory and time as
low as the top of the rankist.
Before posting, I tried to find somthing out.
Memory.
1. reduce the 2-dim mem to 1-dim mem. (mine: done)
2. Try linked list instead of ordinary array. (mine: no)
3. replace double with float? (mine: no)
Even used the above method, the mem still much higher than that,
besides you should risk something.
Time.
1. If you use the linked list, maybe the needed time will be a little lower.
2. the unit time (1min=?Ticks). I let the 1min=210Ticks
maybe someone have better way than this.
Any opinion is welcome. 