Cops and the Thief Devu

problem link : COPS Problem - CodeChef

solution : CodeChef: Practical coding for everyone

why my answer yields WA… I have checked all boundary and possible cases too…Please help.

@ruhul1995
Your code gives output 0 for this case

1

1 2 3

96

It should be

89

Don’t make it complex by using so many conditions and it can be simply solved in nearly O(n) time.

Simple Approach:

maxDis = x*y;
vis[101] → Array to keep track of visited positions.
Just run a loop over Array A and run two loops inside:
current_pos = a[i] (Say, i as your iterator)

  1. loop(j) from current_pos to current_pos+max_dis and while j <= 100
    Mark the vis[j] = 1
  2. loop(j) from current_pos to current_pos-max_dis and while j >= 0
    Mark the vis[j] = 1

Loop over your vis array and count those positions which are 0. This is your final answer.

Here is my Solution : Link