JMK 트레이더 레벨 1. 스킬포인트 뭐찍지?

잠이 안 온다

괜히 치킨이 먹고 싶어서 파파이스에서 치킨이랑 샌드위치를 사 왔다가, 샌드위치만 먹고 치킨은 느끼해서 못먹고 다 버렸다. 그리고 소파에 잠깐 누워서 Doron 이 빌려준 Elements of Statistical Learning 읽다가 깜빡 잠들었다. 정신 차려보니 열 시. 온 몸에 기운이 하나도 없는 게, 피곤하긴 피곤하구나 싶었다. 겨우겨우 일어나서 컴퓨터를 켰지만 뭐 제대로 된 일을 할 기운도 없고.. 해서 일찍 누웠는데, 영 잠이 안 온다. 오랜만에 기름기 많은 것을 먹어서 그런가.

하여간 열심히 시간낭비 하다가 와서 일기써본당

.vimrc

(more)

최근 듣는 노래들

• W&Whale
• 아웃사이더
• 이승환 옛날 노래들
• 두번째달
• 브로콜리너마저
• 허경영 -_-;

SRM440 연습

250 열어보니 이전에 돌았던 셋 같은 느낌이 강하게 들었지만 그냥 돌았음. binary search 250 과 DP 500, 그리고 DP 1000 으로 구성된 셋. 500 은 느리긴 느렸는데 풀긴 풀었고, 1000 은 한참 헤매다가 설마 이게 될까? 하고 1시간 17분째에 냈다. 결론은 PPP ㅠ 만세

(more)

SRM 446 연습

안드로.txt

250 을 쉽게 푼건 좋았는데, 500 에서 사상 최대의 삽질 시나리오.

• string 출력이라, 답의 범위는 long long 이지만 bigint 인 줄 알았다.
• 존내 고생해서 bigint 로 O(lgT * n^2) 솔루션을 짬.
• 문제 잘못 읽음. matrix 고쳐서 walkaround 만듬.
• 너무 느리다.
• 존내 최적화.
• long long 인걸 커피가 가르쳐줌 => long long 으로 변경
• 틀림.
• 1에서 1로 가는 사이클 길이가 음수일 때도 그냥 끝내는 게 나을 수 있다는 점을 신경 못썼음.

.. 뭐 이런 시나리오. 1k 는 일단 어떻게 푸는지 감도 안오고.. 소스코드가 맘에 안들어서 다시 매크로를 쓰지 말까 하는 생각을 하고 있음.

(more)

UVA10403; Escape From Tut's Tomb

문제 링크: 몇년째 풀진 못하고 고민만 하던 문젠데, 결국 탑코더 포럼에 올려서 질문하자, "백트래킹으로 되요" 라는 대답이... 헐... 난 왜 이렇게 할 생각을 못해봤을까. (당연히 시간 안에 안나올 줄 알았지. orz) 자료구조도 모호하게밖에 생각 안 나고.. 해서 그냥 냅뒀는데, 이렇게 간단하게 풀릴 줄이야. ㅠㅠ

막상 짜보니 랭크리스트 1등.... orz

(more)

Linear Fractional Programming

After ACM ICPC Seoul Regional 2009, I hear problem D could easily modeled as a Linear Fractional Programming problem; lewha0 pointed me to the solution of this kind of problem before - here's a brief review of the solution.

Problem

Given a sequence of 0 and 1's, return a continuous subsequence with maximal average. The subsequence must not be shorter than L.

Solution

I am aware of two approaches.

1. Try every length up to 2L: given a subsequence of length 2L, by pigeonhole principle, one of the two L-length halves has the same or better average.
2. Generalize the problem and use LFP.

LFP can solve this generalized version of the problem: Given A[] and B[], return max interval (i, j) where (A[i]+..+A[j])/(B[i]+..+B[j]). In this problem, A[] is either 0 or 1, and B[] is always 1.

Let's start with a guess; will the final solution be smaller than x? Let us assert x is an upper bound of sum(A[i..j])/sum(B[i..j]), for all possible interval,

Rearranging, we get

So is an upper bound if and only if for every possible interval , the above equation is positive. We can easily check this by calculating the vector and find the interval with minimum sum - and see if it's less than zero. If it is greater than zero, is indeed an upper bound.

Now, we can easily do binary searching over possible ranges of .

source code follows ...

Another Wednesday

주말이 끝나고 내일이면 출근이라고 징징댔는데 벌써 3일이 지나가다니.. 시간 빠르다. 요즘은 회사에 있는 시간이 너무 휙휙 지나간다. 일이 재밌어서 그런가. 관심 있고 해보고 싶던 일 하니까 확실히 재미는 있다. 솔직히, 잘 하던 일 내버려 두고 다른 것 하겠다고 이러는 게 잘하는 것인가 생각이 들 때도 가끔 있긴 하지만.. 흐흐. 그렇다고 평생 변화하지 않을 것은 아니니.

오늘은 퇴근하고 곧장 차 빌려서 Oak Park 에 가서 의자를 사 왔다. 지금까지는 식탁에 딸려온 의자를 쓰고 있었는데, 집이 덥다보니.. 땀도 차고, 여러 모로 불편해서 호시탐탐 벼르고 있던 차였다. 한참 고민하고 여기저기 앉아보다가 낸 결론은 역시 그냥 에어론.. nhn 에서도, DRW 에서도 앉고 있으니 최소한 익숙하긴 하다. 의자 무지하게 튼튼한 것은 잘 알고 있는 데다, craigslist 에서 중고 사면 450불 정도면 살 수 있길래 결국 사버렸다. 어제는 TV 사고, 그제는 맥북 사고.. 지름이 그칠 날이 없구만. 잔고 완전 빵꾸났다.

