\(N\) (\(1 \le N \le 25,000\)) cows, each cow only available for a interval of time. \(T\) (\(1 \le T \le 1,000,000\)) shifts. Find minimum number of cows to complete \(T\) shifts.

Link: http://poj.org/problem?id=2376

Notes

• Each shift must has at least one cow assigned to it.
• A cow finishes after the end time. That is, if there are two cows, start and end at \((1, 3)\) and \((4, 10)\) respectively. It is considered as an continuous internal and accepted case for \(T = 10\).
• There can not have any gap between these cows’s working intervals.
• Use scanf() for input otherwise it will run out of the time limit.

Solution

Sort cows by ending time. Using greedy that for each interval, find the cow which has latest end time and before the current end time. As the vector is sorted, the first cow we find is the answer.

There is a 5 * 5 array filled with integers. You can only go up, down, left and right. You can start on any point in the array and can only move 5 times. Therefore, you will get 6 integers.

Find the number of distinct integers you can constructed.

Link: http://poj.org/problem?id=3050

Solution

I use a set to avoid same sequences. Since there are only 6 steps and the array is only 5*5, dfs each point, add into the set.

There are 1 to \(N\) digits (\(1\le N \le 10\)) in certain order. Add adjacent numbers together to get the next line, until the there is only one number left.(Just like Pascal’s triangle) For example, there are 3 integers: $$ 1, 2, 3 $$ $$ 3, 5 $$ $$ 8 $$

So, given \(N\) and the final sum, find the lexicographically least ordering of integers.

Link: http://poj.org/problem?id=3187

Notes:

• Be aware of that the question is asking 1 to \(N\) digits, so we don’t have to test all possible permutations from 1 to 10.

Binary tree is called so because of its shape. It’s like a tree, it have leaves and a root. In computer science, the “tree” is usually upside down, the root at the top and leaves grow below it. It is binary so it every node only can have 0, 1 or 2 leaves.

Terminologies

Leaf Node

The node do NOT have any child nodes.

Inner Node

The Node between the leaf node and the root.

Stack, queue and Linked lists are basic data structures. They appear in our daily life. For example, stacks of intermodal containers at the port, waiting in line(queue) to ride a roller coaster and the film The Human Centipede，if you know it.

Stack

Intro

Stack is like a stack of intermodal containers, or a stack of book. Every time you want to put a new item, you put above the original stack, not between or below. Every time you want to remove a item, you need to start from the top, remove the item which is latest added. Hence, there is a principle called “LIFO”, Last In, First Out.

Why Jekyll and Github Pages

Jekyll is an static site generator, it is simple to use with YAML front matter. It is quite convenient to blog with markdown and Jekyll supports it build-in. Github Pages provide the space to host the website for free. Both of them are well-documented, and works well with each other. One thing that makes they works well but not perfect is that although Github Pages can generate the website using Jekyll but as it generates in safe mode, it does not support Jekyll plugin. However, the good news is we can generate the site locally and then push it to Github. It sounds like not convenient but we can write a bash script to do so automatically in one step. We will talk about it later.