Boxing.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
using namespace std;

typedef long long  int64;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int,int> ii;
typedef string ST;
typedef stringstream SS;

#define Pf	printf
#define	Sf	scanf

#define ep 1e-9
#define CL(a, b)	memset(a, b, sizeof(a))

#define pb	push_back
#define mp	make_pair
#define	SZ(a)	int((a).size())

#define	all(c)	(c).begin(), (c).end()
#define tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

#define	present(x, c)	((c).find(x) != (c).end())		//map & set//
#define	cpresent(x, c)	(find(all(c),x) != (c).end())	//vector & list//

#define forn(i, n)	for(int i = 0; i < n; i++)
#define forab(i, a, b)	for(int i = a; i <= b; i++)
#define rep(i, a, b)	for(int i = a; i>=b; i--)

#define MAX 180001

int a[MAX];

class Boxing
{
public:
	int maxCredit(vector <int> aa, vector <int> b, vector <int> c, vector <int> d, vector <int> e)
	{
		int ret=0;
		CL(a, 0);

		tr(it, aa)	a[*it]++;
		tr(it, b)	a[*it]++;
		tr(it, c)	a[*it]++;
		tr(it, d)	a[*it]++;
		tr(it, e)	a[*it]++;

		forn(i, 10)	Pf("a[%d] = %d, \t", i, a[i]);	

		int l = 0, cnt = 0;
		forn(i, MAX)
		{
			if(!a[i])	continue;
			if(i-l+1 > 1000)
			{
				l = a[i];
				cnt = a[i];
			}
			else
			{
				cnt += a[i];
			}
			if(cnt > 2)
			{
				Pf("Range [%d, %d] = %d", l, i, cnt);
				++ret;
				cnt = 0;
				l = i+1;
			}
		}
				
		return ret;
	}
};

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <int> p1, vector <int> p2, vector <int> p3, vector <int> p4, bool hasAnswer, int p5) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p1.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p1[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p2.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p2[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p3.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p3[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p4.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p4[i];
	}
	cout << "}";
	cout << "]" << endl;
	Boxing *obj;
	int answer;
	obj = new Boxing();
	clock_t startTime = clock();
	answer = obj->maxCredit(p0, p1, p2, p3, p4);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p5 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p5;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <int> p0;
	vector <int> p1;
	vector <int> p2;
	vector <int> p3;
	vector <int> p4;
	int p5;
	
	{
	// ----- test 0 -----
	int t0[] = {1,2,3,4,5,6};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {1,2,3,4,5,6,7};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {1,2,3,4,5,6};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	int t3[] = {0,1,2};
			p3.assign(t3, t3 + sizeof(t3) / sizeof(t3[0]));
	int t4[] = {1,2,3,4,5,6,7,8};
			p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
	p5 = 6;
	all_right = KawigiEdit_RunTest(0, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	int t0[] = {100,200,300,1200,6000};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1.clear() /*{}*/;
	int t2[] = {900,902,1200,4000,5000,6001};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	int t3[] = {0,2000,6002};
			p3.assign(t3, t3 + sizeof(t3) / sizeof(t3[0]));
	int t4[] = {1,2,3,4,5,6,7,8};
			p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
	p5 = 3;
	all_right = KawigiEdit_RunTest(1, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	int t0[] = {5000,6500};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	int t1[] = {6000};
			p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
	int t2[] = {6500};
			p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
	int t3[] = {6000};
			p3.assign(t3, t3 + sizeof(t3) / sizeof(t3[0]));
	int t4[] = {0,5800,6000};
			p4.assign(t4, t4 + sizeof(t4) / sizeof(t4[0]));
	p5 = 1;
	all_right = KawigiEdit_RunTest(2, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// In Olympic boxing, there are five judges who press a button when they think
// that a particular boxer has just landed a punch.  The times of the button
// presses are recorded, and the boxer receives credit for a punch if at least
// three of the judges press their buttons within 1 second of each other. 
// 
// This "algorithm" needs a lot of refinement.  Here is the version that you
// should implement.
// Find the maximum number of disjoint time intervals that can be chosen such that
// each interval is of duration 1 second or less and contains button presses from 
// at least 3 different judges. Two intervals are disjoint if every time within one interval is
// strictly less than every time in the other. We give the boxer credit for one punch during
// each interval.
// 
// The duration of an interval is the amount of time between the instant when it starts and when it
// ends, and a punch may be included in an interval if its recorded time is 
// at the start, end, or in between.
// So, for example, the interval from 1 to 4 has duration 3, and a punch recorded at time 1, 2, 3, or 4
// is in that interval. The intervals 1 to 4 and 5 to 22 are disjoint, but the intervals 1 to 4 and 4 to
// 22 are not disjoint.
// 
// Create a class Boxing that contains a method maxCredit that is given five vector <int>s,
// a, b, c, d, and e, representing the times of the button presses of the five judges
// in milliseconds. The method returns the maximum credits that can be given to the
// boxer.
// 
// 
// 
// DEFINITION
// Class:Boxing
// Method:maxCredit
// Parameters:vector <int>, vector <int>, vector <int>, vector <int>, vector <int>
// Returns:int
// Method signature:int maxCredit(vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> e)
// 
// 
// CONSTRAINTS
// -Each of the five arguments will contain between 0 and 50 elements inclusive.
// -Each element of each of the arguments will be between 0 and 180,000 inclusive.
// -The elements within each of the arguments will be in strictly increasing order.
// 
// 
// EXAMPLES
// 
// 0)
// {1,2,3,4,5,6}
// {1,2,3,4,5,6,7}
// {1,2,3,4,5,6}
// {0,1,2}
// {1,2,3,4,5,6,7,8}
// 
// Returns: 6
// 
// 
// 
//         This match had a fast start, with 6 punches credited in the first 6
//         milliseconds of the match! One way to choose 6 disjoint intervals is
//         to choose  [1,1], [2,2], [3,3], [4,4], [5,5], [6,6] each of which
//         contains button presses from judges a, b, and c.
//         There are three button presses in the time interval from
//         7 through 8, but
//         only from two different judges so no additional credit can be given.
// 
// 
// 
// 1)
// {100,200,300,1200,6000}
// {}
// {900,902,1200,4000,5000,6001}
// {0,2000,6002}
// {1,2,3,4,5,6,7,8}
// 
// Returns: 3
// 
// 
// 
//          One way to form three intervals is [0,1000], [1001,2000], [6000,6002]
// 
// 
// 2)
// {5000,6500}
// {6000}
// {6500}
// {6000}
// {0,5800,6000}
// 
// Returns: 1
// 
// 
//          Any interval that doesn't include 6000 will not have enough button presses,
//          so we can form only one disjoint interval with credit for a punch.
// 
// 
// END KAWIGIEDIT TESTING








//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!