kenneth.cpp

#include <message.h>
#include "kenneth.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int nnodes = NumberOfNodes();
const int nodeid = MyNodeId();

typedef unsigned long long H;
static H C = 123891739; // arbitrary
static H CR = 3985654725013410664ULL; // inverse

// Arithmetic mod 2^64-1. 5x slower than mod 2^64 and more
// code, but works on evil test data (e.g. Thue-Morse).
// typedef H K;
struct K {
	typedef __uint128_t H2;
	H x; K(H x=0) : x(x) {}
	K operator+(K o){ return x + o.x + H(((H2)x + o.x)>>64); }
	K operator*(K o){ return K(x*o.x)+ H(((H2)x * o.x)>>64); }
	H operator-(K o) { K a = *this + ~o.x; return a.x + !~a.x; }
};

vi positions;
int n;
vector<int> active1;
vector<int> active2;
vector<H> fwdHashes, revHashes;
set<int> hasSentTo;
int myBasePos, myEndPos;
int totalLength;

struct Work {
	bool done = false;
	vi remaining;
	vector<H> myhashes;
	int size;
	int pos;
	bool rev;
	int dataUsed = 0;
	int iter = 0;
	int otherParty;
	int sent = 0, received = 0;

	Work(int pos, int rev) : pos(pos), rev(rev) {
		size = positions[pos+1] - positions[pos];
		otherParty = rev ? active1[pos] : active2[pos];
		rep(i,positions[pos], positions[pos+1]) {
			if (rev)
				myhashes.push_back(revHashes[myEndPos-myBasePos-1 - (totalLength-1 - i - myBasePos)]);
			else
				myhashes.push_back(fwdHashes[i - myBasePos]);
		}
		rep(i,0,size) remaining.push_back(i);
	}

	void prework() {
		if (done) return;
		if (iter == 6) {
			trav(i, remaining) {
				PutLL(otherParty, myhashes[i]);
			}
		}
		else {
			int ind = 0;
			H chunk = 0;
			trav(i, remaining) {
				bool bit = myhashes[i] & (1ULL << (63 - iter));
				if (bit) chunk |= 1ULL << ind;
				ind++;
				if (ind == 64) {
					PutLL(otherParty, chunk);
					ind = 0;
					chunk = 0;
					sent++;
				}
				dataUsed++;
			}
			PutLL(otherParty, chunk);
			sent++;
		}
		hasSentTo.insert(otherParty);
	}

	void postwork() {
		if (done) return;
		vi rem2;
		if (iter == 6) {
			trav(i, remaining) {
				if ((H)GetLL(otherParty) == myhashes[i])
					rem2.push_back(i);
			}
			done = true;
		}
		else {
			int ind = 0;
			H chunk = GetLL(otherParty);
			received++;
			trav(i, remaining) {
				bool bit = myhashes[i] & (1ULL << (63 - iter));
				bool recvBit = chunk & (1ULL << ind);
				if (bit == recvBit) rem2.push_back(i);
				ind++;
				if (ind == 64) {
					chunk = GetLL(otherParty);
					received++;
					ind = 0;
				}
			}
			assert(sent == received);
			sent = received = 0;
			if (dataUsed + (iter == 5 ? sz(rem2) * 64 : 0) > size * 3.8 + 7000) {
				// There are short cycles, quit to avoid sending too much data
				done = true;
			}

			iter++;
		}
		remaining = move(rem2);
		if (remaining.empty()) done = true;
	}
};

