Patrick Wezhi Xu

Build a Proxy Server to Access Chinese IP Including Netease Music

Sometimes we need to access Chinese content, like Youku Video, Netease Music (Cloud Music) and QQ music. It is very annoying to get “Can Only Be Streamed in Mainland China” or similar messages. Being tired of that, fortunately I have got a VPS from Aliyun and I build a proxy server using Shadowsocks on it and everything works smoothly now. VPS You need to have a VPS with Chinese IP address, there are tons of choices, like Aliyun(Alibaba Cloud) and Tencent Cloud etc.

USACO Party Lamps

A set of \(N\) \((10 \le N \le 100)\) lamps, numbered from 1 to N. Four types of button: Button type Usage 1 flip all lamps (On to Off, Off to On) 2 flip odd numbered lamps (e.g. 1, 3, 5) 3 flip even numbered lamps (e.g. 2, 4, 6) 4 flip \(3k+1 ; with ; k \ge 0\) numbered lamps (e.g. 1, 4, 7) Given \(C\) (number of button presses, \(0 \le C \le 10000\)) and final state of some of the lamps, find all possible distinct configuration.

POJ 3268 Silver Cow Party

There are one cow from each \(N\) (\(1 \le N \le 1000\)) farms want to go to the number X farm to have a party, hurrah! One cow from each farm need to go to the party and go back. There are \(M\) (\(1 \le M \le 100,000\)) weighted (represents time) one-direction roads connects pairs of roads. Cows are smart though, they want to go via the shortest path. The question is, what is the longest time the cow will take.

UVa 108 Maximum Sum

Given an array with size \(N \times N (N \le 100)\), find the maximum value of its subarray. Link: Problem on UVa Solutions First thought is to brute force - find all possible subarrays then the time complexity will be \(O(N^6)\). TLE for sure. Then comes up with an algorithm that takes \(O(N^4)\), which is enough to AC. However, it can be \(O(N^3)\), see solution 2. Solution 1 We build a sum array which is the sum of the numbers in rectangle area with the top-left of the array and bottom-right node \(i, j)\).

UVa 443 Humble Numbers

Find \(n\)th \( (1 \le n \le 5842)\) number whose only prime factors are 2, 3, 5 or 7. Link: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=384 Solutions Solution 1 Kind of brute force, using STL set and vector to list all humble numbers. Using long long to avoiding overflow. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include<iostream> #include<vector> #include<set> using namespace std; typedef long long ll; const int t[] = { 2, 3, 5, 7}; set<ll> s; int main(void) { s.

POJ 2376 Cleaning Shifts

\(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\).