## 2019年1月2日星期三

### Find132pattern

Problem:
Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Solution 1:
maintain m[j]=min{a[i] | i<=j}
for each j, k such that j < k and a[j] > a[k], want to know if any i < j, such that a[i]<a[k]
note that m[j-1]=min{a[i] | i < j}<a[k] iff exists i < j such that a[i]<a[k]
O(n^2) since we scan j, k twice thru the sequence. search i is O(1), so we are a little better than naive O(n^3) scan thru all i,j,k

public bool Find132pattern2(int[] nums)
{
if (nums == null || nums.Length < 3) return false;
var minUptoIndex = new int[nums.Length];
minUptoIndex[0] = nums[0];
for (int i = 1; i < nums.Length; i++) minUptoIndex[i] = Math.Min(minUptoIndex[i - 1], nums[i]);
for (int j = 1; j < nums.Length; j++)
for (int k = j + 1; k < nums.Length; k++)
if (nums[j] > nums[k] && minUptoIndex[j - 1] < nums[k])
return true;
return false;
}

Solution 2:
Keep m[j] as solution 1 as it helps.
Can we find all j, k such that j < k and a[j] > a[k] in O(n) rather than O(n^2)?
Alternatively, we only need to find the right most j for each k. Because, if right most j have m[j-1]>=a[k], m[i-1]>=m[j-1]>=a[k] for i<j, as m[i] is a DESC list.
Yes, with stack.
Keep pushing item index k to stack from the end of the list.
Maintain stack with a[k] DESC bottom-up. When incoming item a[j] is greater than the top, there are some items a[k] with a[j] > a[k] on the upper stack could be popped out and form wanted j, k pairs.

public bool Find132pattern(int[] nums)
{
if (nums == null || nums.Length < 3) return false;
var minUptoIndex = new int[nums.Length];
minUptoIndex[0] = nums[0];
for (int i = 1; i < nums.Length; i++) minUptoIndex[i] = Math.Min(minUptoIndex[i - 1], nums[i]);
var stack = new Stack<int>(nums.Length);
stack.Push(nums.Length - 1);
for (int j = nums.Length - 2; j >= 1; --j)
{
var k = stack.Peek();
while (nums[j] > nums[k])
{
stack.Pop();
if (minUptoIndex[j - 1] < nums[k]) return true;
if (stack.Count == 0) break;
k = stack.Peek();
}
stack.Push(j);
}
return false;
}

## 2018年1月2日星期二

### [读书]贸易可以使得每个人的状况更好的一个充分必要条件

a1,a2,b1,b2以及生产组合需要满足什么条件才可能双赢呢？a1:a2!=b1:b2，也就是说，某人存在生产某种商品的比较优势，或者说，两个人生产同一种商品的机会成本不同。生产组合几乎没有要求，只需要任何人都不把全部时间都只用来生产一种商品即可。事实上，一个人把全部时间用来生产他有比较优势的商品，也就是机会成本较低的商品，也是可以的。

A出售d个商品2给B，换得cd个商品1。则他们的消费组合为
A:x1+cd, x2-d
B:y1-cd, y2+d

(x1+cd)/a1+(x2-d)/a2=x1/a1+x2/a2+cd/a1-d/a2=1+(c-a1/a2)d/a1>1，即点在直线上方。
(y1-cd)/b1+(y2+d)/b2=1+(b1/b2-c)d/b2>1，也在直线上方！

A:x1+d1, x2-d2
B:y1-d1, y2+d2

(x1+d1)/a1+(x2-d2)/a2>1
d1/a1>d2/a2
d1/d2>b1/b2
(y1-d1)/b1+(y2+d2)/b2<1

## 2017年12月31日星期日

### null as SqlParameter.Value

Foo
@p1 int = 1

p1.Value = null和不设p1，效果都是一样的，都是param value not set，结果会用sproc定义的默认值1

## 2016年2月14日星期日

### ssh tunnel from the phone

sometimes I want to share a photo from my phone via facebook, then I need ssh tunnel on phone.
As I used Android, I get VX connectbot from my local app store. It has port forward functionality build-in.
As I cannot always open putty on my laptop, I put the proxy into background
cat start_proxy.sh
{{{
nohup python proxy.py --port 8080 --hostname '' > proxy.log 2>&1 &
}}}

On my phone, the proxy setting is not at browser level, but at WALN setting, which means the network traffic of any app will go to the proxy, but interesting, the ssh tunnel itself didn't go to the proxy.

Don't forget to stop the proxy when you want to save money.

{{{
pkill -f proxy.py
}}}

## 2016年2月12日星期五

### Fwd: Proxy.py + SSH Tunnel

I have a Linux server S in JP WEST, which can connect to Google.
Then I setup a proxy.py, a single file web proxy which support HTTPS, at S:8080.
Then I use SwitchySharp locally and set S:8080 as proxy server.
However, when I open Google in browser and search something, the connection is closed.
Checked proxy.py log, it should be because the communication between local machine and S was detected contains Google in plain text. Then I understand what happened on the wire.

Then I use Putty to setup SSH Tunnel, map local:1234 to S:8080, and set localhost:1234 as proxy in SwitchSharp.

Finally the information goes like this: my browser -- local proxy at localhost:1234 -- remote proxy at S:8080 -- internet