--- Problem Statement: Anya and Vanya have categorized a set of jokes into disjoint…
- User
Problem Statement:
Anya and Vanya have categorized a set of jokes into disjoint subsets. Anya uses
Msets, and Vanya usesKsets. The task is to compute the "humor compatibility score" between Anya and Vanya, using a formula that compares the observed number of jokes placed into the same sets by both of them against an expected number of jokes based on independent distributions.The steps are as follows:
-
Anya and Vanya each divide a collection of
Njokes intoMandKnon-overlapping sets, respectively. -
For each pair of sets
(A, B), whereAis a set from Anya's categorization andBis a set from Vanya's categorization:- Compute the real observed number of jokes,
o(A, B), that both Anya and Vanya placed into those sets. - Compute the expected number of jokes,
e(A, B), assuming Anya's and Vanya's categorizations are independent.
- Compute the real observed number of jokes,
-
The humor compatibility score is calculated as: [ \sum_{(A, B) : e(A,B) > 0} \frac{(o(A,B) - e(A,B))^2}{e(A,B)} ] where
e(A,B)is the expected value of jokes for the pair(A, B). -
You need to output a floating-point number, the humor compatibility score, with a precision up to
10^{-6}.
Input Format:
- The first line contains two integers
MandK(1 ≤ M, K ≤ 10^5), which are the number of sets Anya and Vanya use. - The second line contains an integer
N(1 ≤ N ≤ 10^5), the number of jokes. - The next
Nlines each contain two integersa_iandb_i(1 ≤ a_i ≤ M,1 ≤ b_i ≤ K), indicating the set to which Anya and Vanya respectively assign thei-th joke.
Output Format:
- Output a single floating-point number representing the humor compatibility score between Anya and Vanya, with an absolute or relative error not exceeding
10^{-6}.
-
- Assistant
To solve the problem of computing the "humor compatibility score" between Anya and Vanya, we'll follow these steps:
-
Count the Number of Jokes in Each Set:
- Anya's Sets: Count how many jokes are in each of Anya's
Msets. - Vanya's Sets: Count how many jokes are in each of Vanya's
Ksets.
- Anya's Sets: Count how many jokes are in each of Anya's
-
Count the Number of Jokes in Each Pair of Sets
(A, B):- For each joke, increment the count for the corresponding pair
(a_i, b_i).
- For each joke, increment the count for the corresponding pair
-
Compute the Compatibility Score:
- For each pair
(A, B)with at least one joke (o(A, B) >= 1), compute the term: [ \frac{o(A, B)^2 \times N}{|A| \times |B|} ] - Sum all these terms and subtract
Nto get the final compatibility score.
- For each pair
Given the constraints (
M, K, N ≤ 10^5), we'll use efficient data structures to handle the counts. Here's the Python implementation that accomplishes this:import sys import threading def main(): import sys import math import sys def input(): return sys.stdin.read() data = sys.stdin.read().split() idx = 0 M = int(data[idx]); idx +=1 K = int(data[idx]); idx +=1 N = int(data[idx]); idx +=1 size_A = [0] * (M +1) size_B = [0] * (K +1) pairs = {} for _ in range(N): a_i = int(data[idx]); idx +=1 b_i = int(data[idx]); idx +=1 size_A[a_i] +=1 size_B[b_i] +=1 key = (a_i, b_i) if key in pairs: pairs[key] +=1 else: pairs[key] =1 total = 0.0 for (a,b), o in pairs.items(): A = size_A[a] B = size_B[b] term = (o * o * N) / (A * B) total += term result = total - N print("{0:.6f}".format(result)) # For faster input reading threading.Thread(target=main).start()Explanation of the Code:
-
Reading Input Efficiently:
- We read the entire input at once and split it into tokens for faster access. This is especially important given the large input size (
N ≤ 10^5).
- We read the entire input at once and split it into tokens for faster access. This is especially important given the large input size (
-
Counting Sizes of Sets:
size_Aandsize_Barrays store the number of jokes in each of Anya's and Vanya's sets, respectively. We useM + 1andK + 1sizes to accommodate 1-based indexing.
-
Counting Jokes in Each
(A, B)Pair:- We use a dictionary
pairsto count how many jokes are in each pair(A, B). Each key in the dictionary is a tuple(a_i, b_i), and the value is the counto(A, B).
- We use a dictionary
-
Calculating the Compatibility Score:
- For each
(A, B)pair inpairs, we compute the term: [ \frac{o(A, B)^2 \times N}{|A| \times |B|} ] and add it to thetotal. - After iterating through all pairs, we subtract
Nfrom thetotalto obtain the final compatibility score.
- For each
-
Output Formatting:
- The result is printed with six decimal places as required.
-
Handling Large Inputs:
- We use a separate thread to avoid stack overflow issues that might arise with large inputs when using recursive functions or deep call stacks in Python.
Example:
Let's consider a small example to illustrate how the code works.
Input:
2 2 4 1 1 1 2 2 1 2 2Explanation:
- Anya has 2 sets: Set 1 contains jokes 1 and 2, Set 2 contains jokes 3 and 4.
- Vanya has 2 sets: Set 1 contains jokes 1 and 3, Set 2 contains jokes 2 and 4.
Calculations:
- For
(1,1):o=1,A=2,B=2, term =(1^2 * 4) / (2*2) = 1.0 - For
(1,2):o=1,A=2,B=2, term =1.0 - For
(2,1):o=1,A=2,B=2, term =1.0 - For
(2,2):o=1,A=2,B=2, term =1.0 - Total sum =
4.0 - Compatibility score =
4.0 - 4 = 0.0
Output:
0.000000This output indicates perfect compatibility under the provided definition, meaning the actual distribution of jokes perfectly matches the expected distribution based on independent assignments.
Conclusion:
The provided Python code efficiently computes the humor compatibility score by leveraging counting techniques and optimized data structures. It handles large inputs gracefully and ensures the required precision in the output.
-