Wednesday, December 24, 2014

Smallest Enclosing Circle Solution

1. Smallest Enclosing Circle : 2-Dimension Problem
2. Smallest Enclosing Sphere : 3-Dimension Problem

Thesis Link

Let P(X, Y, Z) = (Average(x(i)), Average(y(i)), Average(z(i)))
Average(x(i)) = Sum(x(i)) / N
Average(y(i)) = Sum(y(i)) / N
Average(z(i)) = Sum(z(i)) / N

P is inside of the points' convex hull.

Now find the farthest point(M) to P.

Move P toward M a little bit and the ratio should be small and decreasing.

If there is no such a movement, that is the answer.

Total Time Complexity is O(N * constant number)

(We can reduce 'N' by getting convex hull.)

My 2-Dimension Problem's Solution Code

My 3-Dimension Problem's Solution Code

Monday, December 22, 2014

해싱(Hashing)

1. 개요

해싱(Hashing)은 긴 길이의 문자열이나 큰 크기의 값을 어떤 작은 값으로 치환하는 방법입니다. 특히 문자열 관련 문제에서 강력한 힘을 발휘하며, 매우 높은 정확도로 해싱한 값이 중복되지 않게 할 수 있기 때문에 효율적입니다. 보통 일반적인 시간복잡도에서 꽤나 큰 상수로 나눈 시간복잡도로 최적화시키기 때문에 실제 대회에서 많이 사용됩니다.

2. 기본 방법

1) 문자열을 정수값으로 치환하기

dad라는 단어가 있다고 생각합시다. 이 단어를 하나의 정수로 치환하려고 합니다. 기본적인 아이디어는 (문자의 종류) 진법으로 생각하여 정수로 치환하는 것입니다. 'a'는 0, 'b'는 1, … , 'z'는 25가 된다고 가정할 수 있습니다. dad는 3*(26^2)+0*(26^1)+3*(26^0)이 됩니다.
만약 문자열이 너무 길다면, 10글자씩 정도로 끊어서 저장할 수 있습니다. 아니면 전체 길이에 대해서 위의 방법대로 해싱을 하다가 큰 값(M)으로 나눈 나머지를 가지고 그 문자열의 해싱값으로 생각할 수 있겠습니다.
이 때, 한 M에 대해서 같은 값을 가지는, 서로 다른 문자열들이 생길까봐 걱정하실 수 있습니다. 그러면 서로 다른 큰 값 M1과 M2, … , Mk로 나눈 나머지들을 가지고 있다면 그 문제가 어느 정도 해결됩니다. 프로그램 수행시간은 k배 정도 증가하겠지만… 길 가다가 벼락 맞을 확률로, 해싱값들이 모두 일치하는데 정작 문자열은 다를 수 있겠다고 할 수 있겠습니다.
아! 참고로 M은 소수인 게 좋습니다. 왜냐하면 M으로 나누어 떨어진다면 해싱값이 0으로 되는 경우가 상대적으로 많기 때문입니다.

2) 정수값을 정수값으로 치환하기

정수를 정수로 치환하는 게 무슨말이냐 싶으시죠? 예제로 다음 문제를 가져와서 설명드려보겠습니다. 1920번 수 찾기 문제 이 문제의 정해는 A 배열의 원소들을 O(N log N)에 정렬하고 M개의 수들을 하나씩 이분탐색하는 것입니다. 하지만! 해싱으로 풀 수 있습니다.
우선 주어지는 정수들이 int 범위이기 때문에 적당히 1000007 정도로 해싱을 해봅시다. 음수인 경우는 나누었을 때의 나머지를 양수로 바꾸어주는 것에 주의합니다. A(i)의 해싱 값이 h(i)라면 어떤 vector <int>의 h(i)번째 방에 A(i)를 넣어줍니다. 이런 식으로 A[]들을 처리하고, M개의 수에 대해서 M(i) % 1000007한 값을 M`(i) 합시다. M`(i)번째 방의 원소들을 일일이 보면서 M(i)와 일치하는지 판별합니다. 확률적으로 vector <int>에 골고루 A(i)들이 들어갔다면 대략 O(N^2 / 1000007) 정도의 시간복잡도를 가질 것이며 실제로 이 방법으로 넉넉한 시간으로 Accepted를 받을 수 있습니다.

3. 응용 문제

1. 2014년 ACM-ICPC 한국 예선 G번

