On November 5th I (and I hope other 2,000 people) got this e-mail:

Thank you for participating in this year's Hacker Cup Competition and congratulations for making it to the top 2,000! As a Top 2000 participant, you have earned a Hacker Cup 2020 T-shirt. __ Instructions: To redeem this shirt, you will receive an email ([email protected]) from our 3rd party swag company with the website and unique code by end of next week. All redemption requests must be submitted by December 4, 2020. Be sure to keep an eye out for this email and check your spam folder.

Based on my calculation by "end of next week" they were referring to November 15th (or even November 14th as Americans tend to see Sunday as a first day of the week).

I didn't get any e-mail — did anybody get it?

Some of you must have received the following e-mail. So IPSC is coming back to us again. I created this topic to let people search for teammates (in case they want to participate in teams and don't have one).

Please comment below if you are available to join team and a little description about yourself.

= ORIGINAL E-MAIL=

Your favorite programming competition is back for its 18th year! We excitedly invite you to compete in IPSC 2016.

Internet Problem Solving Contest is an online programming competition for teams of up to three people. The problems range from easy to very hard, so everyone is welcome to compete. We also have separate ranklists for individuals and secondary school students. You can use any programming language, or even solve problems by hand. Most of the problems are algorithmic in nature, but IPSC is particularly known for its unusual and fun problems.

IPSC 2016 will take place on Saturday, 18 June 2016 from 11:00 to 16:00 UTC. Visit http://ipsc.ksp.sk/ to register, either as an individual or as a team of up to three people.

While you're waiting for 18 June 2016, you can also visit http://ipsc.ksp.sk/train/ to practice on problems from previous years of IPSC.

If you like IPSC, help us spread the word! Tell your friends, classmates, coworkers, internet strangers, et cetera.

Good luck in the contest, and have fun!

IPSC Organizing Team

I'd like to ask professional opinion on the following problem — Count String from Hackerrank.

I was able to solve it (at least to produce solution, which passes all testcases). But I am not happy with this solution, because there are testcases where it goes exponential and TLEs. Those testcases are not used to judge the problem, but apparently if it was used in Codeforces or Topcoder round it would have been easily hacked.

Short idea of problem (for more detailed description — follow the link):

• you are given simplified regular expression, not longer then 100 characters
• count number of strings with specific length which match that regular expression. Length can go astronomical (10^9 :)

Solution:

• Because of Length going up to 10^9, the first idea I had was to use Matrix Multiplication
• To use matrix multiplication you need to create DFA graph
• It is easy to build NFA graph from regexp. But you can't use NFA graph to count strings because of epsilon-transitions
• It is easy to convert NFA to DFA getting rid of epsilons

Problem done. Almost. Conversion from NFA to DFA in worst case scenario is exponential. Oops.

Question — is there better approach, which can guarantee polynomial run-time?

There is no editorial for this problem on the site. I don't know if it was used in programming contests.

Hi,

Just wanted to double check if my solutions for Distributed Code Jam practice problems are reasonably correct. This is not the full description, but just ideas on how to solve:

Sandwich

Cut sandwich into number_of_nodes pieces. Every node is responsible for delivering four numbers to central node. Four numbers being "maximum eating from the left", "maximum eating from the right", "total sum", "maximum eating from both ends". Central node having all this numbers can do any algorithm (even O(n^4) if you wish) to come up with an answer, as n is not more than 100 at that point.

Majority

Population is split evenly between every node. Every node sends to central node the best candidate and the runner-up candidate. Central node combines No'1 and No'2 candidates and picks two most frequent (maybe one is enough?). Central node sends request to all other nodes to provide vote count for two most frequent candidates. Nodes respond, central node adds votes up and produces result. (UPD — wrong approach — see in comments below)

Shhhh

I found it most interesting. My solution went like this — we have to go through the whole circle to get the answer, there is no way around it. We want to split work across nodes, but we can't do it evenly, as we don't know where each person sits. Randomization helps (was it intended solution?). I played with numbers a little bit to see that if we have 100*number_of_nodes "key numbers", every node can start from each of it's 100 key_numbers and go right until getting to another key_number. Then send to the central node information in form "from key number x to key number y distance is D". Central node combines all this data and give out result. I think we are protected by statistics from situation where one node might get unusually long sequence leading to TLE.

Load Balance

Classical partitioning problem. I only used 8 nodes for small and 64 nodes for large (not 100). With 52 numbers you can split them into 64 sub-tasks with 45 numbers each. 45 numbers are solvable by "meet in the middle" algorithm for sub sequence sum search. So each node receives 45 numbers and sum to search for. Sum to search for is Total / 2 adjusted depending on whether you include first 7 numbers in this sub-task or not.

Hi everbody,

I am going through preparations now — my only experience with this staff before is single course at Udacity about Parallel programming with CUDA. Not exactly the same thing, but the same paradigm.

My question is regarding their testing environments:

Dstributed Code Jam Guide

I do want to be able to test some solutions beforehand and have this tool at hand during the round itself.

Did anybody try to get this thing working with MS Visual C++? Does it make sense to try?

Should I try to make this thing working with MS Visual C++, switch to gcc or switch to Python for this round?

What are your impressions of this tool?

There was a question lately about music. I wanted to get understanding of what is favorite hardware you like to use for programming competitions.

• what brand, do you have preferences, maybe some history of how you got to using it
• is there some must about computer you're using (like if it must have specific screen resolution, or multiple screens or you like to have multiple cores)
• if you prefer desktops or laptops or you don't have much choice
• any specific keyboard / mouse brands which you find convenient for yourself

Also if your hardware is provided by employer, would be nice to hear about it (as long as you feel comfortable disclosing).

Answers like "Doesn't matter, I can code on anything which has at least one button and one pixel" are also welcome.

NB: By commenting in this thread you agree not to make any offensive comments regarding race, religion , computer brand, make, other people's preferences.

This is one of the famous Interval tree problems, I think many of you solved it at some point of you competition career. The problem is this:

Can you answer this Queries V

Below is my solution — it is not perfect obviously, but with similar code I already solved GSS1 and GSS3:

Can you answer this Queries I Can you answer this Queries III

So it is partially tested and AC'ed. The problem I encountered — under Miscrosoft Visual Studio Express 2013 it compiles and works fine in debug mode. I tried preparing random test cases for it and none of the runs I did (several thousand random testcases) could replicate the problem.

SPOJ reponse to this code is always the same — SIGABRT or SIGSERV, randomly. I understand that for SIGSERV I should be looking for writing outside of boundaries of array, but solution uses only vectors and it should be detected in debug mode... Maybe I was not able to replicate that single specific testcase which leads to the problem.

Can anybody please provide any clues?

Thanks,

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <cassert>

using namespace std;

struct entry
{
	entry() : sum(0), best(0), left(0), right(0) {};
	entry(int value) : sum(value), best(value), left(value), right(value) {};
	entry(int v1, int v2, int v3, int v4) : sum(v1), best(v2), left(v3), right(v4) {};

	int best;
	int sum;
	int left;
	int right;
};

vector<vector<entry>> M;


entry getValue(int a, int b, int depth, int s = 0)
{
	if (a > b) return entry(0);

	int left = (1 << depth) * s;
	int right = (1 << depth) * (s + 1) - 1;

	if (a == left && b == right) return M[depth][s];

	int mid = (left + right) / 2;

	if (a <= mid && b <= mid) return getValue(a, b, depth - 1, 2 * s);
	if (a > mid && b > mid) return getValue(a, b, depth - 1, 2 * s + 1);

	entry Left = getValue(a, mid, depth - 1, s * 2);
	entry Right = getValue(mid + 1, b, depth - 1, s * 2 +1);

	return entry(Left.sum + Right.sum, max(max(Left.best, Right.best), Left.right + Right.left), max(Left.left, Left.sum + Right.left), max(Right.right, Right.sum + Left.right));
}

int main()
{
	int t;

	cin >> t;

	while (t--)
	{

		ios_base::sync_with_stdio(0);

		int n;
		cin >> n;

		M = vector<vector<entry>>();

		M.push_back(vector<entry>(n));

		for (int i = 0; i < n; i++)
		{
			int t;
			cin >> t;

			M[0][i] = t;
		}

		int k = n;
		int depth = 0;

		while (k > 0)
		{
			depth++;
			M.push_back(vector<entry>(k / 2 + 2));

			for (int i = 0; i < M[depth - 1].size(); i += 2)
			{
				if (i + 1 == M[depth - 1].size())
				{
					M[depth][i / 2].sum = M[depth - 1][i].sum;
					M[depth][i / 2].best = M[depth - 1][i].best;
					M[depth][i / 2].left = M[depth - 1][i].left;
					M[depth][i / 2].right = 0;
				}
				else
				{
					M[depth][i / 2].sum = M[depth - 1][i].sum + M[depth - 1][i + 1].sum;
					M[depth][i / 2].left = max(M[depth - 1][i].left, M[depth - 1][i].sum + M[depth - 1][i + 1].left);
					M[depth][i / 2].right = max(M[depth - 1][i + 1].right, M[depth - 1][i + 1].sum + M[depth - 1][i].right);
					M[depth][i / 2].best = max(max(M[depth - 1][i].best, M[depth - 1][i + 1].best), M[depth - 1][i].right + M[depth - 1][i + 1].left);
				}
			}

			k = k / 2;
		}

		int q;
		cin >> q;

		while (q--)
		{
			int x1, x2, y1, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			x1--, y1--, x2--, y2--;

			int ans;
			if (y1 < x2)
			{
				entry Middle = getValue(y1 + 1, x2 - 1, depth);
				entry Left = getValue(x2, y2, depth);
				entry Right = getValue(x1, y1, depth);

				ans = Left.left + Right.right + Middle.sum;
			}
			else
			{
				int Middle = getValue(x2, y1, depth).best;

				int l1 = getValue(x1, x2, depth).right;
				int r1 = getValue(x2 + 1, y2, depth).left;
				l1 = max(l1, l1 + r1);

				int r2 = getValue(y1 + 1, y2, depth).left;
				int l2 = getValue(x1, y1, depth).right;
				l2 = max(l2, l2 + r2);

				ans = max(Middle, max(l1, l2));
			}

			cout << ans << "\n";

		}

	}
}

В новостях появились сообщения о том, что:

"Корпорация Google закрывает свой инженерный офис в России в связи с ограничением интернет-свобод в отношении использования данных иностранными компаниями, работающими в стране, пишет Wall Street Journal."

Хотелось бы от людей, которые имеют отношение к Гугл в России узнать как это повлияет на инженеров — предлагают переехать в другой офис/страну? Увольняют? Или на самом деле всё не так плохо как пишет WSJ?

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

Всем привет,

Так как мне на данный момент довелось жить в курортном регионе (причём довольно необычном), хотел воспользоваться возможностью и предложить встретится и пообщаться с теми из вас, кто окажется проездом на нашем маленьком острове. Сообщение сознательно на русском языке, и приглашение направлено русскоговорящей части этого сообщества.

Для проживающих в США и Канаде, Каймановы острова в принципе являются неплохим выбором для проведения отпуска, хотя могут быть немного скучноваты для тех, кому нужен очень активный отдых. Большинство туристов здесь именно из США и Канады и русская речь слышна в основном от приехавших из Нью-Йорка.

Отдыхающие из России сюда приезжают обычно на круизных кораблях, в один из дней круиза по карибским отсровам. Плывут, конечно, не прямо из России, а приплывают из Майами :), просто место здесь дорогое и ехать только сюда из России — не самый выгодные способ потратить отпускные деньги. А круиз — это много стран сразу + январские праздники в России не совпадают с рождественскими в США и можно рассчитывать на некоторые скидки.

