## Monday, January 15, 2018

### LeetCode OJ - Special Binary String

Problem:

Please find the problem here.

Analysis:

First, note that a special string is basically well parenthesized expressions, with 1 being the open bracket and 0 being the close bracket. With the given definition, it could be ()()().

It is convenient to work with a single bracket, so we simply bracket the whole thing, like this:

(()()())

That allow us to model this as a tree, the one as a single root node with 3 children, which in turn has no children.

Solution:

The idea to obtain the largest lexicographical string is to sort the sub trees. Note that a tree with height 3 is going to be better than the tree with height 2, because the former is bound to be 1110... and the later is 110... With the same height? That is not so easy. Assuming both trees are already optimal, we basically compare bit by bit. Let say we are comparing a tree named left and a tree named right. If the first children of left is lexicographically larger/smaller than the first children of right, then left is lexicographically larger/smaller than right. Otherwise we compare the second children, and so on. If all children matches up, the one with more children wins (because it will have a one, and the other will have a 0). And just in case they have the same number of children? They are basically identical.

The sorting suggest a recursive algorithm, the base case is a tree with no children, there is nothing to sort. Assuming the children are optimized, then we can optimize it by sorting the children using the comparison above.

To make height comparison fast, I compute and save the height as part of the optimization.

Last but not least, I spent some good time to debug this problem, the print() routine is very useful to visualize the tree. It prints out the brackets at the right height. In this first print, it is called after optimize(), but it is actually the before optimize tree because the s and e values are unchanged. The second time is the optimized tree.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/special-binary-string

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

using namespace std;

namespace _LEET_SPECIAL_BINARY_STRING
{
#define LOG

struct Bracket
{
vector<Bracket*> children;
Bracket* parent;
int height;
size_t s;
size_t e;
};

int compare(const Bracket* a, const Bracket* b)
{
if (a->height == a->height)
{
for (int i = 0; i < a->children.size() && i < b->children.size(); i++)
{
int result = compare(a->children[i], b->children[i]);
if (result != 0)
{
return result;
}
}
return a->children.size() - b->children.size();
}
else
{
return a->height - b->height;
}
}

class Solution
{
public:
void optimize(Bracket* node)
{
node->height = 1;
for (auto child : node->children)
{
optimize(child);
node->height = max(node->height, child->height + 1);
}
sort(node->children.begin(), node->children.end(), [](const Bracket* a, const Bracket* b) -> bool
{
return compare(a, b) > 0;
});
}

void build(Bracket* node, ostringstream& sb, bool skip)
{
if (!skip)
{
node->s = sb.tellp();
sb << "1";
}
for (auto child : node->children)
{
build(child, sb, false);
}
if (!skip)
{
node->e = sb.tellp();
sb << "0";
}
}

#ifdef LOG
void print(Bracket* node, string t)
{
for (int h = node->height - 1; h > 0; h--)
{
for (size_t i = 0; i < t.size(); i++)
{
t[i] = ' ';
}
print(node, t, h);
cout << t << endl;
}
}

void print(Bracket* node, string& t, int height)
{
if (node->height > height)
{
for (auto child : node->children)
{
print(child, t, height);
}
}
else if (node->height == height)
{
t[node->s] = '(';
t[node->e] = ')';
}
}
#endif

string makeLargestSpecial(string s)
{
Bracket* root = new Bracket();
Bracket* current = root;
for (size_t i = 0; i < s.size(); i++)
{
if (s[i] == '1')
{
Bracket* new_bracket = new Bracket();
new_bracket->s = i;
new_bracket->parent = current;
current->children.push_back(new_bracket);
current = new_bracket;
}
else
{
current->e = i;
current = current->parent;
}
}
optimize(root);
#ifdef LOG
print(root, s);
#endif
ostringstream sb;
build(root, sb, true);
#ifdef LOG
print(root, s);
#endif
return sb.str();
}
};
};

using namespace _LEET_SPECIAL_BINARY_STRING;

int LEET_SPECIAL_BINARY_STRING()
{
Solution solution;
cout << solution.makeLargestSpecial("1101001110001101010110010010") << endl;
return 0;
}

### Codechef - Chef And his Cake

Problem:

Please find the problem here.

Solution:

There are only two possible configurations. Just compute the cost of both and output the one with smaller cost.

Code:

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

use std::io;

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

