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;
}

No comments :

Post a Comment