Предложение простое — если спишемся через личку и по времени всё получится — покажу остров, поболтаем (в том числе о спортивном программировании :)) и просто познакомимся — мир маленький, может ещё где-то когда-то пересечёмся.

Если кому-то будет интересно приехать сюда на недельку, то есть возможность предоставить дешёвое (по кайманским меркам) жильё на неделю (есть у меня тут один местный timeshare). Но не рекламирую, только если кто-то заинтересуется.

В общем, как говориться — будете в наших краях — пишите.

P.S. Включено — знакомство с лучшим спортивным программистом Каймановых Островов. Для тех кто хочет пошутить, что будучи единственным спортивным программистом на Кайманах, я значит и худший программист тоже — неправда, есть ещё один пользователь из наших краёв на Topcoder.

Хотелось спросить — был ли Google замечен в рассылках "полуавтоматических" "шаблонных" писем с предложением пообщаться по поводу работы и прислать резюме? Может быть по какой-то выборке из участников Google Codejam?

Я бы никогда в таком Google не заподозрил, но мне пришло какое-то странное письмо, озаглавленное "Engineering opportunities in Google".

С точки зрения источника происхождения у меня особых сомнений нет, реальный человек и действительно работает над поиском персонала в Google. Странно письмо тем, что мне особенно хвастаться на программистском поприще нечем, поэтому для себя я сей факт могу объяснить только тем, что попал в какую-то выборку (может быть случайно).

