Monday, November 4, 2013

Tuesday, October 29, 2013

ACM ICPC 2010 Daejeon Regional - H Installations

Problem Link

우선, 먼저 알 수 있는 사실은 다음 2가지이다.
1) 모든 작업이 끝나기 위해서는 Sum(s1, s2, ... , sn)의 시간이 필요하다.
2) 시간이 t가 흘렀고, 마치지 못한 작업의 마감 시간이 di, dj일 때(t > di, t > dj), di < dj라고 가정을 한다면, di를 먼저하고 dj를 하는 것이 항상 이득이다.
i) i 다음에 j를 할 경우 : (t+si-di) + (t+si+sj-dj) = 2t + 2si + dj - (di+dj)
ii) j 다음에 i를 할 경우 : (t+sj-dj) + (t+sj+si-dj) = 2t + si + 2dj - (di+dj)
따라서 i)의 결과가 ii)의 결과보다 작게 되므로 dk(1<=k<=n)를 시간순으로 정렬한 다음에 작업들을 순차적으로 처리하면 됨을 알 수 있다.

여기서 d(t, i)를 시간 t에 대해서 i번 작업까지 수행했을 때, 최소 비용( minimmum sum of the penalties of the jobs with the two largest penalties)으로 테이블을 정의하여 dynamic programming을 떠올렸었다. 그러면 시간복잡도는 O(T*N)이라서 시간 안에는 충분히 나올 것 같았다. 그런데 생각을 더 하다보니 이 문제의 핵심은 2개의 작업에 대해서만 패널티의 합을 최소화하면 된다는 것이다.

n개의 작업들을 d를 기준으로 오름차순 정렬하였을 때, 일들을 순차적으로 처리해 나가다가 생겨나는 패널티의 최댓값(M1)과 그 다음 최댓값(M2)이 답이 아닐까 생각해보았다. 하지만 이 방법은 첫번째 예제에서부터 틀렸음을 알 수 있다. 위에서 보였던 '2)'는 di와 dj를 비교할 때, i 다음에 곧바로 j를 수행함으로써 성립하는 사실이기 때문이다. 따라서 답이 되는 M1과 M2가 인접하여 생겨나지 않을 경우가 반례인 것이다.

위의 방법으로 나온 M1과 M2가 생성된 위치 중 가장 나중의 위치를 p라고 하자. 지금까지 구한 해보다 더 좋은 해는 p 이하인 지점에서 생성됨을 알 수 있는데 이는 증명을 생략한다.(이 부분 때문에 d가 같다면 s가 내림차순으로 정렬되어야한다.) 1~p번째 작업에 대해서 i번째(1<=i<=p) 작업을 가장 나중에 했을 때, 위의 방법과 마찬가지로 M1과 M2를 구해서 더 좋은 답이 있는지만 검사해주면 되겠다고 생각했고 이 방법으로 AC를 받았다.

명우와 연습을 할 때, 실제 대회와 같은 긴장감 속에서 연습을해서 패널티가 중요했기 때문에 손으로 몇 가지 경우를 해보다가 위의 방법이 반례가 없길래 시도해보았다. 아직 엄밀하게 이 방법을 증명하진 못했지만, 2개의 작업에 대해서만 패널티의 합을 최소화하는 것이라서 가능한 것 같다. 시간복잡도는 O(N^2)이다.

2010년 리저널을 연습할 때, 명우와 2명이서  2시간 30분 동안 긴장감있게 연습하였는데 2시간 동안 7문제를 풀었다. 나머지 3문제는 좀처럼 해결될 기미가 잘 보이지 않았다. 두호형을 포함해서 3명이 같이 했었다면 남은 3시간 동안 1~2문제는 더 풀었을 것 같다. 대회 당시 1등팀이 2시간 반만에 10문제를 모두 해결하였음을 고려하면(2등팀이 8문제이긴 하지만) 아직은  뒷심이 부족하다고 생각된다.

소스 코드 : http://ideone.com/CrKv8U

Sunday, September 22, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 7


이번에는 명우랑 역할분담이 잘되어서 릴레이 식으로 잘 푼 것 같다ㅎㅎ

Link : http://www.acmicpc.net/contest/view/14

A. 삼각 그래프 - Accepted
위상정렬 + dp이지만 그래프 특성상 위상정렬을 별도로 할 필요없음.

