TAP2012D - Designing T-Shirts
[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/taip2012-problems.pdf]
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.
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.
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.
Input: 3 PEREZ GONZALEZ LOPEZ GARCIA PERALTA RODRIGUEZ 2 RODRIGO GONZALEZ GONZALO RODRIGUEZ 3 LOPEZ PEREZ LOPEZ PEREZ LOPEZ LOPEZ 1 GIMENEZ JIMENEZ 6 HEIDEGGER GAUSS GROTHENDIECK ERDOS CHURCH TURING HEISENBERG GALOIS EULER ALLEN GODEL CHURCHILL -1 Output: 4 12 15 0 13
The following test case helped me
AC in first go :D
@Mulkit09 did u find the problem , i am also getting WA
Getting WA... Can anyone post some sample input please?