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.