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

[dert]

Всем доброе время суток. Кто нибудь занимается здесь ACM?

[_TrachinuS_]

Когда то занимался. Щя времени нет:(

[dert]

Понятно. Ну если есть желающие, хочу посоветовать один архивчик:
http://olymp.krsu.edu.kg/

[German Stimban]

Когда-то участвовал. В последнее время забросил. Иногда читаю задачки пытаюсь вспомнить былое, решить что-то

[Nadir Zaitov]

Я тоже участвовал. Было весело. Нужна, как правило, хорошая математика как классическая так и прикладная. :)

[dert]

Я тоже участвовал. Было весело. Нужна, как правило, хорошая математика как классическая так и прикладная. :)
Не всегда :) Обычно нужны знания алгоритмов. Единственно соглашусь, что в команде нужен как минимум один математик.

[OmoN]

Всем доброе время суток. Кто нибудь занимается здесь ACM?
Занимался когда был студентом.

[vcoder]

Понятно. Ну если есть желающие, хочу посоветовать один архивчик: http://olymp.krsu.edu.kg/

здесь - http://acm.timus.ru/ коллекция побольше

[Khamza Davletov]

Тоже пару раз участвовал. Очень интересное мероприятие (и полезное ;) ).

Решил вернутся в это дело, чтобы хоть как то форму поддержать (решаю из http://acm.timus.ru/).

Посоветуйте книжку (или книги) пожалуйста, где-бы можно было бы получить теоретические знание. (Data structure, algorithms, оценка от "Big O", dynamic programming...).

Кнут уж слишком, да и очередная книжка о только базовых понятий (типа what's programming...) тоже скучно :(.

[dert]

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

[Nadir Zaitov]

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

[Khamza Davletov]

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

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

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

http://rapidshare.com/files/255707479/algorithms-in-c-parts-1-4-fundamentals-data-structure-sorting-searching-3rd-edition-pts-1-4.97802013

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

[Kane]

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

[YUU]

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

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

[Khamza Davletov]

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

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

Только не говорите что вы незнали то, что в 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]

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

[Rooslan Khayrov]

Кстати, неалгоритмический вопрос на засыпку. Представьте, что тестируя своё решение, вы написали нечто такое:
cout << f.dequeue() << endl
<< f.dequeue() << endl
<< f.dequeue() << endl;
Почему это плохая идея?

[Khamza Davletov]

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

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

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

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

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