Circular Secret Santa Chain Ledger

Hard

A workplace gifting platform stores directed gift transfers between employees. Table: SecretSanta giver_id: employee who gives a gift receiver_id: employee who receives a gift gift_value: integer value of that gift transfer Business guarantees: (giver_id, receiver_id) is unique. Each employee appears at most once as giver_id. Each employee appears at most once as receiver_id. giver_id is never equal to receiver_id. Task: Identify all distinct circular gift chains. A circular chain is a closed directed loop where each participant has exactly: one outgoing edge to the next participant in the loop, and one incoming edge from the previous participant in the loop. For every detected chain, compute: chain_length: number of participants in the loop total_gift_value: sum of gift_value on loop edges Output requirements: Return exactly these columns in this order: chain_id, chain_length, total_gift_value Define chain_id as a 1-based rank after sorting detected chains by: chain_length descending total_gift_value descending smallest participant id in the chain ascending Supported submission environments: SQL (SQLite 3.27.2) Pandas (Python)

Example 1

Input

SecretSanta:
| giver_id | receiver_id | gift_value |
|----------|-------------|------------|
| 1        | 2           | 20         |
| 2        | 3           | 30         |
| 3        | 1           | 40         |
| 4        | 5           | 25         |
| 5        | 4           | 35         |

Output

[
  {"chain_id":1,"chain_length":3,"total_gift_value":90},
  {"chain_id":2,"chain_length":2,"total_gift_value":60}
]

Explanation

There are two disjoint loops. The 3-person loop ranks ahead of the 2-person loop because chain_length is the primary sort key.

Example 2

Input

SecretSanta:
| giver_id | receiver_id | gift_value |
|----------|-------------|------------|
| 10       | 11          | 7          |
| 11       | 10          | 5          |
| 20       | 21          | 8          |
| 21       | 22          | 9          |
| 22       | 23          | 10         |
| 30       | 31          | 15         |
| 31       | 32          | 5          |
| 32       | 30          | 25         |

Output

[
  {"chain_id":1,"chain_length":3,"total_gift_value":45},
  {"chain_id":2,"chain_length":2,"total_gift_value":12}
]

Explanation

Only closed loops are counted. The chain 20->21->22->23 is open and therefore excluded.

Example 3

Input

SecretSanta:
| giver_id | receiver_id | gift_value |
|----------|-------------|------------|
| 100      | 101         | 20         |
| 101      | 102         | 30         |
| 102      | 100         | 40         |
| 200      | 201         | 50         |
| 201      | 202         | 10         |
| 202      | 200         | 30         |
| 300      | 301         | 60         |
| 301      | 300         | 20         |

Output

[
  {"chain_id":1,"chain_length":3,"total_gift_value":90},
  {"chain_id":2,"chain_length":3,"total_gift_value":90},
  {"chain_id":3,"chain_length":2,"total_gift_value":80}
]

Explanation

The first two loops tie on length and value, so the tie is broken by the smallest participant id in each chain (100 before 200).

Constraints

1 <= number of rows in SecretSanta <= 250000
(giver_id, receiver_id) is unique
1 <= giver_id, receiver_id <= 1000000000
1 <= gift_value <= 1000000
giver_id != receiver_id
Each employee appears at most once as giver_id
Each employee appears at most once as receiver_id
A valid chain is a closed directed loop with no repeated participant except closure
Output columns must be exactly: chain_id, chain_length, total_gift_value
chain_id must be assigned from the requested deterministic ordering
SQL submissions are evaluated with SQLite 3.27.2 semantics
Pandas submissions must return a DataFrame with columns [chain_id, chain_length, total_gift_value]

Preparing your editor. You can read the problem while it loads.

Circular Secret Santa Chain Ledger

Hard

A workplace gifting platform stores directed gift transfers between employees. Table: SecretSanta giver_id: employee who gives a gift receiver_id: employee who receives a gift gift_value: integer value of that gift transfer Business guarantees: (giver_id, receiver_id) is unique. Each employee appears at most once as giver_id. Each employee appears at most once as receiver_id. giver_id is never equal to receiver_id. Task: Identify all distinct circular gift chains. A circular chain is a closed directed loop where each participant has exactly: one outgoing edge to the next participant in the loop, and one incoming edge from the previous participant in the loop. For every detected chain, compute: chain_length: number of participants in the loop total_gift_value: sum of gift_value on loop edges Output requirements: Return exactly these columns in this order: chain_id, chain_length, total_gift_value Define chain_id as a 1-based rank after sorting detected chains by: chain_length descending total_gift_value descending smallest participant id in the chain ascending Supported submission environments: SQL (SQLite 3.27.2) Pandas (Python)

Example 1

Input

SecretSanta:
| giver_id | receiver_id | gift_value |
|----------|-------------|------------|
| 1        | 2           | 20         |
| 2        | 3           | 30         |
| 3        | 1           | 40         |
| 4        | 5           | 25         |
| 5        | 4           | 35         |

Output

[
  {"chain_id":1,"chain_length":3,"total_gift_value":90},
  {"chain_id":2,"chain_length":2,"total_gift_value":60}
]

Explanation

There are two disjoint loops. The 3-person loop ranks ahead of the 2-person loop because chain_length is the primary sort key.

Example 2

Input

SecretSanta:
| giver_id | receiver_id | gift_value |
|----------|-------------|------------|
| 10       | 11          | 7          |
| 11       | 10          | 5          |
| 20       | 21          | 8          |
| 21       | 22          | 9          |
| 22       | 23          | 10         |
| 30       | 31          | 15         |
| 31       | 32          | 5          |
| 32       | 30          | 25         |

Output

[
  {"chain_id":1,"chain_length":3,"total_gift_value":45},
  {"chain_id":2,"chain_length":2,"total_gift_value":12}
]

Explanation

Only closed loops are counted. The chain 20->21->22->23 is open and therefore excluded.

Example 3

Input

SecretSanta:
| giver_id | receiver_id | gift_value |
|----------|-------------|------------|
| 100      | 101         | 20         |
| 101      | 102         | 30         |
| 102      | 100         | 40         |
| 200      | 201         | 50         |
| 201      | 202         | 10         |
| 202      | 200         | 30         |
| 300      | 301         | 60         |
| 301      | 300         | 20         |

Output

[
  {"chain_id":1,"chain_length":3,"total_gift_value":90},
  {"chain_id":2,"chain_length":3,"total_gift_value":90},
  {"chain_id":3,"chain_length":2,"total_gift_value":80}
]

Explanation

The first two loops tie on length and value, so the tie is broken by the smallest participant id in each chain (100 before 200).

Constraints

1 <= number of rows in SecretSanta <= 250000
(giver_id, receiver_id) is unique
1 <= giver_id, receiver_id <= 1000000000
1 <= gift_value <= 1000000
giver_id != receiver_id
Each employee appears at most once as giver_id
Each employee appears at most once as receiver_id
A valid chain is a closed directed loop with no repeated participant except closure
Output columns must be exactly: chain_id, chain_length, total_gift_value
chain_id must be assigned from the requested deterministic ordering
SQL submissions are evaluated with SQLite 3.27.2 semantics
Pandas submissions must return a DataFrame with columns [chain_id, chain_length, total_gift_value]