Joker and Batman Solution Codechef

During a fight with the Joker, Batman’s eyes lose the capability to distinguish between some pairs of colors.

Each color has an integer ID from 11 to NN. There are MM lists where each color belongs to exactly one list. Batman can distinguish colors belonging to different lists, but he cannot distinguish colors belonging to the same list.

Given a strip of LL colors, find the different number of segments Batman will see as a result of his disability. Two positions of the strip are said to belong to the same segment if they are adjacent on the strip and Batman cannot distinguish their colors. See the sample explanation for clarity.

Input Format

  • The first line contains an integer TT, the number of test cases. Then the test cases follow.
  • The first line contain three integers NNMM, and LL – the number of colors, the number of lists, and the length of the strip, respectively.
  • Each of the next MM lines describes a list. It begins with an integer KiKi, the length of the ii-th list, followed by KiKi integers Ai1,Ai2,,AiKiAi1,Ai2,…,AiKi – the color IDs of the ii-th list.
  • The next line contains LL integers S1,S2,,SLS1,S2,…,SL – the color IDs of the strip.

Output Format

For each test case, output in a single line the answer to the problem.

Constraints

  • 1T101≤T≤10
  • 1MN1051≤M≤N≤105
  • 1L1051≤L≤105
  • 1Ki,Aij,SiN1≤Ki,Aij,Si≤N
  • Mi=1Ki=N∑i=1MKi=N
  • Each color belongs to exactly one list.

Sample Input 1 

3
2 2 2
1 2
1 1
2 1
2 2 4
1 1
1 2
1 2 2 1
3 2 3
2 1 3
1 2
1 3 1

Sample Output 1 

2
3
1

Explanation

Test Case 1: Since the strip is composed of colors from different lists, the answer is the length of the strip, which is 22.

Test Case 2: The first and second index have colors from different lists, and the third and fourth index have colors from different lists. So the strip is seen to be composed of 33 consecutive segments.

Test Case 3: Since the strip is composed of colors from the same list, the answer is 11 segment.

 

Also read : Coding Solution
Also read : Joker and Batman Solution Codechef

Leave a Comment