Monday, January 27, 2014

acmicpc.net 1763 - 트리색칠

Problem Link

N개의 노드를 가지고 있으며, 루트가 있는 트리의 각 노드에 가중치가 부여돼 있다. 임의의 노드의 번호를 i라 하고, i번 노드에 부여된 가중치를 C[i]라 한다. 한 노드를 색칠하는 데에는 비용이 드는데, i번 노드가 F[i]번째로 색칠되는 노드라면, i번 노드를 색칠하는 데 드는 비용은 C[i]*F[i]로 계산된다. 전체 트리를 색칠하는 데 드는 비용은 각 노드를 색칠하는 데 드는 비용의 합이다. 단, 어떤 노드를 색칠하기 위해서는 그 노드의 부모 노드가 이미 색칠되어 있어야 한다. 따라서 루트가 가장 먼저 색칠되어야 한다. 이러한 규칙에 따를 때, 최소의 비용으로 트리를 색칠해야한다.
  문제를 풀기 위해서는 다음 2가지의 정리가 쓰인다.
1. Root가 아닌 노드 p가 가중치가 가장 크다면, p의 부모 노드 q가 선택된 이후에는 p를 선택하는 것이 최적이다. (귀류법을 통해 쉽게 증명 가능)
2. '1.'에 의해 q와 p는 인접하며 q가 선택된 이후에만 p가 선택될 수 있다. 이 때, p와 q를 하나의 노드 r로 생각할 수 있는데 r의 자식노드 k는 p와 q의 자식노드이다. 노드 r의 가중치는 (C[p]+C[q])/2가 된다. 트리의 형태가 총 N개의 노드에서 N-1개의 노드로 줄어든 것이다. 이것을 확장시켜 m개의 노드들을 하나의 노드로 생각한다면 그때의 가중치는 (C[x(1)]+C[x(2)]+...+C[x(m)])/m이 된다. 증명은 수학적 귀납법을 통해 가능하다.

Source Code

Friday, January 24, 2014

Aho–Corasick string matching algorithm / Knuth's Algorithm X

Aho–Corasick string matching algorithm & Slides from University of Kuopio

O(n+m)의 선형 스트링 매칭 알고리즘. Suffix Link를 이용한다.


Knuth's Algorithm X

0과 1로만 이루어진 n×m 행렬이 있을 때에 적당한 개수만큼의 행을 선택하여 각 열에 1이 한번씩만 등장하도록 하는 알고리즘.

Thursday, January 23, 2014

법 M에 대한 곱셈의 역원(Inverse Element)

PS를 하다보면 P/Q (mod M) (단, P는 Q의 배수이며 M은 큰 소수)를 계산하게 되는 경우가 있다. 이 때, P와 Q가 엄청 큰 수라서 각각을 구한 후, 나누기가 힘드므로 법 M에 대한 곱셈의 역원을 구하여 계산을 쉽게할 수 있다.
법 M에 대한 양의 정수 a의 곱셈의 역원을 구하는 방법에는 크게 2가지가 있다.

1. Euler's Theorem
'오일러의 정리'란 양의 정수 M과 (a,M)=1인 정수 a에 대하여 aφ(M) ≡1(mod M)임을 말한다. 이 정리는 기약잉여계를 이용하여 간단하게 확인할 수 있으므로 증명은 생략한다. φ(M)은 M이 소수이므로 M-1이 된다.(역도 귀류법에 의해 성립한다.) 따라서 법 M에 대한 양의 정수 a의 곱셈의 역원을 x라고하면 ax≡1(mod M)이고 오일러 정리에 의해 x ≡ aM-2 (mod M)이 된다. 각각의 x를 구할 때마다 O(log M)의 시간복잡도를 가지므로 n개의 역원을 구한다면 전체 시간복잡도는 O(n log M)이 되겠다.

2. 확장 유클리드 알고리즘

