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

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?

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";

		}

	}
}