11883 - Repairing a Road

All about problems in Volume 118. 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
asif_iut
New poster
Posts: 16
Joined: Mon Nov 01, 2010 8:08 am

11883 - Repairing a Road

Post by asif_iut »

Code: Select all

cut after AC
Last edited by asif_iut on Thu Nov 11, 2010 5:05 pm, edited 1 time in total.

bm_anas
New poster
Posts: 10
Joined: Fri May 15, 2009 9:13 pm

Re: 11883

Post by bm_anas »

After a quick overview i found a bug to your problem. you take the input N and R and instead of taking R roads you are taking N roads of information.

However if you correct this i think you will get tle.......
In the warshall() function u used a loop
for( double x = 0.00; x <= v[z][l]; x += eps ) where your eps is 1e-6
this will lead to tle......

asif_iut
New poster
Posts: 16
Joined: Mon Nov 01, 2010 8:08 am

Re: 11883

Post by asif_iut »

thanks a lot bm_anas...i made a stupid error as well as reduced the eps to 1e-2 and AC!!!! thanks once again... :D

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Re: 11883

Post by rujialiu »

asif_iut wrote:thanks a lot bm_anas...i made a stupid error as well as reduced the eps to 1e-2 and AC!!!! thanks once again... :D
oops, this is not the intended way to solve this problem. The test cases are not strong enough but I admit that I have no idea how to generate good ones. Any one has some ideas?
:-)

asif_iut
New poster
Posts: 16
Joined: Mon Nov 01, 2010 8:08 am

Re: 11883

Post by asif_iut »

oops, this is not the intended way to solve this problem. The test cases are not strong enough but I admit that I have no idea how to generate good ones. Any one has some ideas?
what should have been the idea for solving this problem??

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Re: 11883

Post by rujialiu »

asif_iut wrote:what should have been the idea for solving this problem??
you may take a look at this: http://en.wikipedia.org/wiki/Ternary_search
:-)

bm_anas
New poster
Posts: 10
Joined: Fri May 15, 2009 9:13 pm

Re: 11883

Post by bm_anas »

I solved this problem using Dijkstra and Differentiation..... :D

Post Reply

Return to “Volume 118 (11800-11899)”