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