Google Code Jam 2016 Distributed Round 1 B. oops
I’ve got MLE. So I couldn’t advance the round 2. If there was a practice round or I joined the last year’s one, I could…
problem
愚直解のコードが与えられている。 これと等価な処理を高速に実行せよ。
solution
Compute the maximum of the difference of items.
Distribute the ranges into the nodes, calculate max and min in each node, and solve in the master node. $O(N / P)$ where $P$ is the number of nodes.
memo
limits
- The memory limit is often very small.
- The
Send
/Receive
limit is a bit large.
how to test
-Wall
,-D_GLIBCXX_DEBUG
is important.
$ ../dcj-testing-tool/dcj.sh build --source=a.cpp --extra_flags=-Wall,-D_GLIBCXX_DEBUG
$ ../dcj-testing-tool/dcj.sh run --executable=./a --nodes=100 --output=all
header, sample
$ ls *.h
oops.1.h oops.2.h oops.3.h oops.h
$ cat oops.h
#include "oops.1.h"
distribute items into nodes
int l = n *(ll) my_id / nodes;
int r = n *(ll) (my_id + 1) / nodes;
repeat_from (i,l,r) { ... }
or
for (int i = my_id; i < n; i += nodes) { ... }
nodes whose range is empty
if (n <= nodes) {
nodes = n;
if (nodes <= my_id) return 0;
}
implementation
If you use vector<int>
ans sort( ... )
, it causes RE (I think this RE is MLE with std::bad_alloc
).
#include <message.h>
#include "oops.h"
#define MASTER_NODE 0
#include <iostream>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
template <class T> bool setmin(T & l, T const & r) { if (not (r < l)) return false; l = r; return true; }
int main() {
ll nodes = NumberOfNodes();
ll my_id = MyNodeId();
ll n = GetN();
ll l = n * my_id / nodes;
ll r = n * (my_id + 1) / nodes;
ll max_x = GetNumber(0);
ll min_x = GetNumber(0);
repeat_from (i,l,r) {
ll x = GetNumber(i);
setmax(max_x, x);
setmin(min_x, x);
}
PutLL(MASTER_NODE, max_x);
PutLL(MASTER_NODE, min_x);
Send(MASTER_NODE);
if (my_id == MASTER_NODE) {
repeat (node,nodes) {
Receive(node);
setmax(max_x, GetLL(node));
setmin(min_x, GetLL(node));
}
cout << max_x - min_x << endl;
}
return 0;
}