USACO - Job Processing

We can calculate the earliest finish time for each job with machine A or B independently in a greedy way. For example, with each job to be delivered, we use free_x[i] to represent when will machine i of type x will be available for it, and rate_x[i] to denote the processing rate of machine i of type x. For job j, find the smallest free_x[i] + rate_x[i], assign it to done_x[j] which is the finish time for job j using machine type x alone, then update free_x[i] with value done_x[i].

We get done_a[1..njob] and done_b[1..njob] with this method. Max(done_a[1..njob]) should be the answer to the first question of the problem. To find the answer to the second question, we can use yet another greedy approach which is introduced by the following lemma:

For two arrays A[1..n] and B[1..n] of positive integers and also of the same size, with A[1..n] and B[1..n] already sorted increasingly and decreasingly respectively, and A'[1..n] and B'[1..n] to represent any other possible permutations of the elements of the two arrays, we say Max(A[i]+B[i]) will be no bigger than Max(A'[i]+B'[i]).

We can prove this lemma by induction. It's trivial for n=1. Assume it's true for size n-1, then for arrays of size n, we first remove the last element of each array leaving A[1..n-1] and B[1..n-1] with the relation Max(A[i]+B[i]) <= Max(A'[i]+B'[i]) for i<n. We now need to consider A[n]+B[n] with respect to Max(A[i]+B[i]).

1. If A[n] + B[n] >= Max(A[i]+B[i]), then Max(A[i]+B[i]) = A[n] + B[n] for i<=n. Since B[n] is the smallest value of B'[1..n], we know A[n] + B[n] <= Max(A'[i]+B'[i]). Combine the two relations we get Max(A[i]+B[i]) <= Max(A'[i]+B'[i]) for i<=n.
2. If A[n] + B[n] < Max(A[i]+B[i]), we need to further divide this situation into 3 sub-problems. Assume A'[k] + B'[k] = Max(A'[i]+B'[i]) for i<n.
• Pair A[n] with B'[k], then A[n] + B'[k] >= Max(A'[i]+B'[i]) since A[n] > A'[i] for all i<n.
• Pair B[n] with A'[k], i.e. we substitute A[n] for A'[k] in the original A'[1..n-1], Then how can it possible that Max(A'[i]+B'[i]) can be smaller for i<n since the biggest A[n] is in.
• Leave A'[k] + B'[k] as it is. It's apparent that this won't lower the Max(A'[i]+B'[i]) for i<=n.

Then we can conclude that it is true Max(A[i]+B[i]) <= Max(A'[i]+B'[i]) for i<=n.

The answer for the second question then is Max(done_a[i] + done_b[njob-i]) for 1<=i<=njob. Do you get it? Here is a digram from the ANALYSIS of the problem by USACO staff.

I got information said this problem is related to a more general algorithm named "Johnson" for job scheduling. Links to Wikipedia are listed below.

1. Johnson's Rule, http://en.wikipedia.org/wiki/Johnson%27s_Rule
2. Job shop scheduling, http://en.wikipedia.org/wiki/Job_shop_scheduling

Sample code.

check periodically if port is open from windows

因为远端的机器问题莫名其妙就连接不上了，各种原因。用netcat和schtasks来定期检查本机上的端口是不是开着，没开着就重启。netcat的Windows版本见文末链接。

把以下代码存为文件test-7771.bat。


@echo off

nc -z 10.17.17.177 7771
if ERRORLEVEL 1 shutdown -r -t 180

exit %RANDOM%


用以下命令添加任务计划，每10分钟执行test-7771.bat一次。


schtasks /sc MINIUTE /mo 10 /tn test-7771 /tr C:\test-7771.bat


有用的链接：
netcat (Windows), http://www.securityfocus.com/tools/139

netsh portproxy not working within windows xp

netsh interface portproxy在Windows XP上边不起作用，一直报"connection refused"。因为缺少IPV6MON.DLL。需要使用ipv6 install来安装IPv6协议。如果还是不行，记得使用reset来重置之前所设置的项。具体请见文末链接。

