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}도 동일한 공간을 생성한다.

Thursday, November 20, 2014

Algospot ICPC Seoul Regional Warmup 2009 TILING 풀이

알고스팟 문제 링크

Source Code

D(n) = D(n-1) + 2*D(n-2) + 6*D(n-3) + D(n-4) - D(n-6)

위의 점화식을 행렬로 바꿔서 O(T log n)에 풀면 됨.

그런데 점화식에 음수가 있다보니 답 출력할 때, 양수로 변환해주는 것에 주의.

2013 KAIST ACM-ICPC 교내 대회 CLEANING 문제 풀이

알고스팟 문제 링크

Source Code


Mincost Maxflow 알고리즘으로 해결된다.

이분그래프를 구성하는데 좌변,우변에 1~n번째 점들을 배치한다.

i번째 점에서 x좌표 부호가 반대인 방향으로 (유량 = 1, 코스트 = 거리)로 엣지를 준다.

소스에는 왼쪽 부분그래프, 싱크에는 오른쪽 부분그래프에 (유량 = 1, 코스트 = 0)을 준다.

그리고 y축에 배치시키는 것을 왼쪽 부분그래프의 i번째 점에서 오른쪽 부분그래프의 i번째 점으로 (유량 = 1, 코스트 = 2*|X(i)|)로 준다.

MCMF를 돌린 후, Total Cost / 2을 답으로 정해주면 된다. 왜 나누기 2를 하냐하면, (a, b)가 짝이 된다면, 그 둘 사이의 거리가 2번 카운트 되기 때문이다. 현재 위치에서의 물건 개수와 선대칭 시킨 후 물건 개수가 같아야 하므로 대칭시켰을 때의 물건들과 현재 물건들과 항상 일대일 매칭 시킬 수 있음이 자명하므로 이 문제가 MCMF로 Polynomial한 시간에 풀린다고 할 수 있겠다.

Sunday, November 9, 2014

2014 대전 리저널 후기

우리 팀은 팀명이 ACRush라서 팀 번호가 1번이었다.

대회 도중의 상황이 어땠는지는 암담해서 뭐 하나하나 적기 그렇지만... 대회 시작할 때는 월파나갈 것 같다가 중반부터 거의 막바지에 이르러 멘탈이 다 터질 뻔한 상황까지 갔다. 마지막에 극적으로 연달아 틀렸던 것들을 고치면서 그나마 상항이 나아졌다.

대회 끝나고 당일이랑 그 다음날까진 후회가 별로 없었고, 실력 부족이라 생각했는데 재현이형 글을 읽으면서 진짜 가슴이 먹먹해질 정도로 후회가 되더라.

일단 페어 프로그래밍을 막바지에 하면서 틀렸던 것들이 하나씩 맞기 시작했고, 대회 시작하고 1시간 이내에 옳은 풀이를 떠올렸는 걸 4시간 후에 맞춘 게 팀워크가 0이었다는 걸 절실히 보여주었다고 생각한다.

아.. 개인적으로 태규가 진짜 이 문제 저 문제에서 맹활약해주었다. 예상치못하게 지훈이가 K번으로 고전을 겪었는데, 난 문제 설명을 전해듣고 30일 이내만 참조하면 되는 것에서 솔루션을 바로 떠올렸는데, 지훈이한테 말만 이렇게이렇게 하면 될 거같다고해주고 그 당시에 내가 I번 TLE의 원인을 모르던터라 차마 내가 그것마저 떠맡기 두려워서 회피했다ㅠㅠ 후...

결국 지훈이는 능력을 하나도 발휘하지 못하게 내가 막아버린 것이다.

예선 때, 내가 풀 수 있다고 생각한 문제들은 다 가져가서 하나씩 풀었더니 시간이 많이 부족했던터라 이번엔 골고루 나누면 좋겠다고 생각했는데 참 똥 같은 전략이었다 ㅋㅋ ㅠㅠ

뭐 운이 좋아서 인터넷 예선에서 상위권팀들 중 각 학교 리저널 2등 팀에게 주는 상도 받고, D번을 Fisrt to Solve해서 특별상도 받았고...보상(?)은 많았지만 성적은 형편없었다ㅋㅋㅋ

