Xenny had N numbers and he loved equal triplets (An equal triplet is group of 3 numbers…
- User
Xenny had N numbers and he loved equal triplets (An equal triplet is group of 3 numbers that are equal). He defined a K-equal-triplet as a triplet in which all 3 integers were equal to K. Given an integer K, he wanted to find out the probability of getting a K-equal triplet, from the N numbers.
Xenny is bad at understanding floating point numbers. Help him to find the probability in terms of a fraction, reduced to its lowest terms. Input First line contains a single integer - T, the total number of testcases. T testcases follow. Each testcase consists of 2 lines: First line contains 2 space-separated integers - N and K, which represent the total number of integers Xenny had, and the value K whose K-equal-triplet was required.
Output For each testcase, print the probability of finding a K-equal-triplet in terms of the lowest fraction. For example, if the answer is 4/8, you must print 1/2, which is the lowest reduced fraction of 4/8.
Constraints 1 ≤ T ≤ 50 1 ≤ N ≤ 10^6 1 ≤ Numbers ≤ 10^9 1 ≤ K ≤ 10^9
Note:
- 2 testcase files are large (about 20 MB) in size. Please use fast I/O in your code.
- Candidates need to attempt only one of the given problems
SAMPLE INPUT 1 5 4 1 4 4 4 1
SAMPLE OUTPUT 1/10
Explanation
K = 4 There is exactly one triplet (4, 4, 4) that can be selected from the given numbers. Hence, the probability of selecting a 4-equal-triplet is 1/10.
Assistant
We need to solve: For each test case, given N numbers and a K, we want the probability that a randomly selected triplet (3 distinct positions? Or is it combination of three numbers? Typically "selecting a triplet from the N numbers" suggests choosing three distinct elements uniformly at random from the multiset of N numbers (order doesn't matter). The sample: N=5, numbers: [1,4,4,4,1]. Count of triplets = C(5,3) = 10. Number of triplets that are all equal to K (i.e., all three numbers = K) is the number of ways to choose three of the positions where the number equals K. Let count of K = m. Then number of favorable triplets = C(m,3). Probability = C(m,3) / C(N,3). Output as reduced fraction.
But careful: The problem statement: "Xenny had N numbers and he loved equal triplets (An equal triplet is group of 3 numbers that are equal). He defined a K-equal-triplet as a triplet in which all 3 integers were equal to K. Given an integer K, he wanted to find out the probability of getting a K-equal triplet, from the N numbers." So indeed, we consider all possible triplets (likely unordered, distinct positions). So probability = number of triplets where all three are K divided by total number of triplets.
Now we need to output reduced fraction. So compute numerator = C(m,3) and denominator = C(N,3). Simplify by dividing by gcd.
Edge cases: If m < 3, then numerator = 0. Probability 0? Should output "0/1"? Typically probability 0 would be represented as 0/1. Check: if m < 3, there are no K-equal triplets, so probability = 0. So output "0/1". Similarly if N < 3, then total number of triplets is 0? But N >= 1 according to constraints, but N can be less than 3? The constraints say 1 ≤ N ≤ 10^6, so N could be 1 or 2. Then C(N,3)=0, so probability is undefined. But maybe they assume N >= 3? The sample has N=5. But constraints didn't guarantee. In probability terms, if there are no triplets, probability is 0? Or undefined. Usually they'd guarantee N>=3. But just to be safe, we can handle: if N<3 or m<3 then probability 0? Actually if N<3, no triplets exist, so the event of selecting a triplet is impossible; but maybe the probability is 0? Or we could output "0/1"? Problem might assume N≥3. But let's check: The problem says "Xenny had N numbers ... he wanted to find out the probability of getting a K-equal triplet, from the N numbers." If N<3, then it's impossible to form a triplet, so the probability is 0. That seems plausible. Also if m<3, it's 0. So we can output "0/1". For N<3, C(N,3)=0, so if we compute denominator as 0, we can't compute fraction. So we should treat that separately.
But typical contest problem would have N ≥ 3, but it's not explicitly said. However, constraints 1 ≤ N ≤ 10^6, so we need to consider N=1,2. They might test. Let's decide: if N < 3, then there are no possible triplets, so the probability of picking a K-equal triplet is 0. So output "0/1". Similarly if m < 3, numerator = 0, denominator = something >0 => 0/1. So we can compute:
if N<3 or m<3: numerator = 0, denominator = 1 (so 0/1). Actually we need to be careful: if N<3, denominator should be 0? But we output 0/1 as per convention. I think it's okay.
Alternatively, compute numerator = C(m,3) (which may be 0 if m<3) and denominator = C(N,3) (which may be 0 if N<3). If denominator=0, then probability undefined; but given the problem likely ensures N≥3, we don't have to handle. But to be robust, we can check: if denominator==0, output "0/1"? That is arguable. But I think they intend N≥3 because otherwise the concept of picking a triplet from N numbers is not defined. Most combinatorics probability problems assume that the selection is possible, so they'd guarantee N≥3. Let's check sample. Not specified. I'd assume N≥3. However, constraints: 1 ≤ N ≤ 10^6 includes N=1,2. But maybe test cases won't include them. Usually they'd include. But we can just ensure our code doesn't crash: If N<3, then C(N,3)=0. We cannot have denominator 0; we should treat as probability 0? But it's actually undefined. But I think safer to treat as 0 output? Or maybe we can output "0/1" and ignore denominator. I'd check: In many problems, they define probability as favorable/total number of possible triplets. If total is 0, then the probability is 0 because there is no way to choose a triplet? But mathematically, it's undefined. However, I'd guess they won't test N<3. But I can include a condition: if N<3: print "0/1". If N>=3 but m<3: print "0/1". If both >=3, compute fraction.
Now we need to read input fast because files are large. Use sys.stdin.buffer.read, parse integers. T up to 50, N up to 10^6, so total numbers up to maybe 50 * 1e6 = 50e6, which is large, but note there are only two large test case files, meaning total input size may be up to 20 MB per file? Actually they mention 2 testcase files are large (~20 MB). So total input may be up to 40 MB. Using fast I/O is needed in languages like C++, Python needs to be efficient. Use sys.stdin.buffer.read and convert to ints.
Approach: Read all ints. First int T. Then for each test case: read N, K. Then read N numbers. Count how many equal to K (m). Compute numerator = m*(m-1)(m-2)//6 if m>=3 else 0. Compute denominator = N(N-1)*(N-2)//6 if N>=3 else 0? Actually if N>=3 denominator = C(N,3). Then reduce fraction: compute g = gcd(numer, denom). Then print f"{numer//g}/{denom//g}". But careful: if numerator=0, we should output "0/1" (since gcd(0, denom) = denom, which would reduce to 0/1? Actually gcd(0, denom) = denom, then numerator//g = 0//g = 0, denominator//g = denom//g = 1, so that works if denom>0. If denominator=0 (N<3), we can't compute gcd because denominator=0 (division by zero). So need to handle separately: if numerator==0 and denominator==0? Actually N<3 leads denominator=0, numerator will be 0 because m <= N <3, so C(m,3)=0. So we have 0/0. That's undefined. But as argued we treat as 0/1? Or we can set denominator=1 in that case. So we can condition: if N < 3: print "0/1". That resolves.
But also if N>=3 and denominator>0, numerator may be 0, then gcd gives reduction to 0/1 because denominator//g = denom//denom =1? Actually if numerator=0, gcd(0, denom)=denom, then numerator//denom = 0, denominator//denom = 1. So it's "0/1". That's fine.
Thus code:
def solve(): import sys, math data = sys.stdin.buffer.read().split() it = iter(data) t = int(next(it)) out_lines = [] for _ in range(t): N = int(next(it)) K = int(next(it)) # count numbers equal to K among next N ints m = 0 for i in range(N): if int(next(it)) == K: m += 1 # compute numerator and denominator if N < 3: # no possible triplets out_lines.append("0/1") continue # compute C(m,3) and C(N,3) numer = m*(m-1)(m-2)//6 if m >= 3 else 0 denom = N(N-1)*(N-2)//6 g = math.gcd(numer, denom) numer //= g denom //= g out_lines.append(f"{numer}/{denom}") sys.stdout.write("\n".join(out_lines))
But careful: For large N (up to 10^6), C(N,3) can be huge, up to about (1e6)^3/6 ≈ 1.666e17, which fits within 64-bit? 1e18 is roughly 2^60 ~ 1e18. 1.666e17 fits in 64-bit signed (max 9.22e18). So Python int can handle arbitrary. So fine.
Now the main challenge: reading N numbers and counting m for each test case. Since total numbers across test cases could be up to 50 * 1e6 = 50e6, but maybe T is small for large N. They said two test case files are large ~20 MB, so total input size maybe 20 MB per file, so about 20 million numbers? Actually 20 MB of integers as text: each integer average maybe 5 digits + space, so about 6 bytes per number, so maybe ~3.3 million numbers. That's manageable. But to be safe, we need efficient counting. Our loop over N and int conversion for each number might be fine, but we can also count by iterating through the list of integers. Since we are already using fast parsing, it's fine.
But maybe there is nuance: The numbers are up to 1e9, but we only compare to K, so we don't need to store the numbers, just count equality. That's what we do.
Potential pitfalls: The input may contain numbers across lines; reading split and iterating works.
Edge Cases: m=0,1,2: numer=0; output 0/1. Denominator positive as long as N>=3.
Check sample: N=5, K=4, numbers [1,4,4,4,1] => m=3 => numer = 321/6=1, denom=543/6=10 => gcd=1 => 1/10. Good.
Now we should consider time complexity: O(total numbers). With up to 50 million numbers, Python might be borderline but probably okay with optimized I/O. Since they mention large files 20 MB, total numbers across all test cases maybe about 4 million (assuming each integer about 5 chars + space). 20 MB / 6 ~ 3.33 million numbers. For two files maybe total 40 MB => ~6.66 million numbers. That's fine.
But what about T=50 with each N=10^6? That would be 50 million numbers, which is about 300 MB input (if each number ~6 bytes) far more than 20 MB. So they probably have T small for large N. So our solution should be okay.
Now I recall that the problem might be from some contest, and they might want to compute probability as fraction reduced to lowest terms. That's it.
But wait: Is the probability defined as selecting a triplet uniformly from all combinations? Or could it be selecting three numbers with replacement? Usually "from the N numbers" suggests picking three distinct numbers. The sample matches combination count. So fine.
Now we need to produce final answer.
But there is also the concept of "equal triplet" as group of 3 numbers that are equal. So any equal triplet, not necessarily K. But they ask specifically K-equal-triplet. So probability that a randomly chosen triplet is a K-equal-triplet.
Thus solution stands.
Now regarding handling large numbers: math.gcd works with Python ints.
One nuance: In Python 3.8 and later, math.gcd works with 0 as argument, returns the other argument. So that's fine.
But for N<3, we output 0/1. But what if N=0? Not possible. N>=1.
Now final code.
We should also consider reading the numbers line by line? Better to use sys.stdin.buffer.read().
Now testing with sample.
We'll implement solve() function.
Potential improvements: Use local variables for speed: read = sys.stdin.buffer.read, split = data.split; but it's fine.
Double-check: The first line contains T, then each test case: first line N K, then second line contains N numbers? The description says each testcase consists of 2 lines: first line contains N and K; second line contains the N numbers. But the numbers could be across multiple lines? It says second line contains the N numbers, but maybe they are space-separated and could wrap? Usually it's one line. But to be safe, using split works regardless of line boundaries.
Thus final code.
We'll produce final answer.
But wait: There is a note: "Candidates need to attempt only one of the given problems". That is irrelevant.
Now let's think about possible pitfalls: The numbers could be large, but counting equality is fine.
Now think about the fraction reduction: Use gcd.
Edge: If numerator and denominator both zero (N<3), we avoid division.
But what about N=3 and m=3? Then numer=1, denom=1 => output "1/1".
Now everything seems fine.
One more nuance: Could there be leading/trailing spaces? Using split handles.
Thus the solution is straightforward.
But before finalizing, we might consider whether the probability might be defined as picking three numbers with replacement? Usually "triplet" without replacement. The sample uses combination count. So we are correct.
Now writing final solution with explanation.
I'll produce final answer in Python with function solve().
Time to produce final. ```python
import sys import math
def solve() -> None: data = sys.stdin.buffer.read().split() it = iter(data) t = int(next(it)) out_lines = []
for _ in range(t): N = int(next(it)) K = int(next(it)) # count how many numbers equal K cnt_k = 0 for _ in range(N): if int(next(it)) == K: cnt_k += 1 # handle the case where no triplet can be formed if N < 3: out_lines.append("0/1") continue # number of triplets of value K num = cnt_k * (cnt_k - 1) * (cnt_k - 2) // 6 if cnt_k >= 3 else 0 # total number of triplets den = N * (N - 1) * (N - 2) // 6 g = math.gcd(num, den) num //= g den //= g out_lines.append(f"{num}/{den}") sys.stdout.write("\n".join(out_lines))if name == "main": solve()