USACO \2013\January\Gold\1 - "LINEUP_GOLD"

Farmer John's N cows (1 <= N <= 100,000) are lined up in a row.  Each cow is
identified by an integer "breed ID" in the range 0...1,000,000,000; the
breed ID of the ith cow in the lineup is B(i).  Multiple cows can share the
same breed ID.

FJ thinks that his line of cows will look much more impressive if there is
a large contiguous block of cows that all have the same breed ID.  In order
to create such a block, FJ chooses up to K breed IDs and removes from his
lineup all the cows having those IDs.  Please help FJ figure out
the length of the largest consecutive block of cows with the same breed ID
that he can create by doing this.

PROBLEM NAME: lineup

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K.

* Lines 2..1+N: Line i+1 contains the breed ID B(i).

SAMPLE INPUT (file lineup.in):

9 1
2
7
3
7
7
3
7
5
7

INPUT DETAILS:

There are 9 cows in the lineup, with breed IDs 2, 7, 3, 7, 7, 3, 7, 5, 7. 
FJ would like to remove up to 1 breed ID from this lineup.

OUTPUT FORMAT:

* Line 1: The largest size of a contiguous block of cows with
        identical breed IDs that FJ can create.

SAMPLE OUTPUT (file lineup.out):

4

OUTPUT DETAILS:

By removing all cows with breed ID 3, the lineup reduces to 2, 7, 7, 7, 7,
5, 7.  In this new lineup, there is a contiguous block of 4 cows with the
same breed ID (7).

SOLUTION:

Let's consider solution using sliding window algorithm. 

N <= 1e5, hence complexity of the algorithm should be approximately N*log(N).

At each iteration, we move the right pointer and must maintain the segment satisfying the conditions that there are less or equal K+1 types of ID. If the segment is correct, then we can simply delete the least groups of types in that interval and there will be all the same elements. Otherwise, we move the left pointer.
To do this we need to count the number of types somehow. The first idea is binary tree, right? We may use priority_queue or set, or just map. Let's use map.

So, what we have:

We have map<int,int> that can respond how many elements within current interval with some ID. 
We can figure out is the current segment is correct (if number of types <= K+1)
If the segment is correct - try to maximize the answer and keep going increasing right pointer
If the segment is not correct - just increment left pointer (move to the right)


The final algorithm looks as follows:


map<int,int> m;
int A[]; // input IDs
...
for (int i = 0, j = 0; i < n; i++)
{
   if (m[A[i]] == 0) types++;
   m[A[i]]++;
   for (; types > k+1; j++)
   {
       m[A[j]]--;
       if (m[A[j]] == 0)
       {
          types--;
       }
   }
   ans = max(ans, m[A[i]]);
}

Problem “Сonsumer” (Republican Programming Contest 2014, Day 1, Problem 3)

Split the set of numbers into subsets

 Разбить множество чисел на подмножества, разница сумм которых минимальна и вывести на экран эту разницу.
Для решения этой задачи будем использовать динамическое программирование.
Не сложно понять, что сумма каждого из двух выбранных множеств должна быть как можно "ближе" к половине суммы всего исходного множества т.е. если представить сумму всего исходного множества за C, а суммы двух выбранных подмножеств за A и B, то:
A + B = C;
A ~ C / 2
B ~ C / 2
И так, задача сводится к нахождению подмножества с суммой C/2.
Почитайте это

Перейдём к реализации.

Так как каждую вещь можно брать только один раз, то будем идти не слева направо, а справа налево.

Будем хранить 1 или 0, что значит можно ли достичь суммы M, если взять N предметов.

0 <= M <= C/2

Ответом будет ячейка таблицы отмеченная как 1 и с максимальной M (т.к. нам нужно взять набранную сумму как можно ближе к C/2)

#include <iostream> 
#include <vector> 
#include <cmath> 

#define REP(i,n) for (int i = 0; i < n; i++)

using namespace std;

bool f[100];
int main()
{
    int n;
    long sum = 0;
    cin >> n;
    vector<int> v(n);
    REP(i,n) cin >> v[i], sum += v[i];
    int m = sum/2;

    int w = 0;
    f[0] = 1;
    for (int i = n-1; i >= 0; i--)
    {
        for (int j = m; j >= 0; j--)
        {
            if (f[j] == 1)
            {
                f[j+v[i]] = 1;
            }
        }
    }
    for (int i=m;i>=0;i--) if (f[i]) {
        w=i;
        break;
    }
    cout << abs(w-(sum-w)) << endl;

    return 0;
}

Knapsack problem

Пусть имеется набор предметов, каждый из которых имеет два параметра — вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. (Wikipedia)

1. Когда каждый тип предмета можно брать неограниченное количество раз:

Рассмотрим следующую функцию. Пусть F(s, n) есть максимальная стоимости предметов, которые можно уложить в рюкзак максимальной вместимости n, если можно использовать только первые s предметов из заданных k.

Зададим краевые значения функции F(s, n).

Если s = 0, то F(0, n) = 0 для всех n (ни один предмет нельзя брать, поэтому максимальная стоимость равна 0).

Если n = 0, то F(s, 0) = 0 для всех s (можно брать любые из первых s предметов, но вместимость рюкзака равна 0).

