Google Kickstart Round G 2022: Walktober

In this post, we’ll discuss the solution to the easiest problem of Google Kickstart Round G 2022, that is, Walktober. So without further ado, let’s begin!

Problem

John participates in an annual walking competition called Walktober. The competition runs for a total of N days and tracks the daily steps of the participants for all the N days. Each participant will be assigned a unique ID ranging from 1 to M where M is the total number of registered participants. A global scoreboard is maintained tracking the daily steps of each participant.

John is determined to win Walktober this year and his goal is to score the maximum daily steps on each of the NN days among all the participants. Having participated in Walktober last year as well, he wanted to know how many steps he fell short of in achieving his goal. Given the previous year scoreboard, calculate the minimum additional steps he needed over his last year score in order to achieve his goal of scoring the maximum daily steps every day.

Input

The first line of the input gives the number of test cases, T. T test cases follow.
The first line of each test case contains three integers M, N, and P denoting the total number of participants, the total number of days the competition runs, and the last year participant ID of John.
The next MM lines describe the scoreboard of the previous year and contains N integers each. The j-th integer of the i-th line denotes the step count Si,j of the participant with ID ii on the j-th day of the competition.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum total additional steps needed by John to achieve his goal.

Limits

Memory limit: 1 GB.
1≤T≤100
1≤N≤31
1≤Si,j≤60000 for all i and j.
1≤P≤M.

Test Set 1

Time limit: 20 seconds.
M=2.

Test Set 2

Time limit: 40 seconds.
2≤M≤1000.

Sample

Sample 1 –

Sample Input	Sample Output
1 2 3 1 1000 2000 3000 1500 1500 3000	Case #1: 500

Sample 2-

Sample Input	Sample Output
2 3 2 3 1000 2000 1500 4000 500 4000 3 3 2 1000 2000 1000 1500 2000 1000 500 4000 1500	Case #1: 1000 Case #2: 2500

Solution

This is a quite straightforward problem. For each of the ‘n’ days, we need to calculate the maximum score for that particular day ‘j’. The difference between John’s score and the maximum score will be the additional steps needed on the jth day.

Now our result will be the sum of the additional steps needed on each day. Have a look at the code below-

Time Complexity: O(MN), where M = number of participants and N = number of days

Space Complexity: O(1), constant space.