DICEG | DICE Game | Editorial

Editorial

Problem Link

Setter: Mohit Yadav
Tester: Sidharth Sethi
Editorial: Nikhil

Problem Statement

Sid and Mohit are playing an online dice game. The game has a very unique winning condition. The game has N number of rounds. In each round both players get their turn to throw the dice to get his score. The game has a scoreboard. All the scores are recorded on the scoreboard after every single round.

The winning conditions are given below: -

  • The winner will be based on the highest score of each round but there is some twist. The winner must have the maximum number of occurrences of the maximum score they get in each round.

Example let’s have N = 5
the scoreboard after N rounds

  Rounds   |   SID   |   MOHIT  
:---------:|:-------:|:---------:
1          | 1       | 5         
2          | 4       | 3         
3          | 6       | 3         
4          | 6       | 6         
5          | 2       | 4         

So, in round 3 and 4, Sid has the maximum score and its occurrence is 2. The winner will be Sid in this case.

There’s always a winner in this. None of the test case results in draw.

Sample Input
5
1 5
4 3
6 3
6 6
2 4

Sample Output
SID

Hint

We know that a die has only 6 outcomes. Think if there is any way to store the frequencies/occurrences of score in each round for both the players?
We can use Arrays

Approach

Store the frequencies of the score for both players in two different arrays
Compare the frequencies of maximum score (In a die maximum score = 6)
The player that has maximum frequency wins the game
If both players have the same frequency for maximum score, then compare the frequency for next maximum score and do it until we find the winner

Explanation

First, take an input n (number of rounds)
Initialize two arrays for both the players with 0 (mohit_score[7] = {0}, Sid_score[7] = {0})
Note: here index of an array denotes the score and value at the index denotes
the frequency of that score

Then, use a for loop to take the scores of both players for n rounds
While taking input, we’ll increment the frequency of score for both players in their respective arrays

Now that we have counted all the frequencies of the score for both the players, we need to select the winner.
– We know that winner is the one that has maximum frequency of the maximum score.
– In a die, the maximum outcome is 6. So, first we need to compare the values at 6, if mohit_score[6] > sid_score[6], then winner is MOHIT, else if sid_score[6] > mohit_score[6], then winner is SID.
If mohit_sore[6] = sid_score[6], then we need to compare the values at next maximum value (=5) and so on(we’ll use for loop to check this).

Code (C++)

#include<bits/stdc++.h>
using namespace std;
 
 
int32_t main()
{
    int n;// number of rounds
    cin >> n;
 
    int mohit_score[7]={0}, sid_score[7]={0};
    // we can also use vector in C++
 
    for(int i=0;i<n;i++){
        int x, y;
        cin >> x >> y;
        sid_score[x]++;// incrementing the frequencies of score x for sid
        mohit_score[y]++;// incrementing the frequencies of score y for mohit
    }
 
    // selecting the winner
    // According to question, we must have a winner
    for(int i=6; i>0; i--){
        if(mohit_score[i] > sid_score[i]){// mohit has maximum occurencies of maximum element
            cout << "MOHIT" << endl;
            break;
        }else if(sid_score[i] > mohit_score[i]){// sid has maximum occurencies of maximum element
            cout << "SID" << endl;
            break;
        }
    }
    return 0;
}

Code(Java)

import java.util.*;
 
public class diceGame {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
 
        int mohit_score[] = new int[7];
        int sid_score[] = new int[7];
 
        for(int i=0;i<n; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
 
            sid_score[x]++;
            mohit_score[y]++;
        }
 
        for(int i=6; i>0; i--){
            if(mohit_score[i] > sid_score[i]){
                System.out.println("MOHIT");
                break;
            }else if(sid_score[i] > mohit_score[i]){
                System.out.println("SID");
                break;
            }
        }
 
    }
   
}

Time Complexity

O(N) , where N = number of rounds

Space Complexity

O(1) → because we are using array of size 7