Теперь составим рекуррентное соотношение в общем случае. Необходимо из предметов с номерами 1, ..., s составить рюкзак максимальной стоимости, чей вес не превышает n. При этом возможно два случая: когда в максимальный рюкзак включен предмет с номером s и когда предмет s не попал в максимальный рюкзак.

Если предмет s не попал в максимальный рюкзак массы n, то максимальный рюкзак будет составлен только из предметов с номерами 1, ..., s - 1, следовательно, F(s, n) = F(s - 1, n).

Если же в максимальный рюкзак включен предмет s, то масса оставшихся предметов не превышает n - ws, а от добавления предмета s общая стоимость рюкзака увеличивается на ps. Значит, F(s, n) = F(s - 1, n - ws) + ps. Теперь из двух возможных вариантов составить рюкзак массы, не превосходящей n, из предметов 1, ..., s нужно выбрать наилучший:

F(s, n) = max ( F(s - 1, n), F(s - 1, n - ws) + ps ).

Теперь составим программу. Будем считать, что веса предметов хранятся в массиве w[1], ..., w[k], а их стоимости в массиве p[1], ..., p[k]. Значения функции F(s, n), где 0<=s<=k, 0<=n<=W, будем хранить в массиве F[k+1][W+1].

int F[k+1][W+1];
for(n=0;n<=W;++n)       // Заполняем нулевую строчку
    F[0][n]=0;
for(s=1;s<=k;++s)       // s - максимальный номер предмета, 
{                       // который можно использовать
    for(n=0;n<=W;++n)   // n - вместимости рюкзака
    {
        F[s][n]=F[s-1][n]; 
        if ( n>=w[s] && ( F[s-1][n-w[s]]+p[s] > F[s][n]) )
            F[s][n] = F[s-1][n-w[s]]+p[s];
    }
}

В результате исполнения такого алгоритма в элементе массива F[k][W] будет записан ответ на поставленную задачу. Легко видеть, что сложность этого алгоритма, равно как и объем используемой им памяти, являются величиной O(kW).

Рассмотрим пример работы этого алгоритма. Пусть максимальная вместимость рюкзака W = 15, количество предметов k = 5, их стоимости и массы таковы:
w1 = 6, p1 = 5, w2 = 4, p2 = 3, w3 = 3, p3 = 1,
w4 = 2, p4 = 3, w5 = 5, p5 = 6.

В приведенной ниже таблице указаны значения заполненного массива F[k+1][W+1].

2. Когда надо получить не только стоимость, но и сам набор:

Сравним значение F[k][W] со значением F[k-1][W]. Если они равны, то максимальный рюкзак можно составить без использования предмета с номером k. Если не равны, то предмет c номером k обязательно входит в максимальный рюкзак. В любом случае, задача печати рюкзака сводится к задаче печати рюкзака для меньшего числа предметов. Напишем это в виде рекурсивной функции Print(int s, int n), которая по параметрам s и n печатает номера предметов, входящих в максимальный рюкзак массой не более n и составленный из предметов 1, ..., s:

void Print(int s, int n) {
  if (F[s][n]==0) // максимальный рюкзак для параметров (s,n)
    return;        // имеет нулевую ценность, 
                   // поэтому ничего не выводим
  else if (F[s-1][n] == F[s][n]) 
    Print(s-1,n);  // можно составить рюкзак без предмета s
  else
  {                               
    Print(s-1,n-w[s]); // Предмет s должен обязательно 
    cout<<s<<endl;     // войти в рюкзак
  }
}

3. Когда каждую вещь можно брать только один раз:

Тут всё ещё проще: надо просто в каждой итерации идти по массиву не снизу вверх, а сверху вниз, то есть, от W к 0. Тогда получится, что при рассмотрении max[n-w[s]], там всё ещё будет записано, набор какой максимальной стоимости веса n — w[s] можно получить, используя только вещи 0..s-1. Следовательно, если получится, что в оптимальном наборе надо использовать s-тую вещь, то она будет использована только один раз.

4. Выбор значения, как можно более близкого к данному:

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

В всех случаях ассимптотика времени работы и используемой памяти та же.

5. Когда каждую вещь можно брать определённое количество раз:

Есть вариация задачи, в которой вещь с номером i можно брать от 0 до q[i] раз. Конечно, можно «размножить» i-ю вещь на q[i] единиц и решить задачу о 0-1 рюкзаке. Однако, сложность такого решения будет O(W * ∑q[i]), что не очень хорошо. На самом деле, можно поступить хитрее.

Пусть q[i] = 1 + 2 + 4 + 8 +… + 2^k + r[i], где r[i] < 2^(k+1).
Тогда рассмотрим k+2 предмета объёмом 1*v[i], 2*v[i], ..., 2^k*v[i], r[i]*v[i] и стоимостью 1*c[i], 2*c[i], ..., 2^k*c[i], r[i]*c[i] соответственно.
(«Названия» новых предметов — «1 i-я вещь», «2 i-ых вещи», «4 i-ых вещи» и т. д.)

Ясно, что выбирая различные подмножества этих k+2 предметов, можно получить любое количество (от 0 до q[i]) вещей типа i. Т. е. вместо «размножения» вещей i-го типа на q[i] единиц, мы сумели ограничиться k+2 = O(log q[i]) единицами.

Такой метод будет иметь сложность порядка O(W * ∑log q[i]), что куда более эффективно, чем «наивное» решение.