int main() {
	C = K(C) * C * C - 0; // larger C
	CR = K(CR) * CR * CR - 0;
	assert(K(C) * CR - 0 == 1);
	srand(2);

	int cur = 0;
	set<int> markers;
	markers.insert(0);
	vi before, after, before2, after2;
	rep(i,0,nnodes) {
		before.push_back(cur);
		cur += (int)GetPieceLength(i);
		after.push_back(cur);
		markers.insert(cur);
	}
	myBasePos = before[nodeid];
	myEndPos = after[nodeid];
	totalLength = cur;
	rep(i,0,nnodes) {
		before2.push_back(cur);
		cur -= (int)GetPieceLength(i);
		after2.push_back(cur);
		markers.insert(cur);
	}

	// COMPUTE HASHES

	K h = 0, pw = 1;
	K hR = 0, pwR = 1;
	K beforeH = 0, beforeHR = 0;
	vector<H> localHashes, localHashesR;
	rep(i,myBasePos,myEndPos) {
		h = h * C + GetSignalCharacter(i);
		localHashes.push_back(h - 0);
		pw = pw * C;
	}
	for (int i = myEndPos-1; i >= myBasePos; i--) {
		hR = hR * CR + GetSignalCharacter(i);
		localHashesR.push_back(hR - 0);
		pwR = pwR * CR;
	}

	K cor = 1;
	rep(i,0,nnodes) {
		PutLL(i, h-0);
		PutLL(i, pw-0);
		PutLL(i, hR-0);
		PutLL(i, pwR-0);
		Send(i);
	}
	rep(i,0,nnodes) {
		Receive(i);
		K h2 = GetLL(i);
		K pw2 = GetLL(i);
		if (i < nodeid) {
			beforeH = beforeH * pw2 + h2;
		}
		if (i > nodeid) {
			cor = cor * pw2;
		}
	}
	for (int i = nnodes-1; i >= 0; i--) {
		K hR2 = GetLL(i);
		K pwR2 = GetLL(i);
		if (i > nodeid) {
			beforeHR = beforeHR * pwR2 + hR2;
		}
	}

	pw = K(1);
	pwR = K(1);
	trav(x, localHashes) {
		pw = pw * C;
		x = (beforeH * pw + K(x)) - 0;
	}
	trav(x, localHashesR) {
		pwR = pwR * CR;
		x = (beforeHR * pwR + K(x)) * cor - 0;
		cor = cor * C;
	}

	fwdHashes = localHashes;
	revHashes = localHashesR;

	// END HASHES

	/* rep(i,0,myEndPos-myBasePos)
		cerr << "hash[" << i << "] = " << fwdHashes[i] << endl;
	rep(i,0,myEndPos-myBasePos)
		cerr << "hashr[" << i << "] = " << revHashes[i] << endl; */

	// We want a chunk with only short cycles, which doesn't abort early.
	if (totalLength >= 1000) markers.insert(totalLength - 1000);
	positions.assign(all(markers));

	n = sz(positions) - 1;
	active1.assign(n, -1);
	active2.assign(n, -1);
	rep(i,0,nnodes) {
		int it1 = (int)(find(all(positions), before[i]) - positions.begin());
		int it2 = (int)(find(all(positions), after[i]) - positions.begin());
		rep(j,it1,it2) {
			assert(active1[j] == -1);
			active1[j] = i;
		}
	}
	rep(i,0,nnodes) {
		int it1 = (int)(find(all(positions), after2[i]) - positions.begin());
		int it2 = (int)(find(all(positions), before2[i]) - positions.begin());
		rep(j,it1,it2) {
			assert(active2[j] == -1);
			active2[j] = i;
		}
	}
	trav(x, active1) assert(x != -1);
	trav(x, active2) assert(x != -1);

	vector<Work> myactive;
	myactive.reserve(n*2);
	vector<Work*> myactiveRecv;
	rep(i,0,n) {
		Work *a, *b;
		if (active1[i] == nodeid) myactive.emplace_back(i, 0), a = &myactive.back();
		if (active2[i] == nodeid) myactive.emplace_back(i, 1), b = &myactive.back();
		if (active2[i] == nodeid) myactiveRecv.push_back(b);
		if (active1[i] == nodeid) myactiveRecv.push_back(a);
	}

	for (;;) {
		bool ready = true;
		trav(w, myactive) if (!w.done) ready = false;
		if (ready) break;
		trav(w, myactive) w.prework();
		trav(x, hasSentTo)
			Send(x);
		trav(x, hasSentTo)
			Receive(x);
		hasSentTo.clear();
		trav(w, myactiveRecv) w->postwork();
	}

	int best = totalLength;
	trav(w, myactive) if (!w.rev) {
		trav(x, w.remaining) {
			auto y = totalLength - (x + positions[w.pos] + 1);
			if (y) {
				best = min(best, y);
			}
		}
	}

	PutInt(0, best);
	Send(0);

	if (nodeid == 0) {
		rep(i,0,nnodes) {
			Receive(i);
			best = min(best, GetInt(i));
		}

		cout << best << endl;
	}

	return 0;
}