B. 피파 월드컵 - Accepted
2^x꼴로 만들어주면 된다.

C. 아즈텍 피라미드 - Accepted
계차수열임을 알면 쉽게 풀 수 있다.

D. 나이트 이야기 - Later Solved
그리디하게 100*100 안으로 넣은 다음에 bfs를 통해 구한 값을 이용해서 나이트의 최소 이동 횟수를 알 수 있다. 그 다음에는 bitmask dp를 통해서 풀면 됨. 종료 3분 후, Accepted 받음.

E. 정규형 - Accepted
명우가 혼자 풀었는데 특별히 어렵지는 않은 문제인 것 같다.

F. 월드 오브 큐브 - Not Solved
문제 보고 어려운 것 같아서 안 품.

G. 최대 공통 증가 수열 - Accepted
"D[n][m] : S가 1~n까지, A가 1~m까지일 때의 최대 길이"라고 정의하고 dp로 풀면된다.
O(N^3)을 떠올리기 쉽지만, 전처리를 통해서 O(N^2)으로 풀 수 있다.

H. 병원 - Accepted
문제 이해하기가 힘든 문제. O(VE)에 명우가 품.

I. 사탕 줍기 대회 - Accepted
어떤 k번째 행에서 i번째를 선택하면 i-1번째와 i+1번째를 선택하지 못하는 경우의 최대합을 구하는 함수를 dp(k)라 하자. 모든 행에 대해서 dp(k)를 수행하고 그 값들로 새로운 행을 만들어서 다시 dp(k)를 수행하면 된다.

J. 거의 최단 경로 - Accepted
별로 어렵지 않은 문제. 명우가 품.

Saturday, September 21, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 6


이번엔 myungwoo랑 팀플을 해봤는데..
앞/뒤로 나눠서 한 명은 코딩하고 다른 한 명은 생각하는 건 비효율적이고 안 좋다는 걸 깨달음.

Link : http://www.acmicpc.net/contest/view/13

A. 쌍둥이 역설 - Accepted
그냥 식에 대입해서 풀면 됨.

B. 두 교수 - Solved Later
1번 교수와 2번 교수가 싫어하는 특수한 조건을 제외하고 문제를 푼 뒤(그리디), 1번 교수와 2번 교수가 같은 강의실을 사용할 경우 답에 +1을 해줌. 그리고 답이 2보다 작다면 2로 갱신해주어야함.

C. YAPTCHA - Accepted
각 항의 값이 0 또는 1이 됨을 알면 규칙을 찾아서 쉽게 소수 찾는 알고리즘으로 풀 수 있음.

D. 팀의 난이도 - Accepted
이분매칭 + 멕시멈 플로우

E. 풍선 - Solved Later
거리 차의 절댓값을 기준으로 오름차순으로 정렬한 후, 차례로 보면서 A에 가까우면 A에 몰아주고 B에 가까우면 B에 몰아줌. 풍선의 개수가 부족하면 다른 풍선을 써주면됨.

F. 자물쇠와 열쇠
그리디하게 재귀적으로 풀면되는데 열쇠를 하나만 들고 다닐 수 있음에 유의.

G. 힙 세기 - Solved Later
답이 (n-1)! / (2~n번 노드들의 서브 트리의 개수들의 곱) 임을 알면 소인수 분해를 통해서 답을 구할 수 있다.

H. 스도미노쿠 - Accepted
백트랙킹

I. 전구 게임
문제도 안 읽어봄.

J. 전기 요금 - Accepted
간단하게 하라는 대로 풀면 되는 문제.

Thursday, September 19, 2013

ACM ICPC 2009 Greater New York Regional

A. Simple sorting O(N log N)

B. Greedy O(N^2)
The value of a divided subset has to be bigger than a element.
If you decide a value, you can check the fact that it is possible or not.