이에 대해선 앞선 게시글에 언급한 바가 있어서 자세히 설명하진 않겠다.
두 양의 정수 a, b에 대하여 r0 = a, r1 = b라 하고 a0 , ... , an , r2 , ... , rn , rn+1 을 다음을 만족하는 정수라 하면,
r0 = a0 r1 + r2 (0<r2<r1)
r1 = a1 r2 + r3 (0<r3<r2)
r2 = a2 r3 + r4 (0<r4<r3)
...
rn-1 = an-1 rn + rn+1 (0<rn+1<rn)
rn = an rn+1, (a, b) = rn+1
그리고 
S= 1, S= 0, SSi-2 ai-2 Si-1 (2 ≤ i ≤ n+1)
T= 0, T= 1, TTi-2 ai-2 Ti-1 (2 ≤ i ≤ n+1)
이라 두면 ri = a ST(0 ≤ i ≤ n+1)이 성립하고, 특히 (a, b) = rn+1 = Sn+1 Tn+1 이 성립한다. 이를 이용하여 ax≡1(mod M)를 (a, M) = 1이므로 일차부정방정식의 형태로 고쳐서 풀 수 있다. 시간복잡도는 오일러 정리를 이용한 것과 큰 차이가 없다.
추가적으로 예를 들어 설명하자면, 3x≡1(mod 5)는 (3, 5)=1이므로 3×2+5×(-1)=1 임을 통해 x≡2(mod 5)의 해를 얻게 된다.

Closest pair of points problem in 2D

▶ 문제
  평면에 여러 개의 점 S={p1, p2, ... , pn}이 주어졌을 때, 가장 인접해 있는 두 점을 계산하는 문제

▶ Divide & Conquer Algorithm
  (1) (Divide Step) S를 크기가 같은 2개의 집합 S1, S2로 분할한다. 분할할 경우에는 각 점을 x축의 좌표에 따라 정렬하여, 아래 그림과 같이 분할한다.
  (2) (Conquer Step) S1, S2에 대하여 재귀적으로 문제를 해결한다.
  (3) (Merge Step) S1, S2에서 가장 가까운 두 점과 S1, S2에 양 끝점이 각각 속하는 가장 인접한 두 점 중에서 가장 가까운 두 점을 계산한다.


▶ Merge Step
 {p1, p2}를 점 S1에서 가장 가까운 두 점이라 하고, δ1을 그 두 점 사이의 거리라 하자. 또한 {q1, q2}를 S2에서 가장 가까운 두 점이라 하고, δ2를 그 두 점 사이의 거리라 하자.
 δ = min{δ1, δ2}
 그리고 다음 두 조건을 만족하는 두 점 {p, q}를 찾는다.
    (1) p ∈ S1, q ∈ S2
    (2) distance(p, q) < δ
 위의 두 조건을 만족하는 점은 반드시 분할 수직선 L과의 거리가 δ 이내에 있어야한다.
P1, P2를 아래 그림과 같이, 각각 수직선 L의 양쪽에서 폭이 δ인 수직영역이라 하자.



 p ∈ S1에 대하여, S2에서 가장 가까운 점을 구하기 위해서는 위 오른쪽 그림과 같이 δ×2δ 사각형 영역에 있는 점만을 고려하면 된다.
 그러나, 이 δ×2δ 사각형 영역에는 최대 6개의 점만이 존재할 수  있다. 왜냐하면, 이 사각형 내부에 있는 점들은 최소한 δ만큼의 거리로 떨어져 있어야 하기 때문이다.
 p ∈ S1에 대하여, S2의 δ×2δ 사각형 영역에 속하는 최대 6개의 점들은 S2에 속하는 모든 점들을 y좌표에 따라서 정렬을 한 후, p의 y 좌표에 인접한 최대 6개 점과의 거리만을 계산하면 된다.


Monday, January 20, 2014

Burnside's lemma

From Petr Mitrichev's Blog

The last TopCoder SRM (the problem statement is at here, but that requires a TopCoder account to view) has inspired me to write about a small and quite easy fact in group theory which I think was the most useful part of group theory for me in programming competitions.

It's called Burnside's lemma and says (citing from Wikipedia): let G be a finite group that acts on a set X. Then the number of orbits is equal to the average number of points fixed by an element of G. What does this all mean and how is this applicable to programming competitions? Let's continue with an example.

