Algorithm problems: 2014

Sunday 3 August 2014

Длина объединения отрезков

На прямой заданы отрезки координатами левого и правого конца. Необходимо найти длину их объединения. Поместим все координаты в отдельный массив, при этом левому концу сопоставим -1, а правому +1. Все прямая разобъется на подотрезки, внутри которых нет других точек. Для каждого такого отрезка нужно определить надо ли добавлять его длину в общую сумму. Легко заметить что если количество левых концов слева от данной области равно количеству правых, то эта область не покрыта ни одним исходным отрезком, поэтому ее длину не надо добавлять. Для выяснения этого факта будем поддерживать переменную - баланс левых и правых концов.

template<typename T>
T segments_union(vector<pair<T, T>> s) {
    vector<pair<T, int> > v;
    for (int i = 0; i < sz(s); ++i) {
        v.pb(mp(s[i].first, -1));
        v.pb(mp(s[i].second, 1));
    }
    sort(all(v));
    T res = 0;
    for (int i = 0, sum = 0; i < sz(v); ++i) {
        if (sum) {
            res += v[i].first - v[i - 1].first;
        }
        sum += v[i].second;
    }
    return res;
}

Monday 21 July 2014

Дерево отрезков с одиночной модификацией

Данная структура используется для быстрого поиска суммы, минимумма, максимума на диапозоне массива, в ситуациях когда предполагается изменение элемента массива по определенному индексу. Операция запроса и изменения имеют логарифмическую сложность от количества элементов в массиве.

#define OP(x, y) ((x) + (y))
#define NEUTRAL (0)

struct SegmentTree
{
    vi q;
    int n;
    SegmentTree(int size = 0) {
        while (size & (size - 1)) ++size;  // it is not required
        n = size;
        q = vi(2 * n, NEUTRAL);
    }
    void clear() {
        fill(all(q), NEUTRAL);
    }

    void set(int p, int val) {
        for (p += n; p; p >>= 1) {
            q[p] = OP(q[p], val);
        }
    }
    
    int get(int lo, int hi) {
        int res = 0;
        for (lo += n, hi += n; lo <= hi; ++lo >>= 1, --hi >>= 1) {
            if ((lo & 1) == 1) res = OP(res, q[lo]);
            if ((hi & 1) == 0) res = OP(res, q[hi]);
        }
        return res;
    }
};

Thursday 19 June 2014

Поиск максимального потока в неориентированном графе

int N, Source, Dest;
vector<vi> C;
vi Use;

void addEdge(int u, int v, int w) {
    C[u][v] += w;
    C[v][u] += w;
}

int augment(int u, int val) {
    if (u == Dest) return val;
    Use[u] = true;
    for (int v = 0; v < N; ++v) {
        if (Use[v]) continue;
        if (C[u][v] <= 0) continue;
        int r = augment(v, min(val, C[u][v]));
        if (r > 0) {
            C[u][v] -= r;
            C[v][u] +=r;
            return r;
        }
    }
    return 0;
}

int maxFlow() {
    int flow = 0;
    Use = vi(N, 0);
    while (true) {
        fill(all(Use), false);
        int f = augment(Source, 1 << 30);
        if (f == 0) break;
        flow += f;
    }
    return flow;
}

Monday 26 May 2014

Рюкзак и его разновидности

Рассмотрим следующую задачу. Имеется некоторое количество предметов обладающих весом и стоимостью. Нужно сделать из них выборку, так чтобы сумма не превышала некоторого порогового значения а суммарная стоимость была максимальна (минимальна). Различают следующие основные разновидности этой задачи:

0-1 knapsaсk - каждый предмет мы можем брать не более одного раза
unbounded knapsack - можно взять неограниченное количество каждого предмета
bounded knapsack - максимальное количество каждого предмета ограниченно сверху

Данную задачу можно решить с помощью динамического программирования. Для решения всех трех поздачач используются двухмерная таблица. Элемента таблицы в i-ой строке и j-ом столбце это максимальная сумма которую можно набрать используя первые i предметов так чтобы суммарные вес предметов в наборе был равен j.

0-1 Knapsack

Для решения нам необязательно хранить всю таблицу. Достаточно хранить текущую строку и обновлять ее для каждого нового предмета. При добавлении нового предмета для каждого веса от 0 до W мы можем либо использовать этот предмет, либо обойтись только предыдущими в зависимости от полученной стоимости. Веса нужно просматривать в порядке убывания чтобы при просмотре сохраненного значения с меньшим весом мы использовали значение без учета нового предмета.

vector<int> O1_knapsack(vector<Item> &A, int W)
{
    int n = sz(A);
    vector<int> dp = vector<int>(W + 1, -INF);
    dp[0] = 0;
    for (int k = 1; k <= n; ++k) {
        int wk = A[k - 1].w; // вес
        int ck = A[k - 1].c; // стоимость
        for (int w = W; w >= wk; --w) {
            if (dp[w - wk] != -INF) {
                dp[w] = max(dp[w], dp[w - wk] + ck);
            }
        }
    }
    return dp;
}

