CCC '20 S5 - Josh's Double Bacon Deluxe - DMOJ: Modern Online Judge

CCC '20 S5 - Josh's Double Bacon Deluxe

View as PDF

Submit solution

All submissions

Best submissions

Points: 17 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

ThreeInches

Problem types

Canadian Computing Competition: 2020 Stage 1, Senior #5

On their way to the contest grounds, Josh, his coach, and his $N-2$ ~N-2~ teammates decide to stop at a burger joint that offers $M$ ~M~ distinct burger menu items. After ordering their favourite burgers, the team members line up, with the coach in the first position and Josh last, to pick up their burgers. Unfortunately, the coach forgot what he ordered. He picks a burger at random and walks away. The other team members, in sequence, pick up their favourite burger if available, or a random remaining burger if there are no more of their favourite burger. What is the probability that Josh, being last in line, will get to eat his favourite burger?

Input Specification

The first line contains the number $N$ ~N~ $(3 \le N \le 1\,000\,000)$ ~(3 \le N \le 1\,000\,000)~, the total number of people and burgers. The next line contains $N$ ~N~ numbers, the $i$ ~i~-th being $b_i$ ~b_i~ $(1 \le b_i \le M \le 500\,000)$ ~(1 \le b_i \le M \le 500\,000)~, denoting the item number of the $i$ ~i~-th person's favourite burger. The first person in line is the coach, and the $N$ ~N~-th person is Josh.

For $4$ ~4~ of the $15$ ~15~ available marks, $N \le 100\,000$ ~N \le 100\,000~ and $M \le 1\,000$ ~M \le 1\,000~.

For an additional $5$ ~5~ of the $15$ ~15~ available marks, $M \le 5\,000$ ~M \le 5\,000~.

Output Specification

Output a single number $P$ ~P~, the probability that Josh will get to eat his favourite burger, $b_N$ ~b_N~. If the correct answer is $C$ ~C~, the grader will view $P$ ~P~ correct if $|P - C| \le 10^{-6}$ ~|P - C| \le 10^{-6}~.

Sample Input 1

3
1 2 3

Output for Sample Input 1

0.5

Explanation of Output for Sample Input 1

The coach randomly chooses between the three burgers. With probability $1/3$ ~1/3~, he chooses his favourite burger (burger 1), and Josh gets to eat his favourite burger (burger $3$ ~3~). With probability $1/3$ ~1/3~, he chooses Josh's favourite burger, and Josh fails to eat his favourite burger. With probability $1/3$ ~1/3~, he chooses the second person's burger, there is a $1/2$ ~1/2~ chance that the second person chooses Josh's burger, denying Josh the pleasure of eating his favourite burger.

Sample Input 2

7
1 2 3 1 1 2 3

Output for Sample Input 2

0.57142857

Comments

2

SimonV commented on Nov. 25, 2023, 1:30 a.m.

Explanation of Output for Sample Input 1: 1/3 + (1/2)*(1/3) + 0 = 3/6

12

peatlo17 commented on July 9, 2020, 9:29 p.m.

After some calculation I got that for $N > 0$ ~N > 0~ people having distinct burgers, the probability that the last person gets their burger is

$\dfrac{(N-2)!\sum_{k=0}^{N-2} \frac{1}{k!}}{(N-1)!\sum_{k=0}^{N-1} \frac{1}{k!}} = \dfrac{\lfloor (N-2)! \cdot e\rfloor}{\lfloor (N-1)! \cdot e\rfloor}$

Pls check my math.

-21

Ben_Zhou commented on Nov. 13, 2021, 9:45 p.m.

what is "e" and what is "k"?

This comment is hidden due to too much negative feedback. Show it anyway.

45

Kevy3030 commented on March 28, 2020, 3:18 p.m.

2019 Canadian Mathematical Olympiad - Qualifying Repechage Problem 7:

There are n passengers in a line, waiting to board a plane with n seats. For 1 ≤ k ≤ n, the k th passenger in line has a ticket for the k th seat. However, the first passenger ignores his ticket, and decides to sit in a seat at random. Thereafter, each passenger sits as follows: If his/her assigned is empty, then he/she sits in it. Otherwise, he/she sits in an empty seat at random. How many different ways can all n passengers be seated?

hmmmmm...

-227

j9292002 commented on March 13, 2020, 11:25 p.m. ← edit 2 →

this year's s5 is too mathy! can this hit 1000 downvotes?

This comment is hidden due to too much negative feedback. Show it anyway.

-30

harry7557558 commented on March 24, 2020, 7:56 a.m. ← edited →

CEMC's full name is "The Center of Education in Mathematics and Computing".

This comment is hidden due to too much negative feedback. Show it anyway.

112

richardzhang commented on March 23, 2020, 10:00 p.m. ← edited →

Were this year's S3 and S4 too stringy as well? And I assume that S2 was much too graphy for your tastes. In my personal opinion, S1 was surely too implementy compared to other S1s.