Reaching round 1C at long last. As is usually the case, this one’s a breeze compared to the two previous rounds. So it’s more of a speed race to score fast than a selection based on what people were able to solve.

Problem A, “Closest Pick”, gives us full visibility on raffle tickets that have been sold, and asks us for the probability of winning if we were to purchase two optimal tickets. A ticket wins if it’s strictly closer to the drawn number than any other player’s ticket.

A selection’s probability of winning is the number of raffle drawings that result in our win divided by the number of possible raffle drawings.

It seems we can’t ever win by playing a number that’s already played: no matter the drawing, we’re not going to have a ticket strictly closer than that rival’s ticket on the same number. So we have to play between other players’ tickets. What’s the optimal position in a multi-slot ticket hole? The middle, of course. And the trickier part: what probability of winning does that middle offer?

We may have to get a bit of mathematical rigor out (or just trial and error). It’s probably easier with an quick chart:

Our ticket \(x\) is roughly in the middle between tickets \(L\) and \(R\). Which picks result in a victory for us?

A pick of \(x\) always wins. On the L side, there’s a gap of two, one slot of which is ours. On the R side, there’s a gap of three, but still only one winning slot for us: the middle one is at equal distance to both \(R\) and \(x\), so nobody wins.

The formula for the L case appears to be \(x-L-1 \over 2\); for the R case \(R-x-2 \over 2\). It doesn’t take too much convincing to generalize those to \(\left\lfloor{x-L-1}\over 2\right\rfloor\) and \(\left\lfloor{R-x-1}\over 2\right\rfloor\), respectively: the \(2\) can afford to become a \(1\) in the R case because we know it’s an odd-width gap. And with proper scrutiny, we can simplify \(\left\lfloor{x-L-1}\over 2\right\rfloor + 1 + \left\lfloor{R-x-1}\over 2\right\rfloor\) further to just \(\left\lfloor R-L\over 2\right\rfloor\).

This has the added benefit of actually working for edge cases: if \(L=R\), there’s no gap, no winning position. If \(L+1=R\), there’s none of these either. Starting at \(L+2=R\), there’s a place for a ticket of ours.

But we’re only halfway through.

There’s an additional edge case we haven’t accounted for yet: the areas around \(0\) and \(K\). We can efficiently claim the entire area there by simply buying the ticket at the boundary with tickets already bought.

And then… we’ve only considered cases where we’re buying a single ticket. We’re allowed two. What does this change?

We could always use the same strategy twice. This does yield claimable ranges. But there’s another possibility: we now can claim an entire gap instead of just its middle by buying the tickets at its boundaries.

So the best double pick would check both. Let’s implement.

solve :: Int -> [Int] -> Double
solve k ps =
  let
    single l r = (r - l) `div` 2
    atStart = head ps - 1
    atEnd = k - last ps
    singles = atStart : atEnd : zipWith single ps (tail ps)

Assuming the ps come in sorted, this is a direct transcription of what I’ve detailed above. The same for the doubles:

    double l r = r - l - 1
    doubles = zipWith double ps (tail ps)

And we can now take the best among the both:

  in
    fromIntegral (max (maximum (0 : doubles))
                      (sum $ take 2 $ sortOn Down singles))
    / fromIntegral k

You’ll note I included a zero before taking the maximum: if there’s a single sold ticket in the input, there’s no range, so no double to extract a maximum from. (It isn’t an issue for singles because those always have the range endpoints.) Also, I tolerate the double function possibly returning negatives: if that’s the case, there will necessarily be a “better” single counterpart to make up for it.

I assumed a sorted input ticket list, so let’s take care of it in the wrapper:

main :: IO ()
main = do
  t <- readLn :: IO Int
  forM_ [1..t] $ \i -> do
    [_,k] <- map read . words <$> getLine
    ps <- map read . words <$> getLine
    putStrLn $ "Case #" ++ show i ++ ": " ++ show (solve k (sort ps))

This concludes today’s problem. Full code is on github.