make code for the following algorithm:
Algorithm 1.9 — The following algorithm correctly solves the problem:
Step 1: Read Input: Read integers n and m, the binary string b str of length n, and the array c0
containing n double values.
Step 2: Initialize D0 and C0: Set D0 ← 0.0 (cumulative difference based on categories)
and C0 ← 0.0 (total initial sum).
For each index i = 1 to n:
• If b str[i] = ’1’, then D0 ← D0 + c0[i].
• Otherwise, D0 ← D0 − c0[i].
• Update C0 ← C0 + c0[i].
Step 3: Initialize Summations and Current Sum: Set sum A ← 0.0 (accumulator for category
’1’), sum B ← 0.0 (accumulator for category ’0’), and C ← C0 (current total sum).
Step 4: Perform m Iterations: For each iteration t = 0 to m − 1:
• Update sum A ← sum A + ln
1 + 1
C

.
• Update sum B ← sum B + ln
1 −
1
C

.
• Update C ← C +
D0+t
C
(adjust the current sum based on cumulative difference and iteration).
Step 5: Compute Multiplicative Factors: Calculate factor A ← e
sum A (scaling factor for
category ’1’) and factor B ← e
sum B (scaling factor for category ’0’).
Step 6: Compute Expected Values
For each index i = 1 to n:
• If b str[i] = ’1’, then E[ci(m)] ← c0[i] × factor A.
• Otherwise, E[ci(m)] ← c0[i] × factor B.
Step 7: Output Expected Values: Output E[ci(m)] for all i = 1 to n with fixed decimal precision.
Proof of Correctness:

Aarush Kulkarni (November 18, 2024) 2024-25 PRIMES Math Solutions
Lemma 1.10
After initialization, the variables satisfy:
C0 =
Xn
i=1
c0[i] and D0 =
Xn
i=1
c0[i] · (2bi − 1)
where bi = 1 if b str[i] = ’1’ and bi = 0 otherwise.
Proof. By the initialization loop:
C0 =
Xn
i=1
c0[i]
and
D0 =
Xn
i=1 (
c0[i], if b str[i] = ’1’
−c0[i], if b str[i] = ’0’
=
Xn
i=1
c0[i] · (2bi − 1)
Lemma 1.11
After m iterations, the accumulators satisfy:
sum A =
mX−1
t=0
ln 
1 +
1
Ct

and sum B =
mX−1
t=0
ln 
1 −
1
Ct

where Ct+1 = Ct +
D0+t
Ct
.
Proof. The algorithm iteratively updates sum A and sum B by adding ln
1 + 1
C

and ln
1 −
1
C

respectively in each iteration t. The current sum C is updated as:
Ct+1 = Ct +
D0 + t
Ct
Thus, after m iterations:
sum A =
mX−1
t=0
ln 
1 +
1
Ct

sum B =
mX−1
t=0
ln 
1 −
1
Ct

Lemma 1.12
The multiplicative factors satisfy:
factor A =
mY−1
t=0

1 +
1
Ct

and factor B =
mY−1
t=0

1 −
1
Ct


Aarush Kulkarni (November 18, 2024) 2024-25 PRIMES Math Solutions
Proof. By definition:
sum A =
mX−1
t=0
ln 
1 +
1
Ct

=⇒ factor A = e
sum A =
mY−1
t=0

1 +
1
Ct

Similarly:
sum B =
mX−1
t=0
ln 
1 −
1
Ct

=⇒ factor B = e
sum B =
mY−1
t=0

1 −
1
Ct

Theorem 1.13
After executing the algorithm, for each i ∈ {1, 2, . . . , n}:
E[ci(m)] = c0[i] ·
(
factor A, if bi = 1
factor B, if bi = 0
Proof. From Lemma 1.10, we have:
C0 =
Xn
i=1
c0[i], D0 =
Xn
i=1
c0[i] · (2bi − 1)
At each operation t, the algorithm updates:
sum A ← sum A + ln 
1 +
1
Ct

sum B ← sum B + ln 
1 −
1
Ct

Ct+1 = Ct +
D0 + t
Ct
By Lemma 1.11, after m operations:
sum A =
mX−1
t=0
ln 
1 +
1
Ct

, sum B =
mX−1
t=0
ln 
1 −
1
Ct

And by Lemma 1.12:
factor A =
mY−1
t=0

1 +
1
Ct

, factor B =
mY−1
t=0

1 −
1
Ct

For each element i:
E[ci(m)] = c0[i] ·



Qm−1
t=0 
1 + 1
Ct

, if bi = 1
Qm−1
t=0 
1 −
1
Ct

, if bi = 0
= c0[i] ·
(
factor A, if bi = 1
factor B, if bi = 0