C. Dynamic Programming
D(i, j) : minimum value in total 'j' stairs, having 'i' balls.
D(i, j) = min( D(i-1, j), max(1+D(i-1,k-1), 1+D(i, j - k) )

D. Stack or Heap O(N) or O(N log N)

E. STL next_permutation()

F. Dynamic Programming
D(i, j, k) : The number of ways in length 'i', adjecent bit are 'j', situation 'k'(number in 'i'th)
D(i, j, 0) = D(i-1, j, 0) + D(i-1, j, 1)
D(i, j, 1) = D(i-1, j-1, 1) + D(i-1, j, 0)
the answer is D(n, m, 0) + D(n, m, 1)

G. Graham Scan

H. Graham Scan & Mathematics

I. BFS with bitmask

Tuesday, September 17, 2013

Google Codejam 2008 Round 3 - C ( = acmicpc.net 1014)

Link : http://www.acmicpc.net/problem/1014
Link : http://code.google.com/codejam/contest/32002/dashboard#s=p2 (Problem C : No Cheating)

1) Small case(n, m <= 10)
Bitmask Dynamic Programming : O(N^2*(2^(2*N)))
But actual time complexity is much smaller because of the impossible situations.

2) Large case(n,m <= 80)
Bipartite matching , Maximum Flow

#include <iostream>
#include <memory.h>
#include <string>
using namespace std;
int C, N, M;
string bd[100];
int nbx[100][100], nby[100][100], v[100][100];
int T=0;
bool dfs(int a, int b) {
 if (a<0) return true;
 if(v[a][b]==T) return false;
 v[a][b]=T;
 for (int i=a-1;i<=a+1;i++) {
  for (int j=b-1;j<=b+1;j+=2) {
   if (i>=0 && i<M && j>=0 && j<N && bd[i][j]=='.') {
    if (dfs(nbx[i][j], nby[i][j])) {
     nbx[i][j]=a; nby[i][j]=b;
     nbx[a][b]=i; nby[a][b]=j;
     return true;
    }
   }
  }
 }
 return false;
}
int play() {
 memset(nbx,-1,sizeof(nbx));
 memset(nby,-1,sizeof(nby));
 memset(v, -1, sizeof(v)); T=-1;
 int rst=0;
 for(int i=0;i<M;i++) for(int j=0;j<N;j++) {
  if (bd[i][j]=='.') {
   rst++;
   if (j%2) {
    T++;
    if (dfs(i,j)) rst--;
   }
  }
 }
 return rst;
}
int main() {
 cin>>C;
 for (int i=1; i<=C; i++) {
  cin>>M>>N;
  for (int r=0;r<M;r++) cin>>bd[r];
  cout<<play()<<endl;
 }
 return 0;
}

Sunday, September 15, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 5


Link : http://www.acmicpc.net/contest/view/11

A. 콘센트 - Accepted
Greedy. Note that if n and m is 0, the answer is 1

B. K번째 숫자 - Accepted
Segment tree, Merge Sort or Binary search

C. 포켓볼 - Accepted
Easy to solve with STL Map or Set.

D. 토너먼트 조작 - Accepted
Given n = (2^k) teams, and a team 1 such that for every team t that 1 cannot beat, 1 can beat a team t` that can beat t and 1 can beat as least half of the teams.
For every round (k in total) of the tournament
1) Match as many teams t that beat 1 to teams t` that can win them.
2) Let 1 play against a team from which it can win.
3) Let any remaining teams play against each other.
4) Remove the losers.

E. 책 쌓기 - Accepted
Pulling out a book in the sorted top is never useful, so always pull out the first non-sorted book
To move a big book from the top to position i, takes ( 2 ^ i )−1 steps.
Through the fact, we can solve this in O(N).

F. RFID 추적
Not solved yet.

G. L퍼즐
2 - SAT. Make connections for 'B'  with 4 directions and 'W' with all of  'B'.

H. 열차 지연 - Accepted
1) Dijkstra with heap or priority queue or 2) Bellman-Ford Algorithm.
D[x][t] = when the time is 't', the minimum cost of station 'x'.

I. 수영장 만들기
Not solved yet.

J. 정수 직사각형 - Accepted
Preprocess - sorting and counting

Saturday, September 7, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 2


Link : https://www.acmicpc.net/contest/scoreboard/7