아 너무너무 미안하다. 팀원들 개개인 능력을 합하면 다른 팀에 꿇릴 게 전혀 없어보이는데 팀장 역할을 했던 내가 다 시원하게 말아버린 것이다. 그리고 사실 팀원들이 연습을 거의 안했던 것도 내가 대구에 살아서 그런 점도 있으니 내 잘못이 크다ㅠㅠ 내가 서울에만 살았어도 작년에 명우가 날 훈련시키듯이 같이 연습했을텐데...

나 개인적으로는 작년보다 실력이 좀 늘어서 나름 기대했었는데... 후... G번이랑 L번 고민했는데 결국 못 푼 걸 보면 내 개인 실력도 많이 부족하고.. 내년에 팀이 어떻게 될 진 모르겠지만, 올해 아쉬웠던 것들을 메모해둔 걸 바탕으로 다신 두 번 다시 실수하지 말아야지. 이 모든 것들이 팀원들과 자주 팀 전략을 짜고, 연습을 하고, 개인 연습도 많이 하면 다 해결되는 거라 구차한 변명밖에 안되지만....

Monday, September 8, 2014

오늘 푼 플로우 문제들

1. CEOI 2002 5번

N * M 그리드에 0에 룩을 최대 몇 개 놓을 수 있는지의 문제이다.

이분 그래프를 구성하는데, 왼쪽에는 가로로 배치되는 룩의 구간들, 오른쪽에는 세로로 배치되는 룩의 구간들을 놓고 최대 매칭을 구하면 된다.
예를 들어, 가로로 배치되는 룩의 구간을 구한다고하면, (i, 1)~(i,m)까지 보면서 2를 만나면 번호를 늘려주고 아니면 계속 그 번호를 유지하면된다. (i, j)에서 가로로 배치되는 구간의 번호와 세로로 배치되는 구간의 번호에 용량 1을 지정해주면 된다. 당연히 소스랑 싱크에도 다 용량은 1로 지정해준다.

소스 코드

2. BOJ 1017

첫 번째 수와 짝지을 두 번째 숫자를 정한 다음에 나머지 숫자들에 대해서 어떤 2개(i번째와 j번째)가 더해서 소수가 된다면 i번째와 n+j번째에 용량을 1로 주는 이분 그래프를 구성해서 최대매칭을 구한 후, 그 값이 n-2(첫 번째 수와 두 번째 수를 제외하고 다 쌍이 생겼다는 말)인지 확인한다. n-2이면 정한 두 번째 숫자가 답이 될 수 있으므로 출력하면 끝.

소스 코드

3. Baltic Olympiad in Informatics 2008 6번

Min-cut 문제이다. 답이 되는 그래프의 꼴을 잘 생각해보면, 어떤 정점들을 기준으로 이분그래프로 분할되는 것을 알 수 있다. 각 정점들을 2개로 쪼개서, 사이에 각 톨게이트의 점거비용으로 유량을 준다. 나머지 간선들과, 소스 및 싱크에서 각 점들에 해당하는 유량들은 모두 무한대로 준다. 이렇게 그래프를 구성한 다음에 Maximum Flow를 돌려주면, 그 값이 최소 점거비용이 됨을 쉽게 알 수 있다. Minimum Cut Problem은 Maximum Flow와 동치임을 보여주는 문제이다. 여기서 문제는 점거해야하는 도시들을 출력해야하는 것이다.
Min-cut Vertex(그래프 상에서는 Edge지만, 정점을 2개로 쪼갰으니...)들을 구하기 위해서는
1) Source에서 residual(용량 - 흐른 유량)이 양수인 점들만을 bfs로 탐색하고 표시해둔다.
2) 표시된 점들과 표시 안된 점들 사이에 간선이 있는데, residual이 양수고 용량이 0이 아니라면 그 Edge가 Min-cut Edge이므로 색칠된 점들이 Min-cut Vertex가 된다.

나는 이 문제에서 점들을 이분화할 때, i번 톨게이트를 2*i-1번(들어오는 점)과 2*i번(나가는 점)으로 분리했다. 따라서 소스는 0번이 되고, 싱크는 2*n+1번이 된다.

소스 코드

20140908

