## Friday, October 10, 2014

### UVa Problem 679 - Dropping Balls

Problem:

Please find the problem here.

Solution:

After taking a brief break - I started to code again. Now I am on divide and conquer chapter. This problem has a straightforward simulation algorithm, which I implemented. In the worst case it takes $Q \log n$ time. That's not good since $Q$ can be large.

Off my head I don't have idea, so I try to spot patterns. Spotting pattern is a good way for solving ProjectEuler problems, so I used it. Here is my blog of my solved Project Euler problems!

First of all, I dumped the leaf numbers for each drop, they look like this.

8
12
10
14
9
13
11
15

I don't know if you can feel it or not, but I do feel there is something going on with its binary representation, so I looked at their binary representations.

00001000
00001100
00001010
00001110
00001001
00001101
00001011
00001111

Now the pattern is very obvious to me now. All I need to do is to implement the pattern, and I did, it got accepted.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/external/6/679.html

#include "UVa679.h"

#include <iostream>
#include <bitset>

using namespace std;

// #define simulation

int UVa679()
{
int number_of_cases;
cin >> number_of_cases;
for (int c = 0; c < number_of_cases; c++)
{
int depth;
int drops;
int number_of_internal_nodes = 1;

cin >> depth;
cin >> drops;

#ifdef simulation
// We don't need to keep the flag for the leaves
for (int d = 0; d < (depth - 1); d++)
{
number_of_internal_nodes *= 2;
}
number_of_internal_nodes--;

bool* tree = new bool[number_of_internal_nodes];

for (int i = 0; i < number_of_internal_nodes; i++)
{
tree[i] = false;
}

for (int i = 0; i < drops; i++)
{
int ball_position = 1;
// The ball only go down (depth - 1) times
for (int j = 0; j < depth - 1; j++)
{
if (tree[ball_position - 1] == false)
{
tree[ball_position - 1] = true;
// Go to left
ball_position = ball_position * 2;
}
else
{
tree[ball_position - 1] = false;
ball_position = ball_position * 2 + 1;
}
}

// Showing the leaf number for all drops
// cout << ball_position << endl;

// Showing the binary representation of the solution
cout << bitset<8>(ball_position) << endl;
}

delete[] tree;
#else
/*
* The key to this smart algorithm is based on the observation of the sequence in binary form.
* Running the simulation and shows the sequence in binary can easily reveal the pattern.
*/

// The binary algorithm starts with 0 drops
drops--;
int solution = 0;

for (int i = 0; i < (depth - 1); i++)
{
// Computing the ith bit
if (drops >= 1 << (depth - 2 - i))
{
drops -= 1 << (depth - 2 - i);
solution += 1 << i;
}
}
solution += 1 << (depth - 1);

cout << solution << endl;
#endif
}

return 0;
}