monera's blog

By monera, 10 years ago, In English

http://mirror.codeforces.com/problemset/problem/446/A

Can anyone help with the approach to this problem. Read the tutorial but wasn't able to get the idea.

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

| Write comment?
»
10 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

I will try to explain the logic with an example : Consider the given case :
6
7 2 3 1 5 6

Step1 : Make the subegments from the given sequence such that each segment is strictly increasing.i.e the required subsegments are : {7},{2,3},{1,5,6}

Step2 : iterate over all the subsegments by taking two consecutive subsegments at a time i.e from the above input we will get two cases : {7},{2,3}
{2,3},{1,5,6}
Now taking {7},{2,3} : we can observe that the maximum required subsegment length we can form is 3 i.e by changing 7 from first segment to 1 we can get {1,2,3}. Now taking {2,3},{1,5,6} : here in this case the maximum required subsegment length we can form is 5 i.e by changing 1 from second segment to 4.so the new subsegment formed is {2,3,4,5,6} of length 5. So the final answer is max(3,5)=5.

Now let us take another example :
4
1 1 1 1

From step1 ,we can form subsegments like : {1},{1},{1},{1}

Step2 : iterate over all the subsegments by taking two consecutive subsegments at a time i.e from the above input we will get two cases : {1},{1} -> considering 1,2
{1),{1} -> considering 2,3
{1},{1} -> considering 3,4
Now taking {1},{1} : we can observe that the maximum required subsegment length we can form is 2 i.e by changing 1 from first segment to 0 we can get {0,1}.OR 1 from second segment to 2, we can get {1,2}.Any how you can get max length as 2. Now the another 2 cases are similar to first So final answer is max(2,2,2)=2

Note: Try to think how this approach works and also try to implement the logic.In case you cannot check my code : http://mirror.codeforces.com/contest/447/submission/9161790 I think you will understand that. If you have any doubts/require some more examples comment below.

»
10 years ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

Lets say given array is A[].

first of all let say I[] and D[] are two arrays.

I[i] = tells you the length of the longest increasing sub segment you can have which ends at i(index).

D[i] = tells you the length of the longest decreasing sub segment which starts at i.

For example :

given array : 7 2 3 1 5 6

I[i] : 1 1 2 1 2 3

D[i] : 1 2 1 3 2 1

you can construct I[] and D[] in O(n). Trivial cases:

  1. for any i we can change A[i] to a suitable integer to construct a segment with I[i-1] + 1 length.

  2. again for any i we can change A[i] to a suitable integer to construct a segment with D[i+1] + 1 length.

remember we can change A[i] to any integer positive or negative.

  1. Now, again we can construct increasing segment by changing i and thus joining segments ending at (i-1) and starting at (i+1) with length I[i-1]-S[i+1] + 1.

So our answer is the overall maximum length.

for the 3rd case : when changing a element i we have to check whether we can change A[i], as A[i] should be A[i-1]<A[i]<A[i+1].

My code : code