Unbounded knapsack

Задача решается аналогично предыдущей с тем лишь исключением, что теперь веса просматриваются в порядке возрастания, т.к. количество предметов каждого типа неограниченно и обращаясь к меньшему весу мы получаем значение, которое теоретическу уже может включать в себя текущий предмет.

vector<int> unbounded_knapsack(vector<Item> &A, int W)
{
    int n = sz(A);
    vector<int> dp = vector<int>(W + 1, -INF);
    dp[0] = 0;
    for (int k = 1; k <= n; ++k) {
        int wk = A[k - 1].w; // вес
        int ck = A[k - 1].c; // стоимость
        for (int w = wk; w <= W; ++w) {
            if (dp[w - wk] != -INF) {
                dp[w] = max(dp[w], dp[w - wk] + ck);
            }
        }
    }
    return dp;
}

Bounded knapsack

Данную задачу можно свести к 0-1 knapsack добавив необходимое количество копий каждого предмета. Однако это существенно увеличивает сложность при больших значениях ограничений на количество предмета - O(NWU), где U - максимум среди ограничений. Можно улучшить эту оценку до O(NWlogU) добавив для каждого предмета веса по степеням двойки. Это даст возможность набрать любой вес от 0 до Wk*Uk. При этом количество весов будет log(Uk). Например если у нас есть Wk=1 и Uk=20 то мы получим веса 1,2,4,8,5 и это даст нам возможность представить любой вес от 1 до 20.

Однако, существует способ решить эту задачу как и предыдущие рассмотренные за время O(NW). Заметим, что

dp[k][w] это минимум среди:

dp[k - 1][w - 0 * wk] + 0 * ck

dp[k - 1][w - 1 * wk] + 1 * ck

dp[k - 1][w - 2 * wk] + 2 * ck

....

dp[k - 1][w - uk * wk] + uk * ck

Мы можем разбить все веса от 0 до W на группы по остатку от деления веса на wk и в пределах каждой группы мы должны быстро считать максимум в окне из (uk + 1) элементов из массива dp[k - 1] с некоторым добавочным значением.

Иными словами имеем следующую задачу. У нас есть массив A из N элементов, необходимо рассчитать максимум для каждого окна размера K, где элемент окна на позиции i равен A[shift+i] + X*i, где shift - смещение окна, X - некоторая константа. Задача поиска минимума в окне массива решается стандартно с использованием алгоритма поиска максимума в очереди. В данном случае необходима неболшая модификация. Добавим к i-ому элементу массива A величину i*X. Тогда, когда мы будем получать очередной максимум для окна со сдвигом shift мы будем получать максимум для элементов:

A[shift] + shift*X,

A[shift+1] + (shift+1)*X,

...

A[shift+K-1] + (shift+K-1)*X.

Т.е. чтобы получать интересующий нас максимум мы должны из полученного значения вычесть shift*X. Адаптировав это для решения поставленной задачи можно получить следующий код:

Queue q;
vector<int> bounded_knapsack(vector<Item> &A, int W)
{
    int n = sz(A);
    vector<vector<int>> dp = vector<vector<int>>(2, vector<int>(W + 1, INF));
    dp[0][0] = 0;
    int prev = 0, cur = 1;
    for (int k = 1; k <= n; ++k) {
        int wk = A[k - 1].w;  // вес
        int ck = A[k - 1].c;  // стоимость
        int uk = A[k - 1].u;  // максимальное количество
        for (int sw = 0; sw < wk && sw <= W; ++sw) {
            q.clear();
            int cum = 0;
            for (int w = sw; w <= W; w += wk, cum += ck) {
                if (dp[prev][w] == INF) {
                    q.push(INF);
                } else {
                    q.push(dp[prev][w] - cum);
                }
                while (q.size() > uk + 1) q.pop();
                dp[cur][w] = q.get();
                if (dp[cur][w] != INF) {
                    dp[cur][w] += cum;
                }
            }
        }
        swap(prev, cur);
    }
    return dp[prev];
}

Задачи:

Счастливая страна

Friday 23 May 2014

Определение минимального элемента в очереди за константное время

Структура данных очередь используется во многих алгоритмах. Помимо стандартных операций иногда существует необходимость в получении минимального (максимального) элемента за константное время. Поддержка такой статистики со стеком реализуется тривиально - вместе с добавленным элементом сохраняется минимум всех элементов на стеке (рассчитывается как минимум из добавленного элемента и значения минимума предыдущих значений на стеке). Этот подход адаптируется и для очереди. Как известно очередь можно реализовать с помощью двух стеков: стек для добавления элементов S1 и стек для изъятия элементов S2. Т.е. любое добавление в очередь добавляет элемент в S1, а любое изъятие проверяет стек S2 и если он пустой, то перекладывает все элементы из S1 в S2. После этого извлекает элемент с вершины стека S2. Т.о. реализовав очередь с помощью двух стеков с поддержкой минимального элемента, мы в любой момент можем получить минимум в очереди как минимум минимальных элементов стека S1 и S2.

