In this post I will mainly talk about some enrollment tips for future new Chinese students to UW-Madison. Some tips also are also applicable to students to other U.S. Universities.

In this post I will give some algorithm problem from Google OA as well as Leetcode and my thoughts on them.
Our main problem here will be the OA problem appeared in the OA practice of Google Intern 2020 Online Assesment.

## Problem Description

Problem Removed due to DMCA issue.

## Thoughts

### Original Problem

Patience. Deal cards $c_1, c_2, …, c_n$ into piles according to two rules:

• Can’t place a higher-valued card onto a lowered-valued card.
• Can form a new pile and put a card onto it.
Goal. Form as few piles as possible.

### Dual Problem

The dual problem for this is Longest increasing subsequence. And the Problem is defined as: Given a sequence of elements $c_1, c_2, …, c_n$ from a totally-ordered universe, find the longest increasing subsequence.

### Duality Proof

• Greedy Algorithm
• Place each card on leftmost pile that fits.
• Observation. At any stage during greedy algorithm, top cards of piles increase from left to right.
• Weak duality.
• In any legal game of patience, the number of piles ≥ length of any increasing subsequence.
• Proof.
1. Cards within a pile form a decreasing subsequence.
2. Any increasing sequence can use at most one card from each pile.
• Strong duality
• [Hammersley 1972]Min number of piles = max length of an IS; moreover greedy algorithm finds both.
• Proof.
Each card maintains a pointer to top card in previous pile at time of insertion.
1. Follow pointers to obtain IS whose length equals the number of piles.
2. By weak duality, both are optimal.

Conclusion
The length of longest increasing subsequence is equal to the smallest number of decresing subsequences.

## Solution

### Greedy Algorithm + Binary Search Algorithm

Time complexity: $O(n\log n)$

### DP

Time complexity: $O(n^2)$

• Patience sorting
• Deal all cards using greedy algorithm; repeatedly remove smallest card.
• For uniformly random deck, time complexity: $O(n^{3/2})$
• ([Persi Diaconis]Patience sorting is the fastest wayto sort a pile of cards by hand.)

## Reference

In this post, I will introduce the essential steps to install MATLAB on a server with only Command Line Interface.

Keywords: MATLAB, CLI, installation, activation

There are many public face datasets available on the Internet for reseach purposes at present. In this post, I collect most of them and give each of them a small desciption so that people can select the proper one quickly. Selecting and preprocessing the datasets properly can be critical to the performance and reliability of the results.

Keywords: face-recognition, dataset, VGG-Face, VGG-Face2, CASIA-WebFace, UMDFaces, MS-Celeb-1M, MegaFace

0%