|
02 Jul 2011
|
2011-06-30
- 어제는 밤에 정리 못하고 잠들어서 오늘.
- 어제는 아점으로.. 뭘 먹었는지 기억이 안난다. -_-; 원고하다가 운동 댕겨오고, water tower place 에서 저녁 먹고 Ovo 보고 왔다. 집에 와서 디자인 어떻게 좀 해보려다가 결국 themeforest 에서 하나 지르고 잠.
- Ovo 는 다섯 번째로 본 Cirque 쇼인데.. 이건 서커스라기보단 이제 퍼포먼스에 더 가까운 느낌. 묘기보다는 연출이나 퍼포먼스, 스토리텔링(?? -_-)에 비중을 둔 듯. 마음 편하게 보면 훨씬 재미있었을텐데, 이쯤되니까 전에 본것들이랑 계속 비교를 하면서 보는 안좋은 습관이 생긴듯.. -.-;;
- 원고는 챕터13에 첫 예제가 기하인건 너무하다는 의견 때문에.. 딴거 넣을까 하다가 다항식 수치적 해법 넣었는데.. 좀 더 간단한 거 하나 더 넣어봐야겠음.
- 연습1 원고5 개발8
2011-07-01
- 점심에는 알리오 올리오 재도전. 처음에 마늘 볶을 때 약불에서 오래볶는게 포인트였던 거 같다. 오늘은 맛있게 먹음. 저녁은 돼지고기랑 집에 있는 야채 이것저것 집어넣고 볶아먹었다. 이제 새로운 요리책이 필요한 시점이 왔다. -_- 이 책에서 해먹고 싶은건 다 해먹을 만큼 해먹어서;;;
- 어제 theme 사고 나니까 웹 개발이 다시 재밌어져서 -_- 하루종일 작업했다. 일단 위키는 완성.
- 근데 theme 에 왠만한 디자인 요소가 있으니까 굉장히 생산성이 높아진다. 실제로 내가 웹 개발할 때 디자인 요소에 버리는 시간이 많았다는 걸 실감하는 계기였던거 같다.
- 하여간 이정도면 django 생산성도 괜찮은 듯.. 원래 장고가 잘될때는 좋은 프레임워크는 맞다. -_-
- virtualenvwrapper 처음으로 깔아서 쓰기 시작했는데 지금까지 왜안썼어 이거..
- 개발13
|
|
|
|
원고 하기 싫을 때 시간 낭비하는 게 싫어서 장고로 AOJ+알고스팟 개선하는 프로젝트를 해볼까 생각한지 어느덧 몇 개월.. -_-
로고도 만들어 보고 (지금 보니까 맨 아래건 게이 커뮤니티 같네 -_-)
새 디자인 시늉도 내 봤지만 결국 디자인의 벽을 넘지 못하고 아.. 귀찮아.. 하고 있었다. 그러다가 어제 에이 몰라 하고 themeforest에서 테마를 하나 지르고 잠들었다.
그리고 오늘 저녁에는 ...
|
|
|
|
파스타 해먹을 때마다 맨날 하는 과정
- 저번에 파스타 먹었을때 배가 안불렀으니 좀더 삶아야지
- 어씨 삶고 보니 너무 많네, 조금만 소스에 넣어야겠다
- 아씨 다 넣을걸.. 소스 다먹었다 ㅠㅠ
|
|
|
30 Jun 2011
|
- 어제는 종훈종우네 집에서 용진이랑 넷이 회먹고 맥주먹고 집에 와서 일찍 잠들었다. 덕분에 일기가 없다. =.=
- 9시 반쯤에 쓰러졌다가 12시 반쯤에 씻어야지 하고 깼는데 씻으니까 잠깨서.. 네시 반까지 딴짓하고 집에 앨범 다꺼내보고 하다가 잤다. ㅋㅋ
- 일어나서 감자국 후딱 끓여서 점심 먹고, 집에서 원고 좀 하다가, 월그린에 모자란 휴지 사러 나갔다가, 원고 좀 하다가, 나가서 산책하고 들어왔다가, 원고.
- Google+ 의 출시와 함께 구글 검색 페이지 디자인이 바뀌었는데 참 맘에 든다.
- 그런 의미에서 알고스팟 리뉴얼 디자인은 어떻게 할까 고민을 해보았는데 참 답이 없다. orz 흑흑 디자인은 왤케 어렵나여.
- 이제 피곤해서 자야 할거 같은데 왤케 라면이 먹고 싶나. 으.
- 원고는 30챕터 릴리즈. 이제 챕터 두개 남았다. 13챕터 카메라레디 만드는중.
- 원고9 연습3 개발3
|
|
|
28 Jun 2011
|
- 아침은 한밭설렁탕, 점심은 치폴레, 저녁은 집에서 김치찌개.
- 아침에 수정이 공항에 데려다 주느라 6시에 일어나서 미드웨이 댕겨옴. 아침 먹고, 집에 와서 원고 한세션 하고 쓰러져 잠들었다가 일어나서 병원. 댕겨와서 김선생님이랑 하체운동. 집에 와서 원고. =_= 세탁기땜에 짜증좀 나주시고. orz
- 원고만 하려니까 원고가 안되면 시간을 낭비하는 문제가 생겨서, 앞으로는 이것저것 다 시간에 트래킹하기로 했다. 다시 algospot / aoj 관련 작업을 좀 들여다봄.
- 최단거리 챕터 마지막 연습문제 풀이 쓰는 중. 이거 하면 1st iteration 은 끝나고, 하루 이틀이면 무난하게 릴리즈할 수 있기를 기도해보지만..
- TCO R2 이지-미듐 다시 풀어봤다. Aㅏ.. 어려워. -_-
- 원고7 연습2 운동2 개발1
|
|
|
27 Jun 2011
|
- 일어나서 원고 조금 하다가 Taste of Chicago 댕겨왔다. 사람 많고 정신 없고 ㅋㅋ 그래도 시끌벅적한데서 기름진 음식 먹고 맥주 먹으니 뭐 좋을수밖에? -_-;; 2008년 생각이 나더라. 하하 =.= 그땐 3년 후에 내가 아빠가 될 줄은 몰랐겠지... 으으음...
- 브라질리안 bbq, 미트볼, 딥디시 피자, 이름모를 아프리칸 샌드위치, 바비큐 칠면조 다리, pulled pork 샌드위치, 겨자가 들어간 튀김옷을 입혀 튀긴 catfish, 생선 타코, 코코넛 아이스크림, 츄러스 등을 먹은거 같은데 -_-;; 뭔가 빼먹었을지도;;;
- Taste 갔다 들어오니까 네시.. 조금 놀다가, 원고 좀 하다가, 김치찌개 끓여서 저녁 먹고. 원고하다 놀다가.
- 내일은 수정이 라이드해줘야 해서 6시에 일어나야 하는 관계로.. 얼른 자야지.. =_=
- 원고7
|
|
|
26 Jun 2011
|
- 아침에 일어나서 졸린 눈을 비비며 TCO R2.. 앞으로 이 매치를 625 대참사로 부르기로 마음먹었다. 레이팅 4-year low -_-;;;; 주여;;; 자비란 없단 말입니까;;; 공부할께요 잘못했어요 엉엉엉
- 이게 현실인지 악몽인지 실감이 나지 않는 가운데.. 부부동반 모임 있어서 q가서 늦은 점심 먹음. 크 바베큐 맛있어요. 우리가 제일 많이 먹은듯.
- 집에 와서 좀 자고=.= 꿀꿀이 유모차랑 카싯 왔길래 풀어보고, 하다가 원고 시작. 벨만포드 설명까지 했고, 벨만포드 연습 문제도 골랐고, 플로이드 설명. 나 이거 드래프트 쓸 때는 정말.. 잘 못썼구나. 지금도 잘쓴건 아니지만 으으. 두번째 이터레이션에서는 대대적인 리팩토링이 예상됨...
- 연습2 TCO3 원고8
|
|
|
|
gah it's like 2006 all over again
|
|
|
25 Jun 2011
|
- 요즘 너무 돼지고기만 먹는 것 같아서 점심에는 오야코동, 저녁에는 뚝배기불고기. 둘다 첨해보는 건데 성공했다 핫핫;;
- 그 외에는 내일 TCO R2 땜에 연습을 좀.. -.- SRM 508 돌고 (망하고) SRM 509/508 다시 짜고, 일루옹이랑 SRM 506 돌고, MCMF 라이브러리 짜고.. 하느라고 시간을 많이 보냈다. 내 라이브러리도 어느새 내용물이 많아졌넹.
- 원고는 다익스트라 세번째 연습문제 풀이 쓰는 중.. 첫 두개는 너무 단순해서 소스 코드도 안 붙여 넣었다. -_-
- 원고2.5 연습11.5
|
|
|
|
- The easy solution for 250 pointer made me feel like a fool. If I had half the patience to write down the patterns in pen and paper, could have done it in 3 minutes.
- For the medium there were some intricacies involved, because you can place add/remove in between change operations. I took care of some combinations, since the example covers them, but didn't get one.
- The pattern I didn't get was adding a char on the left, changing it to something, and changing the rightmost char to match it. Bah.
- The elegant way to do it seems to be introducing a NULL symbol -- deleting is merely changing a char to NULL, and adding is changing NULL to a char. Then we can calculate the minimum cost to make two symbols match, then the problem is a no brainer.
- So another take home lesson would be: 서로 조합해서 경우의 수가 많아지는 연산들을 직접 다룰 때는, 가능한 한 개의 연산으로 나머지를 표현해 보면 더 쉽다. another path in this case can be trying to normalize the order of the operations, which doesn't work in this problem, obviously.
source code (rewritten) ...
|
|
|
|
- Seems like the recent problems are more "observation-oriented", which means, there are more steps you need to reduce the given problem to something easily solvable.
- For the easy, I thought the fact you can always divide and then shift pretty much nails the problem, but it wasn't. I should have stopped when "divide all and then shift" doesn't give a solution, since my assumption of always divide as much as possible didn't prove to be right. If so, I could have discovered the corner case where N was a prime.... meh
- For the medium, you have to see that no carry can happen. Seems like this came instantly to many of the competitors. If this is done the problem is easy as hell.
source code (rewritten) ...
|
|
|
24 Jun 2011
|
- 아침에 식욕이 영 없어서 빵하나 먹고 있다가, 오후 좀 늦게 점심으로 피자 먹었다. 루말나티 씬크러스트! 맛있어 맛있어. 그리고 저녁은 늦게 집에서 전 먹었다.
- 근데 요즘은 한국 피자가 먹고 싶다. 여기서 도미노나 파파존스는 완전 구린뎅.. 흑흑.. 뉴욕스타일 몇개 시켜먹어봤는데 다 구리고.. ㅜㅜ
- 원고는 30챕터 최단경로 알고리즘.. 드래프트 다듬기 시작. 존슨 알고리즘은 지우고. 다익스트라 증명 재구성하느라 대부분의 시간을 보냈다. 일단 다익스트라 부분 1st iteration 은 끝냄.
- 김선생님이랑 저녁에 가슴이랑 삼두 운동 하고..
- SRM509 연습하고 좆망하고.. -_-;;; 나 R3은 갈수있을까....
- Edward Tufte가 시카고에 1-day course하러 온대서.. 들어볼까 고민 중인데, 너무 비싸다. orz 책 네권을 다 준다지만 그래도 $380 은 너무 비싸 엉엉;;; 학생할인 하면 할만할거 같은데 주변에 누구 풀타임 학생 명의 도용을 해야 하나. -_-
- 운동2 연습3 원고9
|
|
|
23 Jun 2011
|
- 밑반찬이랑 미역국으로 아점 먹었는데, 양이 영 부족해서 간식-_-으로 비빔면 먹었다. 하하 저녁은.. 아무 생각 없이 삼겹살을 굽기 시작하고 양파도 채썬김에 가쯔오부시 국물이랑 간장으로 양념하고 계란 넣어서 삼겹살돈부리! 였으나... 밥이 너무 많아서 시망.. orz
- SRM510 연습 잠깐 하고.. 뭐.. 원고. -.-
- 원고는 11챕터/12챕터 RC 릴리즈. 11.2랑 11.3 합치는 작업이 컸고, 도입부 다시 쓰고.. 그 정도. 12챕터는 하나도 안 고쳤다. ㅡ,.ㅡ
- 치즈인더트랩 을 우연히 보기 시작해서 정주행했는데 꽤 재밌었다. 참 단순한 대학 생활을 했던 본인으로써는 으음... 공감은 전혀 안되고 뭐 얼불노도 아니고 환타지 보는 기분으로 봤다고나 할까.. -_-;;; 좀 카레카노 같은 느낌도 있고.
- 연습3 원고10
|
|
|
|
아주 오랜만의 연습 로그로군. 완전 처참했던 셋이란걸 알고 시작해서 더 신중하게 했다. 250은 생각보다 쉬운 문제였는데 시간 날려서 아쉽고, 500은 디버그하다가 버그 두개 잡아서 리섭밋 -_-;; 그래서 맞긴했다;;;;;
(more)
|
|
|
22 Jun 2011
|
- 음 이거 지난주 주간리뷰도 안썼네 지금 쓰다보니 -_- 이러면 안되는데.. 으.. -_-
- 오늘도 챕터10 연습문제에 막혀서 의욕없어 하는 사이에 시간이 쌩하고 가버림 -_-;;
- 요즘 슬슬 산후조리랑 애기 키우는 거 공부하고 있다능.. 으음 >.<
- 이두랑 등운동.. 하는데 오늘 운동 시작이 늦어서 허리랑 복근은 스킵. ㅋ
- 아점으로 콩나물밥 먹고, 저녁에는 두부조림해서 미역국이랑 먹었다.
- 원고는 챕터10 연습문제 내놓고, 챕터11 리팩토링 개시. 도입부가 그래프 최단거리 전략이랑 챕터가 합쳐져 있던 시절에 쓴 물건이라 좀 부적절한 부분이 많았다. 과도한 일반화도 좀 있고. 그거 고치고.. 11.2랑 11.3 합치고.. 그러면 무난하지 않을까 생각한다. -.-
- 지난 TCO R1 하드를 포함배제로 어떻게 짜야 하나 졸라 고민했다. 나는 N개의 set 이 있을 때, 원소들을 포함관계로 파티션한 셋들을 iterate 하는 방법이 없나 고민했는데, 그냥 비싼 것부터 iterate 하면서 이전 것들과의 교집합 크기를 재면 된다. orz
- 연습3 원고7
|
|
|
|
- 음 -.- 어제 안쓰고 잤네 뭐했더라;; 아침에 병원 가서 진료받고 (3주남았다!) 아씨 가서 산후조리 광고 전화주신분 뵙고 머리 자르고 밥 먹고 장보고 집에왔더니 4시.
- 김선생님이 부르셔서 운동. 지난주에도 하체운동하고 죽을뻔해서 어제는 살살했다. 공포의 덤벨런지 ㅜ.ㅜ
- 그리고 Friends Sushi 가서 저녁 먹고, 집으로 돌아와서 수다떨다가, 보은이네는 가고 나는 원고.. 를 하려그랬으나 그리디 챕터 마지막 연습문제가 너무 짜증나는거지!! 결국에 덱스터 보기 시작해서 시즌1 세편 내리 보고 잠들음. orz
- 원고3 망했어요
|
|
|
20 Jun 2011
|
- 점심엔 전에 재워뒀던 제육볶음 먹고, 저녁에는 김치볶음밥 해먹었다.
- 그냥 별로 한거 없는데 시간이 훅훅가네 ㅡ,.ㅡ 낮잠도 좀 자고.. 대청소도 좀 하고.. 원고도 조금 하고 (근데 그리디 챕터 마지막 연습문제에 막혀서.. ToT 내가 왜 이렇게 어려운걸 내기로 했을까...)
- 원고7
|
|
|
19 Jun 2011
|
- 아침에 일어나서 작년 R1 연습으로 돈 다음 TCO R1.. 이지 레코드 내고 (<- 챌페일) 미듐 삽질하다 못풀고 (망) 하드 간신히 맞아서 4x0 등으로 어드밴스.. 그래도 하드 풀었는데 이 등수는 뭐냐. 절망했다!
- 그거 끝나고.. 절망해서 미듐 소스코드 이것저것 보면서 이렇게 저렇게 구현해봄. 그리고 수열이가 나가고 싶대서.. 나가서 Chick-a-Fila 가서 저녁 먹고 (맛있었다. 근데 사람 많아서 정신 없음) 미시건 산책하다가 급 영화.
- Super 8 봤는데 마지막까지 Super 8 이 뭔진 몰랐고 나중에 위키피디아에서 찾아봤다. 별 기대 안하고 본 영화였는데.. 이게 스릴러인지 애들 연애물인지 뭔지.. -_-;;; 나름 재밌긴 했는데.. 하하. 다코타 패닝 동생 이쁘더라. 쟤가 13살이라고? -_-
- 집에 와서 챕터10 RC 만들기. 길지 않아서 금방 할 수 있을 듯. i++ 등의 후위연산을 전위연산으로 고치는 작업 하고.. 그다음엔 자잘한 리뷰들.
- 아졸려
- 연습7 TCO3 원고4 = 14
|
|
|
|
미듐 결국 못풀고.. -_- 반성하는 마음으로 상위권 랭커들의 코드를 보면서 에디토리얼을 써 봅니다.
(more)
|
|
|
|
For search: Min cost max flow. Min-cost max flow.
Alright I finally wrote a MCMF library after all these years.
- Version 1: Uses repeat-until-not-updated Dijkstra. Push unit amount per augmenting path
- Version 2: Use priority queue, but still repeat until updated
- Version 3: Use adjacent list instead, push max amount of flow per augmenting path
- Version 4: Use potentials to ensure all edge weights are nonnegative
Runtime for some random data: Version 1 (89s) Version 2 (12s) Version 3 (3.2s) Version 4 (3s)
I don't know whether the big jump in speed (12 to 3) comes from adjacent list or pushing multiple units at once. I'm suspecting pushing multiple units.
Tested on: TCO10 R1 Hard. SRM506 Medium. UVA10594 Data Flow.
lang:cpp
// ASSUMPTIONS:
// no more than one edge between two vertices
// small number of vertices
const int INF = 987654321;
struct MCMF1 {
int V, totalFlow, totalCost;
vector<vector<int> > cap, cost, flow;
MCMF1(int n): V(n), totalFlow(0), totalCost(0) {
cap = cost = flow = vector<vector<int> >(n, vector<int>(n));
}
void setEdge(int u, int v, int cap, int cost) {
this->cap[u][v] = cap;
this->cost[u][v] = cost;
}
int improve(int s, int t) {
vector<int> distance(V, INF);
vector<int> parent(V, -1);
parent[s] = s;
distance[s] = 0;
bool changed = true;
while(changed) {
changed = false;
for(int u = 0; u < V; u++)
if(distance[u] < INF)
for(int v = 0; v < V; v++) {
int cand;
if(flow[v][u] > 0)
cand = distance[u] - cost[v][u];
else if(cap[u][v] > flow[u][v])
cand = distance[u] + cost[u][v];
else
continue;
if(cand < distance[v]) {
distance[v] = cand;
parent[v] = u;
changed = true;
}
}
}
if(distance[t] < INF) {
int here = t;
while(here != s) {
int there = parent[here];
flow[there][here]++;
flow[here][there]--;
here = there;
}
totalFlow++;
totalCost += distance[t];
}
return distance[t];
}
};
improvements ...
|
|
(0)