SSH真的是非常好。今天拿到一个从路由器到内网机器的端口映射，只此一个。除去偶尔VNC来查看一下，还想要在里边多装几个Linux虚拟机，山寨一个词语，我需要“TCP port multiplexer”。嗯，SSH很好用。

参考链接
NETSH INTERFACE PORTPROXY do not work when doing port redirection between IPv4 and IPv4 addresses., http://support.microsoft.com/kb/555744/en-us
win7-xsnews.txt, http://psfreedom.com/win7-xsnews.txt

Co-existence of python 2.x and python 3.x

此文用于备忘两个命令：ASSOC，FTYPE

先安装的是2.7，然后再安装的3.2，3.2后来居上成为默认的.py文件解释器。如果平时都是使用2.x版本工作的话，这样就不行了。以下是解决方法演示


F:\>assoc .py
.py=Python.File

F:\>ftype Python.File
Python.File="C:\Python32\python.exe" "%1" %*

F:\>ftype Python.File="C:\Python27\python.exe" "%1" %*
Python.File="C:\Python27\python.exe" "%1" %*

F:\>ftype Python.File
Python.File="C:\Python27\python.exe" "%1" %*


这样就让2.7成为默认的解释器了。

发觉Python核心的开发流程应该很不错，之前对Python源代码的简单接触也让我对其兴趣渐增，应该要学习一下了。特别是关于测试、项目流程和组织方面，嗯。

FFmpeg Notes

记录一下常用的选项，经常去ffmpeg-doc.html去翻那一大坨选项满不好的。

首先，Sheldon的“吓死喔了”

ffmpeg -i "The.Big.Bang.Theory.1x17.The.Tangerine.F
actor.720p.HDTV.x264-DIMENSION.[tvu.org.ru].mkv" -ss 00:11:02.450 -t 00:00:01.70
0 nearly_scared_me_to_death.mp3

-i：	指定输入文件（input）
-ss：	选择起始时间点（seek start point），格式HH:MM:SS[.xxx]
-t：	指定时长（duration）

参考链接
FFmpeg Documentation, http://ffmpeg.org/ffmpeg-doc.html

yszhou's First Haskell Function

这个暑假在杭州实习，前天晚上用手机翻到Haskell的主页，看到《Learn You a Haskell for Great Good》，很轻松的那种。之前尝试过《Real World Haskell》，也许英语水平不行？反正很挫。

今天晚上在CPyUG上看到有pyer感慨函数式编程，便把毕设时开小差下载下来的HaskellPlatform安装上，写了以下函数，用于实现Descartesian Product。算是一步一步更General吧。高级语言表达思维，硬件来确认，他们接起来的细节是什么？

enum :: Int -> [[Char]]
enum 1 = ["A", "T", "C", "G"]
enum n = [ x:enum_decr | x <- "ATCG", enum_decr <- enum (n - 1) ]

enum' :: [Char] -> Int -> [[Char]]
enum' init_value 1 = [ [x] | x <- init_value ]
enum' init_value n = [ x:enum_prev | x <- init_value, enum_prev <- enum' init_value (n - 1) ]

enum'' :: [a] -> Int -> [[a]]
enum'' init_value 1 = [ [x] | x <- init_value ]
enum'' init_value n = [ x:enum_prev | x <- init_value, enum_prev <- enum'' init_value (n - 1) ]

type And object in Python

首先笔记以下在解释器中的记录：

>>> isinstance(type, type)
True
>>> isinstance(type, object)
True
>>> isinstance(object, object)
True
>>> isinstance(object, type)
True
>>>

在文章《Python Types and Objects》分析的初始阶段，有如下图。所以：
1. type是type的实例，在图中已经体现；
2. 由于type是object的子类，加上条件1，所以type是object的实例；
3. 由于ojbect是type的实例，type又是object的子类，所以object也是object的实例；
4. 在图上已经体现。

另外，"type"或者"class"在Python中有如下特点：
1. 能被子类化（subclassed），或者说被继承（inherited）；
2. 能被实例化（instantiated），即“创造出实体”来。由“人”创出“张三”，由“int”创出“2”；
3. 它们的type（调用type()）或者__class__都为<type 'type'>。即使是层次很深的继承亦如此。


参考链接：
Shalabh Chaturvedi, Python Types and Objects