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)에 위치한다.