## Saturday, September 6, 2014

### a bit of topcoder: SRM 632 Div 2 Medium

Problem Statement:
Given d[i] array of trailing zeroes in in the representation of a[i] (where a[i] can be any satisfying integer), determine whether a consecutive sequence a[i], a[i+1], ..., a[j] can form a geometric sequence.

Solution:
I think this is a good problem :D The important observation is that a[i], ..., a[j] can form a geometric sequence if and only if d[i], ..., d[j] forms an arithmetic sequence. This is because for a[i] to have a change in d[i] to d[i+1], it has to be multiplied with a constant $$r = r_0(2^k)$$ where $$k$$ is the difference between d[i] and d[i+1]. Furthermore, $$r_0$$ must be odd, otherwise if we factor out $$2$$ from $$r_0$$ it will contribute to $$k$$ leading to a contradiction. Now if d[i], ..., d[j] does not form an arithmetic sequence, there is some point where the $$k$$ in $$r$$ changes value, which contradicts the fact that $$r$$ is constant. Finally, setting $$r_0=1$$ or any other odd valued integer will give us the desired geometric sequence.