November 2011
Problem 3
Anonymous Shopping

A serious battle in the Pepsi vs. Coke debate is breaking out in your school. Being a fan of a healthy fruit juice beverage instead, you would prefer to not get involved. Careful to keep your beverage preferences hidden, you've always paid in cash at the store, but eventually the loyalty card program had you tempted with a delicious store discount in exchange for just your date of birth, gender, and area code (no big deal, right?). It has then dawned to you that the same information can be easily found in school records (and your Facebook's profile), linking it back to your name. How likely is that you'll be identified?1.

The input file DATA3.txt will contain 5 test cases. Each test case starts with two integers, 1 <= N, M <= 100, separated by a space. Followed by N entries of store records, and M entries of school records.

Store's record is in the form of: store_id YYYYMMDDGZIP drink, where drink is a single word describing drink preference determined for the associated loyalty card member.

School's record is in the form of: name YYYYMMDDGZIP. Name can be treated as a single word.

The output file OUT3.txt will contain 5 lines of output, the number of people out of a set M, who's drink preference can be deduced from the information available. It can be assumed that every match does belong to some entry from list M (e.g. there is only a single school in the area). It can also be assumed that names are unique.

Sample input notes: in first sample, both Dan and Tony are uniquely identified, while AJ and Cyril don't have matching records. So the answer is 2. In the second case, Dan matches two different records (there is someone else with the same DOB, Gender, and area code), but since both records are "Coke", the drink preference can be deduced. Tony also matches two records, but his preference can't be figured out based on available data. So the answer is just 1.

1: for those in U.S., date of birth, gender, and zip code uniquely identify 87% of the population. https://www.eff.org/deeplinks/2009/09/what-information-personally-identifiable

Sample Input (first 2 shown):
2 4
1 19860101M123 Coke
2 19860202M123 Pepsi
Dan 19860101M123
Tony 19860202M123
AJ 19920303M123
Cyril 19930404M123
4 2
1 19860101M123 Coke
2 19860101M123 Coke
3 19860202M123 Coke
4 19860202M123 Pepsi
Dan 19860101M123
Tony 19860202M123
Sample Output: