Thursday, August 27, 2015

Latin America Regional Contests 2010 G번(BOJ 5699번)

문제 링크(acmicpc.net 5699번)

Aho-Corasick 알고리즘으로 풀 수 있다.

주어지는 입력 문자열들로 트라이를 구성하고, 기존의 노드(x)에서 새로 뻗어나가는 노드(y)의 실패링크(yf) 걸어줄 때

d[y] = max(d[x], d[yf]) + "노드 y에서 끝나는 string의 개수"

O( 문자열의 길이의 합 ) 에 해결할 수 있다.

내 소스 코드

Wednesday, August 26, 2015

Coder's High 2013 J번 Bookthief

평범한 0-1냅색이라고 가정하면 다음과 같은 DP식을 세울수있다.

D[N,V] := N종류의 아이템에 대해 고려해서, V칸을 채웠을때의 최대 값어치
D[N,V] = max{D[N−1,V],D[N−1,V−(volume of item)]+(value of item)}

vi=(volume of item), ci=(value of item)이라고 하고, 아이템의 갯수를 ki라 하자. 위의 식에서 0-1을 0-k로 확장시킨다는 느낌으로 식을 바꿔 써보면,

D[N,V] = max{D[N−1,V],D[N−1,V−vi]+ci,D[N−1,V−vi×2]+ci×2, ... ,D[N−1,V−vi×ki]+ci×ki}

묶어서 쓰면 다음처럼 쓸수있다.

D[N,V] = max{D[N−1,x]+(V−x)/vi×ci} (단,x≡V mod vi이고,V−vi×ki≤x≤V이다.)

x에 대한 식만 남기고 V에 대한 부분은 밖으로 뺄 수있다.

D[N,V] = max{D[N−1,x]−x/vi×ci}+V/vi×ci

f(x) = D[N−1,x]−x/vi×ci 라고 하자.

그렇다면 D[N,V]를 다음과 같이 구할수 있다.

1. f(V)값을 PQ에 넣는다.
2. PQ의 top인 x값이 V와 vi×ki를 넘게 차이나면 top을 제거한다
3. PQ의 top인 f(x)값에 대해 D[N,V]=f(x)+V/vi×ci이다.

최대 PQ의 크기는 O(V)이므로, 시간 복잡도는 O(NVlgV)이다. 이렇게 작성해도 AC를 받기엔 충분한 속도지만, 조금 더 속도 향상을 할 수 있다. PQ안에 있는 2개의 t1 < t2에 대해 생각해보자. 만약 f(t1) < f(t2)라면 t1은 PQ의 top이 영원히 될수 없다. 그러므로 이러한 t1은 전부 배제되었다고 가정하면,

1. PQ안 원소들의 x값들을 순서대로 x1<x2<x3..라 하면
2. f(x1)≥f(x2)≥f(x3)≥...을 만족한다.

또한 위의 조건을 만족하도록 PQ를 관리하여야 한다. 이러한 구조는 선형 deque로도 관리할수있으며, 매 원소는 최대 한 번 삽입과 삭제가 발생하게 되므로 이때의 시간 복잡도는 amortized O(NV)이다.

Saturday, August 1, 2015

KOI 2005 고등부 3번 - 소방차

문제 링크
우선 가장 쉬운 건 O(NM)의 dynamic programming.
D(i, j) = min(D(i-1, j), D(i,j-1), D(i-1,j)+|P(i)-F(j)|).
D(i-1, j)랑 D(i, j-1)을 참조할 때는 min(i-1, j-1)+1과 같은 지 확인하면서 compute하면 된다.

그런데 사실 해법은 dynamic programming과는 다르게 greedy method이다.

펌프 2개 P1<P2가 있고, 소방차 2개 F1<F2가 있다고 하자.
만약 이 펌프들과 소방차들을 이어주는데, 가능한 구간을 고려해보자.
P1<P2<F1<F2일 때 (F1-P1) + (F2-P2) = (F2-P1) + (F1-P2).
P1<F1<P2<F2일 때 (F1-P1) + (F2-P2) < (F2-P1) + (P2-F1).
따라서 구간이 일부분만 겹칠 필요없이, 완전히 포함되거나 독립적이다.

