online advertising

Thursday, April 5, 2018

LeetCode OJ - Bomb Enemy

Problem:

Please find the problem here.

Analysis:

A brute force solution will be scanning, for each blank space, how many enemies can the bomb kill. Such a solution lead to $ O(wh(w + h) $ time algorithm with no extra space.

Solution:

But we notice a lot of scan are repeated, if we knew how many enemy we could kill on a cell just left to us, we know how many we could kill at the current cell, it has to be either 0 (if the left hand side is a wall), the same as the left hand side (if the left hand side is a blank) or 1 + left hand side (if the left hand side is an enemy). The same can apply to all direction.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/bomb-enemy

#include "LEET_BOMB_ENEMY.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

namespace _LEET_BOMB_ENEMY
{
    class Solution
    {
    public:
        int maxKilledEnemies(vector<vector<char>>& grid)
        {
            if (grid.size() == 0 || grid[0].size() == 0)
            {
                return 0;
            }
            int height = grid.size();
            int width = grid[0].size();

            vector<vector<int>> left;
            vector<vector<int>> right;
            vector<vector<int>> top;
            vector<vector<int>> bottom;
            
            left.resize(height);
            right.resize(height);
            top.resize(height);
            bottom.resize(height);
            for (int i = 0; i < height; i++)
            {
                left[i].resize(width);
                right[i].resize(width);
                top[i].resize(width);
                bottom[i].resize(width);
                for (int j = 0; j < width; j++)
                {
                    left[i][j] = 0;
                    right[i][j] = 0;
                    top[i][j] = 0;
                    bottom[i][j] = 0;
                }
            }
            int count;
            for (int row = 0; row < height; row++)
            {
                count = 0;
                for (int col = 0; col < width; col++)
                {
                    if (grid[row][col] == 'W') { count = 0; } else if (grid[row][col] == 'E') { count++; }
                    else { left[row][col] = count; }
                }
                count = 0;
                for (int col = width - 1; col >= 0; col--)
                {
                    if (grid[row][col] == 'W') { count = 0; } else if (grid[row][col] == 'E') { count++; }
                    else { right[row][col] = count; }
                }
            }

            for (int col = 0; col < width; col++)
            {
                count = 0;
                for (int row = 0; row < height; row++)
                {
                    if (grid[row][col] == 'W') { count = 0; }
                    else if (grid[row][col] == 'E') { count++; }
                    else { top[row][col] = count; }
                }
                count = 0;
                for (int row = height - 1; row >= 0; row--)
                {
                    if (grid[row][col] == 'W') { count = 0; }
                    else if (grid[row][col] == 'E') { count++; }
                    else { bottom[row][col] = count; }
                }
            }
            int kill = 0;
            for (int row = 0; row < height; row++)
            {
                for (int col = 0; col < width; col++)
                {
                    kill = max(kill, left[row][col] + right[row][col] + top[row][col] + bottom[row][col]);
                }
            }
            return kill;
        }
    };
};

using namespace _LEET_BOMB_ENEMY;

int LEET_BOMB_ENEMY()
{
    Solution solution;
    vector<vector<char>> grid;
    grid.resize(3);
    grid[0].resize(4);
    grid[1].resize(4);
    grid[2].resize(4);
    grid[0][0] = '0'; grid[0][1] = 'E'; grid[0][2] = '0'; grid[0][3] = '0';
    grid[1][0] = 'E'; grid[1][1] = '0'; grid[1][2] = 'W'; grid[1][3] = 'E';
    grid[2][0] = '0'; grid[2][1] = 'E'; grid[2][2] = '0'; grid[2][3] = '0';
    cout << solution.maxKilledEnemies(grid) << endl;
    return 0;
}

Wednesday, April 4, 2018

LeetCode OJ - Predict the Winner

Problem:

Please find the problem here.

Analysis:

At this first move, I can either choose the left or the right element, then we recursively solve the sub-problems. Imagine a function that can output both scores, the result would be

MyScore = max(left + Solve(all but left).MyScore, right + Score(all but right).MyScore)
YourScore is simply the corresponding Solve.YourScore.

The MyScore/YourScore is clumsy, all we wanted to know is if I win, so instead of tracking two numbers, let's simply track the difference.

ScoreDifference = max(left - ScoreDifference(all but left), right - ScoreDifference(all but right))

Notice the subtraction, it is a subtraction because ScoreDifference output the ScoreDifference of the current player, so when I have already took one, the score difference is actually (YourScore - MyScore), that why we need to subtract to get it right.

The sub-problem is obviously overlapped, so we need dynamic programming!

Solution:

ScoreDifference is defined on an interval, let say [i, j].

To make it easier to represent, let ScoreDifference(i, L) to be the ScoreDifference on [i, i + L], now it is obvious that we only depend on L-1, give us some space saving.

The final formula is ScoreDifference(i, L) = max(nums[i] - ScoreDifference(i + 1, L - 1), nums[j] - ScoreDifference(i, L - 1)).

Note the double buffer technique in action again, two arrays is good enough.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/predict-the-winner

#include "LEET_PREDICT_THE_WINNER.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_PREDICT_THE_WINNER
{
    class Solution
    {
    public:
        bool PredictTheWinner(vector<int>& nums)
        {
            // Denote f(i, L) to be the (nextPlayer - otherPlayer) on the interval [i, i + L] 
            // f(i, L) = nums(i) for all i
            // f(p, L) = max(num[p] - f(p + 1, L - 1), nums[q] - f(p, L - 1))
            vector<int> buffer1;
            vector<int> buffer2;
            buffer1.resize(nums.size());
            buffer2.resize(nums.size());
            for (int i = 0; i < nums.size(); i++)
            {
                buffer1[i] = nums[i];
            }
            vector<int>* prevPointer = &buffer1;
            vector<int>* nextPointer = &buffer2;
            for (int l = 1; l < nums.size(); l++)
            {
                vector<int>& prev = *prevPointer;
                vector<int>& next = *nextPointer;
                for (int p = 0; p + l < nums.size(); p++)
                {
                    next[p] = max(nums[p] - prev[p + 1], nums[p + l] - prev[p]);
                }
                swap(prevPointer, nextPointer);
            }

            // Be careful, the last computed buffer is pointed by prevPointer!
            return (*prevPointer)[0] >= 0;
        }
    };
};

using namespace _LEET_PREDICT_THE_WINNER;

int LEET_PREDICT_THE_WINNER()
{
    Solution solution;
    int test[] = { 1, 5, 233, 7 };
    cout << solution.PredictTheWinner(vector<int>(test, test + _countof(test))) << endl;
    return 0;
}

Thursday, March 15, 2018

LeetCode OJ - Longest Valid Parentheses

Problem:

Please find the problem here.

Analysis:

The "finding the longest valid substring" problem reminds me of the maximum contiguous sum problem where we have an elegant dynamic programming solution. This is modeled after that problem.

Note that a valid substring is also a valid prefix, therefore it would be useful to keep track of all the valid prefixes. If we can further identify what prefix is also a valid string, then we can simply report the longest one.

With that in mind, let's started to look into how to extend a valid prefix.

If the next character is '(', my claim is that valid prefix is still going to be a longest valid prefix, because you can easily just close it and the string is essentially the same.

If the next character is ')', then we have a problem, we don't know if it is still a valid prefix.
'()' is a valid prefix, but '())' is not.

We actually need to know how many more closing parentheses is needed. For if we knew, we can reduce that count by 1 and see if it is still a valid prefix.

One last interesting observation is that if we have a prefix that need k more closing parentheses, there must be one that need one less close parentheses - with the exception of k = 1, here is how:

From the prefix that need k close parentheses, remove any prefixes of that prefix that is a valid substring of its own. Then remove the first open parentheses that come after.

The algorithm above won't work with k = 1 because it may produce an empty string.

Solution:

The last interesting observation suggest we can build a stack of those valid prefixes with the position in the stack denote the number of parentheses required.

For example, the prefix at the top of the stack requires 0 closing parentheses, meaning it is a valid substring. The one below it requires 1, and so on.

As a special case, the top of the stack might be -1, meaning there is none valid prefixes.

To begin with, we have no valid prefixes, so the top of the stack is simply one.

Here is the really interesting part, updating the stack is easy!

Suppose we see a '(', all we have to do is to push -1. There is no valid substring that ends with the '(', and all existing strings are still valid prefix needing one more closing parentheses. The only special case is that we want to make sure we don't let -1 enter the interior of the stack.

Suppose we see a ')', all we have to do is to pop, any existing valid prefix are still valid with one less parentheses required, of course, except the one was valid to begin with isn't. In case the stack is empty, make sure we still have a -1.

Last but not least, in the popping process, we keep track of the best known valid substring and return it at the end.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/longest-valid-parentheses/

#include "LEET_LONGEST_VALID_PARENTHESES.h"
#include <stack>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_LONGEST_VALID_PARENTHESES
{
    class Solution
    {
    public:
        int longestValidParentheses(string s)
        {
            stack<int> st;
            st.push(-1);
            int m = 0;
            for (int i = 0; i < s.size(); i++)
            {
                if (s[i] == '(')
                {
                    if (st.top() == -1)
                    {
                        st.pop();
                        st.push(i);
                    }
                    st.push(-1);
                }
                else
                {
                    st.pop();
                    if (st.size() > 0)
                    {
                        if (st.top() != -1)
                        {
                            m = max(m, i - st.top() + 1);
                        }
                    }
                    else
                    {
                        st.push(-1);
                    }
                }
            }
            return m;
        }
    };
};

using namespace _LEET_LONGEST_VALID_PARENTHESES;

int LEET_LONGEST_VALID_PARENTHESES()
{
    Solution solution;
    cout << solution.longestValidParentheses("(()") << endl;
    cout << solution.longestValidParentheses(")()())") << endl;
    return 0;
}

Sunday, March 11, 2018

Codechef - Rectangle

Problem:

Please find the problem here.

Solution:

As long as we can find two pairs, we are good. 'a' can only pair with 'b', 'c' or 'd', and the remaining two must be a pair too, therefore we can use that simple condition to check.

Code:

// https://www.codechef.com/problems/RECTANGL

use std::io;

fn read_line(stdin: &io::Stdin) -> io::Result<String>
{
    let mut input = String::new();
    match stdin.read_line(&mut input)
    {
        Ok(_) => Ok(input.trim().to_string()),
        Err(e) => Err(e)
    }
}

pub fn codechef_rectangl()
{
    let stdin = io::stdin();
    let read_first_line_result = read_line(&stdin);
    if read_first_line_result.is_err()
    {
        return;
    }
    let first_line = read_first_line_result.unwrap();    
    let parse_first_line_result = first_line.parse::<usize>();
    if parse_first_line_result.is_err()
    {
        return;
    }
    let t = parse_first_line_result.unwrap();
    for _i in 0..t
    {
        let read_test_line_result = read_line(&stdin);
        if read_test_line_result.is_err()
        {
            return;
        }
        let test_line = read_test_line_result.unwrap();
        let mut iter = test_line.split_whitespace();
        let optional_token_1 = iter.next();
        if optional_token_1.is_none()
        {
            return;
        }
        let optional_token_2 = iter.next();
        if optional_token_2.is_none()
        {
            return;
        }
        let optional_token_3 = iter.next();
        if optional_token_3.is_none()
        {
            return;
        }
        let optional_token_4 = iter.next();
        if optional_token_4.is_none()
        {
            return;
        }
        let token1 = optional_token_1.unwrap();
        let token2 = optional_token_2.unwrap();
        let token3 = optional_token_3.unwrap();
        let token4 = optional_token_4.unwrap();
        let token1_parse_result = token1.parse::<i32>();
        let token2_parse_result = token2.parse::<i32>();
        let token3_parse_result = token3.parse::<i32>();
        let token4_parse_result = token4.parse::<i32>();
        if token1_parse_result.is_err()
        {
            return;
        }
        if token2_parse_result.is_err()
        {
            return;
        }
        if token3_parse_result.is_err()
        {
            return;
        }
        if token4_parse_result.is_err()
        {
            return;
        }
        let a = token1_parse_result.unwrap();
        let b = token2_parse_result.unwrap();
        let c = token3_parse_result.unwrap();
        let d = token4_parse_result.unwrap();
        if (a == b && c == d) || (a == c) && (b == d) || (a == d) && (b == c)
        {
            println!("YES");
        }
        else {
            println!("NO");
        }
    }
}

Friday, March 9, 2018

LeetCode OJ - Number of Subarrays with Bounded Maximum

Problem:

Please find the problem here.

Solution:

Cartesian tree rocks!

The key observation is that with a Cartesian tree, we can divide all the intervals into three types:


  1. Including the root
  2. Completely on the left, and
  3. Completely on the right.
For intervals of type 1 - we can easily count the numbers of them by (1 + leftSize)(1 + rightSize). We either accept them all of discard them all, because we know the root is the maximum.

For intervals of type 2 or 3, we can simply get them from recursion.

That's how I solved the problem.

The code for building the Cartesian tree is simply adopted from geeksforgeeks with some simple modification to make it works.

It is not obvious, but the tree construction is $ O(n) $, the top down recursive solution spent $ O(1) $ work on each node, so it is also $ O(n) $ amount of work to compute the final answer.


Code:

#include "stdafx.h"

// https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum

#include "LEET_NUMBER_OF_SUBARRAYS_WITH_BOUNDED_MAXIMUM.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_NUMBER_OF_SUBARRAYS_WITH_BOUNDED_MAXIMUM
{
    struct Result
    {
        int size;
        int answer;
    };

    class Solution {
    public:
        int numSubarrayBoundedMax(vector<int>& arr, int L, int R) {
            size_t n = arr.size();
            // Arrays to hold the index of parent, left-child,
            // right-child of each number in the input array
            vector<int> parent; parent.resize(arr.size());
            vector<int> leftchild; leftchild.resize(arr.size());
            vector<int> rightchild; rightchild.resize(arr.size());

            // Initialize all array values as -1
            for (int i = 0; i < arr.size(); i++)
            {
                parent[i] = -1;
                leftchild[i] = -1;
                rightchild[i] = -1;
            }

            // 'root' and 'last' stores the index of the root and the
            // last processed of the Cartesian Tree.
            // Initially we take root of the Cartesian Tree as the
            // first element of the input array. This can change
            // according to the algorithm
            int root = 0, last;

            // Starting from the second element of the input array
            // to the last on scan across the elements, adding them
            // one at a time.
            for (int i = 1; i <= n - 1; i++)
            {
                last = i - 1;
                rightchild[i] = -1;

                // Scan upward from the node's parent up to
                // the root of the tree until a node is found
                // whose value is greater than the current one
                // This is the same as Step 2 mentioned in the
                // algorithm
                while (arr[last] <= arr[i] && last != root)
                    last = parent[last];

                // arr[i] is the largest element yet; make it
                // new root
                if (arr[last] <= arr[i])
                {
                    parent[root] = i;
                    leftchild[i] = root;
                    root = i;
                }

                // Just insert it
                else if (rightchild[last] == -1)
                {
                    rightchild[last] = i;
                    parent[i] = last;
                    leftchild[i] = -1;
                }

                // Reconfigure links
                else
                {
                    parent[rightchild[last]] = i;
                    leftchild[i] = rightchild[last];
                    rightchild[last] = i;
                    parent[i] = last;
                }

            }

            // Since the root of the Cartesian Tree has no
            // parent, so we assign it -1
            parent[root] = -1;

            Result result = compute(root, arr, parent, leftchild, rightchild, L, R);
            return result.answer;
        }

        Result compute(int node, vector<int>& arr, vector<int>& parent, vector<int>& leftchild, vector<int>& rightchild, int L, int R)
        {
            Result result;
            if (node == -1)
            {
                result.size = 0;
                result.answer = 0;
            }
            else
            {
                Result leftResult = compute(leftchild[node], arr, parent, leftchild, rightchild, L, R);
                Result rightResult = compute(rightchild[node], arr, parent, leftchild, rightchild, L, R);
                result.size = leftResult.size + 1 + rightResult.size;
                result.answer = leftResult.answer + rightResult.answer;
                if (L <= arr[node] && arr[node] <= R)
                {
                    result.answer += ((1 + leftResult.size) * (1 + rightResult.size));
                }
            }

            return result;
        }
    };
};

using namespace _LEET_NUMBER_OF_SUBARRAYS_WITH_BOUNDED_MAXIMUM;

int LEET_NUMBER_OF_SUBARRAYS_WITH_BOUNDED_MAXIMUM()
{
    Solution solution;
    int test_array[] = { 2, 1, 4, 3 };
    cout << solution.numSubarrayBoundedMax(vector<int>(test_array, test_array + _countof(test_array)), 2, 3) << endl;
    return 0;
}