#define ZERO (1LL<<60)
#define ADD(x, y) (min((x), (y)))

typedef pair<lint, lint> plii;
typedef long long lint;

const int MAX = 1000000 + 10;

struct Queue {
    
    plii v1[MAX], v2[MAX];
    int n1, n2;
    
    Queue() {
        clear();
    }
    
    void push(lint x) {
        v1[n1] = mp(x, ADD(x, v1[n1 - 1].second));
        n1++;
    }
    
    void pop() {
        if (n2 == 1) {
            while (n1 > 1) {
                lint x = v1[--n1].first;
                v2[n2] = mp(x, ADD(x, v2[n2 - 1].second));
                n2++;
            }
        }
        n2--;
    }
    
    lint get() {
        return ADD(v1[n1 - 1].second, v2[n2 - 1].second);
    }
    
    int size() {
        return n1 + n2 - 2;
    }
    
    void clear() {
        n1 = n2 = 0;
        v1[n1++] = mp(ZERO, ZERO);
        v2[n2++] = mp(ZERO, ZERO);
    }
};

Данная структура данных применяется в следующих задачах:
- рюкзак с ограничением количества элементов. Позволяет решить задачу за O(NW)
- поиск минимума во всевозможных диапозонах массива фиксированной длины (скользящее окно по массиву)

Topcoder - подключение плагина moj

Для того чтобы упростить себе жизнь в соревнованиях топкодер существует различные плагины.
Рассматриваемые в этом посте плагин moj умеет следующее:

генерировать скелет решения (класс и метод) и сохранять его в указанное место
включить в сгенерированный скелет необходимый prewritten код
генерировать по сэмплам из условия задачи код, необходимый для тестирования

1. Для начала качаем архив с необходимыми файлами по ссылке
2. После этого заходим в арену, выбираем Options->Editor->Add. В появившемся диалоге указываем:

Name: CodeProcessor
EntryPoint: codeprocessor.EntryPoint
ClassPath: нажимаем browse и выбираем все jar файлы из скаченного архива (moj.jar, CodeProcessor.jar, FileEdit.jar)

3. Нажимаем Configure и в поле Editor Entry Point пишем fileedit.EntryPoint и ниже добавляем строчку с содержимым moj.moj.
4. Снова нажимаем Configure для того чтобы задать настройки плагина. Здесь необходимо указать имя директории куда будут сохраняться сгенерированные файлы. Кроме того рекомендуется снять галочку Backup existing file then overwrite. Наконец, нужно вставить код шаблона для используемого языка программирования. Так, для C++ он может выглядеть следующим образом:

#include <iostream>
#include <sstream>
#include <cmath>
#include <string>
#include <string.h>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define sz(x) ((int)((x).size()))
#define rep(i, N) for (int i = 0; i < N; ++i)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();++it)
typedef long long lint;
typedef vector<string> vs;
typedef vector<int> vi;
typedef pair<int, int> pii;

class $CLASSNAME$ {
public:
 $RC$ $METHODNAME$( $METHODPARMS$ ) {
 }
};

$BEGINCUT$
$TESTCODE$ 

$DEFAULTMAIN$
$ENDCUT$

Wednesday 15 January 2014

Useful CouchDB tips

curl

HOST="http://127.0.0.1:5984"

1. Create database:

curl -u admin:admin -X PUT $HOST/db

{"ok":true}

2. Delete database

curl -u admin:admin -X DELETE $HOST/db

{"ok":true}

3. Create document

curl -X PUT $HOST/db/foo -d '{"count":1}'

{"ok":true,"id":"foo","rev":"1-74620ecf527d29daaab9c2b465fbce66"}

4. Update document

curl -X PUT $HOST/db-replica/foo -d '{"count":2, "_rev":"1-74620ecf527d29daaab9c2b465fbce66"}'


{"ok":true,"id":"foo","rev":"2-de0ea16f8621cbac506d23a0fbbde08a"}

5. Replication

curl -u admin:admin -H "Content-Type:application/json" -X POST $HOST/_replicate -d '{"source":"db", "target":"http://127.0.0.1:5984/db-replica"}'

{"ok":true,"session_id":"48d43591b4f145ae08a9207dcc586fe2","source_last_seq":1,"replication_id_version":3,"history":[{"session_id":"48d43591b4f145ae08a9207dcc586fe2","start_time":"Wed, 15 Jan 2014 09:59:42 GMT","end_time":"Wed, 15 Jan 2014 09:59:42 GMT","start_last_seq":0,"end_last_seq":1,"recorded_seq":1,"missing_checked":1,"missing_found":1,"docs_read":1,"docs_written":1,"doc_write_failures":0}]}

6. Changes

curl $HOST/_changes?feed=longpoll&amp;heartbeat=300000&amp;style=all_docs&amp;since=233

Views

1. View conflicts

function(doc) {
  if(doc._conflicts) {
    emit(doc._conflicts, null);
  }
}

Algorithm problems

SyntaxHighlighter