Bot or not
InterviewTime limit2sMemory limit512 MB
Score pairs of secondary accounts by shared posts they follow, then count accounts similar to a known human.
- Level
Medium6 of 10
- Topics
- Implementation, Hash map, Brute force
- Solved
- No attempts yet
Problem
Fake news spreads mostly through bot accounts. A bot follows other accounts and reposts their stories so that it looks like a person. Bots and people repost in different patterns. Use that difference to decide which accounts are human.
There are two kinds of accounts: primary accounts that post stories, and secondary accounts that repost stories from primary accounts. For each secondary account you get the primary accounts it follows, whether it is known to be human, and the list of posts it reposted. Assume a secondary account sees every post made by every primary account it follows. Leaving a post it saw without a repost is therefore a deliberate choice.
The similarity score of two secondary accounts is set by three integers , , with . Only the posts of primary accounts that both secondary accounts follow enter the score. For each such post, if of the two accounts reposted it, add . Both reposting or neither reposting gives a positive score, and a repost by exactly one of them gives the negative score . If the two accounts follow no primary account in common, their score is 0.
Two accounts are similar if their total score is at least the threshold . A secondary account is judged human if it is similar to an account known to be human. Being similar to an account that was judged human does not make an account human, so the judgement applies only one step.
For each data set, count the secondary accounts that are known human or judged human.
Input
The first line contains the number of data sets . The data sets follow, each in this format.
The first line of a data set contains six integers , , , , , . Here is the number of primary accounts, is the number of secondary accounts, are the similarity scores, and is the similarity threshold.
The next line contains integers (), where is the number of posts made by primary account . Posts are numbered from 1: the first posts belong to primary account 1, the next posts to primary account 2, and so on.
The next lines describe one secondary account each. A line starts with the integer , which is 1 if the account is known to be human and 0 if it is not known whether it is human or a bot. Next comes the integer (), the number of primary accounts that follows, followed by distinct integers between and , the indices of those primary accounts. Next comes the integer (), the number of reposts made by , followed by distinct integers between and , the posts that reposted. No input has an account reposting a post of a primary account it does not follow.
Output
For each data set, print Data Set x: on a line of its own, where is the number of the data set counting from 1. On the next line print the number of secondary accounts that are known human or judged human. Print one blank line after each data set.