A standard problem that is best solved using Burnside's lemma is: consider a circular stripe of n cells. How many ways are there to color these cells with two colors, black and white, up to a rotation? Here, X is a set of all colored stripes (it has 2^n elements), and G is the group of its rotations (it has n elements: rotation by 0 cells, y 1 cell, by 2 cells, etc, by (n-1) cells), and an orbit is exactly the set of all stripes that can be obtained from each other using rotations, so the number of orbits will be the number of distinct stripes up to a rotation. Now let's apply the lemma, and find the number of stripes that are fixed by the rotation by K cells. If a stripe becomes itself after rotating by K cells, then its 1st cell must have the same color as its (1+K modulo n)-th cell, which is in turn the same as its (1+2K modulo n)-th cell, etc, until we get back to the 1st cell when m*K modulo n=0. One may notice that this will happen when m=n/gcd(K,n), and thus we get n/gcd(K,n) cells that must all be of the same color. Analogously, the same amount of cells must be of the same color starting with cell 2, (2+K modulo n), etc. Thus, all cells are separated into gcd(K,n) groups, with each group being of one color, and that yields us 2^gcd(K,n) choices. An by Burnside's lemma, the answer to the original problem is sum(2^gcd(K,n))/n, where the sum is taken over K from 0 to n-1.

That was rather complicated; here's a somewhat simpler example: Consider a square of 2n times 2n cells. How many ways are there to color it into X colors, up to rotations and/or reflections? Here, the group has only 8 elements (rotations by 0, 90, 180 and 270 degrees, reflections over two diagonals, over a vertical line and over a horizontal line). Every coloring stays itself after rotating by 0 degrees, so that rotation has X^(4n^2) fixed points. Rotation by 180 degrees and reflections over a horizonal/vertical line split all cells in pairs that must be of the same color for a coloring to be unaffected by such rotation/reflection, thus there exist X^(2n^2) such colorings for each of them. Rotations by 90 and 270 degrees split cells in groups of four, thus yielding X^(n^2) fixed colorings. Reflections over diagonals split cells into 2n groups of 1 (the diagonal itself) and (2n^2-n) groups of 2 (all remaining cells), thus yielding X^(2n^2-n+2n)=X^(2n^2+n) unaffected colorings. So, the answer is (X^(4n^2)+3*X^(2n^2)+2*X^(n^2)+2*X^(2n^2+n))/8.

I understand that this looks kind of too much formulas for too little gain, but once you get the hang of it, it becomes really simple and easy to use.

And as a plus, you get to verify that you haven't made a bug: the lemma has a division in the end (e.g., the division by 8 in the last formula). If that division produces a remainder, you've miscalculated somewhere. And chances are, if you have made a mistake, feeding the program random testcases will make the formula produce a remainder quite soon.

P.S. The Formula 1 GP at Interlagos starts in 20 minutes! I will be rooting for Massa to win the championship (I don't exactly know why - maybe because he's losing :)). The event is very likely to turn out quite exciting.

  • 경우의 수를 세는데, 특정 transform operation(회전, 반사, ..)해서 같은 경우들은 하나로 친다. 전체 경우의 수는?
    1. 각 operation마다 이 operation을 했을 때 변하지 않는 경우의 수를 센다 (단, "아무것도 하지 않는다"라는 operation도 있어야 함!)
    2. 전체 경우의 수를 더한 후, operation의 수로 나눈다. (답이 맞다면 항상 나누어 떨어져야 한다)
  • Application:
    • n×n (n은 편의를 위해 짝수) 크기의 격자를 x개의 색깔로 칠하는 경우의 수는? 단 회전해서 같은 경우는 같은 것으로 친다.
      • 아무것도 하지 않을 때: 모든 격자가 변하지 않는다. xnn
      • 90도 회전, 270도: 4개씩 칸을 그룹지어, 각 그룹은 같은 색이어야 한다. 따라서 xnn/4
      • 180도 회전: 2개씩 칸을 그룹지어, 각 그룹은 같은 색이어야 한다. 따라서 xnn/2개의 경우의 수
    • 최종 답은 이들의 평균!

Saturday, January 18, 2014

acmicpc.net 8462 - 배열의 힘