A. RNG - Accepted
Change the form of the equation
y = a(x^2)+bx+c mod (2^n)  into  a(x^2)+bx+c`=0 mod (2^n)
if x is a solution for n, (x mod 2^(n-1)) is a solution for n-1
So, if x is an unique solution for n-1
1) x is possible solution for n
2) x + 2^(n-1) is possible solution for n
Maintaining solutions for increasing n
1) if solution is unique, continue.
2) else we can't get the unique solution.

B. 나쁜과학자
Minimum vertex cover

C. 큐빙
I didn't read the problem because the cube makes me tired.

D. 차원 워프 드라이브
I didn't read the problem.

E. 아! - Accepted
Simple strings' length comparison.

F. 도어맨 - Accepted
Greedy method.

G. 전화번호 목록 - Accepted
Ordinary Trie problem.
http://en.wikipedia.org/wiki/Trie

H. 무글 맵스 - Accepted
Dynamic programming. d[i][j] = min(d[k][j-1] + s[k][i])

I. 대충 정렬
I didn't read the problem.

J. 연결
It might be solved with Minimum Cost-Maximum Flow(MCMF)
Similar problem : http://poj.org/problem?id=2195

Friday, August 30, 2013

COCI 2012/2013 #1 ~ #6

Croatian Open Competition in Informatics Contest #1 ~ #6

#1
1. http://www.acmicpc.net/problem/2789 : Simply delete some letters.
5. http://www.acmicpc.net/problem/2793
strength(A) + strength(A+1) + ... + strength(B) = strength(B)-strength(A-1)
According to the description, N is divisible A-1, A-2, ... , 1
Lcm( x1, x2, x3, x4, ... ) =  Lcm( ... Lcm ( Lcm ( Lcm( x1, x2 ) , x3), x4 ), ...)
A<B<10^17. So we can guess xn would be small.

#2
1. http://www.acmicpc.net/problem/2783 : Easy
2. http://www.acmicpc.net/problem/2784 : Easy
4. http://www.acmicpc.net/problem/2786
Sort the prices by B(i)
As we calculate ith minimum cost, we consider two cases.
1)  k which is min(A(k)) is in [1, i]
2)  k is not in [1, i]
We can get the minimum cost by accumulating smaller A(i) from the back.
ith minimum cost = min( Sum of B(1 ~ i-1) + min(A(j)) , Sum of B(1 ~ i) + min(A(k)-B(k)) )
for  j >= i, 1 <= k <= i .

#3
1. http://www.acmicpc.net/problem/3076 : Easy

#4
1. http://www.acmicpc.net/problem/3985 : Easy
3. http://www.acmicpc.net/problem/3987
BFS. care about changing of direction.
4. http://www.acmicpc.net/problem/3988
Minimum distance can be exist on the adjacent numbers.
Maximum distance is the difference betweein the smallest and the largest.
So  1) sort the numbers 2) choose N-K numbers from the beginning. 3) Add and delete one by one with heap or priority queue.

#5
4. http://www.acmicpc.net/problem/5214
BFS. The point is that we don't have to visit the hurb which has been visited.

#6
2. http://www.acmicpc.net/problem/5623 : Easy
3. http://www.acmicpc.net/problem/5624 : O(N^2)
5. http://www.acmicpc.net/problem/5626
Dynamic Programming.
From left to right, calculate the ways like pascal triangle.
d(i, j) = d(i-1, j-1) + d(i-1, j) + d(i-1, j+1)

Thursday, August 29, 2013

Asia Regional Contest 2012 in Tokyo A

http://www.acmicpc.net/problem/3825

<Description>
은행수란 정수 m과 n의 쌍 (m,n)이다. 예를 들어, (1,1), (-2,1), (-3,-1)은 은행수이다.
은행수의 곱셈 (m,n) · (x,y) = (mx - ny, my + nx) 이다. 예를 들어, (1,1)·(-2,1) = (-3,-1)이다.
이 때, (m,n) · (x,y) = (p,q)를 만족하는 은행수 (x,y)가 존재한다면, (m,n)은 은행수 (p,q)의 약수라고 한다. 모든 (1,0), (0,1), (-1,0), (0,-1), (m,n), (-n,m), (-m,-n), (n,-m)은 임의의 은행수 (m,n)의 약수이다. 만약, m2 + n2 > 1이라면, 앞의 8개 수는 모두 다를 것이다. 즉, m2 + n2 > 1을 만족하는 은행수는 적어도 8개의 약수가 있다. 만약, m2 + n2 > 1을 만족하는 은행수 (m,n)의 약수가 8개라면, 이 수를 소수라고 한다.
은행수가 주어졌을 때, 소수인지 아닌지 알아내는 문제이다.
---------------------------------------------------------------------------------------------------------------
문제를 처음 접하게 되면 생소한 정의에 낯설게 느껴지는데 input data limit를 보고 희망을 가지게 된다. 1 < m2 + n2 < 20000.
 
문제의 정의에 의해 (m,n) · (x,y) = (p,q)라면, (m2 + n2)(x2 + y2) = p2 + q2 가 된다는 것까지는 쉽게 알 수 있지만 별 의미가 없다.  m2 + n2 > 0인 경우에  m2 + n2이 mp + nq와 mq - np의 공약수라면 (m,n)은 (p,q)의 약수이고, 그 역도 성립한다는 사실 하나만으로도 이 문제는 쉽게 풀린다.
그런데 저 정리를 증명을 못했는데 고민해 볼 만한 것 같다.

Application of stack to some problems

http://www.acmicpc.net/problem/6549
: i번째에서 왼쪽과 오른쪽으로 둘 다 넓혀나갈 수 있음에 주의

http://www.acmicpc.net/problem/2104
: Indexed tree로 O(n log n)에 푸는 걸 떠올리는 게 더 쉬움

Knuth-Morris-Pratt Algortihm

String Matching : http://www.acmicpc.net/problem/1786

Pi[i] : 1부터 i번째까지의 부분 문자열에서 1 ~ k와 (i-k+1) ~ i까지가 같은 k값들 중 최댓값

#include <stdio.h>
#include <string.h>
#define MN 1000005
char T[MN], P[MN];
int pi[MN], sol[MN], sn, n, m;
int main() {
    int i, j, p;
    gets(T+1); n = strlen(T+1);
    gets(P+1); m = strlen(P+1);
 
    pi[0] = -1;
    pi[1] = 0;
    for (i = 2; i <= m; i++) {
        p = i-1;
        while (P[pi[p]+1] != P[i] && p >= 1) {
            p = pi[p];
            if (p <= 0)
                break;
        }
        pi[i] = pi[p]+1;
    }
    pi[0] = 0;
    j = 1;
    for (i = 1; i <= n; i++) {
        if (T[i] != P[j]) {
            p = pi[j-1];
            j = p+1;
            if (j == 1 && T[i] != P[j]) i++;
            i--;
        } else j++;
        if (j == m+1) {
            sol[++sn] = i-m+1;
            j = pi[j-1]+1;
        }
    }
    printf("%d\n",sn);
    for (i = 1; i <= sn; i++) printf("%d\n",sol[i]);
    return 0;
}
 
 
Pi 를 응용해서 푸는 문제 : http://www.acmicpc.net/problem/1787

Fenwick tree range updates

From : http://petr-mitrichev.blogspot.kr/2013/05/fenwick-tree-range-updates.html

A Fenwick tree is a wonderful data structure that supports two operations on an array: increment a given value by a given amount, and find the sum of a segment of values, both in O(log n) time. What's more, the Fenwick tree is represented as just an array of the same size as the array being updated and queried, and we don't need to store the original array itself! In other words, we can support the above operations without any additional memory. Yesterday I've discovered that it's capable of even more!

For a start, here is the entire code for a Fenwick tree:

private void update(int at, int by) {
    while (at < data.length) {
        data[at] += by;
        at |= (at + 1);
    }
}

private int query(int at) {
    int res = 0;
    while (at >= 0) {
        res += data[at];
        at = (at & (at + 1)) - 1;
    }
    return res;
}

Here, query(at) returns the sum of all elements from the first element to at-th element. Finding a sum of arbitrary segment can be done via query(right)-query(left-1). You can find more details using your favorite search engine.

The standard Fenwick tree only supports updating one element at a time. However, it is quite natural to expect it to handle range updates, too - the update command now becomes "increment each value between left-th and right-th by the given amount". It turns out that we can modify the tree to handle such updates in O(log n) time, too! Here's how (warning, code untested - but I hope it works):

private void update(int left, int right, int by) {
    internalUpdate(left, by, -by * (left - 1));
    internalUpdate(right, -by, by * right);
}

private void internalUpdate(int at, int mul, int add) {
    while (at < dataMul.length) {
        dataMul[at] += mul;
        dataAdd[at] += add;
        at |= (at + 1);
    }
}

private int query(int at) {
    int mul = 0;
    int add = 0;
    int start = at;
    while (at >= 0) {
        mul += dataMul[at];
        add += dataAdd[at];
        at = (at & (at + 1)) - 1;
    }
    return mul * start + add;
}

In other words, we implement a Fenwick tree with range updates via a normal (point-update) Fenwick tree that stores linear functions instead of just values. Is this a well-known trick?