Solution set

Algorithms & Mathematics Society AMS Round 1 | March 2026

THE GOLD STANDARD FOR QUANT-TRACK ENGINEERING TALENT [Link]

A. High-Frequency Expected Returns Time: 2s | Memory: 256 MB

Problem A:

Hint 1
Can you compute the expected profit for a single instrument i in isolation? Think about what each side (ask and bid) independently
contributes.

Hint 2
Since all fill events are independent across instruments and sides, linearity of expectation lets you sum contributions freely. For
instrument i, the ask contributes pi · si and the bid contributes qi · si , regardless of whether pi + qi ≤ 1.

Solution.
By linearity of expectation:
N
X
E[Profit] = si (pi + qi )
i=1

Simply read each triple and accumulate. O(N ) time, O(1) space.

C++ Solution // Author: tee_01

1 # include < bits / stdc ++. h >

2 using namespace std ;
3

4 int main () {
5 ios :: sync_with_stdio ( false ) ;
6 cin . tie ( nullptr ) ;
7

8 int N ; cin >> N ;

9 long double ans = 0.0 L ;
10

11 for ( int i = 0; i < N ; ++ i ) {

12 long double p , q , s ;
13 cin >> p >> q >> s ;
14 ans += s * ( p + q ) ;
15 }
16

17 cout << fixed << setprecision (6) << ( double ) ans << " \ n " ;
18 return 0;
19 }
B. Birthday Paradox Time: 2s | Memory: 256 MB

Problem B.
P
Given D days in a year and a threshold probability Q (with gcd(P, Q) = 1), find the minimum number of people N such that
P
P (collision) ≥ Q, where:

D × (D − 1) × · · · × (D − N + 1)
P (collision) = 1 − P (all different), P (all different) =
DN

Hint 1
P Q−P
Instead of tracking P (collision), think about its complement. You want P (all different) ≤ 1 − Q = Q . Can you multiply in one new
person at a time and check when this threshold is crossed?

Hint 2
Each new person n multiplies the running probability by D−n
D . Start with current_prob = 1.0 and keep multiplying until current_prob
≤ Q−P
Q . The answer is the number of multiplications performed. Since D ≤ 106 , this loop terminates quickly — the birthday paradox
√
guarantees N = O( D).

Solution.
Iterate n = 1, 2, . . ., maintaining:
D−n
current_prob ×=
D
Q−P
√
Stop when current_prob ≤ Q . Output n. By the birthday paradox, the loop runs at most O( D) steps, giving overall complexity
√
O(T D).

C++ Solution

1 # include < bits / stdc ++. h >

2 using namespace std ;
3 using ll = long long ;
4

5 void solve () {
6 ll D , P , Q ; cin >> D >> P >> Q ;
7 double target = ( double ) ( Q - P ) / Q ;
8

9 double current_prob = 1.0;

10 double invD = 1.0 / D ;
11 ll n = 1;
12

13 while ( current_prob > target ) {

14 current_prob *= ( D - n ) * invD ;
15 n ++;
16 }
17 cout << n << " \ n " ;
18 }
19

20 int main () {
21 ios_base :: sync_with_stdio ( false ) ;
22 cin . tie ( NULL ) ;
23 int t ; cin >> t ;
24 while (t - -) solve () ;
25 return 0;
26 }

C. Portfolio Drift Time: 2s | Memory: 256 MB

Hint 1
Since the same multiplicative shock is applied to all assets simultaneously each day, the expected total value after d days factors
P cleanly.
What is the expected multiplier for a single day? Can you express the answer as S0 × (single-day multiplier)d , where S0 = pi ?

Hint 2
The single-day expected multiplier is:

a 100 + x b 100 − y a(100 + x) + b(100 − y)

µ= · + · =
a+b 100 a+b 100 100(a + b)
9
Since the answer must be given modulo 109 + 7, division becomes modular inverse. Use Fermat’s little theorem: Q−1 ≡ Q10 +5

(mod 109 + 7). Then raise µ to the d-th power with fast exponentiation.

Solution Approach.
Pn
Step 1. Compute S0 = i=1 pi (mod 109 + 7).
Step 2. Compute the single-day expected multiplier as a fraction:

a(100 + x) + b(100 − y)
µ= (mod 109 + 7)
100(a + b)

using modular inverse for the denominator.

Step 3. The answer is S0 · µd (mod 109 + 7), computed via fast exponentiation in O(log d).
Overall complexity: O(n + log d).

C++ Solution

1 # include < bits / stdc ++. h >

2 using namespace std ;
3 using ll = long long ;
4 const ll MOD = 1 e9 + 7;
5

6 ll power ( ll base , ll exp ) {

7 ll res = 1; base %= MOD ;
8 while ( exp > 0) {
9 if ( exp & 1) res = res * base % MOD ;
10 base = base * base % MOD ;
11 exp > >= 1;
12 }
13 return res ;
14 }
15

16 ll modInverse ( ll n ) { return power (n , MOD - 2) ; }

17

18 void solve () {
19 ll n , d , a , b , x , y ;
20 cin >> n >> d >> a >> b >> x >> y ;
21

22 ll S0 = 0;
23 for ( int i = 0; i < n ; ++ i ) {
24 ll p ; cin >> p ;
25 S0 = ( S0 + p ) % MOD ;
26 }
27

28 ll numerator = ( a % MOD * ((100 + x ) % MOD ) % MOD

29 + b % MOD * ((100 - y + MOD ) % MOD ) % MOD ) % MOD ;
30 ll denominator = 100 % MOD * (( a + b ) % MOD ) % MOD ;
31

32 ll mu = numerator % MOD * modInverse ( denominator ) % MOD ;

33 ll ans = S0 * power ( mu , d ) % MOD ;
34 cout << ans << " \ n " ;
35 }
36

37 int main () {
38 ios_base :: sync_with_stdio ( false ) ;
39 cin . tie ( NULL ) ;
40 solve () ;
41 return 0;
42 }
D. Apex Duel Probability Time: 1s | Memory: 256 MB

Problem D.
A tournament of 2n nodes proceeds over n stages. At each stage k , the 2k surviving nodes are paired uniformly at random; the node
with the smaller dominance index always wins. Nodes 1 and 2 always survive until they meet. Find the probability that nodes 1 and 2
meet exclusively in Stage 1 (the final), expressed as an irreducible fraction p/q .

Hint 1
Since nodes 1 and 2 always beat everyone else, both are guaranteed to survive every stage. So the only question is: when do they get
paired? At stage k there are 2k nodes. What is the probability that two specific nodes are paired together?

Hint 2
With 2k nodes, the probability two specific nodes are paired is 2k1−1 . For nodes 1 and 2 to meet only in Stage 1, they must avoid each
other in every stage k = n, n − 1, . . . , 2, then meet in Stage 1 (probability 1). This gives a telescoping product — look for cancellation
across consecutive terms.

Solution Approach.
2k −2
The probability nodes 1 and 2 are not paired at stage k is 2k −1
. So:

n n n
Y 2k − 2 Y 2(2k−1 − 1) n−1
Y 2k−1 − 1
P = = = 2 ·
2k − 1 2k − 1 2k − 1
k=2 k=2 k=2

The product telescopes:

n
Y 2k−1 − 1 (21 − 1)(22 − 1) · · · (2n−1 − 1) 1
= = n
2k − 1 (22 − 1)(23 − 1) · · · (2n − 1) 2 −1
k=2

Therefore:
2n−1
P =
2n − 1
Since 2n−1 is even and 2n − 1 is odd, gcd(2n−1 , 2n − 1) = 1 — the fraction is already irreducible. For n ≤ 62, values fit in 64-bit integers
but use __int128 to safely compute 2n .

C++ Solution

1 # include < bits / stdc ++. h >

2 using namespace std ;
3 using ll = long long ;
4

5 int main () {
6 ios :: sync_with_stdio ( false ) ;
7 cin . tie ( nullptr ) ;
8

9 ll n ; cin >> n ;
10

11 __int128 num = ( __int128 ) 1 << ( n - 1) ;

12 __int128 den = (( __int128 ) 1 << n ) - 1;
13

14 ll g = __gcd (( ll ) num , ( ll ) den ) ;

15 num /= g ;
16 den /= g ;
17

18 cout << ( ll ) num << " / " << ( ll ) den << " \ n " ;
19 return 0;
20 }
E. Spread Extraction Valuation Engine (SEVE) Time: 2s | Memory: 256 MB

