Hello . I have recently seen a question and I want your help ....
We have a sequence of numbers . Each of them is 1 or -1 .
In every second we can choose a contiguous subsequence of them and do
the operation for each of them : a[i] = a[i] * -1
The question is that given the sequence what is the minimum time needed to transform all of the numbers to 1 ?
Example
Input :
6
1 -1 -1 1 -1 1
Output :
2
I think that the answer is the number of segments consisting of -1.
ignore
There's a useful trick for this type of problems.
Let's define a new array
, where A[0] = A[N + 1] = 1 by definition. Notice that multiplying any segment [a, b] by -1 only causes B[a] and B[b + 1] to be multiplied by -1, and since A[] can be recovered from B[] uniquely, making all B[i] = 1 is the same as making all A[i] = 1.
Since we can pick a, b arbitrarily in each step, we only need
steps, where x is the number of -1s in B[] (notice that it's always even). And yes, that's the number of segments of -1s in A[].
Can anyone tell me how can I terminate my code automaticly before exceed the time limit?
I know it is far from this blog but I do not want to open a blog for this.