문제 링크(acmicpc.net 8462)
자연수 n 개로 이루어진 배열 a1,a2,a3,,an이 있다.
l 부터 r  까지 부분 배열은 al,al+1,,ar 이다.
Ks는 부분 배열 안에 있는 자연수 s 의 개수이다.
부분 배열의 힘이란 모든 자연수 s 에 대해서, KsKss   를 합한 값이다.
배열과 부분 배열의 범위가 주어졌을 때, 각 부분 배열의 힘을 구하시오.

- 문제를 푸는 동안의 과정 -

1) 전체 길이 n의 배열을 루트 n 길이의 배열들로 나눈 다음에 각 쿼리에 대해서 좀 더 빠르게 처리하는 것이었다. O(NQ)보다는 좀 더 빠른 O(Q 루트 N)이었다. 하지만 TLE.

2) 쿼리를 가지고 어떻게 구하는 순서를 변형할 수 없을까 고민하였다. 주어진 쿼리가 (L(i), R(i))일 때, R(i)를 오름차순으로 정렬한 다음에 1)의 알고리즘과 같은 방법을 적용시켜보기로 했다. 그러면 R(i)에서 R(i+1)로 갈 때에는 더하는 일만 발생하고 L(i)에서 L(i+1)로만 갈 때, 빼는 일이 발생하므로 시간이 단축될 것 같았다. 물론 L(i)에서 L(i+1)로 가는 것보다 R(i+1)에서 L(i+1)로 가는 게 더 빠르면 후자를 택했다. 하지만 TLE.

3) 문제를 풀었던 이승재 선배(RiKang)랑 홍은기 선배(pichulia)의 도움을 받았다. 이 풀이법의 핵심은 쿼리를 sum( |R(i+1)-R(i)| + |L(i+1)-L(i)| )를 (상수)*(N 루트 N)과 가깝게 정렬하는 것이다. 그러면 인접한 쿼리에 대해서 그냥 선형적으로 훑으면서 부분 배열의 힘을 처리하여도 O(N 루트 N)에 가까운 시간복잡도가 된다.
정렬을 할 때, compare함수를 임의의 쿼리 L, R에 대해서 "(int)(L/루트(N))*루트(N)+(R/루트(N))"순으로 정렬하면 된다. 우선, 왜 그런지를 알기 전에 문제의 조건에 의해 L≤R임을 알아두자.
X = (int)(L/루트(N))*루트(N)이라 하면 각 X에 대해서 0 이상이면서 루트(N) 이하인 범위의 R을 참조할 수 있게 된다. 나중에 각 쿼리마다 부분배열의 힘을 계산하는 과정에서 소요되는 시간비용은 각 X에 대해서 O(max(X에서의 R(i))-min(X에서의 R(i)))가 된다. 따라서 총 시간복잡도는 O(X의 개수 * N) ≒ O(N 루트 N)이 된다.

참고로 Q(i)에서 Q(i+1)로 넘어갈 때 다음의 원리를 알면 부분배열의 힘을 선형시간 내에 계산할 수 있다. a에서 a+b가 될 때 a^2 에서 (a+b)^2가 된다. 여기서 차수가 2인 항에서는 2ab+b^2만이 추가되므로 b=1이라면 2a+1만이 증가하게된다.

Source Code

Thursday, January 16, 2014

acmicpc.net 2187 - 분해반응

문제 링크(acmicpc.net 2197)

한 개의 트리(정점 n개, 간선 n-1개)에서 m개의 정점만을 남기기 위한 최소 간선 삭제 횟수를 구하는 문제로서 전형적인 tree dynamic programming 문제이다.

d[i][j] : i번 노드의 위치에서 j개의 정점을 없앨 때의 최소 필요 분해 횟수

d[x][n-m]의 유효한 값 중 최솟값 답이 된다.

주의해야할 점으로 i번 노드의 위치에서 k번째 자식을 볼 때, k번째로 인한 테이블 갱신을 먼저 한 후에, k번째가 가지고 있던 값 중 더 좋은 값을 i번째가 취해야한다. 그렇지 않으면 같은 부트리에서 중복되는 결과를 가져오기 때문이다.