DP, Greedy, Flow 문제들을 많이 풀어봤으니, 이제 2-SAT과 DS 문제들 위주로 풀어야겠다.
태규가 생각보다 DP와 그리디를 잘 푸는 것 같으니, 지훈이만 예전만큼만 감이 빨리 돌아오면 꽤나 만족스러운 결과를 얻을 수 있을 것 같다. 작년엔 명우랑 같이 연습(사실은 반강제적으로...)하다가 올해는 거의 혼자하는 상황에 오니까, 명우의 소중함을 깨닫게 되기도 한다ㅋㅋㅋ
인터넷 예선 때는 내가 교내 2위 안정권까지는 주도적으로 코딩을 하고, 팀워크를 맞춰서 뒷심을 발휘해보는 방향으로 가야겠다.

Sunday, August 24, 2014

20140824

Codeforces Round #151(Div. 2) : All solved

내가 AC 받았던 소스코드들

Problem A

Problem B

Problem C

Problem D

Problem E

E에 관해서 정리를 해보면

1) BFS로 numbering

2) 각 node마다 2^k 위의 parent를 구함

3) 쿼리 (v, k) : depth[v] + k의 깊이에 해당하는 노드 L(i)~R(i)에 대해 이분탐색을 하면서 k 깊이 위의 부모가 v인지 검사하는 식으로 구간 [L, R]을 구함.

4) 구간들을 Bucket Sorting하고( [L/루트(N)]*루트(N) + [R/루트(N)], [ ] : 가우스 기호 ) acmicpc.net 8462 '배열의 힘' 문제 솔루션 대로 쿼리에 대해서 답을 구한다.
(acmicpc.net 8462 솔루션 링크)

전체적인 시간복잡도는 O(Q log^2 N + N루트(N))이 된다.

ALPS 회원들한테 문제를 공유하고나서 좀 더 생각해보니, 쿼리가 만약 (r, v, k) : 루트가 r일 때, 쿼리 (v, k)로 루트가 입력받을 때로 지정된 게 아니라 쿼리에서 바뀔 수 있다면, 에디토리얼에 있는 BIT나 세그먼트 트리를 써야지 풀릴 것 같다. 루트가 바뀌면 구간이 [P,P]+[L,R]꼴이 되는데 [P, P]처리가 안되네 ㅋㅋ

자꾸 연습을 div2만 돌고 있는데, div1에서는 보통 많아야 2~3문제 밖에 못 푸는데 그게 div2랑 겹치다보니 ㅋㅋㅋ... 자꾸 연습하다보면 div1에서 편하게 연습 돌 때가 오겠지ㅎ

Tuesday, August 19, 2014

20140817 ~ 20140819

1. Baekjoon Online Judge 모의고사 : All solved


나랑 경근이형만 첫날부터 시작하고 나머지 사람들은 둘째날부터했다. 내일까지 계속 진행된다. F번 같은 건 한번에 맞추었어야한다. int 배열로 잡아야할 걸, char로 잡는 실수를 했다.

2. Codeforces Round #261(Round 2) : All solved

내가 AC 받았던 소스 코드

백준 저지에서 모의고사를 풀던 중, min-plus algebra라는 걸 명우를 통해서 알게되었다. 내가 대회 도중에는 직관적으로 플로이드 비슷한 Loop를 떠올리면서 행렬 곱을 해주어서 log T에 계산했었는데, 그게 알고 보니 수학적인 베이스가 기초된 정리였다.
min-plus algebra Link
행렬 곱을 함으로써 A^T을 계산하던 걸, 서로 다른 두 행렬의 원소를 Plus Calculation한 걸 min 값으로 취하는 연산으로도 같은 방식을 적용할 수 있다. 사실 A^T을 A*A*A*....해보면 차이가 없다는 걸 알 수 있는데, 거듭제곱 꼴이 과연될까 싶었는데 대회 도중에 해보니까 되더라 ㅋㅋ
비슷하게 max-plus algebra도 가능한 경우가 있으니 참고하자.

Saturday, August 16, 2014

20140815 ~ 20140816

2014 KOI 지역본선 중등부4번/고등부3번
Baltic OI 2009 4번
Baltic OI 2014 2번
NOI, China 2012 Day1 1번
IOI 2005 Mean Sequencec
IOI 2010 Quality
ACM ICPC 2012 Japan Tokyo A번
ACM ICPC 2013 Japan Aizu A번
ACM ICPC 2013 Japan Aizu G번 (복습이 필요...ㅠㅠ)

월간 텝스 풀어보고 복습하느라 PS 거의 못함ㅠㅠ

