http://codeforces.me/problemset/problem/446/A
Can anyone help with the approach to this problem. Read the tutorial but wasn't able to get the idea.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
http://codeforces.me/problemset/problem/446/A
Can anyone help with the approach to this problem. Read the tutorial but wasn't able to get the idea.
Name |
---|
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://codeforces.me/contest/447/submission/9161790 I think you will understand that. If you have any doubts/require some more examples comment below.
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:
for any i we can change A[i] to a suitable integer to construct a segment with I[i-1] + 1 length.
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.
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