1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#include <iostream>
#include <cmath>
#include <limits>
#include <vector>

#include "message.h"
#include "kanapka.h" 

////////////////////////////////////////////////////////////////////////////////
// A class for assigning jobs to nodes

class scheduler_t {
protected:
	// Minimum reasonable number of indices per node
	int min_jobs_per_node;

	long long num_jobs;
	int num_used_nodes;
	long long jobs_per_node;

public:
	scheduler_t(long long num_jobs, int num_nodes, int min_jobs_per_node);
	int get_num_used_nodes() const;
	bool is_node_used(int node_id) const;
	std::pair<long long, long long> get_jobs_for_node(int node_id) const;
};

scheduler_t::scheduler_t(long long num_jobs, int num_nodes,
	int min_jobs_per_node) : min_jobs_per_node(std::max(1, min_jobs_per_node)),
		num_jobs(num_jobs) {

	if(num_jobs < min_jobs_per_node) {
		num_used_nodes = 1;
		jobs_per_node = num_jobs;
	} else {
		// At most as many nodes as jobs
		num_used_nodes = std::min(num_jobs, static_cast<long long>(num_nodes));
		// As a result jobs_per_node here is at least 1
		jobs_per_node = num_jobs / num_used_nodes;

		// If the number of jobs per node is smaller than the limit
		if(jobs_per_node < min_jobs_per_node) {
			num_used_nodes = num_jobs / min_jobs_per_node;
			jobs_per_node = num_jobs / num_used_nodes;
		}
	}
}

int scheduler_t::get_num_used_nodes() const {
	return num_used_nodes;
}

bool scheduler_t::is_node_used(int node_id) const {
	return node_id < num_used_nodes;
}

std::pair<long long, long long> scheduler_t::get_jobs_for_node(int node_id) const {
	// Unused node
	if (node_id >= num_used_nodes) {
		return std::make_pair(-1, -1);
	}

	// For the used nodes
	// Distribute the reminder of jobs equaly
	long long rem = num_jobs - jobs_per_node * num_used_nodes;

	long long first;
	long long last;
	if (node_id < rem) {
		first = (jobs_per_node + 1) * node_id;
		last = first + jobs_per_node;
	} else {
		first = (jobs_per_node + 1) * rem + jobs_per_node * (node_id - rem);
		last = first + jobs_per_node - 1;
	}
	
	return std::make_pair(first, last);
}

////////////////////////////////////////////////////////////////////////////////
// A class for assigning jobs to nodes

class result_t {
public:
	long long sum;
	long long min_sum;
	long long max_sum;
	long long max_neg;

	result_t() : sum(0LL), min_sum(0LL), max_sum(0LL), max_neg(0LL) {
	}
	void update(long long val) {
		sum += val;
		min_sum = std::min(min_sum, sum);
		max_sum = std::max(max_sum, sum);
		max_neg = std::min(max_neg, sum - max_sum);
	}
	void update(result_t other) {
		// sum is an ffset for the data from other
		other.min_sum += sum;
		other.max_sum += sum;

		// max_neg can be the one from other...
		max_neg = std::min(max_neg, other.max_neg);
		// ... or can be the difference between other.min_sum and current max
		max_neg = std::min(max_neg, other.min_sum - max_sum);

		// The total sum, min_sum and max_sum after passing other
		sum += other.sum;
		min_sum = std::min(min_sum, other.min_sum);
		max_sum = std::max(max_sum, other.max_sum);
	}
	void send_to_node(int target) const {
		PutLL(target, sum);
		PutLL(target, min_sum);
		PutLL(target, max_sum);
		PutLL(target, max_neg);
		Send(target);
	}
	int receive_from_node(int source) {
		source = Receive(source);
		
		sum = GetLL(source);
		min_sum = GetLL(source);
		max_sum = GetLL(source);
		max_neg = GetLL(source);

		return source;
	}
};

result_t compute_max_neg(int from, int to) {
	result_t result;

	for(int i = from; i <= to; ++i) {
		result.update(GetTaste(i));
	}

	return result;
}

////////////////////////////////////////////////////////////////////////////////
result_t compute_locally(const scheduler_t &sched) {
	// Get indices assigned to this node
	std::pair<int, int> inds = sched.get_jobs_for_node(MyNodeId());

	// Compute the result for the assigne bit
	return compute_max_neg(inds.first, inds.second);
}

void aggregate_results(const scheduler_t &sched, result_t result) {
	// The master node is the last one
	if(MyNodeId() == 0) {
		int num_other_nodes = sched.get_num_used_nodes() - 1;
		// If there are any other nodes
		if(num_other_nodes > 0) {
			// Get storage for aggregating the data from nodes
			std::vector<result_t> aggreg_res(num_other_nodes);
			result_t remote;

			// Get messages from all other nodes
			for(int i = 0; i < num_other_nodes; ++i) {
				// Get a message from any node
				int source = remote.receive_from_node(-1);
				// Node 0 is the current so all other ids need to be decremented
				aggreg_res[--source] = remote;
			}

			// Aggregate results
			for(auto &res : aggreg_res) {
				result.update(res);
			}
		}

		// Print the final result
		std::cout << result.sum - result.max_neg << std::endl;
	}
	// Workers just send their results
	else {
		// Send the local result to the master node
		result.send_to_node(0);
	}
}

////////////////////////////////////////////////////////////////////////////////

void test_sched() {
	if(MyNodeId() == 0) {
		int num_jobs = 0;
		int num_nodes = 0;
		int min_jpn = 0;
		while(num_jobs >=0 && num_nodes >= 0) {
			std::cerr << "********" << std::endl;
			std::cin >> num_jobs >> num_nodes >> min_jpn;

			const scheduler_t sched(num_jobs, num_nodes, min_jpn);
			std::pair<int, int> prev = {-1, -1};
			std::pair<int, int> p;
		
			int i = 0;
			for(; i < sched.get_num_used_nodes(); ++i, prev = p) {
				p = sched.get_jobs_for_node(i);
				std::cerr << i << ") " << p.first << " " << p.second << " "
					<< (p.second - p.first + 1) << std::endl;
				if(p.first != -1 && p.first != prev.second + 1) {
					std::cerr << "Buba!!!!!!!!" << std::endl;
				}
			}
			if(p.second != num_jobs - 1) {
				std::cerr << "Buba!!!!!!!!" << std::endl;
			}
			for(; i < num_nodes; ++i, prev = p) {
				p = sched.get_jobs_for_node(i);
				std::cerr << i << ") " << p.first << " " << p.second << " "
					<< (p.second - p.first + 1) << std::endl;
				if(p.first != -1 || p.second != -1) {
					std::cerr << "Buba!!!!!!!!" << std::endl;
				}
			}
		}
	}
}

int main() {
	// Get a scheduler
	scheduler_t sched(GetN(), NumberOfNodes(), 20);
	
	// test_sched();

	// Unused nodes do nothing
	if(!sched.is_node_used(MyNodeId())) {
		return 0;
	}
	
	result_t result = compute_locally(sched);
	aggregate_results(sched, result);

	return 0;
}