내일은 시간 내서 GA 모의고사 한 번 쳐봐야겠다.

Thursday, August 14, 2014

National Olympiad in Informatics, China, 2006 Day 2, Problem 1 - Maximum Profit

Problem Link

정점 n개와 간선 m개가 있는데, 정점에는 음의 가중치가 있고, 간선에는 양의 가중치가 있다. 이 때 정점을 몇 개 고르면, 그 정점들로 구성되는 간선을 모두 선택할 수 있다. 정점을 잘 골라서 정점들과 간선들의 가중치의 합을 최대화하는 문제이다.
MCMF인 것 같지만, Min-Cut 문제이다. 이분 그래프 구성법이 독특하여 매우 어려운 문제였는데, 왼쪽에는 간선들을, 오른쪽에는 정점들을 두고
1) 소스에서 간선들에는 유량을 간선의 가중치만큼 준다.
2) 간선에서(u-v면 i->u, i->v) 정점들에는 유량을 무한대 준다.
3) 정점에서 싱크에는 유량을 정점의 가중치만큼 준다.
위 처럼 이분 그래프를 구성하고 max-flow 돌린 다음에, 간선들의 가중치 합에서 maxflow값을 빼주면 됨. 가중치의 합을 최대화하는 문제를, 전체 가중칭서 빼주는 가중치의 합을 최소화하는 문제로 바꿔서 생각해보는 것이 중요하다고 할 수 있겠다.

Source Code

National Olympiad in Informatics, China, 2012 Day 1, Problem 1 - Random Number Generator

Problem Link

A(n) = (a*A(n-1)+c) mod m 이고 A(0)가 주어졌을 때, A(n) mod g를 구하는 문제.

g가 10^8 이하이고, 나머지 값들은 모두 10^18 이하라서, 계산 도중 long long 범위를 넘어갈 수 있음에 주의해야한다. log 시간복잡도에 a^x 계산과 1+a+a^2+....a^x 계산을 할 줄 알면 풀 수 있다. 그리고 ( X mod m ) mod g를 계산할 때에는 X나 m을 g로 나눈 나머지로 계산하면 안되고, m으로 나눈 나머지로 다 계산한 다음에 g로 나눈 나머지를 계산해야한다. modular를 공부했었다면 다 아는 사실이겠지만...

Tuesday, August 12, 2014

Note #1

1. 항상 경계값, 극한값 생각하기. 최소일 때, 최대일 때, 같을 때 고려하기.

2. 일반화의 오류에 빠지지 않기. 해법이 안 떠오를수록 문제를 반복해서 읽고, 1로 돌아가서 풀이를 떠올리기.

3. 제출하기 전에 30초만 차분히 생각하고 제출하기.

4. 1,2,3이 무의식적으로 행해질 수 있도록 반복 연습하기.

Wednesday, August 6, 2014

Counting Subsequences

Problem Link(PEG Judge)

