what does this mean ?
The first user to solve the problems in the Long Challenge(except the Tiebreaker problem), will get 100 laddus. This is what the statement means.
Hoping for something exciting
Very much excited! Let’s do this. _/_
Let’s suppose that you are the first one in solving k problems (no other contestant got full score before you in any of those problems), then you will get 100*k laddus;
Got it Thankyou. …
Unfortunatly it is lot of math this time.
In fact, I would call only two of the A problems “programming problem”, the others are more like “math problems”.
This is not true at all
Hello, Editorials for most problems are ready , and are in verification phase. They will be released at the earliest
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…
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()
Tomorrow night for sure my friend .
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)