OJ Board

A little hint: You should be able to answer each query in O(2^W) based on the result of a DP, where W is the number of coins, which is always 4 in this problem.

i.e. After running a DP, you should answer each query in almost constant time.

Adrian Kuegel wrote:... note that channels are unidirectional (this is also written in the problem statement). ...

Yes, I noticed that, but my sucking mind somehow translated it to "undirected".

Two clarifications requested: Would there be more than one edge connecting the same pair of stations? i.e. Are the following valid test cases? 2 2 2 1 2 1 1 2 1 2 2 3 1 2 1 1 2 2 0 0 0 ... print all pairs of stations (in ascending order) ... This is somehow ambiguous to me. Ascending order of the ed...

Oh. it turns out to be a problem of my own machine. (I still don't know the prblem though.)
Everything is fine after I switch to another machine to register.

Hmm...
Just tried... Still got the same message

I didn't participate in UVa's online contests for a while and just realised there is a system migration. I tried to register (with FireFox 2.0.0.4) in this page: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_comprofiler&task=registers But I got this messgae after click the "...

Mine is O(n^4). Although it's just marginally passed within 10 seconds.

Hmm.. your answer is a little confusing to me...
So there could be duplicated points, right?
If so, what should be the output of this case? 1? or 2?

Clarification: Can I simply assume that all the input points are distinct?

DJWS wrote:What is the answer of this case:

Code: Select all

5
RRRRR
RRRRR
..P..
.....
.....

Is it 1? Or 2?

2

[quote]Now a peculiar incident can occur

Currently the dp table si 2*60*60*60 (it's 4 parameters: t,x,y,z) If we can remove 't', then the table is 60*60*60 (absolutely twice faster). The memory is absolutely reduced by half but the run time is not necesarily absolutely twice faster. The recurence for the dp[2][60][60][60] looks quite simp...

Is there away to only use 3 parameters instead of 4? Yes, and it's actually possible to reduce further to 2 dimensional array. I saw in the problem ranklist, there are people who AC in 2.xxx secs.. it's about twice as fast as the DP talked above and I think because their DP doesn't have the 't' par...

Nazmul Quader Zinnuree wrote:I have sent my code to you by PM. Coz, your approach seems to be like mine. Would you plz check my code, why I'm getting WA.

As mentioned in an earlier post, it's really easy to generate some random input for this problem to test for yourself.

If you start at station 4, you have to go back to station 4 to finish the lap.