Happiest Birthday,
Dear Hiyaa
Nazrana · नज़राना
[For Email]
You are given a weighted rooted binary tree T = (V, E, ω) with exactly 3 nodes:
V = {R, L&sub1;, L&sub2;} where R is the root
val(R) = your birth year (Y)
val(L&sub1;) = numeric day component of your father's date of birth (F)
val(L&sub2;) = numeric day component of your mother's date of birth (M)
Directed edges: R→L&sub1; and R→L&sub2;, both with edge weight ω = Y
Execute the following pipeline strictly in order:
Step 1 — LCA via Binary Lifting:
Construct the binary lifting sparse table. Compute LCA(L&sub1;, L&sub2;). Verify the path length
between L&sub1; and L&sub2; satisfies:
path_length = depth(L&sub1;) + depth(L&sub2;) − 2 × depth(LCA(L&sub1;, L&sub2;)).
If the result ≠ 2, your tree is malformed — do not proceed.
Step 2 — Heavy-Light Decomposition:
Compute subtree sizes. For R, both children have equal subtree size = 1. Break the tie using
node value: the child with the larger val becomes the heavy child. Identify the heavy path P_H
and the single light edge.
Step 3 — Segment Tree over Heavy Path:
Build a segment tree over P_H. For every non-root node v in P_H, store:
contribution(v) = ω(parent(v) → v) × val(v). Perform a range-sum
query over all positions in P_H (excluding root) to obtain C_heavy.
Step 4 — Light Edge Contribution:
For each light edge (R → u), compute:
C_light = ω(R → u) × val(u)
Step 5 — Aggregate: Ω = C_heavy + C_light
Step 6 — Binary Exponentiation:
Let δ = numeric day of your own birth date. Compute δ² using binary
exponentiation (represent the exponent 2 in binary and apply the fast-power algorithm).
Step 7 — Compute W: W = Ω + δ²
Step 8 — Format: Let μ = your birth month, zero-padded to exactly 2
digits.
Return:
"dd" + μ + W + "@gmail.com"
[For Secret Key]
Let S = her name — the word that means brain, yet also means heart, as if she was always
meant to be both — written in lowercase (4 letters).
Let A = integer array of size 3 representing birth day components, each zero-padded to 2 digits,
ordered as: A = [father's birth day, mother's birth day, your own birth day]
Execute the following pipeline strictly in order:
Step 1 — KMP Failure Function:
Compute the π-array (failure function) for string S where:
π[i] = length of the longest proper prefix of S[0..i] that is also a suffix of S[0..i].
Let k = π[|S| − 1]. Compute: rotation_key = (|S| + k) % 3
Step 2 — Right Rotation:
Perform a right rotation of array A by exactly rotation_key positions. Call the result
A_rot.
Step 3 — Merge Sort Inversion Count:
Count the total number of inversions in A_rot using the merge sort divide-and-conquer approach
(an inversion is a pair (i,j) where i < j but A_rot[i] > A_rot[j]). Let
inv = inversion_count % 3.
Step 4 — Left Rotation:
Perform a left rotation of A_rot by exactly inv positions. Call the result A_final.
Step 5 — Suffix Array Checksum:
Construct the suffix array SA of the candidate string:
T = S + A_final[0] + A_final[1] + A_final[2]. Verify:
SA[0] = |T| − 1 (the single-character suffix at the last position must be
lexicographically smallest among all suffixes). If this condition fails, re-examine your
zero-padding or rotation direction.
Step 6 — Construct and Verify Answer:
Confirm len(T) = 10. If not, recheck zero-padding on all elements of
A_final.
Return: The exact
10-character string T
That doesn't seem right ✦