Hi everyone, Infosys conducted the Hackwithinfy contest which just concluded yesterday. I found some questions very interesting but was not able to figure out solutions for those. Please share possible approaches or solutions for these. Any help will be appreciated.

Question 1

You are given 2 numbers N and M and an array of sizes N. A triplet is defined if it satisfies ANY ONE of the following conditions:

1. All numbers in the triplet are the same (Eg. {1, 1, 1})

2. The numbers are consecutive (Eg. {1, 2, 3})

Given the array, find the maximum number of triplets that can be formed. All elements in the array are <= M.

NOTE: Each element of the array can only be part of 1 triplet.

Constraints:
1 <= N <= 10^5
1 <= M <= 10^4
1 <= arr[i] <= M

Sample Input : 
4 2
1 2 2 2
Output : 1
Explanation: Only one triplet can be formed {2,2,2}

Question 2

You are given an array A of N elements. You need to divide the array into 4 non-empty contiguous subsequences B, C, D, E by making 3 cuts to it. Let P, Q, R, S be the sum of elements in the new arrays B, C, D, E.

Your task is to find the minimum possible absolute difference of the (maximum and minimum among P, Q, R, S)

Constraints:
4 <= N <= 10^5
1 <= A[i] <= 10^4

Sample Input : 
10
10 71 84 33 6 47 23 25 52 64
Output: 36

Question 3

(I am presenting the simplified form) We are given K arrays which are all permutations of numbers from 1 to N. The ith array represents the order of N people coming to a theatre on some ith day (1 <= i <= K). You have to find the maximum size of the group of people that come to the theatre in the same sequence each of the K days.

Constraints:
1 <= N <= 1000
1 <= K <= 10
1 <= a[i][j] <= N

Sample Input:
4 (this is N)
3 (this is K)
1 3 2 4 (day 1)
1 3 2 4
1 4 3 2 (day k)

Sample Output:
3
Explanation:
We can see people 1, 3, 2, they come in the same sequence all the days. So the answer is 3.

Note: This is a compilation of questions that were asked to different participants.

Thank You.