QTDDTOB

Revision en2, by Xellos, 2017-06-09 15:38:22

Questions That Don't Deserve Their Own Blog — I guess it'd be good to have something like this as a place to ask random questions about problems ("I accidentally my code, wat do?") without having your blog post get downvotebombed?

old question

Next: I was upsolving DCJ problems during the second practice round (which ended yesterday). The only non-final problem I didn't manage to solve in time was highest_mountain and only because it gives me weird RE.

code

I'm merging O(nodes) small convex hulls of size O(N / nodes) by sending only every K-th point in each hull, merging them in master and sending back the range that remains in the merged convex hull; then, each node sends just the smallest O(N / nodes / K) leftmost or rightmost points of this range to each other node and each node recomputes the convex hull of its own O(N / nodes) points plus all O(N / K) points it got sent.

I proved that this is correct and it passes the small subproblem (with K = 10, nodes = 10, N = 1000), while slightly incorrect implementations don't, so it really should be correct. I also verified that it passes at least one official maxtest, but gives RE later.

The cause of RE should not be too much stuff sent, since each node sends/receives only O(N / K) of data (numerically 2-3 MB, I tried "if this array is too large then return 0" checks and it changed nothing too). The memory limit shouldn't be exceeded too.

Any ideas? Btw don't forget about GCJ/DCJ last online rounds this weekend.

Tags random, programming, questions

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Xellos 2017-06-10 02:26:23 0 Tiny change: 'Questions ' -> ' Questions '
ru2 Russian Xellos 2017-06-09 18:58:33 6144
en2 English Xellos 2017-06-09 15:38:22 6144
en1 English Xellos 2017-05-25 11:47:52 1766 Initial revision for English translation
ru1 Russian Xellos 2017-05-24 18:53:52 1766 Первая редакция (опубликовано)