Да, на письмо я ответил миролюбиво и позитивно, но больше никаких сообщений не получал (уже больше недели), что тоже намекает либо на какую-то ошибку, либо на "массовый" характер рассылки.

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

У кого-то были подобные случаи?

UPDATE:

В целом ситуация понятна, потрясает объем "выкапываемой породы" в поисках "бриллиантов", раз уж даже до меня докопались. :) С точки зрения способа коммуникации — с учётом того, что в письме сразу упоминалось некое первичное общение и направлено оно было конкретному человеку, правила делового этика предполагают, что они должны ответить, хотя бы формальной отпиской — "спасибо за CV, если что-то интересное будет — мы с вами свяжемся". Так что don't be evil, Google, буду ждать ;)

UPDATE2:

Через полторы недели ко мне вернулись пообщаться, так что Google не evil. В качестве комментария — похоже они не только смотрят на занятое место, но и на постояноство результатов — т.е. попадание в определённую группу (видимо те самые 3,000) два года подряд. Всем удачи и (кто этого хочет) писем от Гугла. :)

Я временно перестал участвовать в соревнованиях по "личным обстоятельствам", но продолжаю урывками прорешивать задачки на разных сайтах. Напоролся на задачку (точнее мой генератор случайных чисел напоролся на задачку) 8843 Complete the Set.