그래서 생각해낸 것이, 구간이 완전히 안에 포함되는 쌍은 바깥쪽 쌍보다 위상이 더 높다고 한다면, 같은 위상 상에서는 완전히 독립적인 구간들 밖에 없어서, 선형 시간에 서로 다른 인접한 원소들을 잘 짝지어서 그 쌍의 합들이 최소화할 수 있게 된다.

위상을 numbering하는 방법은, 펌프들의 위치와 소방차들의 위치를 다 모아놓고 위치순으로 정렬한 다음에, 연속해서 펌프나 소방차가 나온다면, 각각의 경우에 대해 위상의 증감을 반대로 누적해주면 된다.

각 위상마다 애들을 위치순으로 보면 P로 시작해서 F와 P가 번갈아 등장하다가 P로 끝날수도 있고, F로 끝날 수도 있다. (F로 시작하는 건 P로 시작하는 것과 똑같이 처리하면 되므로 일단은 생략)
만약 P로 시작해서 F로 끝나면 그냥 처음부터 보면서 (i+1)번째와 i번째를 짝 지어주는 게 최선이다. 왜냐하면 가능한 짝은 다 지어야하므로.
만약 P로 시작해서 P로 끝난다면 중간에 빈 원소가 하나 생기게 되므로 기존의 인접한 짝들을 지은 것에다가, 끝에서부터 엇갈리게 보면서 새로운 쌍을 이어주고, 기존의 쌍을 없애줄 수 있다. 그 작업을 매번 할 때마다 부분해를 갱신해주면 된다. 그림으로 표현하면 아래와 같다.

따라서 전체적으로 정렬을 사용한다면 O( (N+M) log (N+M) )에 풀 수 있고, 위상에 따라 카운팅 소트하듯이 하면 O(N+M)에 해결할 수 있다.

Thursday, July 9, 2015

Croatian Olympiad in Informatics 2009 OTOCI

문제 링크(Problem Link)

주어진 쿼리를 수행하다보면 최종 그래프의 형태가 Forest가 된다. 따라서 Heavy-Light Decomposition이나 Link-Cut Tree로 그래프를 모델링하여 각 쿼리마다 수행되는 시간을 줄여볼 수 있다.

그런데 나는 조금 다르게 접근하여 보다 쉽게 풀었다. 우선 쿼리를 다 저장하여두고, 최종 그래프가 어떤 형태인지 알아낸다. 거기서 각 트리마다 dfs를 순회하면서 chain을 표시하고, 인접한 chain의 정점들은 다 연속한 번호를 가지도록 각 정점을 renumbering한다.(dfs 순회 중 start number로 numbering했는데 finish number로 해도 될 듯) 이렇게 함으로써 나중에 두 정점 사이의 거리를 계산할 때, 한 chain마다 log 시간에 한 번에 구할 수 있다.

이제 쿼리를 순서대로 다시 보면서 각 연산들을 한다.
bridge - O(log*N) : union-find. 
penguins - O(log N) : update the binary indexed tree. 
excursion - O(log^2 N) : 두 노드 A, B 사이의 팽귄 수를 구한다고 가정하면
chain(X) : X가 속한 chain
depth(X) : X가 속한 트리에서 X의 depth
first(chain(X)) : X가 속한 chain의 depth가 가장 작은 노드
parent(X) : X의 부모 노드
chain(X).count(Y, Z) : X가 속한 chain에서 Y와 Z 사이의 거리

output = 0
while chain(A) ≠ chain(B):
if depth(first(chain(A))) < depth(first(chain(B))):
  swap A and B
output = output + chain(A).count(first(chain(A)), A)
A = parent(first(chain(A)))
output = output + chain(A).count(A, B)

따라서 최종적으로 O(N log N + Q log^2 N).

소스 코드(Source Code)

Tuesday, July 7, 2015

IOI 2007 Sails

Observation 1
The inefficiency of a level is determined by the number of sails at that level. The order of the masts does not matter, so we can rearrange them in ascending order of height.
Greedy strategy:
Place the sails from front (shortest) mast to rear (tallest) mast. For each new mast, place each sail on the level from the bottom that has least number so far. (As you go back and the masts increase in height, so new levels have count 0.)
Is this greedy strategy correct?
Given any optimal placement, we can show that we can transform step by step it into something that the greedy strategy will produce. (This is the standard way to prove a greedy algorithm is correct — "exchange" argument.)
Initially, all levels have 0. So, any placement of the first mast is consistent with the greedy suggestion.
Let us assume that upto the first K masts, we have perturbed the optimal solution to look like greedy. We now show that we can rearrange the (K+1)st mast to also be consistent with greedy without losing optimality.
Why is the (K+1)st mast not compatible with greedy?
There is (at least) one mast that is in the wrong place according to greedy, and the greedy slot is vacant.
              l1          o         r1

              l2          *         r2

   <------------------->     <----------------->
    1 to K is greedy     K+1  K+2 onwards is not greedy
      
Assume that l1 < l2, so we want to move the mast from * to o.
Suppose we move the mast from l2 to l1.
The new inefficiency is
old + (l1 - l2) + (r1 - r2)
This is less than or equal to old provided
(r1 - r2) ≤ (l2 - l1)
If this inequality holds, we are done.
What if this inequality does not hold?
r1 - r2 > l2 - l1 > 0
Therefore, r1 is at least 1. Since r1 - r2 > 0, there is at least one position where r1 has a sail and r2 does not. We move one sail from r1 to r2.
Now, the new cost is
old + (l1 - l2) + (r1 - r2) + ((l2 + r2) - (l1 + r1))
which is just the same as old.
Implementing greedy
Maintain a min-heap with pairs of the form (level, sails). When we reach a new mast, insert (l,0) for each newly added level.
This will take time O(number of sails × log (levels)), which gets 40% of the marks.
A more efficient implementation:
Store the levels sorted in descending order. Instead of keeping the absolute value of sails per level, keep the difference of each level with respect to the previous level in the sorted sequence.
e.g., if the levels are ordered as
     10  10   9   8   8   7   7   7   7   0   0
      
we store the differences
           10   0  -1  -1   0  -1   0   0   0  -7   0
      
When we process a new mast, we first append the new empty levels at the right of this list.
Now we want to add K sails to the levels with the lowest occupancy, namely the last K. This means we have to update the last K difference values.
In general, to update a segment [i,j], we only need to change the values at the left and right end — decrease the difference i - (i-1) by 1, or increase the entry at i by 1, and increase the difference at (j+1) - j by 1, or reduce the entry at j+1 by 1. If one endpoint of the segment to be updated is the right end, we only have to update the left endpoint.
For instance, if we add 6 sails from the right to the sequence above, we get
     10   0  -1  -1   0   0   0   0   0  -7   0
                          <------------------->
                              updated levels
      
This difference list corresponds to the updated level values
           10  10   9   8   8   8   8   8   8   1   1
      
after adding 1 to the last 6 entries.
What if we added only 4 entries, not 6? The new difference list would have been
     10   0  -1  -1   0  -1   0   1   0  -7   0
                                  <----------->
      
This corresponds to the updated level values
     10  10   9   8   8   7   7   8   8   1   1
      
which correctly captures the fact that the last 4 entries have been incremented, but this list is not in sorted order.
The problem is that the updated segment ended in the middle of a "level group" of 7's. It is not difficult to see that the only values that are not in sorted order are the elements at the right end of the level group that was only partially incremented.
When we update part of level group, we have to shift the elements from the right of the group to the left end. In this case, the final sorted sequence we should have is
     10  10   9   8   8   8   8   7   7   1   1
     
whose difference sequence is
     10   0  -1  -1   0   0   0  -1   0  -6   0
     
This corresponds to taking the level group of 7's in the original sequence and incrementing a segment [6,7] by 1, so we increase the value at position 6 and decrease the value at position 7+1 = 8, as described for a general [i,j] segment earlier.
                          level group
                         <------------>
     10   0  -1  -1   0  -1   0   0   0  -7   0
                         <---->          <---->
                         update          update

     10   0  -1  -1   0   0   0  -1   0  -6   0
     
This gives us the overall update procedure for adding K sails on a mast:
  • Count the last K levels from the right. If this ends at the boundary of a level group, do a simple update for the interval [N-K+1,N].
  • Otherwise, update everything to the right of the incomplete level group as usual and separately update the left end of the level group.
How do we find the end point of a level group? A level group [A,B] consists of a contiguous interval of 0's, so we need to find the next non-zero value to the left and right of a given position K from the right. To get full credit, this has to be done using a segment tree. For each interval of the sequence of levels, store the position of first nonzero position from the right end of an interval and the first nonzero position from the left end of an internval. Using this, we can find the endpoints of the level group containing a given position K in time proportional to log(number of levels). This segment tree can also be updted in time proportional to log(number of levels).
Overall, the complexity is then O(number of masts × log (max levels)).

Wednesday, July 1, 2015

USACO US Open 2015 Contest Gold - Palindromic Paths

문제 링크(Problem Link)

  우선, 첫 번째로 관찰할 수 있는 게 주어진 그리드가 N by N이어서 생성되는 string들의 길이는 항상 (2N-1)이다. 따라서 길이는 항상 홀수이며 그 가운데에 위치하는 문자는 그리드에서 오른쪽 위에서 왼쪽 아래로 내려가는 대각선 위에 위치하게 된다.
  여기서 착안해서 다음과 같이 DP Table을 정의할 수 있다.
  D(L , a , b) = 가운데에서 양쪽으로 뻗어나가는 길이가 현재 L이고, 왼쪽으로 L번째 문자가 a번째 행까지, 오른쪽으로 L번째 문자가 b번째 행까지 고려됬을 때 가능한 가짓 수
  저기서 a랑 b들은 L에 따라서 위치할 수 있는 곳들이 각각의 대각선들로 정해지는데 탐색하는 순서는 큰 상관 없는 것 같다. 결론적으로 S[a][col(a)] == S[b][col(b)]라면
  D(L, a, b) = D(L-1, a, b) + D(L-1, a-1, b) + D(L-1, a, b+1) + D(L-1, a-1, b+1)이 된다. 만약 해당 좌표가 그리드의 크기를 넘어가면 0으로 처리하면 된다.  답은 D(n-1, 1, n)에 위치한다.

Monday, June 29, 2015

JAG Spring Contest 2013 E번 / KOI 2014 고등부 4번


주어진 그래프에서 MST G(m)이 있다고 하자.

G(m)에 포함되지 않은 간선을 자르는 경우에만 Gi가 현재 MST의 weight sum(=S)과는 다른 값을 가지게 된다. i번째 간선을 자르면 G(m)은 이분 그래프가 되는데, 이 때 두 subgraph를 연결하는 가장 작은 간선을 골라주면 되는 것이다.

Kruskal Algorithm을 기반으로 MST를 구성했다고 가정하자.
MST에 포함되지 않는 간선들을 가중치 순으로 Union-Find 처리해주면서 depth가 서로 다른 두 정점 u, v(dfs tree에서 depth(u) > depth(v))가 있다면, Gi('u와 u의 부모' 간선 index) = S - ('u와 u의 부모' 간선의 가중치) + (현재 i번째 간선의 가중치)를 대입하는 과정을 u와 v가 다를 때까지 반복해주면 된다.
Kruskal Algorithm 원리 특성상 만약 지금 i번째 간선이 MST의 간선이면, i번째 간선(u,v)를 제외했을 때 그 간선의 정점 u, v가 같은 Union이 되기 위해서는 j>i인 j번째 간선이 필수적으로 필요하기 때문에 역으로 처리해준다고 보면 이해하기가 더 쉬울 수 있겠다.

소스 코드(Source Code)

Saturday, February 14, 2015

Number Theory

2013/2학기 응용정수론 청강 중 필기 내용. 모듈러, 오일러 정리, 확장 유클리드 알고리즘, 오일러 파이 함수, 뫼비우스 함수와 반전 공식, 뤼카의 정리.

오른쪽 링크를 클릭 : Dropbox - PDF FIle

Strongly Connected Components Algorithm - Kosaraju

1. 방법과 증명(Dropbox - PDF File)

2. 소스 코드 (BOJ 2150 포맷에 맞추어 작성하였다.)

Friday, February 13, 2015

Minhash for Jaccard Similarity

출처 : POSTECH 한욱신 교수님의 글(minhash for dummies|Andy Han)

참고자료 : 
University of Utah - Jeff M Phillips의 자료

1. 기초

두 개의 set A, B가 주어질 때, 두 set의 유사성을 계산하는 measure로 Jaccard Similarity라는 것을 쓴다. JS(A,B) = |A intersect B|/|A union B|로 정의된다.

이것을 구하기 위해서는, A의 원소를 정렬하고 B의 원소를 정렬한 후에, 두 정렬된 셋(즉, 리스트)를 머지하면서 구하면 된다. 그런데, 이렇게 구하면 O(|A|log|A|+|B|log|B|)의 time complexity가 생기는데, 이것을 줄이기 위해서 나온 것이 minhash이다.

왜 minhash라고 했을까? 즉, 주어진 집합의 모든 원소들을 hash한 후, 가장 작은 hash값을 가지는 원소를 hash값으로 사용하겠다는 것이다. 이를 위해, random permutation 함수 phi를 생각해 보자.
즉, phi는 {1, 2, ..., N} -> {1, 2, ...,N}으로 hash하는 함수이다.
집합 A의 모든 원소에 대해서 phi를 적용한 후, 제일 작은 값을 가지는 원소를 hash 값으로 사용한다. 예를 들어, A={2, 7}로 주어졌는데, phi(2)=3, phi(7)=2로 나오면, minhash(A)=7이 된다.

예제 1: A={1,2}, B={1,3}, C={2,4}라고 하자. 그러면, 모든 원소들의 universe는 {1,2,3,4}가 된다. 즉, 바로 위의 paragraph에서 N이 4가 되는 것이다. 두 가지 random permutation 함수 p1, p2를 생각해보자.
p1(1)=2, p1(2)=1, p1(3)=4, p1(4)=3이고, p2(1)=3, p2(2)=2, p2(3)=1, p2(4)=4라고 하자.
p1에 대해서 A에 대한 minhash값(즉, minhash(A))는 2이 된다. 즉, A의 원소인 1, 2에 대해서 p1(1)(=2) > p1(2)(=1)이므로, 2값을 minhash 값으로 정하게 된다. A에 대해서 p2를 적용한 minhash값은 같은 논리로 2가 minhash로 정해진다.

random하게 phi를 정하게 되면, A에 있는 모든 원소가 확률적으로 동일하게 minhash 값으로 선정될 수 있다. 왜 이것을 사용하면 JS를 구할 수 있을까?

이는 P[minhash(A)=minhash(B)] = JS(A,B) (수식 1)라는 중요한 성질이 존재하기 때문이다. 어떻게 이런 성질이 나오나 생각하면 아래와 같다.

우선, minhash(A)=x 라는 수식을 다른 말로 해석하면, A에서 하나의 random sample을 뽑았는데 그게 x이다라고 생각할 수 있다. 따라서, P[minhash(A)=minhash(B)] = P[x in A and x in B] for a randomly chosen x from A union B (수식 2)라는 중요한 공식이 성립한다.

마지막으로 P[x in A and x in B]= |A intersect B|/|A union B| (수식 3)가 된다.

따라서, 수식 1~3에 의해서 P[minhash(A)=minhash(B)] = JS(A,B)이 된다.

2. 알고리즘과의 연계

그럼 P[x in A and x in B]는 알고리즘으로 표현하면 무엇과 동일한가?

1: hit = 0;
2: for i = 1 to M
3:  get a random sample x from AUB
4   if x is in X and in Y, hit++
5: return hit/M
로 표현할 수 있다. 즉 return값은 궁극적으로 JS(A, B)가 된다.

AUB에서 하나의 random sample을 뽑았는데 그게 A와 B에 모두 있을 확률은 P[minhash(A)=x and minhash(B)=x] 라는 표현할 수 있으므로, 위 알고리즘은 아래와 같이 최종적으로 바뀌고 그게 minhash 알고리즘이 된다.

hit = 0;
for i = 1 to M
   if minhash_i(A)=minhash_i(B), hit++
return hit/M

M을 무한대로 보내면 확률값을 구하게 된다. 일반적으로 M은 |AUB|의 값보다 훨씬 작은 값을 사용한다. 예를 들어, 100?

3. 질문

(Q1) random permutation이랑 무슨 상관?

