### ChitreshApte's blog

By ChitreshApte, history, 5 weeks ago,

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.

• +32

 » 5 weeks ago, # | ← Rev. 4 →   +17 Problem 1 is similar to this: JongmahProblem 3 is similar to this: Gargari and Permutations
•  » » 5 weeks ago, # ^ |   0 Thank You
•  » » 5 weeks ago, # ^ |   +3 Someone knows how to solve b ?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 Iterate for the 2nd cut. Let's say the second cut is at the ith index. Now using binary search on prefix sum array, find the best cut for array[0:i] and using binary search on suffix sum array, find the best cut for array[i:n]. For each i from 0 to n-1, we use binary search two times, so the total time complexity is O(nlogn).Do comment if you feel something is wrong.
•  » » » » 5 weeks ago, # ^ |   0 Nice approach ! Thanks :)
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 find the best cut for array[0:i] what condition will you use to find the best j in the prefix ?
•  » » » » » 5 weeks ago, # ^ |   -9 Choose the prefix whose sum is closest to sum(array[0:i])/2
•  » » » » » » 5 weeks ago, # ^ |   +2 I can not understand, like doing so will minimize the difference between P and Q. And if we do the same with the suffix. Like chose the closest to sum(array[i + 1 : n]). Then this will minimize the difference between R and S. But how does this minimizes the difference between max{P, Q, R, S} and min{P, Q, R, S}. P, Q, R, S is the individual sum of array partition as mention in the problem.
•  » » » » » » » 5 weeks ago, # ^ |   0 Let the best cut for the left array according to my algorithm be P and Q. Let the actual best cut be P' and Q'. Let P <= Q and P' <= Q'. We can show that |P-Q| <= |P'-Q'|. Using P+Q = P'+Q' and |P-Q| <= |P'-Q'|, we can conclude P' <= P and Q' >= Q. Now whatever be the value of R and S, max{P, Q, R, S}-min{P, Q, R, S} <= max{P', Q', R, S}-min{P', Q', R, S}.Not a proper proof but hope it helps
 » 5 weeks ago, # |   +3 2) I'm a bit skeptical about this, but it seems like a 3-pointers problem.3) I believe that this is just the longest common subsequence of all $a_i$. That should run in $O(KN^2) \approx 10^7$.
 » 5 weeks ago, # |   0 Your slot was yesterday? My slot was on 7th May and problem 1 on my set was exactly same as yours. That's so unfair to those who had the earlier slots.
•  » » 5 weeks ago, # ^ |   0 It was not unfair. That problem is from the 7th May slot only, not from yesterday.
 » 5 weeks ago, # |   +12 Giving problems of rating 2200+ srsly? Infosys? .. ;(
•  » » 5 weeks ago, # ^ |   +4 Sabke bhao badh gaye hain.
 » 5 weeks ago, # |   0 i solved 2 out of 3.What are the chances of me getting selected?
•  » » 5 weeks ago, # ^ |   0 with in few days you will receive mail "YOU Cleared round 1".but solving 2 ques in this year hackwithfy its really good. keep it up!
 » 5 weeks ago, # |   +3 Can someone tell the algorithm for solving problem 3? I currently have $O(KN^K)$ solution.
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   -16 3rd Problem could be done in O(K*N*N)Let's Define a matrix Pos[i][j] which will tell the position of Number 'j' in array 'i'.Now we will find the number of pairs (a,b) such that 'a' occurs before 'b' in all K arrays. Let this count be Cnt.The above could be achieved using Naive approach i.e., iterate for each pair (a,b) [this would take O(N*N) ] and then check for each array 'i' if Pos[i][a] < Pos[i][b]. If this is true for all 'i' in [1,K], then increment Cnt.Now upon observing we can realize that Cnt >= (ans*(ans-1))/2. So just find the closest 'ans' such that above equation is satisfied.Please Let me know if the above approach is incorrect.UPDATE : It's incorrect
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Can't we just fix an array among all given k arrays, let say the first one.Then we find out LCS with all the remaining k-1 arrays in O(N*N).And the minimum LCS will be the answer?I am just asking if it can work or it will fail?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 I don't think your approach using LCS is correctCase : N = 4, K = 3Array 1 : 1 2 3 4Array 2 : 1 4 2 3Array 3 : 2 3 4 1Your approach would give 3 but correct answer is 2.
•  » » » » » 5 weeks ago, # ^ |   0 Ah, I see!Thank you. :)
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Consider this test case: 5 3 3 2 1 4 5 5 1 3 2 4 5 2 3 1 4 Clearly the answer is 2[1, 4]. However, Cnt = 3,[(1, 4), (2, 4) and (3, 4)]. So, from your logic, answer should be 3. So, this is also wrong.
•  » » » » 5 weeks ago, # ^ |   0 But can't we do one thing we find out lcs of first two then Find lcs of the previous lcs and next array
•  » » » » » 5 weeks ago, # ^ |   +11 Do you think LCS is unique?
•  » » » » » » 5 weeks ago, # ^ |   +3 oh yes my bad
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 After getting the matrix of positions, we can consider it as tree edges and then try to find the height of the tree for every number x as the root of the tree. The maximum of all the heights will be the answer.Generating the root has N options and doing a depth traversal from each chosen root to find tree height will be O(N), so the time complexity (for this tree process) will be O(N²). However the matrix creation takes O(K*N²) time. The overall complexity will be O(K*N²).Please let me know if this is incorrect.Update: I just found out that this problem is already available here and has the similar solution as what I tried to convey.
•  » » 5 weeks ago, # ^ |   +12 Link to my code
 » 5 weeks ago, # |   +4 Isn't problem 3 LCS?