Given a string, count all distinct subsequences (not substrings).
As defined previously, a subsequence is a collection of characters from the string (they don't have to be contiguous)

For example, for the string aba, there are 6 distinct subsequences: (a, b, aa, ab, ba, aba).

Input

The string, on one line. It will consist only of lowercase letters.
It will be no longer than 100,000 characters long (this is easier than all substrings!)

Output

The number of distinct subsequences.
Note that this number may be ridiculously large, so print it mod 10,007.

D(i) = "i번째에서 끝나고, i번째 문자를 반드시 넣을 때 만들어지는 
distinct subsequences의 개수"라고 정의하자.

i번째 문자를 S(i)라고 하자. S[i] = S[j](j<i)인 j중 가장 큰 j에 대해서 D[i] = Sum(D[j] ~ D[i-1])

만약 S[i]가 처음 등장했다면, D[i] = Sum(D[1]~D[i-1])+1이 된다.

Source Code

Friday, August 1, 2014

ICPC 팀명ㅋㅋ

'One Rest, Two Retired'에서 문제 많이 맞추자고 'ACRush'로 바꿨다ㅋㅋ

재밌겠다ㅎㅎㅎ

Wednesday, July 30, 2014

Dynamic Programming Optimizations

Codeforces Blog Article of dynamic programming optimization techniques


Codeforces Round #189 (Div. 1) Problem C 는 전형적인 컨벡스헐 트릭 문제이다. APIO 2010 Commando 문제를 짠 지 몇 주 밖에 안 지났는데, 자꾸 코딩 실수하고 처음에 데크로 접근해버렸음ㅠㅠ... 몹쓸 습관이 생겨버린 거 같다. 자꾸 연습해서 빨리빨리 짤 수 있도록 해야겠다.
정리해보면, d[i] = min(d[j]+a[i](=x)*b[j])라는 점화식이 얻어진다. d[i]값은, 선분이 들어있는 리스트 중에서 현재 x값(a[i])이 다음 선분의 유효범위 최소 x값보다 크다면 계속 다음 선분을 보는 것을 반복하다가 더 이상 안될 때, 그 선분에 a[i]를 대입해서 구한다.
선분의 기울기는 단조 감소하는데, 매 i번째마다 선분을 삽입한다. 삽입할 때, Stack에 남아있는 선분(L) 중 top()의 것과 교점을 구해서, L의 유효범위 최소 x값보다 더 작거나 같다면 pop()하는 것을 반복. 결론적으로 O(N)
내 소스코드

컨벡스헐 트릭 문제 하나 더 풀고 오늘 공부는 정리해야겠다.
내일은 Knuth Optimization에 대해서 공부해봐야지.

2013 Canadian Computing Competition, Stage 2, Day 2, Problem 3: Repetitivity

음... 일단 처음에 잘못된 dp로 접근해서... dm을 가지고 이리저리 관찰하다보니
aaaa.. bbbb... cccc ...
이런 것들은
aaaa... 에서 생성되는 파스칼 삼각형 * bbbb... 에서 생성되는 파스칼 삼각형 * ....로 되는 걸 관찰했다. 그런데 aaa...bbb...aaaa...cccc... 같이 되어버리면 aaaa..bbb...aaaaa.... 에다가 ccc...를 곱해주어야 되더라..ㅠㅠ
그래서 하는 수 없이 규칙성으로는 안되겠다고 생각하고 다시 dp로 접근해봤다.
d[i][j] : i번째 문자까지 고려하였을 때, subsequence의 길이가 j일 때의 sum(f(k)^2)의 값.
S[j] == S[i] (j < i)가 된다면 d[j-1]에다가 S[i]를 붙일 수 있는 걸 생각하고 열심히 짜보다가 말려서 irc에 도움을 요청했다. 한동안 어려움을 겪으시는 것 같아서 일단, 문제를 던져준 지훈이한테 해법을 받아서 봄.
가지고 있던 해법이라던 게 소스코드랑 주석인데, 주석에는 f(i)^2을 '어떤 특정한 subsequence가 나타나는 횟수가 f(i)인 것들의 pair 수'로 생각하면 문제를 풀기가 쉽다는 것과, 앞의 관찰을 통해 O(N^3)에서 O(N^2)으로 줄일 수 있다고 적혀있었다. 그러니까.. 예를 들어서 aaaba가 있고 특정한 subsequence인 aaa에 대해서 pair를 나열해보면 {(1,2,3),(1,2,3)}, {(1,2,3),(1,2,5)}, {(1,2,3), (1,3,5)} .... {(2,3,5),(2,3,5)} 총 16(=4^2)개.

소스 코드

D[i]를 i번째 문자까지 고려하였을 때, 'distinct한 subsequence들의 pair 수'의 합이라고 정의한다. 위에서 내가 생각했던 걸 써서, S[j] == S[i](j<i)가 되면 D[j-1]에다가 S[i]를 붙일 수 있기 때문에 D[j-1]값을 다음 S[k] == S[i](j<k<i)가 나올 때까지 D[r]에 (j ≤ r < k) 다 누적해준다. 그리고 최종적으로는 D[i]에서는 D[i-1]에다가 i번째 문자를 넣은 페어와 / 안 넣은 페어가 생기므로 D[i] = D[i-1]*2가 된다. 이해하기 위해서 뭔가 억지로 끼워맞춘 느낌인데... 그리디틱해서 명쾌하게 이해가 안된다ㅠㅠ 여담으로 이 문제를 대회 당시에 푼 사람은 딱 1명으로 Deng Calvin이라는 캐나다 친구인데, ioi 2013에서 은메달을 받았고 지금은 하버드에 있다고 한다... 똑똑한 친구구나...

으아.. N^3을 짰는데 자꾸 고쳐도 틀린다ㅠㅠ 중복 처리가 안되서 답보다 크게 나오는데... 음... N^3부터 올바르게 생각해야 N^2이 완벽히 이해가 될텐데...오늘은 자고 다음에 다시 생각해봐야지..

Monday, July 28, 2014

ACM ICPC 2014 Daejeon Regional, 한국 대학생 프로그래밍 경시대회

http://acm.kaist.ac.kr/



2014 Asia-Daejeon Korea Internet Preliminary Contest:

- Date: Oct. 02~04

2014 Asia-Daejeon On Site Regional Contest:
- Date: Nov. 07~08

- Venue: Lecture Wing, ICC Campus, KAIST, Daejeon
등록 : ~ 9월 19일
인터넷 예선 예비소집 : 10월 2일(목) 19:00~20:00
인터넷 예선 : 10월 4일(토) 14:00~17:00

지역대회 : 11월 7일(금) ~ 8일(토)

우리 팀은 휴학생 1명에, PS를 쉰 지 몇 년 된 친구 2명이 있어서 팀명은 "One Rest, Two Retired" 하기로 했다ㅋㅋ

Monday, July 21, 2014

APIO 2010 Commando 해법(Solution)

Link : APIO 2010 English Problems APIO 2010 Korean Problems

Source Code



S(n)을 x라 하면 y = f(x) = 2aS(i)S(x)+aS(i)^2+bS(i)+f(i)는 기울기가 -2aS(i)인 일차함수가 된다. S(i)는 increasing sequence이고 a < 0이므로 -2aS(i)는 monotonic increasing하게 된다. 그러면 새로 추가되는 (i)번째 선분에 대해서, (i-2)번째 선분과 (i-1)번째 선분의 교점 x값보다 (i-2)번째 선분과 (i)번째 선분의 교점 x값이 작거나 같다면 (i-1)번째 선분은 필요가 없게 된다. 이런 과정을 반복하다가 최종적으로 마지막 선분에 x = S(n)을 대입해주면 답 f(n)을 구할 수 있다. 이러한 기법을 Convex hull Trick이라고 한다.

PEGWiki's Convex hull trick

Thursday, July 17, 2014

Hackerrank - Savita And Friends

Weekly Challenges - Week 7

After completing her final semester, Savita is back home. She is excited to meet all her friends. Her N friends live in different houses spread across the city.
There are M roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between same pair of houses. Savita and Friends decide to meet.
Savita wants to choose a point(not necessarily an integer) P on the road numbered K, such that, the maximum of dist(i) for all 1iN is minimised,
where dist(i) is the shortest distance between the i'th friend and P.
If K'th road connects friend A and friend B you should print distance of chosen point from A. Also, print the max(dist(i)) for all 1iN. If there is more than one solution, print the one in which the point P is closest to A.
Note:
  • Use scanf/printf instead of cin/cout. Large input files.
  • Order of A and B as given in the input must be maintained. If P is at a distance of 8 from Aand 2 from B, you should print 8 and not 2.
Input Format
First line contain T, the number of testcases.
T testcases follow.
First Line of each testcase contains 3 space separated integers N,M,K .
Next M lines contain description of the ith road : three space separated integers A,B,C, where C is the length of road connecting A and B.
Output Format
For each testcase, print two space separated values in one line. The first value is the distance of P from the point A and the second value is the maximum of all the possible shortest paths between P and all of Savita's and her friends' houses. Round both answers to 5 decimal digits and print exactly 5 digits after the decimal point.
Constraints
1T10
2N,M105
N1MN(N1)/2
1A,BN
1C109
1KM
Sample Input
2
2 1 1
1 2 10
4 4 1
1 2 10
2 3 10
3 4 1
4 1 5
Sample Output
5.00000 5.00000
2.00000 8.00000
Explanation
First testcase:
As K = 1, they will meet at the point P on the road that connects friend 1 with friend 2. If we choose mid point then distance for both of them will be 5. In any other position the maximum of distance will be more than 5.
Second testcase:
As K = 1, they will meet at a point P on the road connecting friend 1 and friend 2. If we choose point at a distance of 2 from friend 1: Friend 1 will have to travel distance 2.
Friend 2 will have to travel distance 8.
Friend 3 will have to travel distance 8.
Friend 4 will have to travel distance 7.
So, the maximum will be 8.
In any other position of point choosen, the maximum distance will be more than 8.