pub fn codechef_git01()
{
let stdin = io::stdin();
{
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
{
{
return;
}
let test_line = read_test_line_result.unwrap();
let find_space_result = test_line.find(' ');
if find_space_result.is_none()
{
return;
}
let space_index = find_space_result.unwrap();
let test_token_1 = &test_line[..space_index];
let test_token_2 = &test_line[space_index + 1..];
let parse_height_result = test_token_1.parse::<usize>();
let parse_width_result = test_token_2.parse::<usize>();
if parse_height_result.is_err()
{
return;
}
if parse_width_result.is_err()
{
return;
}
let width = parse_width_result.unwrap();
let height = parse_height_result.unwrap();
let mut cur_row = 0;
let mut cost1 = 0;
let mut cost2 = 0;
for row in 0..height
{
{
return;
}
let test_matrix_row = read_test_matrix_row_result.unwrap();
if test_matrix_row.len() != width
{
return;
}
let mut cur = cur_row;
for c in test_matrix_row.chars()
{
if c == 'R'
{
if cur == 0
{
cost2 = cost2 + 5;
}
else
{
cost1 = cost1 + 5;
}
}
else if c == 'G'
{
if cur == 0
{
cost1 = cost1 + 3;
}
else
{
cost2 = cost2 + 3;
}
}
else
{
return;
}
cur = 1 - cur;
}
cur_row = 1 - cur_row;
}
if cost1 > cost2
{
println!("{}", cost2);
}
else
{
println!("{}", cost1);
}
}
}

## Saturday, January 13, 2018

### LeetCode OJ - Reach a Number

Problem:

Please find the problem here.

Analysis:

In this problem I attempt to solve this problem. In $n$ step, what is the set of reachable places. Turn out we have a nice closed form solution to it.

In the first step, we can reach {-1, 1}, that is obvious.
In the next step, we can reach {-3, -1, 1, 3}
In the next step, we can reach { -6, -4, -2, 0, 2, 4, 6}

It is obvious that the largest reachable number is $\frac{n(n + 1)}{2}$, mirror on the negative side. What is not so obvious is that we can reach every other number in between (as far as we observed). Is that true?

Well, it is, an here is a proof - it is obvious for the base case.
To induce, assume we can reach somewhere in the $k + 1$ step, we can always undo the last step, by induction hypothesis, we should be able to reach its 'neighbor' (i.e. two steps besides it) and redo the last step, that make it possible to reach its new neighbor.

That basically solved our problem, the reachable set of $n$ step is basically every other element in $[\frac{-n(n+1)}{2}, \frac{n(n+1)}{2}]$.

Solution:

With the solution in mind, we can simply find the smallest $n$ such that $\frac{n(n+1)}{2} > t$ and with the same parity. In the code, we will use binary search to find it.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/reach-a-number

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

using namespace std;

namespace _LEET_REACH_A_NUMBER
{
class Solution
{
public:
int reachNumber(int target)
{
if (target < 0)
{
target = -target;
}
int64_t l = 0;
int64_t r = target;
while (true)
{
int64_t m = (l + r) / 2;
int64_t probe = m * (m + 1) / 2;
if (probe >= target)
{
r = m;
}
else
{
l = m;
}
if (r - l == 1)
{
do
{
probe = r * (r + 1) / 2;
if (probe % 2 == target % 2)
{
return (int)r;
}
else
{
r++;
}
} while (true);
}
}

}
};
};

using namespace _LEET_REACH_A_NUMBER;

int LEET_REACH_A_NUMBER()
{
Solution solution;
cout << solution.reachNumber(3) << endl;
cout << solution.reachNumber(2) << endl;
return 0;
}

### LeetCode OJ - 3Sum Closest

Problem:

Please find the problem here.

Analysis:

It is easy to try all triples in $O(n^3)$ time, our goal is to reduce it to $O(n^2)$.

If have $O(n^2)$ time to spend, we can first sort the array.

Solution:

Consider the simple problem of doing 2Sum closest, and we have a sorted array, here is an $O(n)$ algorithm for it. The basic idea is elimination, it can be visualized using this 'diagram'.

p/q 0 1 2 3 . 8 9
0   x           T
1   x x
2   x x x
3   x x x x
.   x x x x x
8   x x x x x x
9   x x x x x x x

The crosses are obvious, we requires p < q, the T marks the pair we want to test next.

Now we have tested a[0] + a[9] > target, therefore we eliminated the last column, they can never be closer to the target than a[0] + a[9], and mark them as D

p/q 0 1 2 3 . 8 9
0   x         T G
1   x x         D
2   x x x       D
3   x x x x     D
.   x x x x x   D
8   x x x x x x D
9   x x x x x x x

Next we have tested a[0] + a[8] < target, so we eliminate the first row, as they can never be closer to target than a[0] + a[8], and mark them as D

p/q 0 1 2 3 . 8 9
0   x D D D D L G
1   x x       T D
2   x x x       D
3   x x x x     D
.   x x x x x   D
8   x x x x x x D
9   x x x x x x x

It goes on until we try everything, this procedure reduce the |p| - |q| by one for each iteration, so it is linear.

For 3Sum closest, all we need to do is to pick a specific element out of the list and consider the rest as a 2Sum closest problem, that we will spend $O(n)$ time for each element, an overall of $O(n^2)$ time.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/3sum-closest

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

using namespace std;

namespace _LEET_3SUM_CLOSEST
{
class Solution
{
public:
int threeSumClosest(vector<int>& nums, int target)
{
sort(nums.begin(), nums.end());

size_t n = nums.size();
bool first = true;
int best_diff = 0;
for (size_t p = 0; p < n; p++)
{
int b = 0;
int e = n - 1;
while (true)
{
if (b == p) { b++; }
if (e == p) { e--; }
if (b >= e)
{
break;
}
int candidate = nums[b] + nums[p] + nums[e];
if (first)
{
best_diff = candidate - target;
first = false;
}
else
{
int diff = candidate - target;
int abs_diff = diff > 0 ? diff : -diff;
int abs_best_diff = best_diff > 0 ? best_diff : -best_diff;
if (abs_diff < abs_best_diff)
{
best_diff = diff;
}
}
if (candidate > target)
{
e--;
}
else if (candidate == target)
{
return target;
}
else
{
b++;
}
}
}

return target + best_diff;
}
};
};

using namespace _LEET_3SUM_CLOSEST;

int LEET_3SUM_CLOSEST()
{
Solution s;
int case1_array[] = { 0, 1, 2 };
vector<int> case1(case1_array, case1_array + _countof(case1_array));
cout << s.threeSumClosest(case1, 0) << endl;
return 0;
}

## Tuesday, January 2, 2018

### Codechef - Days in Month

Problem:

Please find the problem here.

Solution:

This is a trivial problem. The only non-trivial part is start I start learning using Rust.

Code:

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

use std::io;

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

fn to_day_of_week(input: &str) -> Option<usize>
{
if input == "mon"
{
Some(0)
}
else if input == "tues"
{
Some(1)
}
else if input == "wed"
{
Some(2)
}
else if input == "thurs"
{
Some(3)
}
else if input == "fri"
{
Some(4)
}
else if input == "sat"
{
Some(5)
}
else if input == "sun"
{
Some(6)
}
else
{
None
}
}

pub fn codechef_nw1()
{
let stdin = io::stdin();
{
let first_line = read_first_line_result.unwrap();
let parse_first_line_result = first_line.parse::<i32>();
if parse_first_line_result.is_ok()
{
let t = parse_first_line_result.unwrap();
for _i in 0..t
{
{
let test_line = read_test_line_result.unwrap();
let find_space_result = test_line.find(' ');
if find_space_result.is_some()
{
let space_index = find_space_result.unwrap();
let test_token_1 = &test_line[..space_index];
let test_token_2 = &test_line[space_index + 1..];
let parse_day_result = test_token_1.parse::<i32>();
if parse_day_result.is_ok()
{
let days = parse_day_result.unwrap();
let day_of_week_result = to_day_of_week(test_token_2);
if day_of_week_result.is_some()
{
let mut day_of_week = day_of_week_result.unwrap();
let mut stats = [0, 0, 0, 0, 0, 0, 0];
for _d in 0..days
{
stats[day_of_week] = stats[day_of_week] + 1;
day_of_week = day_of_week + 1;
day_of_week = day_of_week % 7;
}
println!("{} {} {} {} {} {} {}", stats[0], stats[1], stats[2], stats[3], stats[4], stats[5], stats[6]);
}
}
}
}
}
}
}
}

## Monday, January 1, 2018

### LeetCode OJ - Single Element in a Sorted Array

Problem:

Please find the problem here.

Solution:

The problem is simple, the hard part is the $O(\log n)$ time requirement. We need a way to find out the single element without looking at all the values.

This requirement sounds familiar with binary search, so here is the key idea for the solution.

An array with pairs and the single element necessarily has odd number of elements.

If we remove "the central pair", either the left or the right has the odd number of elements, just recursively solve the problem there.

Analysis:

The problem size is removed by half for each recursive call, and therefore it does work in $O(\log n)$ time.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/single-element-in-a-sorted-array

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

using namespace std;

namespace _LEET_SINGLE_ELEMENT_IN_A_SORTED_ARRAY
{
class Solution
{
public:
int singleNonDuplicate(vector<int>& nums)
{
return singleNonDuplicate(nums, 0, nums.size());
}

int singleNonDuplicate(vector<int>& nums, int begin, int end)
{
int length = end - begin;
int middle = (begin + end) / 2;

if (length == 1)
{
return nums[begin];
}
else
{
int val_c = nums[middle];
int val_l = nums[middle - 1];
int val_r = nums[middle + 1];
int idx_l;
int idx_r;
if (val_l == val_c)
{
idx_l = middle - 1;
idx_r = middle + 1;
}
else if (val_c == val_r)
{
idx_l = middle;
idx_r = middle + 2;
}
else
{
return val_c;
}
int len_l = idx_l - begin;
int len_r = end - idx_r;
if (len_l % 2 == 1)
{
return singleNonDuplicate(nums, begin, idx_l);
}
else
{
return singleNonDuplicate(nums, idx_r, end);
}
}
}
};
};

using namespace _LEET_SINGLE_ELEMENT_IN_A_SORTED_ARRAY;

int LEET_SINGLE_ELEMENT_IN_A_SORTED_ARRAY()
{
Solution solution;
int input_array[] = { 1, 1, 2, 3, 3, 4, 4, 5, 5 };
vector<int> input(input_array, input_array + _countof(input_array));
cout << solution.singleNonDuplicate(input) << endl;
return 0;
}