DWITE '11 R2 #3 - Anonymous Shopping

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
DWITE, November 2011, Problem 3

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 on you that the same information can be easily found in school records (and your Facebook profile), linking it back to your name. How likely is it that you'll be identified?1

The input will contain 5 test cases. Each test case starts with two integers, 1 \le N, M \le 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 YYYY/MM/DD/G/ZIP 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 YYYY/MM/DD/G/ZIP. name can be treated as a single word.

The output will contain 5 lines of output, the number of people out of a set M, whose 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 the 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 the 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

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

2
1

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.