Спортивное программирование

[Nadir Zaitov]

Предлагаю перевести спортивное программирование в "Разминку для мозгов " и выкладывать туда интересные задачки и их программировать.

[Khamza Davletov]

Сообщение от dert

Khamza Davletov,http://algolist.ru/ очень полезный сайтик. Там можно и книжечки разные найти, да и форум заюзать

Спасибо! Надо будет как небудь по участвовать тоже онлайн. Ато примерно каждые пол года из acm.sgu.ru приходят уведомление об олимпиадax, но ни разу не учавствовал .

Короче тоже покoпался, нашел кое что интересное на английском.

http://rapidshare.com/files/25570747...s-1-4.97802013

http://www.megaupload.com/?d=0DGYFIRZ (Programming Pearls)

[Kane]

Глубже Кнута книг не видел. Если нужно быстро и без глубокой теории - Кормен.

[YUU]

программирование ради программирования - напрасная трата времени и усилий.

Вот если реальную задачу поставить и кто решит тому лавры и призы - то да -смысл есть

[Khamza Davletov]

Сообщение от YUU

программирование ради программирования - напрасная трата времени и усилий.

Вот если реальную задачу поставить и кто решит тому лавры и призы - то да -смысл есть

Только не говорите что вы незнали то, что в interview на работу в Microsoft, Google, IBM... задают типичные вопросы

[Khamza Davletov]

Реальная задача так реальная задача. Приведу task из одного интервью на одной всеми известной компании

You are given an implementation of a LIFO (Last In First Out) data structure, which is also known as a stack:

class LIFO
{
public:
void push(int n); // push n onto the stack
int isempty(void); // test whether stack is empty
int pop(void); // pop top of stack, can be called iff !isempty()
}

Example call sequence:

LIFO l;
l.push(1); l.push(2); l.push(3);
l.pop(); // returns 3
l.pop(); // returns 2
l.pop(); // returns 1

1. Using this LIFO class (which you do not need to implement), implement a FIFO (First in First Out) data structure, also known as a queue.

2. Explain what the complexity of your algorithm is when a sequence of n subsequent push (or n subsequent pop) operations are performed on the LIFO, and whether this complexity is optimal.

class FIFO
{
private:
LIFO l1;
LIFO l2;
public:
void enqueue(int n); // add n to front of queue
int isempty(void); // test whether queue is empty
int dequeue(void); // remove last element of queue, can be called if !isempty()
}

Example call sequence:

FIFO f;
f.enqueue(1); f.enqueue(2); f.enqueue(3);
f.dequeue(); // returns 1
f.dequeue(); // returns 2
f.dequeue(); // returns 3

Больше всего интересует 2й пункт. Мархамат!

[Rooslan Khayrov]

Если использовать вот такую реализацию, то при условии, что все операции со стеком выполняются за константное время, любая последовательность из N операций enqueue и dequeue будет выполнена за O(N) время, т.е. амортизированная сложность оптимальна.

[Rooslan Khayrov]

Оффтоп:

Кстати, неалгоритмический вопрос на засыпку. Представьте, что тестируя своё решение, вы написали нечто такое:

cout << f.dequeue() << endl
     << f.dequeue() << endl
     << f.dequeue() << endl;

Почему это плохая идея?

[Khamza Davletov]

Сообщение от Rooslan Khayrov

Если использовать вот такую реализацию, то при условии, что все операции со стеком выполняются за константное время, любая последовательность из N операций enqueue и dequeue будет выполнена за O(N) время, т.е. амортизированная сложность оптимальна.

http://dumpz.org/11074 - это есть решение для пункта 1. Но пункт 2 у вас явно не полный .

1. Вот например, http://dumpz.org/11075/ - тоже решение для пункта 1, но оно не оптимальнее чем ваш. Почему? - Хотя даже видно почему, но надо доказать уже математическим путём.

2. Ну это тоже не делает ваш алгоритм самым оптимальным. Нужно доказать что оптимальнее нельзя .

P.S. И то, что "Big O" равен O(n) не плохо было бы обосновать математическим путём.