Thursday, September 18, 2014

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]]);
}

Monday, August 25, 2014

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

Friday, April 4, 2014

Robo-Hand (The prototype of robotic hand)

Данный программно-аппаратный комплекс, разработанный нами, является тренажёром для приобретения навыков практического программирования реальных устройств подобного типа, экспериментальный стенд, а так же устройство для проверки и демонстрации на практике математических расчётов. С его помощью можно более наглядно изучить физику движения механизмов подобного типа. В программный комплекс входят: 3D эмулятор робота-манипулятора, лёгкий и функциональный макро-язык, анализатор движения (плавные разгоны и торможения), поддержка USB-джойстика, удалённое управление со смартфона, а так же всё необходимое для реализации алгоритмов движения.

Если вас заинтересовала эта информация - пишите в комментарии.



Saturday, December 21, 2013

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;
}

Friday, October 11, 2013

Broadcasting audio/video/audio & video. FFmpeg + FFserver

FFmpeg - достаточно мощная утилита, кроссплатформенная, поддерживает множество кодеков.
В сети достаточно много различных инструкций по использованию, я постараюсь расписать всё простым языком, с пошаговыми действиями, и своими заметками и опытом. :)

Официальный сайт проекта FFmpeg
Про то как кодировать аудио/видео можно почитать тут: http://nix-sa.blogspot.com/2012/02/ffmpeg.html

Если вкратце, то FFmpeg - берёт входные данные (как самые обычные файлы, так и удалённый поток), и отправляет в другом формате (если это надо) или в файл, или в поток.
FFserver - исходя из названия уже понятно, что это сервер на котором будет происходить получение данных с FFmpeg источников, буферизировать данные, перенаправлять поток,  и давать возможность получать данные устройствам через плеер (я использовал FFplay, а так же VLC).
Что касается плеера: искать нужно под свой формат и кодек. Я использовал G722. VLC отказался проигрывать этот формат, но на счастье, "родной" FFplay его подхватил (если в параметрах FFplay явно не указать g722, он работать не будет, о запуске - ниже).
G722 формат честно говоря, достаточно не плох. Качество звука хорошее, и не сильно забивает сеть.

В интернете видел вопросы людей о том что при трансляции аудио в g722 звук в два раза медленней: сам столкнулся с этим, решение заключается в том, чтобы просто правильно указать битрейт и сэмплрейт. :)


Чтобы не разбивать статью на много небольших, соберу всё здесь:

Начнём про связку FFmpeg + FFserver.

Сперва почитаем https://trac.ffmpeg.org/wiki/Streaming%20media%20with%20ffserver

Скачаем и установим пакет FFmpeg (apt-get install ffmpeg или opkg install ffmpeg или ...)
(How install ffmpeg)

Далее заходим в /etc/ и редактируем/создаём файл ffserver.conf
Пример конфигурационного файла http://ffmpeg.org/sample.html

Запускаем ffmpeg, который будет перенаправлять поток с микрофона в feed ffserver-а (возможно перекодирование).

Начинает работать ffmpeg, если вы не установили флаг запуска daemon-а в фоновом режиме, и вы работаете через терминал, то запустите вторую сессию и запустите ffserver (если конфигурационный файл лежит не в /etc/ffserver.conf, то ffserver -f *ваш путь*)

Подробней можно почитать на официальном сайте.

FFmpeg и сразу в сеть

Мой скрипт для запуска:

#!/bin/bash
############### Uni/Multu cast stream
#ffmpeg -d -f oss -i /dev/dsp -f g722 -ac 1 -ab 8 -ar 16000 \

#-acodec g722 rtp://192.168.80.4:1234

ffmpeg -d -f oss -i /dev/dsp -f g722 -ac 1 -ab 8 -ar 16000 \

-acodec g722 rtp://224.1.1.1:1234 /usb_flash/out.g722

Скрипт для прослушивания:

ffplay.exe -f rtp -acodec g722 -ar 8000 -ab 8k rtp://127.0.0.1:1234

Thursday, October 10, 2013

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]), что куда более эффективно, чем «наивное» решение.

Tuesday, July 30, 2013

Just added syntax highlighting :)
#include <stdio.h>
int main()
{
    printf("Hello Syntax Highlighting!\n");
    return 0;
}
#include <iostream> 
int main()
{
    std::cout << "Hello Syntax Highlighting!" << endl;
    return 0;
}
public class Hello {
    public static void main(String[] args) {
        System.out.println("Hello Syntax Highlighting!");
    }
}
public class Hello
{
   public static void Main()
   {
      System.Console.WriteLine("Hello Syntax Highlighting!");
   }
}
with Ada.Text_IO;
procedure Hello is
 use Ada.Text_IO;
begin
    Put_Line("Hello Syntax Highlighting!");
end;
         .486p
         .model  flat,STDCALL
include  win32.inc
 
extrn            MessageBoxA:PROC
extrn            ExitProcess:PROC
 
.data
 
Hello db "Hello Syntax Highlighting!",0
msgTitle db "Hello",0
 
.code
Start:
         push    MB_ICONQUESTION + MB_APPLMODAL + MB_OK
         push    offset msgTitle
         push    offset HelloWorld
         push    0
         call    MessageBoxA
 
         push 0
         call ExitProcess
ends
end Start
(Кому интересно - ссылка)