Context: Argentina’s rugby is currently in one of its best moments of all time. Recently the under-18 and under-21 national teams qualified for their corresponding world cups, so the coaches of both teams have asked the Incredible Commission for the Production of Clothing (ICPC) to provide the t-shirts for these events. Each team is formed by N players, but because the two world cups do not take place simultaneously it was agreed that the ICPC would provide only N t-shirts, to be used by both teams.

For this reason, the t-shirts must be a valid set of clothing for both teams. The rules of the rugby world cups state that each player must go in the field with a t-shirt imprinted with a unique number, along with a prefix of the player’s surname, not necessarily unique. This includes boundary cases such as a t-shirt with no surname prefix (that is, a prefix of length 0) and a t-shirt with a complete surname.

The experts of ICPC immediately realized that they could simply provide N t-shirts with only numbers and no surnames on them, and each of them would be a valid t-shirt to be used by any player of any of the two teams. However, the coaches would rather have the t-shirts with the longest possible prefixes, of course without violating world cup rules, because this way it’s easier for them to identify the players while the matches are taking place.

Your task is to help the ICPC finding the maximum amount of letters that can be imprinted on a set of N t-shirts, so that this set is a valid clothing set for both teams. For example, if we have N = 3 players, the under-18 team is composed of “PEREZ”, “GONZALEZ” and “LOPEZ”, whereas the under-21 team is composed of “GARCIA”, “PERALTA” and “RODRIGUEZ”, the optimal choice consists in having one t-shirt with the 1-letter prefix “G” (to be used by “GONZALEZ” and “GARCIA”), anotherone with the 3-letter prefix”PER” (to be used by “PEREZ” and “PERALTA”), and the third t-shirt with a 0-letter prefix (to be used by”LOPEZ” and “RODRIGUEZ”). This way, the answer in this case would be 1+3+0=4.

Input

Each test case is described using three lines. The first line contains a single integer number N, indicating the number of players in each of the two teams (1 ≤ N ≤ 104). The second line contains the surnames of the N players in the under-18 team, whereas the third line contains the surnames of the N players in the under-21 team. Each surname is a non-empty string of at most 100 uppercase letters. In each test case the total number of characters in the 2N surnames is at most 105, and two or more players of the same or different teams may have the same surname.

The end of the input is indicated by a line containing the number -1.

Output

For each test case, you should print a single line containing an integer number, representing the maximum number of letters that can be imprinted on a set of N valid t-shirts to be used by both teams as explained in the problem statement.

My code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int N;
    
    while (scanf("%d", &N) && N != -1) {
        int total_letters = 0;

        // Dynamically allocating an array of strings for the teams
        char ***teams = (char ***)malloc(2 * sizeof(char **));
        for (int i = 0; i < 2; i++) {
            teams[i] = (char **)malloc(N * sizeof(char *));
            for (int j = 0; j < N; j++) {
                teams[i][j] = (char *)malloc(101 * sizeof(char)); // Allocates 101 characters for each name
            }
        }

        
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < N; j++) {
                scanf("%100s", teams[i][j]); 
            }
        }

        // Comparison between players of team 0 and players of team 1
        for (int i = 0; i < N; i++) {
            int max_prefix = 0; 

            // Compare player i of team 0 with all players of team 1
            for (int j = 0; j < N; j++) {
                int current_prefix = 0; 
                
                // Compare character by character
                for (int k = 0; teams[0][i][k] != '' && teams[1][j][k] != ''; k++) {
                    if (teams[0][i][k] == teams[1][j][k]) {
                        current_prefix++; // Increment the length of the prefix
                    } else {
                        break; // Stop when a difference is found
                    }
                }

                // Update the longest common prefix found for player i of team 0
                if (current_prefix > max_prefix) {
                    max_prefix = current_prefix;
                }
            }

            // Accumulate the longest prefix found for player i
            total_letters += max_prefix;
        }

        // Print the total number of letters that can be printed on the shirts
        printf("%dn", total_letters);

        // Free the allocated memory
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < N; j++) {
                free(teams[i][j]); // Free each string
            }
            free(teams[i]); // Free the array of strings
        }
        free(teams); // Free the main array
    }

    return 0;
}

Well, my code runs as it’s supposed to with lower inputs, like:

Input:3
PEREZ GONZALEZ LOPEZ
GARCIA PERALTA RODRIGUEZ
Output:4

This output is correct according to the Beecrowd website.

However, when it comes to larger inputs, it becomes a mess and loses its precision.

Input:11
BABBABAABAABBAABABBBBAABABBAAAABABBBBBBBAAAABAA ABB BBBBBABAABAABBAABBAAABBABBBBABBBBBBBBBAABAAAABABABAABAABBBABBBAABABBAAAABBAABABBABABBBAB BABBAAABBBBABAAAABBBBBBBABAAAAABBABBAAAAAABBAABAAABABBBBAAAAABAABAAABBABBABAABA BABBBBBBBABBBAAAABBAAABABABABBAAAAABBAABAABABABAABABBABAAAABBBBBAB BBBBAAABBBBA BBBB ABBABBABABAAAAABAABABBABABBBBBAABABAABBAAABABBAABAAABBBAAABBABBBBAAABAAABAAABB BAABAABAAAAAABBABBAAABABBABAABBBABABABABBBABAAAABABBBAAAABBABAABBBBBABAAAABABABBABBB ABBBBAAABABABABBAABBAAABBBAABABBAABABABABBBABBABABA ABBBAABBBABBAAABAABBBABAAAAAAAAAAAABBAAAABBBABBBBBAAAAABAABA
BBABABBBAABABBAABBBBAABBAAABABAB BABAAABBBAAABABBABBBBAAAAABBAAABAAAABBBAABAABBBAABAABA AAAAAAAAAAABBAABBBBABBABABBAAABAABBBBBBABBABBABAABABBAABBBAAAABBABAAABABABBABBBABAAAABBAAB BAAAAAABAABBABBABAAAAAAABAABBBBAABABAAAAAABABABBAABABBABAAAABAABAABBAABBAABABABAAABBAABBA BABBAAAAAAAAABABBBAABBBBAAABBABABAABABBBBABAABAABBABBBAAAAAABBABABBBABB AABABBABBABBBBABABBABABABBABABBBAAAAABBBBBBABBAAABAAABAAAAAABBBABABBBBABABBBBBBABABBABAAABABB BBABBAAABBAAABBBBABBBBBAAABABABAAABBABBBBBBABAAABABAAABAABABAAAABABAABABAAABA AABBBBABBAAABBABABABABABBBABBAABBBBABBBBBABBA AABABAAAABBABBAAAA AABBBBBBBBBBAAABBBABBBAABBBBBBBAABBBBBBABBB ABBABABABAABBBBBBABABBBABABA
Output:39

This output is incorrect according to the Udebug website (Beecrowd’s debug site); it should be 25. I have no idea why this is happening.