SRM link

Your local time

Hello everybody!

Recently I have faced the following graph problem: Given a directed graph with nonnegative weights. There is a need to find a number of paths between two nodes which path's weights are less then specified number. Graph may contain cycles and path may contain cycles.

I have found the Yen's algorithm which can find K shortest paths and which may be adjusted to partially solve my problem (the algorithm finds loopless paths) and wondering now if there is an approach to solve the problem.

Мне посчастливилось попасть в летнюю школу Сазанка 2013 практически совершенно случайно. Будучи никак несвязанным с АСМ движением и переросшим все мыслимые и немыслимые возрастные лимиты (мне 29), я всё же был приглашён на сборы в Саратов.

Перед школой были двоякие чуства. С одной стороны, радость от того, что встречу единомышленников, которым нравятся олимпиадные задачки и разнообразные алгоримты, в Берлине я так и не смог найти таковых. С другой стороны, разность в возрасте могла оказать негативное влияние на процесс общения. К огромной радости опасения не оправдались, и я получил огромный опыт.

Что же такое саратовская Сазанка 2013?

I) Это 5 чётко структурированных 2-х часовых лекций по строковым алгоритмам. До лекций у меня было туманное представление что такое Z- или префикс-функции, не смотря на то, что я перечитал несколько статей на Хабре и на емаксе. Их значение, построение и использование было объяснено очень грамотно и доступно, так что теперь они кажутся довольно простым инструментом.

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

II) Это 50 часов тематических и нетематических контестов. По моему мнению, принцип "learn by doing" это самый эффективный способ обучения, и он с успехом применялся в Школе. Вполне естественно, что не всё ясно во время лекции, какие-то детали упускаются слушателями, однако, упущенное навёрстывается за время контеста: когда нужно заново реализовать сложную структуру данных за ограниченное время.

III) Это многочасовые дорешивания. Как только заканчивался контест и утолялось чуство голода после 5-ти часовой гонки, большенство участников приступало к решению тех задач, которые не удалось сдать на контесте. Прелесть дорешивания в том, что можно неспеша обсудить и понять идею решения с товарищами по команде или другими участниками.

IV) Это вкусное трехразовое питание. Осторожно: набор веса гарантирован!

V) Это 3 похода в сауну с арбузами, мороженным и забегами в Волгу. Кстати, в один из таких вечеров некоторые участники узнали истинную причину моего приезда.

VI) Это заключительная вечеринка, на которой участники не только кушают вкусное мясо, но и общаются в неформальной обстановке. Там я узнал, каких сил стоило создать проект Кодефорсес, и каких сил стоит его поддерживать.

В общем, я невероятно рад, что посетил Сазанку 2013, теперь ожидаю улучшение рейтинга, как на Codeforces, так и на TopCoder. Всем кто раздумывает ехать или не ехать — ответ однозначен: ехать, другое дело в том, хватит ли для вас свободного места ;-)

PS: http://codeforces.me/blog/entry/8616 — фотографии

On 3rd of December the second part of the Standford algorithms course starts! Check it here

Напоминалка об СРМ 560, время тут

Просматриваю сейчас курс на www.coursera.org Web Intelligence and Big Data и профессор задаёт следующий вопрос:

The time it takes to search a ‘normal’ hash-table that maps a large number (n) of objects to a small number (m) hash values is ..

• A) O(log n)
• B) independent of n
• C) independent of m
• D) O(log m)

Ответом лектора оказался B)

Правильного ответа тут вообще не присутствует (O(1+loadFactor)).

Однако, в данной выборке ответов более логичным видится ответ C)

А вы что думаете?

Всем доброго вечера. В книге Кормена "Введение в алгоритмы" имеется следующее описание функции DELETE для хэш таблицы (раздел 11.2): CHAINED-HASH-DELETE [T, x], где T — хэш таблица, а x удаляемый элемент. В ячейке хэш таблицы хранится начало двунаправленного списка. В книге постулируется, что удаление стоит O(1) по времени, если список двунаправленный. Может кто-нибудь объяснить как можно удалить элемент из двунаправленного списка за константу, ведь в функцию передается не элемент списка, а элемент, который находится в поле data элемента списка?

Сегодня, во время контеста участник enesoncu взломал задачу В участника karti аж целых 3 раза.

Посмотрев код karti можно сделать вывод, что либо karti играет в поддавки, либо участник enesoncu сабмитит с другого аккаунта и ломает решение.

Думаю, что администрация в силах разобраться кому ставить бан.

Задача: 169B - Replacing Digits

Сабмит: 1413765

Код:

int m,n;
char str[200000],ptr[200000];
void read(){
	int i,j,ind,s,p;
	char min=120,t,c;
	cin>>str>>ptr;
	if(strcmp(str,"54656451321")==0){ cout<<"2121414445754"; return; }
	s=strlen(str);
	p=strlen(ptr);
	sort(ptr+0,ptr+p);
	ind=p-1;
	For(i,0,s-1){
		if(ptr[ind]>str[i]){ str[i]=ptr[ind]; ind--; if(ind==-1) break;}	
	}
	cout<<str;
}

Hi all!

I have seen a lot of people saying that they are really happy about the website.

I think that it would be a very nice idea to let people make a material contribution to the website.

So that if somebody who loves this site or took high place in the contest can express his/her feeling by making a donation.