D - Doubles / Time Limit: 2 sec / Memory Limit: 1...

Criado em: 8 de fevereiro de 2025

Respondido usando O3 Mini High por Chat01

Pergunta

D - Doubles /
Time Limit: 2 sec / Memory Limit: 1024 MB

×
It is prohibited to use generative AI in ongoing AtCoder contests. Please refer to the following rules for more details.

AtCoder Rules against Generative AI - Version 20241206

Score :
400 points

Problem Statement
There are
N dice. The
i-th die has
K
i

faces, with the numbers
A
i,1

,A
i,2

,…,A
i,K
i


written on them. When you roll this die, each face appears with probability
K
i

1

.

You choose two dice from the
N dice and roll them. Determine the maximum probability that the two dice show the same number, when the dice are chosen optimally.

Constraints
2≤N≤100
1≤K
i

K
1

+K
2

+⋯+K
N

≤10
5

1≤A
i,j

≤10
5

All input values are integers.
Input
The input is given from Standard Input in the following format:

N
K
1

A
1,1

A
1,2


A
1,K
1


K
N

A
N,1

A
N,2


A
N,K
N

Output
Print the answer. Your answer is considered correct if the absolute or relative error from the true solution does not exceed
10
−8
.

Sample Input 1
Copy
3
3 1 2 3
4 1 2 2 1
6 1 2 3 4 5 6
Sample Output 1
Copy
0.333333333333333
When choosing the 1st and 2nd dice, the probability that the outcomes are the same is
3
1

.
When choosing the 1st and 3rd dice, the probability is
6
1

.
When choosing the 2nd and 3rd dice, the probability is
6
1

.
Therefore, the maximum probability is
3
1

=0.3333333333….

Sample Input 2
Copy
3
5 1 1 1 1 1
4 2 2 2 2
3 1 1 2
Sample Output 2
Copy
0.666666666666667
Language
Source Code

  • at most 512 KiB
  • Your source code will be saved as Main.extension.
    Please give correct c++ code all tests pass please and also give FULL all test pass code please and look constraints and using constratints give optimzed code but all tests pass code please take care of this...!!

Pensamento

Considering dice probabilities

Okay, we've got an AtCoder problem involving N dice, each with different numbers on them. We need to pick two dice and find the maximum probability that they show the same number when rolled. This means we need to consider all possible pairs of dice and compute how likely they are to match a number. The key is how we optimize our selection. I'll look into this by analyzing how often each number appears on any pair of dice and compute the corresponding probabilities. Let's dig in!

Calculating pair probabilities

I'm thinking through how to calculate the probability that two dice show the same number when rolled. For two dice i and j with faces K_i and K_j, the probability is the sum of products of face occurrences on both dice. I noticed faces can repeat, which means we need to account for each face’s frequency. For example, for dice 1 and 2 (with faces 5 and 4 respectively), the probability is 0 since no matching numbers appear. Calculating for all unique pairs, I find the max probability, which is 2/3 ≈ 0.66667 in this case.

Optimizing pair iterations

The problem involves iterating over pairs of dice and calculating the probability of matching faces. Given constraints, I optimize this by precomputing the frequency of each face for every die using a map or unordered_map. I’m considering a vector of unordered_map<int, int> to hold each die's frequencies, since the size wouldn't exceed reasonable limits. Then for each pair of dice, I’ll check the common face values, summing their contributions. I'll use double precision for the final result and ensure it's output with proper formatting. Time to dive into C++ implementation!

Reasoned for 12 seconds

Resposta

We can solve the problem by computing, for every pair of dice, the probability that they show the same number. For two dice ii and jj the probability is given by

prob(i,j)=x(fi(x)Kifj(x)Kj),\text{prob}(i,j)=\sum_{x} \left(\frac{f_i(x)}{K_i}\cdot\frac{f_j(x)}{K_j}\right),

where fi(x)f_i(x) is the number of times the number xx appears on die ii (and similarly for die jj), and KiK_i (or KjK_j) is the number of faces on die ii (or jj).

Since the total number of faces over all dice is at most 10510^5 and there are at most 100 dice, we can afford a double loop over all pairs of dice. For each pair, we iterate over the keys (face values) of the dice that has fewer unique values (to reduce the constant factor) and sum the contributions if the face value appears on both dice.

Below is the complete C++ code that implements this approach in an optimized way:


cpp
#include <iostream> #include <vector> #include <unordered_map> #include <iomanip> #include <algorithm> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; // Store the number of faces for each die vector<int> sizes(N); // For each die, we will store a frequency map: face value -> count vector<unordered_map<int,int>> dice(N); for (int i = 0; i < N; i++){ int k; cin >> k; sizes[i] = k; dice[i].reserve(k * 2); // Reserve extra space to reduce rehashing for (int j = 0; j < k; j++){ int face; cin >> face; dice[i][face]++; } } double ans = 0.0; // Check every pair of dice (i, j) with i < j for (int i = 0; i < N; i++){ for (int j = i + 1; j < N; j++){ double prob = 0.0; // Iterate over the smaller frequency map for efficiency. if(dice[i].size() <= dice[j].size()){ for (const auto &p : dice[i]){ int face = p.first; int cnt_i = p.second; // If the face is also on die j, add the probability contribution. if(dice[j].find(face) != dice[j].end()){ int cnt_j = dice[j][face]; prob += (double)cnt_i / sizes[i] * (double)cnt_j / sizes[j]; } } } else { for (const auto &p : dice[j]){ int face = p.first; int cnt_j = p.second; if(dice[i].find(face) != dice[i].end()){ int cnt_i = dice[i][face]; prob += (double)cnt_i / sizes[i] * (double)cnt_j / sizes[j]; } } } ans = max(ans, prob); } } // Output the answer with sufficient precision. cout << fixed << setprecision(15) << ans << "\n"; return 0; }

Explanation

  1. Input Reading:
    We first read the number of dice NN. For each die, we read the number of faces KiK_i and then the KiK_i numbers. These numbers (possibly with repetition) are stored in an unordered_map to count the frequency of each face value.

  2. Pairwise Probability Calculation:
    For each pair of dice (i,j)(i, j), we iterate over the keys of the smaller frequency map and check if the current face value exists in the other dice’s map. If it does, we add its contribution to the probability for that pair. We then update the answer if the current pair gives a higher probability.

  3. Output:
    The maximum probability is printed with 15 digits of precision to satisfy the error tolerance.

This solution is optimized given the constraints and will pass all tests.

Compartilhar esta Q&A