Problem E.
A Bellman-optimal quote engine operates in a liquidity regime with N equiprobable outcomes per cycle:

• Events 1 through N − 1: favourable fills — if current P&L is M , it becomes M + k after event k

• Event N : adverse selection event (ASE) — position liquidated at zero P&L; cycle terminates immediately

At each step the engine chooses to continue (risk the next event) or flatten (lock in current P&L), always following the Bellman-optimal
policy. Given N and Q queries, answer:

• Type 1 — Seat Fee: is the optimal expected P&L from M = 0 at least F ?

• Type 2 — State Valuation: given current mark-to-market P&L of M ticks, what is the maximum achievable expected P&L under the
optimal policy?

Hint 1
Let ev(M ) be the Bellman-optimal expected P&L from state M . The engine continues only if the expected gain from doing so exceeds
M (i.e. flattening). Note that once M ≥ T = N (N2−1) , the remaining events can add at most T ticks total, so flattening is always optimal.
What is ev(M ) for M ≥ T ?

Hint 2
For M ≥ T , ev(M ) = M (flatten immediately). For M < T , since the engine is Bellman-optimal and ev is non-decreasing, continuing
is always better — so:
N −1
1 X
ev(M ) = ev(M + k)
N
k=0

This is a sliding window average of N consecutive values. Fill backwards from M = T − 1 to M = 0, maintaining a running sum of the
window.

Solution Approach.

N (N −1)
Threshold. For M ≥ T = 2 , always flatten: ev(M ) = M .
Backward recurrence. For M < T :
N −1
1 X
ev(M ) = ev(M + k)
N
k=0

Initialise ev(M ) = M for all M ≥ T . Then iterate M = T − 1 down to 0, keeping a running sum over the window [ev(M ), . . . , ev(M +
N − 1)]. Each step: add ev(M ), subtract ev(M + N − 1), divide by N .
Queries. Type 1: compare ev(0) against F . Type 2: output M if M ≥ T , else ev(M ).
100×99
Complexity. O(T ) per test case with T ≤ 2 = 4950, then O(1) per query.
 C++ Solution

1 # include < bits / stdc ++. h >

2 using namespace std ;
3 using ll = long long ;
4 using ld = long double ;
5

6 const int MAXN = 3000005;

7

8 int main () {
9 ios_base :: sync_with_stdio ( false ) ;
10 cin . tie ( NULL ) ;
11 cout << fixed << setprecision (2) ;
12

13 int t ; cin >> t ;

14 while (t - -) {
15 ll n , q ; cin >> n >> q ;
16 ll threshold = n * ( n - 1) / 2;
17

18 ll limit = min ( threshold , ( ll ) MAXN ) ;

19 vector < ld > ev ( limit + n + 100) ;
20

21 // Base case : ev ( M ) = M for M >= threshold

22 for ( ll i = limit ; i < limit + n + 50; i ++)
23 ev [ i ] = ( ld ) i ;

24

25 // Sliding window sum over [ ev ( limit ) , ... , ev ( limit +n -2) ]

26 ld current_sum = 0;
27 for ( int i = 0; i < n - 1; i ++)
28 current_sum += ev [ limit + i ];
29

30 // Fill backwards
31 for ( ll m = limit - 1; m >= 0; m - -) {
32 ev [ m ] = current_sum / n ;
33 current_sum += ev [ m ];
34 current_sum -= ev [ m + n - 1];
35 }
36

37 while (q - -) {
38 int type ; cin >> type ;
39 if ( type == 1) {
40 ll f ; cin >> f ;
41 cout << ( ev [0] >= ( ld ) f - 1e -9 L ? " YES " : " NO " ) << " \ n " ;
42 } else {
43 ll m ; cin >> m ;
44 if ( m >= threshold ) cout << m << " .00\ n " ;
45 else cout << ev [ m ] << " \ n " ;
46 }
47 }

48 }
49 return 0;
50 }