Chef Likes Good Sequences Codechef October Lunchtime Problem solution

 Chef Likes Good Sequences Codechef October Lunchtime Problem solution -

Lets read the problem statement carefully. 
Problem statement- 

Chef calls a sequence good if it does not contain any two adjacent identical elements.

Initially, Chef has a sequence a1,a2,,aN. He likes to change the sequence every now and then. You should process Q queries. In each query, Chef chooses an index x and changes the x-th element of the sequence to y. After each query, can you find the length of the longest good subsequence of the current sequence?

Note that the queries are not independent.


  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains two space-separated integers N and Q.
  • The second line contains N space-separated integers a1,a2,,aN.
  • Q lines follow. Each of these lines contains two space-separated integers x and y describing a query.


After each query, print a single line containing one integer ― the length of the longest good subsequence.


  • 1T5
  • 1N,Q105
  • 1ai109 for each valid i
  • 1xN
  • 1y109


Subtask #1 (35 points): Q=1

Subtask #2 (65 points): original constraints

Example Input

5 2
1 1 2 5 2
1 3
4 2

Example Output


Chef Likes Good Sequences Codechef October Lunchtime Problem solution


First of all do not confuse with subarray and subsequence. 
subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A subarray will always be contiguous but a subsequence need not be contiguous.

It's easy problem follow some simply step-
step 1- Calculate the longest subsequence in the initial array without changes.

Now think that if you made changes at xth position of array it will affect initial length if y!= a[x]
if y!=a[x] there occur some cases  for which initial length may affect. You have to observe these cases and handle initial length accordingly. 

  • Case 1 : (a_x == a_{x-1}) and (a_x == a_{x+1}), then answer will increase by 2 as it will make 1 segment into 3 segments.
  • Case 2 : (a_x \neq a_{x-1}) and (a_x == a_{x+1}), then the answer will increase by 1 as earlier a_x == a_{x+1} and y will introduce an extra segment. If y = a_{x-1} then we will reduce the answer by 1 as earlier we added 1 as changing to y increased the segment count but now it will be merged with previous segment. Example : let a_x = a_{x+1} = 1 and a_{x-1} = 2, so If y = 3 answer will increase by 1, and if y = 2 then there will no change to the answer.
  • Case 3 : (a_x == a_{x-1}) and (a_x \neq a_{x+1}), similar to above case, we will increase the answer by 1. if y=a_{x+1} then we will reduce the answer by 1.
  • Case 4 : (a_x \neq a_{x-1}) and (a_x \neq a_{x+1}), then if y=a_{x-1} we will reduce answer by 1. if y = a_{x+1} we will reduce answer by 1.(Note that you might reduce the answer by 2 when y=a_{x-1}=a_{x+1}).

Must join my telegram channel -https://t.me/competitiveProgrammingDiscussion

Follow my code - 


all right reserved @technicalkeeda.in. Powered by Blogger.