Any one know why my solution is wrong
DIST_VALS Problem - CodeChef (problem)
CodeChef: Practical coding for everyone
My idea
for each a[i]/cur
calculate the distance of max(first) and closest second max(second) in range [i+1, n-1], and the distance is the all the subarrays valid for a[i]/cur, add to result
I use a treemap to maintain the order of all values in range[i+1, n-1]
for closest second max in range [i+1, n-1], I did a range binary search
Your approach is correct. You are on right track. But, Taking second max in range [i+1,n-1] isn’t sufficient. You also need to remove the second max and then iterate the process again.
lets say , for some x, where x belongs to [i+1,n-1], we found second max as a[x];
now we need to reiterate the same process from [i+1,x-1] . we also need to consider the subarrays which are starting at index ‘i’, but ending before second max index ‘x’ .
that part seems to be missing.
This should be iterative ( or recursive process ) . because could happen n-i-1 times to be precise.