Topcoder SRM 553 Div-II-500 tutorial

The problem

Problem statement (requires login)

Summary of the statement is:

Given an array of non-negative integers program[], an integer wantedResult, and pseudocode of a peculiar program. This program takes program[] as argument, and reads it through. There’s also a stack initially filled with infinite number of 0’s. If program[i] = 0 it pops topmost two elements from the stack, adds them up, and pushes the sum into the stack, otherwise it pushes program[i] into stack. At the end of execution, it pops and prints the top element of the stack.

The trouble is exactly one of program[]s elements is -1. But the program operates only on non-negative integers. Return the smallest non-negative integer with which -1 can be replaced such that the program’s output is wantedResult. If no such non-negative integer exists, return -1 instead.

The idea

I started with trivial observations like disregarding all values before first 0 except the last two doesn’t change the result, etc. The key idea came out after some more moment’s thought.

The most important thing to note is, the program’s output is the sum of some positive integers, hence its output is bounded to be strictly increasing. Whenever I observe an increasing/decreasing function, binary search is the first thing that pops in my mind.

Closer examination reveals that three possible cases may arise as the replacement of -1. They are:

  1. infinite number of valid choices (i.e. in fact, the value at -1 is never added to the program’s output)
  2. only one unique choice (i.e. the program returns wantedResult, if and only if -1 is replaced with this value)
  3. no valid choice at all (i.e. the program never outputs wantedResult whatever we replace -1 with)

A check for 0 as -1’s replacement is sufficient to get rid of case 1, and for the rest two a binary search will do. Rushed into coding then.

Solution

I ended up with the Following C++ code.

class Suminator
{
    public:
        int val(vector<int> program, int ln)
        {
            int l = 0;
            vector<int> s;

            for(int i = 0; i < ln; i++)
            {
                if(program[i] == 0)
                {
                    long long a = 0, b = 0;

                    if(l > 0)
                    {
                        a = s[l - 1];
                        s.pop_back();
                        l--;
                    }

                    if(l > 0)
                    {
                        b = s[l - 1];
                        s.pop_back();
                        l--;
                    }

                    s.push_back(a + b);
                    l++;
                }
                else
                {
                    s.push_back(program[i]);
                    l++;
                }
            }

            if(l == 0)
            {
                return 0;
            }

            return s[l - 1];
        }

        int findMissing( vector <int> program, int wantedResult )
        {
            int ln = program.size();
            int lb = 0, ub = 1000000010, mid;
            vector<int> v = program;

            int ind = 0;

            for(int i = 0; i < ln; i++)
            {
                if(program[i] == -1)
                {
                    ind = i;
                    break;
                }
            }

            v[ind] = 0;

            if(val(v, ln) == wantedResult)
            {
                return 0;
            }

            while(lb < ub)
            {
                mid = (lb + ub + 1) >> 1;
                v[ind] = mid;

                if(val(v, ln) > wantedResult)
                {
                    ub = mid - 1;
                }
                else
                {
                    lb = mid;
                }
            }

            v[ind] = lb;

            if(val(v, ln) == wantedResult)
            {
                return lb;
            }

            return -1;
        }
};

Mistake!

But, this solution got stuck on some case in the system test. I was just too confident about my reasoning. Only mistake I could imagine is overflow, and really it was.

Correction

In line 29 of function val(), an addition is being performed. As elements of program[] may be as large as 10^9, an overflow is possible. Changing the function val()’s return type (line 4) and vector<int> s’s type (line 7) to long long does the correction.

Advertisements

About f.nasim

A CS undergrad from Bangladesh.
This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s