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:
All numbers in the triplet are the same (Eg. {1, 1, 1})
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.
Problem 1 is similar to this: Jongmah
Problem 3 is similar to this: Gargari and Permutations
Thank You
Someone knows how to solve b ?
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.
find the best cut for array[0:i]
what condition will you use to find the best j in the prefix ?Choose the prefix whose sum is closest to sum(array[0:i])/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.
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
how did you find this
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$$$.
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.
It was not unfair. That problem is from the 7th May slot only, not from yesterday.
Giving problems of rating 2200+ srsly? Infosys? .. ;(
Sabke bhao badh gaye hain.
Can someone tell the algorithm for solving problem 3? I currently have $$$O(KN^K)$$$ solution.
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
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?
I don't think your approach using LCS is correct
Case : N = 4, K = 3
Array 1 : 1 2 3 4
Array 2 : 1 4 2 3
Array 3 : 2 3 4 1
Your approach would give 3 but correct answer is 2.
Ah, I see!
Thank you. :)
Consider this test case:
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.
But can't we do one thing we find out lcs of first two then Find lcs of the previous lcs and next array
Do you think LCS is unique?
oh yes my bad
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.
(https://ideone.com/iLQvgv)
Link to my code
Isn't problem 3 LCS?
Yes, it is LCS, but we have multiple arrays of which we want LCS.
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.
.
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
You should keep in mind that it wasn't a placement round, it was a HACKATHON !!, and hackathons are meant to be challenging.
wtf is this??.. If someone can solve question of rating 2200 ,why will they go to infosys?
I had different questions. Did someone get the matrix question in which we had to throw out garbage?
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 i
such 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
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 here
Thanks soumyadeep_pal_21 and vkgainz
2 is direct copy of this AtCoder problem (they even used the same variables lmao)
HackWithInfy problems
(1)
(2)
(3)
(4)
ANY HELP WILL BE APPRECIATED, THANKS IN ADVANCE :)
ANOTHER QUESTION FROM HACKWITHINFY 2020
Problem Statement
You 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 Format
The 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.
Constraints
1 <= N <= 2000 1 <= M <= 2000
Sample Input 1
2 3
Sample Output 1
1
Sample Input 2
3 2
Sample Output 2
3
Sample Input 3
4 2
Sample Output 3
12
Problem Link: Task #2
Read its editorial.
The question are worth more value than the company itself xD.
The irony is that they don't even make these questions. Just Copy, Paste, and Edit.
Bro which company in the world gives 2200 rating questions for a 8 LPA (in Indian Rupees) job??
That too after taxes and all idk how much people get in-hand salary.
Can anyone help me with this problem asked in infytq link .
It would be great if author can add it to the post.
Can somebody explain me the DP approach of Qn1? I could not understand the editorial.1110D - Jongmah
YouTube Video . Hope it'll help. My Solution from this video.
Hii, for hackwithinfy i was using firefox and the timer wasn’t running but i was able to view and submit problems and after one hour i switched back to chrome will they disqualify me? Also will i get call for PP , I wad able to solve 2 problems full and 1 problem 78% .
Switching the browser is not a problem.
Thanks man, actually i asked the same question on codechef forum and someone replied that 90% chances are of disqualification :(