### Xellos's blog

By Xellos, history, 7 years ago, translation,

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.

• +41

 » 7 years ago, # |   +11 You are missing non-integer solution xi=1/2 of the original problem. It allows to solve KN,N with missing edge using only N points instead of 2(N-1).
•  » » 7 years ago, # ^ |   0 So I can't assume the primal is in integers?
•  » » » 7 years ago, # ^ |   0 No you can't. Dual problem (with real ys) provides only lower bound for integer programming.
•  » » » » 7 years ago, # ^ |   0 BTW, any good source to learn linear programming? :P
 » 7 years ago, # |   0 Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).