fight_back's blog

By fight_back, history, 3 months ago, In English,

Hi guys,

I was trying the problem http://www.spoj.com/problems/LASTSHOT/ using DFS and getting continuous WA. Here are two ways(with little difference) I tried https://ideone.com/zIFdC0(WA) and https://ideone.com/ipq4lw(TLE). Can anyone please say where am I possibly getting wrong ? And what can be a better(or faster) solution. How can this be done with DP , as mentioned in the comments ? Thanks, in advance. :)

HAPPY CODING! :)

 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello there,

Try the following test case —

5 5

1 2

1 3

4 3

4 5

5 2

The expected answer is 4, but your program produces 3.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your mistake is that you did not reset your visited vector for every dfs. I modified your code to correct this error and it ran successfully.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I remember this problem having weak test cases. It did allow an O(N^2) solution to pass, though i doubt if that was the intended solution!