Здравствуйте, уважаемые обитатели Codeforces. В этой теме я собираюсь задать несколько вопросов, которыми, скорее всего, уже надоели многие школьники моего возраста. И я был бы рад не делать этого, но лучше, чем здесь, мне вряд ли где-нибудь ответят. Поэтому кому не сложно, ответьте, пожалуйста :)

Сейчас я в 11 классе одной из санкт-петербургских гимназий, и вот уже через 3 месяца мне понадобится подавать заявку в университет(-ы). И знаете что? Кроме того, что я хочу заниматься программированием, я больше ничего и не знаю. Здесь кто-нибудь может пнуть меня за мою легкомысленность, но да, за те два года, что я занимаюсь этим замечательным предметом, я так и не задумался, кем же я хочу стать. Помимо этого, я вообще не особо интересовался, какие специальности, какие пути развития существуют. И сейчас, оказавшись в такой ситуации, я нахожусь в тупике. Подскажите, пожалуйста, какие интересные/востребованные/многооплачиваемые специальности программистов сейчас существуют? Какую выбрать? Для справки, на работе мне хотелось бы побольше думать и поменьше тупо-кодить. В лучшем исходе мне бы хотелось делать это в загранице. Но это уже детали.

После выбора специальности второй не менее важный вопрос — куда же поступать? Как уже было сказано, я живу в Санкт-Петербурге, поэтому логичным было бы поступать либо в ИТМО, либо на мат-мех СПБГУ. Именно эти два варианта пока являются моими основными. Но я не хочу ими ограничиваться. От знакомых слышал, что есть неплохие ВУЗы в Финляндии и Венгрии, в которые на бюджет ежегодно поступает около 30-40 россиян. Так как я хочу в будущем жить и работать за границей, то это, я думаю, лучшая альтернатива русским ВУЗам. А как вы считаете? Есть ли смысл? Да и вообще, кто слышал про эти самые вузы, там лучше образование, чем у нас, или наоборот? Или в принципе без разницы? Получить работу за границей проще, имея диплом об окончании СПБГУ или финского универа? ...Тут еще много однообразных вопросов, надеюсь, найдется кто-нибудь, кто сможет раскрыть данную тему поподробнее...

Спасибо тем, кто прочитал и не заминусил. И заранее спасибо тем, кто поможет мне разобраться с этой нелегкой задачей :)

Условия задач не скачиваются, вместо них выпадает ошибка. Поправьте, пожалуйста.

Заранее спасибо)

UPD. Более не актуально, все починили, все работает. Спасибо.

Всем привет. Совсем недавно я, наконец, познакомился с такой замечательной структурой, как дерамида. В теории я понял ее практически отлично. Но вот когда дело дошло до реализации, я понял, что не все так хорошо. Долгое время я думал, что знаю все нужные аспекты Java для ОП, но, как оказалось, не все.

Вот то, что я смог написать сам — http://pastie.org/5084738 Это, вроде, самая "нубская" реализация Декартова Дерева. В теории я знаю о том, как можно избавится от приоритетов, о переходе от явного ключу к неявному, но я хочу пройти через все этапы усовершенствований, дабы понимать, что к чему.

Так, много слов, а сути нет. На данном этапе я хочу модифицировать функции add() и remove(), чтобы они использовали по одной операции split()/**merge()**, а не по три. Ясно, как это делается:

Add(x) — спускаемся по дереву поиска, пока не найдем вершину с приоритетом меньшим, чем у добавляемый вершины, посплитим ее по x, и поставим получившиеся l и r как l и r добавляемой вершины, ее же поставим на место найденной

Remove(x) — спускаемся по дереву, находим искомую вершину, мерджим ее l и r, ставим результат на место этой вершины, вуаля

На примере remove() покажу, в чем, собственно, моя проблема. Вот как, по сути, она должна выглядеть:

void remove(int x) {
	Node t = root;
	while (t.x != x)
		t = x < t.x ? t.l : t.r;
	t = merge(t.l, t.r);
}

Но это не работает в силу того, что в данном случае t — лишь одна из ссылок на вершину дерева и, меняя ее, я не меняю само дерево, я лишь меняю эту ссылку. И вот, я не знаю, как правильно это реализовать. То же самое с add().

Возможно, я очень опозорился этим постом, но что ж, ладно, я только учусь, так что ничего. Если кто может помочь советом по реализации или каким-нибудь еще советом — буду очень благодарен. Также буду благодарен за ссылки на готовые реализации, как такого дерева, так и по неявному ключу, чтобы было с чем сравнивать. На емакс и хабр ссылок не надо, читал уже :)

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

Теперь более официальное условие задачи: есть связный взвешенный неориентированный граф без петель и кратных ребер. Также есть список дел. Требуется из данной вершины S придти в F, при этом выполнив все дела из списка. Дело представляет из себя пару чисел s_i и f_i — номера вершин в графе, для каждого дела нужно сначала посетить s_i, а затем посетить f_i. Надо вывести длину минимального пути из S в F, который покрывает все дела, а также сам этот путь. Пусть будет N вершин, M ребер и K дел. Нужно найти самое оптимальное решение. UPD1: Дела необязательно делать последовательно, можно выполнять несколько дел одновременно в любом порядке, в этом и смысл задачи.

Прошу помочь в решении этой задачи, потому что стало интересно, а сам додуматься не смог. Также прошу прощения, если это где-то уже обсуждалось или же за формулировкой задачи скрыто что-то совсем простое, а я не заметил.

UPD2: в комментариях было сказано про метод отжига, статьи о нем можно почитать здесь. Я, если честно, не очень понял, если кто-то может подробно его описать на примере этой задачи, я буду очень благодарен.

Привет всем, кто зашел в эту тему. В ней я бы хотел рассказать вам немного об одной интересной структуре данных, а еще больше — узнать ваше мнение о ней.

Для тех, кто не знает, что это — статья на Википедии. А для тех, кто не очень любит читать много текста, перескажу в двух словах. Фильтр Блума — это вероятностная структура данных, позволяющая хранить некое множество элементов, а также быстро отвечать на запрос о том, есть ли данный элемент во множестве или нет. Вероятностная она потому что при запросе есть вероятность получить ложноположительный ответ. Почему это так? Ответ в алгоритме работы структуры. Сама структура состоит из битового массива размера m и k хэш-функций, каждая из которых для данного элемента возвращает число от 0 до m-1. Добавление элемента происходит достаточно просто — на позиции h1(e), h2(e), ..., hk(e) в массиве проставляются единицы (**hi()** — хэш-функция, е — добавляемый элемент). Как легко можно догадаться, проверка происходит аналогичным образом, считаются хэш-функции и проверяются соответствующие позиции, если на них все единицы, то элемент присутствует во множестве, в противном случае можно на 100% быть уверенным, что его там нет. Теперь ясно, почему положительный ответ на запрос не может считаться 100% верным, ведь может так получится, что для некоего элемента, которого нет в множестве, единицы на месте посчитанных значений уже проставлены в результате того, что некоторые элементы из множества для некоторых хэш-функций имеют одинаковые значения с элементом.