2014년 ACM-ICPC 한국 예선 G번 문제를 해싱으로 풀어보겠습니다.
참고로 이 문제의 정해는 Aho-Corasick 알고리즘을 사용하는 것입니다.
문제를 요약해보겠습니다. 각각 길이가 n과 m인 두 문자열 P와 Q가 주어집니다. Q를 3부분(각 부분은 크기가 0일 수도 있습니다.)으로 나누어서 가운데에 해당하는 부분은 뒤집어서 다시 순서대로 합한 문자열들의 집합을 S라고 하겠습니다.(예를 들어 Q가 AGCAT이고, A/GCA/T로 나누었다면 GCA를 뒤집으면 ACG가 됩니다. 이를 순서대로 합하면 AACGT가 됩니다.)
집합 S의 원소 중, P의 연속부분문자열과 일치하는 것의 개수를 출력하는 것이 문제에서 요구하는 것입니다.
이 문제를 해싱으로 풀기 위해서는, S 집합을 우선 구한 후에 그들을 Hashing Table에 저장해두고, P의 연속 부분 문자열 n-m+1개(이 집합을 T라 하겠습니다.)와 비교해보아야 할 것입니다.
전자의 경우는 위에서 설명한 방법을 쓰면 되고, 후자의 경우를 설명드리겠습니다. n이 10이고 P가 ACGGGTCAAG라고 합시다. 그리고 m은 3이라고 가정해봅시다. 그러면 ACG, CGG, … , AAG와 S의 원소들을 비교해야합니다. 그런데 T의 원소들을 O(n*m)에 해싱하면 TLE가 발생하게 됩니다. T의 원소들을 O(n)에 해싱할 수 있습니다. ACG에서 CGG로 넘어갈 때, CG는 유지되고 앞의 A는 빠지고, G가 삽입됩니다.
ACG에서의 해싱값을 x라 하면, (x - 0(='A'의 치환값) * 4(=문자의 종류 A,C,G,T)^(m-1))*4 + 2(='G'의 치환값)를 해주면 CGG의 해싱값이 나오게 됩니다. m은 불변값이므로 k*4^(m-1)(k는 0,1,2,3)을 사전에 계산해주었다면 O(n)에 이 작업들이 마무리 될 수 있게 됩니다.
아래는 제가 작성한 풀이입니다. 해싱값이 같다면 문자열들을 O(m^2)으로 일일이 비교해주었음에도 불구하고(?) 1.9초로 2초 내에 아슬아슬하게 AC를 받았습니다. Hash값 3개를 구한 후, 3개가 모두 같다면 같은 문자열이라고 판단한다면 훨씬 빨라질 수 있겠습니다.
아래의 소스는 해싱을 할 때 mod 연산을 쓰지 않았습니다. long long 범위를 넘어가면 자동으로 오버플로우 처리되어 mod 연산을 쓴 것과 같은 효과를 내는 것을 이용했습니다. 위의 소스가 1.8~1.9초의 수행시간을 보여주었지만, 아래의 소스는 1.06초의 수행시간을 보여줍니다. 확실히 더 빨라진 것을 알 수 있습니다. long long으로 해싱을 하면 mod 2^64와 같으므로, 2^64와 서로소인 수의 진법으로 해야 최소한의 안전을 보장할 수 있다고 합니다.

2. COCI 2006/2007 Contest #5 6번

COCI 2006/2007 Contest #5 6번 문제를 해싱으로 풀어보겠습니다.
길이가 20만 이하인 문자열이 주어졌을 때, 두 번 이상 등장한 부분 문자열 중 가장 길이가 긴 것의 길이를 구하는 문제입니다. 여기서 관찰할 수 있는 것은 어떤 부분 문자열 S가 k번 등장했다면, S의 부분 문자열 또한 k번 이상 등장한다는 사실입니다.
따라서 Parametric Search를 하면서 해싱을 이용하여 답이 존재하는지 확인할 수 있습니다. 제가 작성한 소스에는 해싱값을 3개 구하여서, 첫 번째 해싱값번째 vector에 페어로 저장하여 비교하는 방법이 사용되어 있습니다. g[i][j][k]는 i^j(i의 j 거듭제곱) mod Hash[k]입니다. 이웃한 부분 문자열로 넘어가면서 해싱값을 구할 때 사용됩니다

4. 실습 문제

Monday, December 15, 2014

Linear Algebra - Theorem dim(V)=dim(Im(T))+dim(Ker(T)) and its proof


USACO US Open 2013 Bronze - 'Photo' / SRM 432 Div.1 Hard

1. USACO US Open 2013 Bronze - 'Photo'

아이디어는 일단, A_i 와 B_i 중 B_i가 가장 작은 것에 대해서 1~B_i-1까지는 무조건 같은 그룹이 될 수 있고 답은 1 증가한다. 그리고 해당 B_i값에 대해서 다른 쿼리가 있다고 하더라도 답에는 영향을 주지 않는다. 왜냐하면 B_i보다 작은 A_k들에 대해서는 서로가 무관하고 A_i와 B_i에 의해 최소한 답은 1이 증가해야하기 때문이다. 따라서 B_i순으로 정렬해두고서 A_k가 B_i 이상이면 B_k를 새로운 Right-most값으로 보고서 답을 Right-most값이 바뀔 때마다 증가시켜주면 된다.

My Source Code

2. SRM 432 Div.1 Hard

한 개의 도시에 집을 다 짓는 경우에 필요한 비용, 두 개의 연결된 도시에서 집을 짓는 경우에 필요한 비용을 생각한다. 거기다가 도로를 이을 때 필요한 비용까지 모든 도시 pair에 대해 고려해서 mst를 구해주면 답.

My Source Code

