| Task | #24 |
|---|---|
| Position | 7 |
| Score | 616,446 |
| Best Score | 39,871 |
| Points | 0.065 |
Problem Statement
You quote derivatives prices which counterparties trade against, posting collateral in dollars.
Counterparty accounts are initialized with a USD deposit, and they gain or lose value as prices move, in proportion to their position size in each instrument.
Accounts must maintain equity of at least 1% of their total position size across instruments.
When prices update, you must find and liquidate any accounts in violation of
this margin requirement by printing liquidate <account id> <equity> <position notional> to stdout and clearing the account’s balance and positions. For any
given price update, liquidate the accounts with the largest total position
notional first (as a tie-breaker, sort by account id descending).
Definitions and invariants
- Account equity =
balance + σ(size_i * price_i) − σ(total_paid_i). - Total position notional =
Σ(|size_i| * price_i). - Total paid = signed sum of all trades on instrument
i, i.e.Σ(trade_size × last_price)for all trades. - Margin rule: if
equity < total notional / 100after any price update, the account is liquidated.
Input (one command per line)
a <balance>— create account with given USD balance. IDs start at 0 and increment.p <instrument_idx> <price>— add or update instrument price (0-indexed).t <account_idx> <instrument_idx> <size>— trade size (signed) at the most recent price of that instrument.- Final line: a single
<account_idx>to query. Output<equity> <notional>for that account and terminate.
Limits:
- accounts ⇐ 100_000
- instruments ⇐ 1_000
- 100 ⇐ price ⇐ 1_000_000
- 1 ⇐ trade_size ⇐ 10_000
Example
a 100 # create account 0 with $100 collateral
p 0 100 # set price of instrument 0 = 100
t 0 0 10 # account 0 buys 10 contracts at 100 (notional 1000)
p 0 90 # price drops to 90 -> account loses 100 equity -> liquidate
0 # query account 0 after liquidation
Output:
liquidate 0 0 900
0 0
Generator: https://gist.github.com/yenw0d/bfeedf3702e579fe10c1b6b3d4a71767
Input Generator
Public; Ported the linked input generator to C++
Solution Sketch
Was not very different from the reference solution. Have a couple of arrays/maps with the data we have to maintain and vectorize the price updates.
Thoughts
This is a problem I was (am?) clueless on for a long time. I believe the trick is to eliminate most price updates, and then use the input distribution’s properties and the current accounts’ available margins to have some bounds outside of which you’ll actually process price updates.
There are two ways I thought of doing this:
- Since we have all the updates, process them back to front in an offline manner, to get the instruments with the largest moves, and then decide on which updates to process
- Use some heuristics to identify accounts at risk, and ignore price updates which don’t put accounts at risk. This can be done by identifying collars for each instrument, and price updates outside those collars trigger updates
I had an implementation of 2, but it failed on a lot of inputs. The issue was that because it’s cross-margin, you can creep towards the collar in every instrument an account holds and thereby cause the account to liquidate, rather than outright cross the collar in a single instrument. Maybe you have a worst-case collar in that case (I set my collar spread really tight), but that removes the gains we get and we end up processing almost every update, but with the overhead of recomputing the collars.