SPOJ Problem: Adjacent Bit Counts

30 Apr 2018 ♦ combinatorics, number-theory

A Little Background

I was trying to solve this problem on SPOJ. It’s a dynamic-programming problem. I tried to find some recursive relation. I spent hours. But no breakthrough.

I even tried looking for hints in comments and I came to know it’s a 3D dynamic-programming problem. Some of the users were even able to reduce it to a 2D technique.

Then I realized I need to rethink the entire approach. So somehow, I started treating it like a combinatorics problem and I landed on a solution — a formula that guarantees linear time execution. I love moments like these when you solve an interesting problem with an uncommon approach. And that’s why I am writing this post.

» Read More

Beggar's Method

29 Apr 2018 ♦ combinatorics, number-theory

Problem

Find the number of integer solutions i.e. ordered pairs $\left(x_1, x_2, \ldots , x_r \right)$ such that

$$x_1 + x_2 + \ldots + x_r = n, \quad x_i \geq 0, x_i \in \mathbb{Z}$$ » Read More