## Tuesday, April 25, 2017

### Negative Fibonacci Numbers

Problem:

The Fibonacci numbers can be extended to zero and negative indices using the relation $F_n = F_{n+2}-F_{n+1}$. Determine $F_0$ and find a general formula for $F_{-n}$ in terms of $F_n$. Prove your result using mathematical induction.

Solution:

Using the usual definition of $F_1 = F_2 = 1$, we have $F_0 = F_2 - F_1 = 0$.

By cranking out some negative Fibonacci number, I propose $F_{-n} = (-1)^{n+1} F_{n}$.

Assuming the formula is true for all number bigger than $-n$, we have

$\begin{eqnarray*} F_{-n} &=& F_{-n + 2} - F_{-n + 1} \\ &=& (-1)^{-n + 2 + 1} F_{n - 2} - (-1)^{-n + 1 + 1} F_{n - 1} \\ &=& (-1)^{-n + 3} F_{n - 2} - (-1)^{-n + 2} F_{n - 1} \\ &=& (-1)^{-n + 1} F_{n - 2} + (-1)^{-n + 1} F_{n - 1} \\ &=& (-1)^{-n + 1} (F_{n - 2} + F_{n - 1}) \\ &=& (-1)^{-n + 1} (F_n) \end{eqnarray*}$

So the hypothesis is proved!

## Sunday, April 23, 2017

### LeetCode OJ - Array Partition I

Problem:

Please find the problem here.

Analysis:

The problem is trivial if there is only 1 pair.

If there are 2 pairs, you always do (a, b) (c, d) assuming $a < b < c < d$.

With more pairs, the idea is to sort the data first, and then pairing them up in order.

It is trivial to argue that you have to take $a$ because eventually it has to be in a pair. You can't pick $d$ regardless because it will lose in any pairs, my only option is picking $b$ or $c$, and the answer is obvious.

However, this argument doesn't generalize. We need something else to prove the idea works.

Solution:

The algorithm is greedy, so maybe we should think about proof strategy for greedy algorithms. Here is my idea, greedy stay ahead.

Let's report the pairs from the back of the array, we first report the (second largest, largest) pair. There is no way another other algorithm can produce any pair better than this one.

By induction, we can assume the algorithm stay ahead for $k$ step, now the algorithm lose in the $k + 1$ step, the only possibility is that the other algorithm somehow found a pair that is better than what my algorithm provides, but that is impossible because it is the largest possible.

I know my language is not rigorous, but you get the point, do you?

With that, the code is very simple.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/array-partition-i/

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

using namespace std;

namespace _LEET_ARRAY_PARTITION_I
{
class Solution {
public:
int arrayPairSum(vector<int>& nums)
{
int result = 0;
sort(nums.begin(), nums.end());
for (size_t i = 0; i < nums.size(); i += 2)
{
result += nums[i];
}
return result;
}
};
};

using namespace _LEET_ARRAY_PARTITION_I;

int LEET_ARRAY_PARTITION_I()
{
Solution solution;
vector<int> nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(3);
nums.push_back(4);
cout << solution.arrayPairSum(nums) << endl;
return 0;
}

## Sunday, April 2, 2017

### HackerRank - Cavity Map

Problem:

Please find the problem here.

Solution:

This is really just finding the local minimums, go through all of the candidates (the slots that is not on the edge) and check one by one would work.

Analysis:

I could potentially goes faster because for every pair of number I checked twice, but asymptotically, this is optimal.

Code:

#include "stdafx.h"

// https://www.hackerrank.com/challenges/cavity-map

#include "HACKER_RANK_CAVITY_MAP.h"

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

using namespace std;

int HACKER_RANK_CAVITY_MAP()
{
int i, j, n;
scanf("%d", &n);
char** grid = (char**)malloc(sizeof(char*) * n);
for (int grid_i = 0; grid_i < n; grid_i++)
{
grid[grid_i] = (char *)malloc(10240 * sizeof(char));
scanf("%s", grid[grid_i]);
}

for (i = 1; i < n - 1; i++)
{
for (j = 1; j < n - 1; j++)
{
if (grid[i - 1][j] < grid[i][j] && grid[i + 1][j] < grid[i][j] && grid[i][j - 1] < grid[i][j] && grid[i][j + 1] < grid[i][j])
{
grid[i][j] = 'X';
}
}
}

for (int grid_i = 0; grid_i < n; grid_i++)
{
printf("%s\n", grid[grid_i]);
}
return 0;
}