집에 와서는 라면 먹으면서 벤자민 버튼의 시간은 거꾸로 간다를 봤다. 아무 생각 없이 브래드 피트 나와서 본건데 의외로 슬펐다능.... ;ㅁ; 다 보고 좀 놀다 보니 이 시간이다. 수열이는 나 씻는 사이에 잠들어 버렸다. 나도 어여 자야지.. 'ㅅ')r

AOJ 해야 할 일들 / 하고 싶은 일들

• 문제 좀 더 잘 분류할 수 있는 체계 갖추기
• 리저지 가능한 저지 구조로 변경
• 문제 삭제 및 publish 지원, 레퍼런스 솔루션 별도 업로드 등등...
• sqlite 외에 멀티스레드 지원하는 db 로 변경
• ABCs: 팀 노트북용 라이브러리 테스트 문제들: 이분매칭, 넷웍 플로, MCMF, convex hull...
• 알고스팟 공식 ICPC 소스코드 리포지토리 (?)
• Contest mode, virtual contest mode 추가

SRM447 Practice

A match sponsored by Facebook. Simple simulation 250, Graph + Bipartite Matching 500. I wasn't sure about whether bipartite matching could be the right solution for 500 (I'm so rusty.. of course, this is a classic example of Konig's theorem.) About 1000, so far no idea.

(more)

SRM449 practice

A simple geometry 250, counting 550 and quite tricky 950. I thought I didn't have a chance writing both 550 and 950 in time, and wasted some time looking and thinking about both problems. I finally went for 550 - that proved to be easier than I thought. So the score is not great... but anyway.

Ah, and the source code for this match was committed with revision 1000 of my personal SVN repository.

(more)

Adaptive Simpson's Method

Simpson's Rule 은 적분이 들어가는 모든 문제에 캡숑 유용하게 쓰이는 방법이다. 목적함수를 2차함수로 근사하기 때문에, 실제 목적함수의 차수가 2차 이하의 다항식인 경우에는 귀찮게 손으로 적분할 필요 없이 정확한 답을 구할 수 있다. 당연하지만 이 이외의 경우 -목적함수가 다항식이 아니거나 한 경우-에는 오차가 매우 커진다.

알고스팟 모의고사 준비하면서 sqrt(r^2 - x^2) 를 적분할 일이 있었다. 물론 닥치고 울프람 형아 적분헤 주떼영 하면 되지만 나도 남자의 자존심이 있어서 그건 싫고 -_- 해서 numerical method 를 쓸 양으로 Simpson's rule 을 써 보았다.

lang:py
def f(x):
    return sqrt(1 - x*x)
def simpson(a, b): 
    c = (a+b)/2.0
    h3 = abs(b-a) / 6.0 
    return h3 * (f(a) + 4.0*f(c) + f(b))

하고, -1 부터 1 까지 적분하면 반원의 넓이니까 pi/2 가 나와야겠지.

In [2]: print simpson(-1,1)
------> print(simpson(-1,1))
1.33333333333

깨갱 -_- 0.2나 차이나네; 이렇게 되면 질수없다. 인터벌을 1000개로 나눠서 각각 구간에서 simpson's rule 을 돌리기로 한다.

In [9]: xs = arange(-1,1,0.002)
In [10]: sum([simpson(xs[i],xs[i+1]) for i in range(len(xs)-1)])
Out[10]: 1.5707083802290707

오 꽤 정확해짐. 하지만 아직도 오차 범위가 1e-5 라서 많이 부족하다. (대개 프로그래밍 대회에서는 1e-7 이하의 정확도를 요구한다.) 인터벌을 몇개로 늘리면 될까. 1만개로 테스트.

In [13]: xs = arange(-1,1,0.0002)
In [14]: pi/2-sum([simpson(xs[i],xs[i+1]) for i in range(len(xs)-1)])
Out[14]: 2.7818300534221407e-06

아니 시발 이게 뭐야 -_-; 결국 테스트를 해보니 5만개 정도로는 나눠야 1e-7 정확도를 얻을 수 있다. 물론 일루옹이 낸 문제답게 n 이 작지도 않고.. 이대로는 절대 시간 안에 안나온다. 그래서 써먹은 것이 Adaptive simpson's method.

기본 규칙은 매우 간단하다. 이 함수가 생긴 모양을 봐서 2차 함수로 적절히 근사가 된다 싶으면 그냥 simpson's rule 을 써서 근사하고, 아니면 절반으로 나눠서 divide & conquer. 위키피디아 엔트리 링크

lang:py
def adaptive(a, b, sum, eps):
    c = (a+b) / 2.0 
    left = simpson(a, c)
    right = simpson(c, b)
    if abs(left + right - sum) <= 15 * eps:
        return left + right - (left + right - sum) / 15
    return adaptive(a, c, left, eps/2) + adaptive(c, b, right, eps/2)

15 로 나누는 부분이 매우 맘에 걸리지만 지금은 수치해석시간이 아니니 자세한 분석은 넘어가기로 하고.. (나 수치해석 학점 B 다..) 말할 것 없이 돌려보면

In [31]: pi/2 - adaptive(-1, 1, simpson(-1, 1), 1e-8)
Out[31]: 7.0505905558349014e-09

실제 simpson() 함수가 계산되는 회수를 세어보면 800회정도밖에 안된다. 우훗! 물론 이거야 이 함수가 매우 스무스하게 생긴거라 그러니 오해하면 안됩니다. 여튼 적분하기 싫은 여러분, 이렇게 이겨냅시다 [....]