Честно говоря ничего в голову не приходит — судя по параметрам задачи — 1100 случаев в одном тесте, 65536 чисел в одном сете — полный перебор вряд ли пройдёт, я имею в виду каждое число с каждым пробовать по OR и AND пока не перестанут появляться новые числа. (хотя бы понятно, что в такой ситуации не надо пробовать что-то большее, чем пары чисел — уже прогресс от "absolute brute force").

Но в голове вертится одна из недавних задачек с Topcoder, где нужно было смешивать краски с помощью XOR и решалась она элегантно гауссовой элиминацией — может быть и здесь какая-нибудь хитрость?

Задачка не очень порешенная, "запылившаяся", решило её меньше 50 человек и разборов в интернете я не нашёл. Если знаете как решать, подскажите только идею — в какую сторону копать.

Большое спасибо!

Совсем недавно — всего лишь неделю назад — началось новое соревнование на сайте Al Zimmermann's Programming Contests

Так как я недавное решил переключится на C++ для использования в соревнованиях, хотелось бы сказать пару слов на эту тему:

• "скриптовые" языки, к которым принадлежит Python, сейчас очень активно используются при разработке приложений для Web. Никто не отбирает лавры самого крутого языка для выжимания максимум из железа у C/C++, но, в то же время, говорить, что языки типа Python, Ruby, PHP и прочих — это такое развлечение для тех, кто на самом деле программировать не умеет — тоже неправильно. А это именно то сообщение, котороые посылают контесты, где с этими языками расситывать не на что.

• Конкретно о Russian Code Cup — проводится под эгидой Mail.ru. Представители Mail.ru, скажите мне, в этой компании всё, что разрабатывается пишется только на Java и C++? или ещё что-то используется? Кажется несколько странным, что в России программируют только на этих двух языках (если не это имелось в виду, то почему название — Russian Code Cup, а не Russian C++ and Java Code Cup ?)

• хорошему программисту наплевать на язык — он читает документацию и пишет на любом — я с этой формулировкой по большей части согласен, поэтому и переключаюсь на С++. Посмотрим, насколько я хороший программист. Пока моя надежда — добраться до уровня рейтингов в 2000, когда я пообвыкнусь и поучаствую в большем количестве сорвенований.