•  » » 5 weeks ago, # ^ |   0 Yes, it is LCS, but we have multiple arrays of which we want LCS.
 » 5 weeks ago, # |   +7 I wonder, what does Infosys want to prove by giving 2000+ rated problems in the contest. It isn't like they are going to give some 20 lpa. They would give a mere 5-7 LPA and they want red coders in their company lol.
•  » » 5 weeks ago, # ^ |   +2 .
•  » » 5 weeks ago, # ^ |   +2 yeah i dont get it either, wallmart labs, microsoft, etc had easier questions, i went through some of the questions my friend told me after her assessment and it was a day before op's assessment and boy was i shocked, it was definitely 2200+ questions, i dont get why would anyone who can solve such questions join infosys xD
•  » » 5 weeks ago, # ^ |   +4 You should keep in mind that it wasn't a placement round, it was a HACKATHON !!, and hackathons are meant to be challenging.
•  » » » 5 weeks ago, # ^ |   0 It was indeed a placement round. Only 108 students get selected for hackathons. Rest upto rank 500, students get pre-placement interview for power programmer role(8 lpa) and upto 2000, system engineer specialist role(5 lpa).
•  » » » » 5 weeks ago, # ^ |   0 It is actually a hackathon only, but they offer jobs to top performers
 » 5 weeks ago, # |   +18 wtf is this??.. If someone can solve question of rating 2200 ,why will they go to infosys?
 » 5 weeks ago, # |   0 I had different questions. Did someone get the matrix question in which we had to throw out garbage?
 » 5 weeks ago, # |   +3 I solved problem 2 but I am not sure if it is correct or not.pre[i][0] = sum of subarray elements starting from o to l where(l < i)pre[i][1]= sum of subarray elements starting from l + 1 to isuch that absolute difference between pre[i][0] and pre[i][1] is minimum.also calculated suf[i][0], suf[i][1] for subarray from i to n — 1.link to my code
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 Great, it makes sense to me. My implementation. Nothing different but I have reused the logic to make prefix and suffix arrays.UPD: This solution got accepted hereThanks palsoumyadeep and vkgainz
 » 5 weeks ago, # |   +16 2 is direct copy of this AtCoder problem (they even used the same variables lmao)
»
5 weeks ago, # |
0
My Problems 10 May, 2021
 » 5 weeks ago, # | ← Rev. 2 →   0 ANY HELP WILL BE APPRECIATED, THANKS IN ADVANCE :)ANOTHER QUESTION FROM HACKWITHINFY 2020 Problem DIFFRENT ARRAYSProblem StatementYou are given an array of size N. At position i, the array has a number of i (eg: A[i] = i).Now you want to perform exactly M swaps. In one swap you will sect two distinct positions and swap the numbers present on these positions.Your task is to calculate the number of different arrays you the end. Since the answer can be very large, return is to modulo(10^9 + 7).Note : Array is following 1-Based Indexing. Input FormatThe first line contains an integer, N, denoting the size of array given. The next line contains an integer, M. denoting the number of swaps you need to perform. Constraints1 <= N <= 2000 1 <= M <= 2000 Sample Input 12 3Sample Output 11 Sample Input 23 2Sample Output 23 Sample Input 34 2Sample Output 312