By looking at the small constraints, brute force (dp) was the only thing that popped in my mind. 
I did figure out the simpler approach later…
1 Like
No need to use dp, You should check out Very Easy Solution here for Chef and Interesting Subsequences
from sys import stdin, stdout
import math
def main():
t = int(stdin.readline())
for _ in range(t):
n, k = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
a.sort()
mx = a[k - 1]
nn, r = 0, 0
for i in range(k):
if a[i] == mx:
r += 1
for i in range(k, n):
if (a[i] == mx):
nn += 1
else:
break
nn += r
ans = math.factorial(nn) / (math.factorial(nn - r) * math.factorial(r))
print(int(ans))
if __name__ == "__main__":
main()
1 Like
Any ETA on Tomorrow night for sure my friend .
2 Likes
I think N \le 100 should work, but anything beyond that won’t - the people who hate everyone else cause my solution to explode 
I WOULD LIKE TO SUGGEST THAT AM NEW HOW TO I SIGN UP FOR THE SEPTEMBER LONG CHALLENGE
Is the editorial ready ?
And can you please give the editorial for DODGERS ?
DOOFST has a much easier solution. I thought of it as essentially a graph colouring problem. Let us observe that two vertices are disconnected if they are in the same set every time (as you said). Now, if we read the number of the sets they were in every time from top to bottom, we get a binary number. Now we can say that we need to colour all vertices in some numbers so that any two disconnected vertices are coloured with the same number and any two connected vertices are coloured with different numbers.
Initially colour all vertices as 0. This serves to minimise the maximum number we’ll have to use.
Take a vertex u which is say coloured in col(u). Colour its neighbours with the same colour as u to col(u)+1. Take any neighbour you just coloured and recurse. Terminate if there are no more neighbours of the same colour.
If the graph is valid, this must be a correct colouring, since any two disconnected vertices have same colour and any two connected vertices have different colour.
We can check this condition by storing a list of edges and checking if for edge (u,v), col(u)=col(v). If yes, the graph is invalid.
There are some corner cases if the graph is disconnected, self loops, and so on.
Finally, the K we want is length of maximum colour number in binary. We can print the partitions by printing the numbers assigned to each vertex in binary from LSB to MSB or other way around, doesn’t matter.
(Hope I didn’t miss anything)
1 Like
Adding to this.
A simple observation is if elements are in same connected component in complement of this graph then it will have exactly same adjacency list in actual graph.
Hence we can use map of vectors, vectors for making groups 
We don’t really need random thing.
@aryanc403 @ssjgz
https://www.codechef.com/viewsolution/26590164
1 Like
I can’t find any editorial for DOOFST yet?
DOOFST is a NP-complete problem. If you read the assignments in binary for each vertex, it is clear that the assignemnents for connected pair of vertices being different is necessary and sufficient condition. Basically it’s a graph colouring problem to colour k-colourable graph with next power of 2 greater than or equal to k. And for instance it is known that it is NP-complete to assign 4-colour a 4-colourable graph. So even if the minimum number of times Dr.D needs to use hateinator is 2, it is NP-complete.
Is this simple reasoning wrong? For a 4-colourable graph, it is possible use hateinator twice, and then I can read the two assignment in binary to get the colour(0 to 3). And it is guaranteed that a bit must be different between two adjacent vertices, which is same as graph colouring problem.
I think you misunderstand the problem. Not sure I understand what you’re saying entirely, but here’s an attempt anyway. Yes, it is a graph colouring problem, but a k colouring is NP complete only in the general case. In this specific case, you can definitely show that only specific kinds of graphs work. In fact if you see my solution (a few posts above) you’ll see why. It’s kind of a constructive proof, showing that it’s not, in fact, NP complete by providing a polynomial time algorithm. This is also demonstrated by aryanc403’s post above. I hope I got the point across (F to pay respects if I failed miserably).
Thanks a lot
1 Like