Last Updated: 28 Mar, 2022
Market Survey
Moderate
Asked in company
Market Research firm is surveying popular brands. The person who has the best pulse of the survey the firm will reward the population. The survey comprised of N questions was taken by M participants, not simultaneously but one after the other. There is no correct answer since it is a survey of brands. Each question can have only four options (1,2,3,4). Most expected answers to different questions are used as a template to measure brand popularity. Think of this as a default answer sheet where the question paper is the Survey. '0' represents no answer to a question. Thus it means that the participant has skipped answering that question.
Right Answer: For a particular question, the highly chosen option till that point in time is treated as the correct answer. If multiple options have the exact count, then out of those options, the one which was chosen recently is treated as the correct answer.
Score of a Participant: One point will be awarded for each correct answer. No negative points for wrong answers.
Instant Result: This is shared with the Participant instantly after completing his/her exam. (this is equal to the number of correct answers)
Final Result: Only the final top scorer(TOPPER) is announced along with his score.
Note:
At the end of all M Participants completing the exam, the final correct answers get decided.
Based on these answers score of each candidate gets recalculated, and the one with the highest score is the TOPPER!!!
If more than one Participant gets the top score, then the one who attempted the exam first is treated as TOPPER.
Input Format:
The first line of the input contains a single integer ‘T’ representing the no. of test cases.
The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, denoting the number of questions and number of participants, respectively.
The second line of each test case contains ‘N’ space-separated integers representing the default answers.
The following ‘M’ lines of each test case contain ‘N’ space-separated integers, denoting answers given by each participant.
Output Format:
For each test case, print two lines.
The first line for each test case contains ‘M’ space-separated integers representing the instant results of every participant.
The second line of each test case contains a single integer representing the TOPPER.
Note:
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer in the form of an array of length ‘M’+1. The first ‘M’ integers represent instant results, and the last element denotes the TOPPER.
Constraints:
1 ≤ T ≤ 10
1 ≤ M, N ≤ 1000
0 ≤ responses and default answer ≤ 4
Time limit: 1 Sec
Approaches
We just follow the instructions of the statement and for each participant, we first calculate the most frequent answer for that participant and then publish the instant results. After we have found instant results for each participant then we find out the topper which has the maximum number of correct answers as compared to the final frequent answers. Implementation details are as per the following algorithm.
Algorithm:
Given Function
- Declare and initialize integer array instant = default
- Declare integer array ans
- Declare 2D integer array freq of size N * 4
- Declare integer array maxFreq of size n initialized to all zeroes
- Iterate over i from 0 to m-1
- Declare and initialize integer correct = 0
- Iterate over j from 0 to n-1
- If survey[i][j] == instant[j]
- Increment correct
- If survey[i][j] == instant[j]
- Append correct to ans
- Iterate over j from 0 to n-1
- If survey[i][j] = 0
- Continue
- Increment freq[j][survey[i][j]-1]
- Declare and initialize integer frequency = freq[j][survey[i][j]-1]
- If frequency > maxFreq[j]
- maxFreq[j] = frequency
- instant[j] = survey[i][j]
- If survey[i][j] = 0
- Declare and initialize integer topper = 0, maxCorrect = 0
- Iterate over i from 0 to m-1
- Declare and initialize integer correct = 0
- Iterate over j from 0 to n-1
- If survey[i][j] == instant[j]
- Increment correct
- If survey[i][j] == instant[j]
- If correct > maxCorrect
- maxCorrect = correct
- topper = i+1
- Append topper to ans
- Return ans