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?