votev's blog

By votev, history, 6 weeks ago, In English

We are given an array A of length N <= 500000.

We need to find the smallest valid number. A number V is valid if the following conditions are met:

  • in the prefix of length V of the array, atleast one number >= V must appear.
  • If we colour a window of length V starting from each position of appearance of a number >= V, all the elements except possibly some prefix are coloured. In other words, for all 'i' such that A[i] >= V, we colour all elements A[i], A[i+1], ..., A[min(i+V-1, N-1)]. After all such colouring operations, the entire array except possibly some prefix of the array should be coloured.

Any help would be appreciated, thanks a lot!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by votev (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by votev (previous revision, new revision, compare).