아래는 위의 문제에 대한 탑코더 공식 해설
Like many other "hard" problems - this one relies on the smaller subproblems.
In the beginning, let's determine how much is paid to builders for building houses in the same city. In the i-th city, the first house costsbefore[i]*houseCost[i], the second (before[i]+1)*houseCost[i], ..., the last - (after[i]-1)*houseCost[i]. The total cost is houseCost[i]*(before[i]+after[i]-1)*(after[i]-before[i])/2. Now we will think about how to reduce "between cities" and road building payments.
Consider the second building phase for only two cities i and j connected by a road. When building after[i]-before[i] new houses in the i-th city, each of old before[j] builders int the j-th city will get houseCost[i] units of money, so this expense equals to (after[i]-before[i])*before[j]*houseCost[i]. Similarly, after building new houses in the j-th city, old i-th city builders are paid (after[j]-before[j])*before[i]*houseCost[j] units of money in total. What's left is how much money will new builders get.
Consider any new house x in the i-th city and new house y in the j-th city. If house x is built before house y, the builder from x will gethouseCost[j] units of money for (x,y) houses pair. If house is built before x, the builder from y will get houseCost[i] units for the same(x,y) pair.
Note that for each such (x,y) pair we will have to pay some amount - either houseCost[i] or houseCost[j], depending on which house is built before. We don't have any other expenses. From it we can conclude, that it's always better to build first all the houses in the city, which has more houseCost. So, the minimal total payment for new builder is Min(houseCost[i], houseCost[j])*(after[i] - before[i])*(after[j] - before[j]).
Now consider the second building phase for any number of cities. It's not hard to see that the same happens here: for any pair of housesx and y from the neighboring cities - we have to pay money to builder either from x or y (except the case when both x and y are old houses), depending on which one is built earlier. So, it's always profitable to build each time a new possible house in the city with maximal houseCost.
It's time to combine both phases of building. When building a new road between cities i and j, we have to pay not only roadCost*(before[i]+before[j]) units of money for constructing it, also we must consider that it adds to our expenses (after[i]-before[i])*before[j]*houseCost[i]+(after[j]-before[j])*before[i]*houseCost[j]+Min(houseCost[i],houseCost[j])*(after[i] - before[i])*(after[j] - before[j]) units. So, their sum is the actual cost of that road. If this road already exists, we only add that last amount to our answer.
The remaining part is clear - we must construct Minimal Spanning Tree (MST) from all existing and possible new roads (In fact it's not exactly spanning tree, there are some more edges). For it, you can use either Kruskal's or Prim's algorithm.
... and be careful - int overflow!

Thursday, December 11, 2014

Czech, Polish and Slovak Preparation Camp 2007 - Triangulations


put m = n-2 and T(n) = D(m).

D(0) = D(1) = 1.

D(m) = D(0)D(m-1) + D(1)D(m-2) + ... + D(m-1)D(0) = ( 2m C m ) / (m+1)

D(m)/D(m-1) = 2(2m-1)/(m+1)

Using Fenwick Tree, we can update each prime numbers' multiplication(with exponentiation by squaring)

Total Time Complexity equals O(N log N).

My Source Code(hongjun7 소스 코드)

Wednesday, December 10, 2014

Linear Algebra - Plus/Minus Theorem

집합 S를 벡터공간 V의 공집합이 아닌 벡터집합이라 할 때,

(1) Plus Theorem : 만일 S내의 벡터들이 일차독립이고 벡터 v(v∈V)를 S내의 벡터들에 의해서 생성되는 벡터공간 외부의 벡터라고 한다면 S∪{v}도 일차독립이 된다.

(2) Minus Theorem : 만일 벡터  v(v∈S)가 집합 S내의 다른 원소들의 일차결합으로 표현될 수 있다면 S-{v}도 동일한 공간을 생성하게 된다.

(1)의 증명

S = {v(1), v(2), ... , v(n)}라고 표현하자.

S` = {v(1), v(2), ... , v(n), v} = S + {v}이 일차독립임을 보이자.

k(1)v(1) + k(2)v(2) + ... + k(n)v(n) + kv = 0임을 보이는 것과 동치이다.

k ≠ 0이면, v = -(k(1)v(1) + k(2)v(2) + ... + k(n)v(n)) / k 가 되어 v가 벡터공간 외부의 벡터라는 가정에 모순이다.

k = 0이면, S내에 벡터들이 일차독립이므로 k(1)v(1) + k(2)v(2) + ... + k(n)v(n) = 0이고 k(1) = k(2) = ... = k(n) = 0인 유일한 해를 가진다.

∴ k(1) = k(2) = ... = k(n) = k = 0인 유일한 해를 가지므로 S`은 일차독립이다.

(2)의 증명

S = {v(1), v(2), ... , v(n), v}이고 v = k(1)v(1) + k(2)v(2) + ... + k(n)v(n).

w∈S인 w에 대해

w = c(1)v(1) + c(2)v(2) + ... + c(n)v(n) + cv

   = c(1)v(1) + c(2)v(2) + ... + c(n)v(n) + c(k(1)v(1) + k(2)v(2) + ... + k(n)v(n))

   = (c(1)+ck(1))v(1) + (c(2)+ck(2))v(2) + ... (c(n)+ck(n))v(n)

∴ S-{v}도 동일한 공간을 생성한다.