• разница между языками типа C++ и Python большая, но ... константа. Насколько оправданы те лимиты, которые устаналиваются для программ на C++? Конкретно для Russian Code Cup, задачка про трёхцветные шахматы — максимальный размер доски — 14*50. При таком размере хорошее решение на С++ требует 0.4 секунды, хорошее решение на Python — 11 секунд. Если убавить размер до 12*50, Python начнёт умещаться в 2 секунды. Существуют ли какие-то "неправильные", brute force решения на C++, которые могут покрыть поле в 12*50 за две секунды? Сомневаюсь. Обычно в соревнованиях идёт речь о экспоненциальной или как минимум в несколько степеней разнице между правильным и неправильным решением. В такой ситуации разница между Python и C++ не принципиальна.

В общем, не хочу разводить "Питон срач", но просто хотелось выговориться. Думаю, что роль скриптовых языков будет постепенно расти, а системных — оставаться на одном уровне, так что в какой-то момент надо будет принимать решение о том, как сделать соревнования доступными для всех. В соревнованиях, где не важна чистая скорость исполнения — типа того же Google Code Jam, Python уже потихоньку приближается к Java в схватке за второе место по использованию.

Если у кого-нибудь есть мысли по этому поводу — приглашаю к вежливому диалогу.

Вчера и сегодня пытался установить C++ под Windows. Попробовал три пакета, ни в одном не удалось добиться того, что мне нужно. Нужно мне совсем немного — Win32 Console Application, возможность подсовывать файл в stdin, и чтобы всё работало без проблем.

Eclipse Начал с Eclipse, так как пользую её для Python. Нашёл некий СDT C++ для Eclipse, установил. Компилятор в пакет не входил — начал искать компилятор. Вспомнил, что когда-то давно устанавливал Visual Studio — но не смог найти его у себя на диске. Почитал про GCC — не захотелось сразу заморачиваться с установкой MinGW, поэтому следующим пунктом стала установка Visual Studio Express.

Visual Studio Express Установил, выбираю новый проект -> C++. Вылезает список шаблонов. Вижу незнакомое слово XAML и кучу шаблонов про Windows Phone, Windows Tile Application и прочие навороты. Набираю в поиске Win32 Console Application — не найдено. Там есть ссылка на "магазин шаблонов" — захожу туда, опять ищу Win32 Console app — никакого эффекта. Попробовал один из имеющихся шаблонов — объём кода после нажатия ОК сразу превысил что-либо, что я когда-то писал на C++. Испугался.

Попытлся прикрутить микрософтовский компилятор к Eclipse — не получилось. Прочитал про Codeblocks — написано типа устанавливаешь и всё сразу работает, плюс в пакет включён компилятор.

Codeblocks

Установил. Попробовал тестовую програмку — работает. Супер. Попытался загнать файл в stdin — никак. Пробовал в Command line arguments писать всё, что только можно — < input.txt (так работает в консоли), < .\input.txt, < C:\полный путь\input.txt — результат ноль. И хотя в заголовке консоли написана вроде бы правильная строка запуска, приложение файл по stdin не видит, хоть умри.

Eclipse Eclipse сам увидел что у меня появился GCC и сам его подключил — меня это порадовало. Попробовал тестовую программу — не найден iostream. Хорошо. Нашёл все заголовочные файлы, прописал в Header paths для компилятора. Ошибка с include исчезла — вроде бы всё видит. Осталась ошибка — и при компиляции она тоже вылезает — undefined function fprint. Мучился долго, пытаясь научить Eclipse этой стандартной функции, но ничего не получилось — уже всё, что относится к C++, все пути где мог прописал, а ошибка никуда не девается.

Что имею в остатке (после где-то пяти часов):

• Eclipse, который не признаёт fprint
• Codeblocks, который работает, но отказывается передавать файлы в stdin
• Microsoft Visual C++ Express, которые не понимает, зачем нужен Win32 Console и хочет чтобы я уже написал что-нибудь для Windows Phone.

Вопрос — может ли кто-нибудь что-нибудь порекомендовать? Я уже начинаю думать, что может быть забить на C++ и тренировать Java — она у меня с самого начала прекрасно работала в Eclipse. Второй вопрос — скажите мне, это я такой тупой, или что-то не то хочу от своего компьютера?

Да — я писал на C++ в 1997-2000 годах, с тех пор "в руки" не брал, потом был период PHP. В 2009-2010 игрался с Objective C++, потом изучал Java, но ничего большого на Java не написал. С 2012 года на Python — но в соревнованиях, где тайм лимит устанавливает в 1 секунд с Python трудно. Поэтому пытаюсь выбрать, к чему мне вернулся — к C++ или Java.