Hi, I’m reading the linear solution to CSES Fixed-Length Paths II here. I can’t understand why the complexity is O(n). Where does the expression di - max(dc) comes from?
Could someone please explain it to me? Thanks a lot!
this is done by small-to-large merging, which means, when we do node i, we do not change the info from the child node that has max dc and we merge all other child nodes’ info to that in order to build info for node i --> hence di - max(dc, where c is the child of i)
I don’t actually know where this expression is coming from … @dolphingarlic ?
A related (but not identical) expression which makes more sense to me is
S=\sum_{i = 1}^N\left[1+\sum_{c \in i \text{'s children}}(1+d_c) - \max_{c \in i \text{'s children}}(d_c)\right]
=N+\sum_{i = 1}^N\left(\sum_{c \in i \text{'s children}}(1+d_c) - (d_i-1)\right)
Now,
\sum_{i = 1}^N\sum_{c \in i \text{'s children}}(1+d_c)=N-1+\sum_{i=2}^Nd_i
\sum_{i = 1}^N- (d_i-1)=-\sum_{i=1}^Nd_i+N
Summing these two expressions and adding N gives
S=3N-1-d_1
which is \mathcal{O}(N).
1 Like