interviewstreet 4e769c33164d9

kth.py

#!/usr/bin/python
# -*- coding: UTF-8 -*-
import copy
testcases = int( raw_input() )

for i in range(testcases):
    nk = raw_input().split(" ")
    n = int(nk[0])
    k = int(nk[1])
    data = []
    dmin = [0]*n
    dmax = [0]*n

    for j in range(n):
        nums = [int(x) for x in raw_input().split(" ")]
        numscnt = nums[0]
        nums = nums[1:]
        data.append(nums)
        dmin[j] = nums[0]
        dmax[j] = nums[0]
        for jj in range(1,numscnt):
            if nums[jj]<dmin[j]: dmin[j] = nums[jj]
            if nums[jj]>dmax[j]: dmax[j] = nums[jj]
        
    #print data

    cnt = 0
    for j in range(n):
        ddmin = copy.deepcopy(dmin)
        ddmax = copy.deepcopy(dmax)
        xmin = [0] + ddmin[:j] + ddmin[j+1:] + [1<<32]
        xmax = [0] + ddmax[:j] + ddmax[j+1:] + [1<<32]
        
        xmin.sort()
        xmax.sort()
        #print "xmin:", xmin
        #print "xmax:", xmax

        interval = (xmin[k-1], xmax[k])
        #print k,interval, data[j]
        for jj in data[j]:
            if jj > interval[0] and jj < interval[1]:
                cnt += 1

    print cnt