random permutation을 사용하기 때문에, AUB의 모든 원소가 동일한 확률로 제일 작은 min hash값을 가질 수 있다. 즉, "get a random sample x from AUB"를 하기 위해서 random permutation의 개념을 사용한 것이다.

Sunday, January 4, 2015

Polish Olympiad in Informatics 2006/2007 Stage 1 - 'Queries'

Problem Link(문제 링크)

문제 요약 : 1 ≤ x ≤ a이고 1 ≤ y ≤ b일 때, gcd(x, y) = d인 (x, y) 쌍의 개수를 구하시오.

gcd(x, y) = d이므로 x = pd, y = qd라고 하면, 1 ≤ p ≤ a/d이고 1 ≤ q ≤ b/d일 때 (p, q) = 1인 쌍의 개수를 구하는 것과 동치가 된다.(㉠)

가장 먼저 생각할 수 있는 것은 O(ab log x)로서 모든 (p, q) 쌍에 대해 gcd 테스트를 해보는 것이다.

여기서 조금 더 개선하면, 오일러 파이 함수를 써서 하나의 p에 대해서 모든 q에 대해 gcd 테스트를 하지 않을 수 있다. 0~(p-1)까지의 패턴이 반복되므로 q에 걸쳐있는 마지막 패턴에 대해서만 유효한 범위에 대해 gcd 테스를 해볼 수 있다. 시간복잡도에는 큰 변화가 없다.

다르게 생각해보면 gcd(p, q) = 1인 걸 다 구하는 것이 아니라, gcd(p, q) = k인 걸 빼보는 방법을 떠올리 게 된다. 위에서 썼던 ㉠ 방법을 쓰고, 포함배제를 쓰면 O(a log b) 정도에 구할 수 있다.

좀 더 생각하고 관찰해보면 f(p, q) = f(p/2, q/2) + f(p/3, q/3) - f(p/6, q/6) + f(p/5, q/5) + f(p/7, q/7) - f(p/10, q/10) ... 이 되는 걸 알 수 있다. 즉, f(p, q) = 시그마{ f(p/i, q/i) } * 뫼비우스 함수(i)가 되는 것이다.

여기서 뫼비우스 함수는 곱의 함수이므로 약수 구하듯이 해서 n루트n의 시간복잡도에 구할 수 있고, 저 시그마 부분을 빠르게 개선해야한다.

p/i나 q/i 값이 변하게 되는 i 중 최솟값으로 자꾸 갱신시켜주면, 그 갱신이 3*루트(a)번 정도가 됨을 알 수 있다.

따라서 O(쿼리 수 * 루트 a)의 시간복잡도에 문제가 해결된다.

Thursday, January 1, 2015

POJ 3468 - BIT를 이용해 구간에 값을 더하기

문제 : POJ(PKU) 3468 - A Simple Problem with Integers

열 A[1] A[2] ... A[N]이 주어졌을 때에, 연속된 부분 배열 A[i...j]에 x를 더하는 것과 A[i]+A[i+1]+...+A[j]를 묻는 쿼리 M개가 주어진다.

Binary Indexed Tree 2개를 이용해 O(N log N + M log n)에 해결가능하다.

y[i] = A[i]-A[i-1], z[i] = i*y[i]라고 정의하자.(A[0] = y[0] = z[0] = 0)

A[1]+A[2]+A[3]+A[4]

= y[1]+(y[2]+y[1])+(y[3]+y[2]+y[1])+(y[4]+y[3]+y[2]+y[1])

= 4*y[1] + 3*y[2] + 2*y[3] + y[4]

= 5*(y[1] + y[2] + y[3] + y[4]) - (y[1] + 2*y[2] + 3*y[3] + 4*y[4])

= 5*(y[1] + y[2] + y[3] + y[4]) - (z[1] + z[2] + z[3] + z[4])

일반화해보면

Sum(L, R) = A[L]+A[L+1]+...+A[R-1]+A[R]

= (R-L+1)*(y[L]+y[L+1]+...+y[R-1]+y[R]) - (z[L]+z[L+1]+...z[R-1]+z[R])

구간 A[i...j]에 x를 더하는 것은 i번째와 j+1번째의 y, z값만 변하므로 log N에 갱신 가능.

만약 j가 N이라면 j+1이 존재하지 않는 것에 유의하면 된다.

내 소스코드