Mahjong Hands - NZIC 2023 Round 3 Tutorial

This problem comes from New Zealand Olympiad in Informatics (NZOI) 2023 Round 3. For the problem statement refer to here: Mahjong Hands.

I assume there are several different approaches toward this problem, but in this blog I will just describe my own solution.

1. Algorithm

1. We input the number of pins, bamboos and characters, and we store these numbers in an array (nums).

2. We loop through each type of pins (pins, bamboos or characters).

3. We input the tiles of this type, and we store these tiles in an array (tiles) of size 9. For example, each time we get a tile of 2, we increment tiles[1] by 1; each time we get a tile of 5, we increment tiles[4] by 1.

4. We check if the tiles are SIMPLE or not.

5. Then, we loop from 1 to 9:

   1. We calculate the maximum number of STRAIGHTs we can have.
   2. We minus the number of STRAIGHTs.
      For example, if we have PINS: 1, 2, 3, 1, 2, 3.
      Then we would have the tiles as [2, 2, 2].
      This means the the maximum of STRAIGHTs we can have is 2.
      We minus 2 from tiles[0], tiles[1] and tiles[2].
      Hence tiles becomes [0, 0, 0].
   3. We calculate the maximum number of SETs we can have.
   4. We minus the number of SETs.
      This step can be simplified by just doing tiles[i] % 3.
   5. After the above process, we check if tiles[i] is 0 or 2.

6. If the number of tiles in this SUIT is a multiple of 3, this means that the identical pair is not included in this set. Thus all the tiles contribute to STRAIGHTs or SETs, hence tiles should be filled with zeros.
   Otherwise, we have the identical pair in this set. This means we have a tiles[i] with 2 tiles, the rest filled with zeros.
   If tiles meet the above conditions then the set is COMPLETE, otherwise no.

7. Return the state.

I believe the key to this problem is to calculate the STRAIGHTS before the SETS, because 3 tiles with the same number can contribute to a STRAIGHT plus an identical pair.

2. C++ Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int nums[3];
    cin >> nums[0] >> nums[1] >> nums[2];

    bool simple = true, complete = true;

    int tile;
    for (int t = 0; t < 3; t++) {
        int tiles[9] = { 0 };
        for (int i = 0; i < nums[t]; i++) {
            cin >> tile;
            tiles[tile - 1] += 1;
        }

        if (tiles[0] or tiles[8])
            simple = false;
            
        int zeros = 0, twos = 0;
        for (int i = 0; i < 9; i++) {
            if (i < 7) {
                int minus = min({tiles[i], tiles[i + 1], tiles[i + 2]});
                tiles[i] -= minus, tiles[i + 1] -= minus, tiles[i + 2] -= minus;
            }
            tiles[i] = tiles[i] % 3;
            
            if (tiles[i] == 0)
                zeros++;
            else if (tiles[i] == 2)
                twos++;
        }
        
        if (!(nums[t] % 3 == 0 and zeros == 9 or
              nums[t] % 3 == 2 and twos == 1 and zeros == 8))
            complete = false;
    }

    if (simple and complete) 
        cout << "WIN" << endl;
    else if (simple)
        cout << "SIMPLE" << endl;
    else if (complete)
        cout << "COMPLETE" << endl;
    else 
        cout << "SAD";

    return 0;  
}