Dream11: Contest Prizes When Tied Teams Share a Rank
When a contest ends, Dream11 ranks its teams by points and pays out a prize table.
- Difficulty: Hard
- Topics: Window Functions, Joins, Aggregation
- Dialect: MySQL
- Problem: #641
Problem statement
When a contest ends, Dream11 ranks its teams by points and pays out a prize table. Teams with equal points share a rank, and the prizes of all the positions they occupy are pooled and split equally among them. For example, if two teams tie for rank 2, they occupy positions 2 and 3 and each receives half of (prize for 2 + prize for 3); the next team is rank 4.
PrizeSlab gives the prize per position for ranges of positions; positions not covered by any slab pay nothing. For every entry that wins more than 0, return contest_id, entry_id, contest_rank and prize_won (rounded to 2 decimals). Order by contest_id, then contest_rank, then entry_id.
A practice scenario set at Dream11: the tables and data are invented, and this is not a question from, or endorsed by, Dream11.
Tables
Table: ContestEntry
| Column | Type |
|---|---|
| entry_id | int |
| contest_id | int |
| user_id | int |
| points | decimal |
Primary key: entry_id.
The final fantasy points of each team in a contest (steps of 0.5).
Table: PrizeSlab
| Column | Type |
|---|---|
| contest_id | int |
| rank_from | int |
| rank_to | int |
| prize_per_rank | int |
Primary key: contest_id, rank_from.
Positions rank_from to rank_to (inclusive) each pay prize_per_rank rupees. A contest's slabs never overlap.
Examples
Example 1
ContestEntry
| entry_id | contest_id | user_id | points |
|---|---|---|---|
| 1 | 900 | 71 | 512.5 |
| 2 | 900 | 72 | 480 |
| 3 | 900 | 73 | 480 |
| 4 | 900 | 74 | 455 |
| 5 | 900 | 75 | 455 |
| 6 | 900 | 76 | 455 |
| 7 | 900 | 77 | 301 |
| 8 | 901 | 71 | 390 |
| 9 | 901 | 78 | 390 |
| 10 | 901 | 79 | 200 |
PrizeSlab
| contest_id | rank_from | rank_to | prize_per_rank |
|---|---|---|---|
| 900 | 1 | 1 | 10000 |
| 900 | 2 | 3 | 4000 |
| 900 | 4 | 5 | 1000 |
| 901 | 1 | 1 | 500 |
Output
| contest_id | entry_id | contest_rank | prize_won |
|---|---|---|---|
| 900 | 1 | 1 | 10000 |
| 900 | 2 | 2 | 4000 |
| 900 | 3 | 2 | 4000 |
| 900 | 4 | 4 | 666.67 |
| 900 | 5 | 4 | 666.67 |
| 900 | 6 | 4 | 666.67 |
| 901 | 8 | 1 | 250 |
| 901 | 9 | 1 | 250 |
How to solve Dream11: Contest Prizes When Tied Teams Share a Rank
The payout rule has two ingredients: where each team sits, and which positions its tie occupies. RANK() OVER (PARTITION BY contest_id ORDER BY points DESC) gives the shared rank — two teams level on 480 points after the leader are both rank 2 and the next team is rank 4, which is precisely the position numbering the prize table uses. COUNT(*) OVER (PARTITION BY contest_id, points) gives the size k of the tie, so the group occupies positions rank to rank + k − 1.
The prize table is in ranges, so for each slab we need how many of its positions fall inside the tie's range. Two closed intervals overlap when each starts before the other ends — that is the join condition — and the length of the overlap is LEAST(rank_to, last) − GREATEST(rank_from, rank) + 1. Multiplying by the per-position prize and summing over the overlapping slabs gives the pooled money; dividing by k gives each team's share. Teams whose positions meet no slab have no joined rows and are omitted, which is the "more than 0" rule.
The alternative expands the slabs into one row per position with a recursive CTE, computes ranks and tie sizes with correlated counts, and simply sums the positions in range. Ties are capped at a handful of teams, so a share is never a rounding half. The window version sorts each contest once; the correlated one is quadratic.
Reference solution (MySQL)
WITH ranked AS (
SELECT entry_id, contest_id,
RANK() OVER (PARTITION BY contest_id ORDER BY points DESC) AS contest_rank,
COUNT(*) OVER (PARTITION BY contest_id, points) AS tied
FROM ContestEntry
)
SELECT r.contest_id, r.entry_id, r.contest_rank,
ROUND(SUM(s.prize_per_rank * (LEAST(s.rank_to, r.contest_rank + r.tied - 1) - GREATEST(s.rank_from, r.contest_rank) + 1)) / r.tied, 2) AS prize_won
FROM ranked r
JOIN PrizeSlab s
ON s.contest_id = r.contest_id
AND s.rank_from <= r.contest_rank + r.tied - 1
AND s.rank_to >= r.contest_rank
GROUP BY r.contest_id, r.entry_id, r.contest_rank, r.tied
ORDER BY r.contest_id, r.contest_rank, r.entry_idAnother way
WITH RECURSIVE pos AS (
SELECT contest_id, rank_from AS n, rank_to, prize_per_rank FROM PrizeSlab
UNION ALL
SELECT contest_id, n + 1, rank_to, prize_per_rank FROM pos WHERE n < rank_to
),
ranked AS (
SELECT e.entry_id, e.contest_id,
1 + (SELECT COUNT(*) FROM ContestEntry b WHERE b.contest_id = e.contest_id AND b.points > e.points) AS contest_rank,
(SELECT COUNT(*) FROM ContestEntry t WHERE t.contest_id = e.contest_id AND t.points = e.points) AS tied
FROM ContestEntry e
)
SELECT r.contest_id, r.entry_id, r.contest_rank, ROUND(SUM(p.prize_per_rank) / r.tied, 2) AS prize_won
FROM ranked r JOIN pos p ON p.contest_id = r.contest_id AND p.n BETWEEN r.contest_rank AND r.contest_rank + r.tied - 1
GROUP BY r.contest_id, r.entry_id, r.contest_rank, r.tied
ORDER BY r.contest_id, r.contest_rank, r.entry_id← Dream11: Multiple Accounts Behind One Gmail Address · Dream11: Longest Run of Matches With the Same Captain →