ICPC 2020 - K. Space Walls
We have a union of axis-aligned unit cubes. Each robot starts on an exposed unit face, facing along one of the two tangent axis directions of that face, and then keeps moving ``straight'' over the surface. We must fin...
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2020/K-space-walls. Edit
competitive_programming/icpc/2020/K-space-walls/solution.tex to update the written solution and
competitive_programming/icpc/2020/K-space-walls/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
Problem K
Space Walls
Time limit: 15 seconds
Place-Y Technology Corp. plans to launch a new space station soon. The company CEO is known for
being obsessed with perfection. For example, he insists that all the outer surfaces of the space station are
regularly polished and cleaned of what he calls “space debris,” mainly for the station to appear good in
photos. The engineering team tried but failed to convince the CEO that this was not needed. So instead
they developed an innovative technology to maintain the surfaces while minimizing human operations
outside the station. The maintenance is performed by several small robots moving over the space station
surface, just like robotic vacuum cleaners. Before their first flight, Place-Y needs to assess the risks of
collision during the operation of the robots. And this is exactly where you step in.
For the purposes of this problem, we model the space station as a collection of axis-aligned unit cubes
(not necessarily connected). Each robot starts at time t = 0 in the center of an exposed face of one of the
station’s unit cubes (that is, a face which is not shared by a second station cube). The robot is oriented in
one of the four directions parallel to an edge of the cube face. Every time unit, the robot moves straight
ahead to another cube face, possibly pivoting 90 degrees across the space station edges so that it always
maintains contact with the station. Note that if two cubes share an edge, the robot cannot slip between
them (there is no gap).
Figure K.1: Illustration of Sample Input 1. The dots denote starting points of two robots.
Given the layout of the station and starting positions of all the cleaning robots, determine the time of the
earliest collision (if any). The time a collision occurs is either the time unit when two or more robots
are on the interior of the same cube face or the time unit when two robots attempt to swap locations (see
Sample Input 3 for the latter case).
Input
The first line of input contains two integers n and k, where n (1 ≤ n ≤ 100) is the number of regions
describing the space station shape, and k (0 ≤ k ≤ 100) is the number of robots on the surface.
Each of the following n lines contains six integer coordinates x1 , y1 , z1 , x2 , y2 , and z2 (0 ≤ x1 < x2 ≤
106 , 0 ≤ y1 < y2 ≤ 106 , 0 ≤ z1 < z2 ≤ 106 ) describing one region and denoting that all the points
x, y, z satisfying x1 ≤ x ≤ x2 , y1 ≤ y ≤ y2 , z1 ≤ z ≤ z2 are part of the space station. Note that some
unit cubes may be included in more than one region.
Then follow k lines, each describing the starting position of one robot. Such a line contains three
coordinates x, y, and z, and two directions f~ and d. ~ The coordinates specify that the robot starts at a
face of the unit cube (x, y, z) − (x + 1, y + 1, z + 1). The particular face is determined by f~ and the
initial direction of movement is determined by d. ~ Both f~ and d~ are specified by one of the six strings
x+, x−, y+, y−, z+, or z−, where x+ designates the positive direction of the x-axis (1, 0, 0), and so
~ It is guaranteed that the starting cube
on. The axis letter in f~ will be different from the axis letter in d.
belongs to the space station and the given face is an exposed face.
Output
Output the time of the first collision. If there will never be a collision, output ok.
Sample Input 1 Sample Output 1
9 2 44
1 1 1 7 7 7
0 0 0 3 3 3
5 0 0 8 3 3
0 5 0 3 8 3
0 0 5 3 3 8
5 5 0 8 8 3
5 0 5 8 3 8
0 5 5 3 8 8
5 5 5 8 8 8
0 1 0 z- x+
3 5 1 z- y+
Sample Input 2 Sample Output 2
1 3 ok
0 0 0 1 1 1
0 0 0 x+ z+
0 0 0 y+ x+
0 0 0 z- y+
Sample Input 3 Sample Output 3
1 2 0
0 0 0 2 1 1
0 0 0 y+ x+
1 0 0 y+ x-
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
Key Observations
Let the current face normal be on axis $n$ and the current moving direction be on axis $d$. The third axis $a$ is neither $n$ nor $d$. During the whole motion, the coordinate on axis $a$ stays equal to its initial half-integer value. So every robot is confined to one fixed plane $a = c + \tfrac12$.
Intersect the station with that plane. We obtain a union of unit squares on a 2D grid. Every exposed cube face whose normal is orthogonal to axis $a$ becomes one boundary unit edge of this 2D union. Moving straight on the 3D surface is exactly the same as walking along the boundary of this 2D union, one unit edge per time step.
Therefore each robot moves on one directed boundary cycle of one 2D slice. After choosing a fixed orientation of every cycle, the position of a robot is just \[ s + \delta t \pmod L, \] where $L$ is the cycle length, $s$ is the starting offset on the cycle, and $\delta \in \{+1,-1\}$ tells whether the robot follows the chosen orientation or the opposite one.
If two robots use the same invariant axis and the same slice, then they can collide only if they are on the same boundary cycle. If their invariant axes are different, then they can never swap locations; they can only meet on a common face.
Algorithm
1. Build only the slices that are actually needed
The invariant axis and slice coordinate of a robot are determined by its input face normal and initial moving direction. There are at most $k$ distinct slices, so we build only those.
For one fixed slice:
Take all station boxes intersecting that slice.
Project them onto the slice plane.
Coordinate-compress the rectangle borders on the two slice axes.
Mark the occupied compressed cells.
2. Extract directed boundary cycles
For every occupied compressed cell, each side adjacent to empty space contributes one directed primitive boundary edge. The direction is chosen so that the occupied cell lies on the left side of the edge.
At the end of a directed edge, the next edge on the same contour is found by the usual left-hand rule: try left, then straight, then right, then back. This decomposes all primitive edges into disjoint directed cycles.
Along each cycle we merge consecutive collinear primitive edges into one segment and store:
its direction,
the exposed face normal represented by this segment,
its coordinate interval,
its prefix length on the cycle.
3. Map every starting robot state to a cycle position
The starting face is one unit sub-edge of exactly one segment in its slice. Hence we can determine:
which cycle contains the robot,
the cycle length $L$,
the starting index $s$ of its current face on that cycle,
whether its motion agrees with the stored cycle orientation ($\delta = +1$) or not ($\delta = -1$).
4. Check every pair of robots
Same invariant axis and same slice.
They can interact only on the same cycle.
If the cycle is the same, then the face occupied by robot $i$ at time $t$ is \[ p_i(t) \equiv s_i + \delta_i t \pmod L. \]
Same-face collision: solve \[ s_1 + \delta_1 t \equiv s_2 + \delta_2 t \pmod L. \]
Swap collision: this is possible only when $\delta_1 = -\delta_2$. Then robot $2$ must be exactly one step ahead of robot $1$ along robot $1$'s moving direction: \[ p_2(t) - p_1(t) \equiv \delta_1 \pmod L. \]
Both are linear congruences in one variable.
Different invariant axes.
Assume robot $A$ uses axis $a$ and robot $B$ uses axis $b$, and let $c$ be the third axis. They can meet only on faces orthogonal to axis $c$.
For a fixed robot, a cycle segment representing such faces runs along the other robot's invariant axis, so after fixing the other robot's slice coordinate, that whole segment contributes at most one candidate face.
For robot $A$, scan all its cycle segments and collect all candidate common faces into a hash map: \[ (\text{plane coordinate on axis } c,\ \text{sign of the normal}) \mapsto \text{time residue modulo } L_A. \] Do the same scan for robot $B$; whenever the same face appears in both scans, solve the two congruences \[ t \equiv r_A \pmod{L_A}, \qquad t \equiv r_B \pmod{L_B} \] with CRT and keep the smallest solution.
Correctness Proof
We prove that the algorithm returns the earliest collision time.
Lemma 1.
For any robot, the coordinate on exactly one axis stays constant during the whole motion.
Proof.
At every step, the current face normal axis and the current moving axis are two different coordinate axes. The robot always moves over an edge shared by those two directions, so the third axis is not involved in the motion. When the robot continues onto the next face, both the old face center and the new face center still have the same half-integer coordinate on that third axis. Thus that coordinate is invariant forever. □
Lemma 2.
Inside one fixed slice plane, the robot motion is exactly a walk along a boundary cycle of the 2D cross-section, moving one boundary unit edge per time step.
Proof.
Consider the intersection of the station with the invariant slice plane from Lemma 1. Every cube cut by the plane contributes one unit square, so the cross-section is a union of grid squares. An exposed 3D face orthogonal to the slice plane becomes a boundary unit edge of this union.
Now inspect one robot step locally near the crossed cube edge. In the slice plane, this step is precisely the transition from one boundary unit edge to the next boundary unit edge of the cross-section contour. The ``cannot slip between cubes'' rule is exactly the statement that the walk follows the geometric boundary of the occupied region, not a nonexistent gap through it. Therefore the robot walks along one boundary cycle, one unit edge per time step. □
Lemma 3.
After fixing an orientation of a boundary cycle, a robot on that cycle occupies position $s + \delta t \pmod L$ at time $t$ for some constants $s$, $\delta \in \{+1,-1\}$ and cycle length $L$.
Proof.
By Lemma 2 the robot advances by exactly one boundary unit edge per time step on one cycle of length $L$. If the chosen cycle orientation matches the robot's actual traversal direction, the offset increases by $1$ each step; otherwise it decreases by $1$ each step. Hence the formula follows. □
Lemma 4.
For two robots on the same slice, the algorithm finds exactly all same-face and swap collisions between them.
Proof.
Different boundary cycles of the same slice correspond to disjoint sets of exposed faces, so only robots on the same cycle can interact. For robots on one common cycle, Lemma 3 gives explicit formulas for both positions as functions of time.
A same-face collision happens exactly when the two formulas are equal modulo $L$, which is the first congruence solved by the algorithm.
A swap collision on one cycle happens exactly when, at time $t$, robot $2$ occupies the unique neighboring cycle edge that robot $1$ will enter at time $t+1$. That is exactly the second congruence used by the algorithm. So every and only valid same-slice collision is detected. □
Lemma 5.
For two robots with different invariant axes, the algorithm finds exactly all collisions between them.
Proof.
Such robots move in different slice planes, so a swap is impossible: one step between adjacent faces is always contained in a single slice plane. Therefore only same-face collisions matter.
Let the invariant axes be $a$ and $b$, and let $c$ be the third axis. Any common face must be orthogonal to axis $c$, because that is the only face type lying in both slice planes. For each robot, every relevant cycle segment yields at most one such face after fixing the other robot's slice coordinate. The algorithm enumerates precisely those faces and computes, via Lemma 3, the unique time residue modulo the robot's period when that face is occupied.
Thus a collision on a particular common face exists exactly when the two residues are compatible, which is exactly what the CRT check tests. Therefore the algorithm finds every and only valid cross-slice collision. □
Theorem.
The algorithm outputs the earliest collision time, or ok if no collision ever occurs.
Proof.
By Lemmas 4 and 5, for every pair of robots the algorithm enumerates exactly all collision times involving that pair and keeps the smallest one. Any collision among several robots contains at least one colliding pair, so the minimum over all pairs is the global earliest collision time. If no pair yields a collision time, then no collision ever occurs, so ok is correct. □
Complexity Analysis
Let $S$ be the number of distinct slices used by the robots; clearly $S \le k$.
For one slice, there are at most $2n$ compressed coordinates on each slice axis, hence $O(n^2)$ compressed cells and $O(n^2)$ primitive boundary edges. Building one slice with the straightforward marking used in the implementation takes $O(n^3)$ time in the worst case and $O(n^2)$ memory.
For one pair of robots, checking collisions scans only the segments on their own cycles, which is $O(n^2)$ in the worst case.
Therefore the total complexity is \[ O(Sn^3 + k^2 n^2) \] time and \[ O(n^2) \] memory per slice. With $n,k \le 100$, this easily fits.
Implementation Notes
The cycle lengths can be large, and the CRT may combine two periods, so use 64-bit integers.
Boundary edges are directed so that occupied area stays on the left; this makes the successor rule uniform.
In the cross-slice case, the key of a common face is just \[ (\text{coordinate of the plane orthogonal to the third axis},\ \text{sign of the normal}), \] because the two slice coordinates are already fixed by the robot pair.
Code
Exact copied C++ implementation from solution.cpp.
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr long long INF64 = (1LL << 62);
struct AxisDir {
int axis;
int sign;
};
struct Box {
int lo[3];
int hi[3];
};
struct RobotInput {
int cube[3];
AxisDir face;
AxisDir move;
};
long long mod_norm(long long x, long long mod) {
x %= mod;
if (x < 0) {
x += mod;
}
return x;
}
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) {
x = (a >= 0 ? 1 : -1);
y = 0;
return llabs(a);
}
long long x1 = 0, y1 = 0;
long long g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
bool solve_linear_congruence(long long a, long long b, long long mod, long long& result) {
a = mod_norm(a, mod);
b = mod_norm(b, mod);
long long x = 0, y = 0;
long long g = ext_gcd(a, mod, x, y);
if (b % g != 0) {
return false;
}
long long a2 = a / g;
long long b2 = b / g;
long long mod2 = mod / g;
long long inv = mod_norm(x, mod2);
(void)a2;
result = mod_norm(inv * b2, mod2);
return true;
}
bool crt_two(long long r1, long long m1, long long r2, long long m2, long long& result) {
if (m1 == 0 || m2 == 0) {
return false;
}
long long x = 0, y = 0;
long long g = ext_gcd(m1, m2, x, y);
long long diff = r2 - r1;
if (diff % g != 0) {
return false;
}
long long mod2 = m2 / g;
long long mult = (diff / g) * mod_norm(x, mod2);
long long k = mult % mod2;
if (k < 0) {
k += mod2;
}
long long result128 = r1 + m1 * k;
long long lcm = m1 / g * m2;
long long ans = result128 % lcm;
if (ans < 0) {
ans += lcm;
}
result = ans;
return true;
}
AxisDir parse_axis_dir(const string& s) {
AxisDir out{};
if (s[0] == 'x') {
out.axis = 0;
} else if (s[0] == 'y') {
out.axis = 1;
} else {
out.axis = 2;
}
out.sign = (s[1] == '+') ? 1 : -1;
return out;
}
struct Slice {
struct PrimitiveEdge {
int sx = 0;
int sy = 0;
int dir = 0;
long long len = 0;
int normal_axis = -1;
int normal_sign = 0;
};
struct Segment {
int dir = 0;
int run_axis = -1;
int normal_axis = -1;
int normal_sign = 0;
int fixed_coord = 0;
int lo = 0;
int hi = 0;
long long prefix = 0;
long long length() const {
return (long long)hi - lo;
}
};
struct Cycle {
vector<Segment> segs;
long long len = 0;
};
int inv_axis = -1;
int slice_coord = 0;
int p0 = -1;
int p1 = -1;
vector<int> coord0;
vector<int> coord1;
vector<vector<char>> occ;
vector<PrimitiveEdge> edges;
vector<vector<array<int, 4>>> id_at;
vector<int> next_edge;
vector<Cycle> cycles;
static int dir_axis(int dir, int p0, int p1) {
return (dir % 2 == 0) ? p0 : p1;
}
static int dir_sign(int dir) {
return (dir < 2) ? 1 : -1;
}
pair<int, int> edge_end(int sx, int sy, int dir) const {
if (dir == 0) {
return {sx + 1, sy};
}
if (dir == 1) {
return {sx, sy + 1};
}
if (dir == 2) {
return {sx - 1, sy};
}
return {sx, sy - 1};
}
Segment make_segment(const PrimitiveEdge& e) const {
Segment seg;
seg.dir = e.dir;
seg.run_axis = dir_axis(e.dir, p0, p1);
seg.normal_axis = e.normal_axis;
seg.normal_sign = e.normal_sign;
if (e.dir == 0) {
seg.fixed_coord = coord1[e.sy];
seg.lo = coord0[e.sx];
seg.hi = coord0[e.sx + 1];
} else if (e.dir == 1) {
seg.fixed_coord = coord0[e.sx];
seg.lo = coord1[e.sy];
seg.hi = coord1[e.sy + 1];
} else if (e.dir == 2) {
seg.fixed_coord = coord1[e.sy];
seg.lo = coord0[e.sx - 1];
seg.hi = coord0[e.sx];
} else {
seg.fixed_coord = coord0[e.sx];
seg.lo = coord1[e.sy - 1];
seg.hi = coord1[e.sy];
}
return seg;
}
int next_id(int id) const {
const PrimitiveEdge& e = edges[id];
pair<int, int> endp = edge_end(e.sx, e.sy, e.dir);
int ex = endp.first;
int ey = endp.second;
const int order[4] = {(e.dir + 1) & 3, e.dir, (e.dir + 3) & 3, (e.dir + 2) & 3};
for (int nd : order) {
int cand = id_at[ex][ey][nd];
if (cand != -1) {
return cand;
}
}
return -1;
}
};
struct Robot {
int inv_axis = -1;
int slice_coord = 0;
int cycle_id = -1;
long long period = 0;
long long start_index = 0;
int dir_sign = 0;
const Slice* slice = nullptr;
};
Slice build_slice(const vector<Box>& boxes, int inv_axis, int slice_coord) {
Slice sl;
sl.inv_axis = inv_axis;
sl.slice_coord = slice_coord;
vector<int> plane_axes;
for (int axis = 0; axis < 3; ++axis) {
if (axis != inv_axis) {
plane_axes.push_back(axis);
}
}
sl.p0 = plane_axes[0];
sl.p1 = plane_axes[1];
struct Rect {
int u1, u2, v1, v2;
};
vector<Rect> rects;
for (const Box& box : boxes) {
if (box.lo[inv_axis] <= slice_coord && slice_coord < box.hi[inv_axis]) {
rects.push_back({box.lo[sl.p0], box.hi[sl.p0], box.lo[sl.p1], box.hi[sl.p1]});
sl.coord0.push_back(box.lo[sl.p0]);
sl.coord0.push_back(box.hi[sl.p0]);
sl.coord1.push_back(box.lo[sl.p1]);
sl.coord1.push_back(box.hi[sl.p1]);
}
}
sort(sl.coord0.begin(), sl.coord0.end());
sl.coord0.erase(unique(sl.coord0.begin(), sl.coord0.end()), sl.coord0.end());
sort(sl.coord1.begin(), sl.coord1.end());
sl.coord1.erase(unique(sl.coord1.begin(), sl.coord1.end()), sl.coord1.end());
const int w = (int)sl.coord0.size();
const int h = (int)sl.coord1.size();
sl.occ.assign(max(0, w - 1), vector<char>(max(0, h - 1), 0));
for (const Rect& rect : rects) {
int i1 = (int)(lower_bound(sl.coord0.begin(), sl.coord0.end(), rect.u1) - sl.coord0.begin());
int i2 = (int)(lower_bound(sl.coord0.begin(), sl.coord0.end(), rect.u2) - sl.coord0.begin());
int j1 = (int)(lower_bound(sl.coord1.begin(), sl.coord1.end(), rect.v1) - sl.coord1.begin());
int j2 = (int)(lower_bound(sl.coord1.begin(), sl.coord1.end(), rect.v2) - sl.coord1.begin());
for (int i = i1; i < i2; ++i) {
for (int j = j1; j < j2; ++j) {
sl.occ[i][j] = 1;
}
}
}
sl.id_at.assign(w, vector<array<int, 4>>(h));
for (int i = 0; i < w; ++i) {
for (int j = 0; j < h; ++j) {
sl.id_at[i][j].fill(-1);
}
}
auto add_edge = [&](int sx, int sy, int dir, long long len, int normal_axis, int normal_sign) {
Slice::PrimitiveEdge e;
e.sx = sx;
e.sy = sy;
e.dir = dir;
e.len = len;
e.normal_axis = normal_axis;
e.normal_sign = normal_sign;
int id = (int)sl.edges.size();
sl.edges.push_back(e);
sl.id_at[sx][sy][dir] = id;
};
for (int i = 0; i + 1 < w; ++i) {
for (int j = 0; j + 1 < h; ++j) {
if (!sl.occ[i][j]) {
continue;
}
if (j == 0 || !sl.occ[i][j - 1]) {
add_edge(i, j, 0, (long long)sl.coord0[i + 1] - sl.coord0[i], sl.p1, -1);
}
if (i + 1 == w - 1 || !sl.occ[i + 1][j]) {
add_edge(i + 1, j, 1, (long long)sl.coord1[j + 1] - sl.coord1[j], sl.p0, +1);
}
if (j + 1 == h - 1 || !sl.occ[i][j + 1]) {
add_edge(i + 1, j + 1, 2, (long long)sl.coord0[i + 1] - sl.coord0[i], sl.p1, +1);
}
if (i == 0 || !sl.occ[i - 1][j]) {
add_edge(i, j + 1, 3, (long long)sl.coord1[j + 1] - sl.coord1[j], sl.p0, -1);
}
}
}
sl.next_edge.assign(sl.edges.size(), -1);
for (int id = 0; id < (int)sl.edges.size(); ++id) {
sl.next_edge[id] = sl.next_id(id);
}
vector<char> vis(sl.edges.size(), 0);
for (int start = 0; start < (int)sl.edges.size(); ++start) {
if (vis[start]) {
continue;
}
vector<int> path;
int cur = start;
while (!vis[cur]) {
vis[cur] = 1;
path.push_back(cur);
cur = sl.next_edge[cur];
}
Slice::Cycle cyc;
for (int id : path) {
const auto& e = sl.edges[id];
Slice::Segment seg = sl.make_segment(e);
if (!cyc.segs.empty()) {
Slice::Segment& last = cyc.segs.back();
if (last.dir == seg.dir && last.normal_axis == seg.normal_axis &&
last.normal_sign == seg.normal_sign && last.fixed_coord == seg.fixed_coord) {
last.lo = min(last.lo, seg.lo);
last.hi = max(last.hi, seg.hi);
continue;
}
}
cyc.segs.push_back(seg);
}
long long pref = 0;
for (auto& seg : cyc.segs) {
seg.prefix = pref;
pref += seg.length();
}
cyc.len = pref;
sl.cycles.push_back(move(cyc));
}
return sl;
}
long long unit_offset_on_segment(const Slice::Segment& seg, int lower_coord) {
if (seg.dir == 0 || seg.dir == 1) {
return (long long)lower_coord - seg.lo;
}
return (long long)seg.hi - 1 - lower_coord;
}
long long residue_to_face(const Robot& robot, long long face_index) {
if (robot.dir_sign == 1) {
return mod_norm(face_index - robot.start_index, robot.period);
}
return mod_norm(robot.start_index - face_index, robot.period);
}
Robot map_robot(const RobotInput& in, const Slice& sl) {
Robot out;
out.inv_axis = sl.inv_axis;
out.slice_coord = sl.slice_coord;
out.slice = &sl;
int plane_dir = -1;
if (in.move.axis == sl.p0) {
plane_dir = (in.move.sign == 1 ? 0 : 2);
} else {
plane_dir = (in.move.sign == 1 ? 1 : 3);
}
int fixed_coord = in.cube[in.face.axis] + (in.face.sign == 1 ? 1 : 0);
int lower_coord = in.cube[in.move.axis];
for (int cid = 0; cid < (int)sl.cycles.size(); ++cid) {
const auto& cyc = sl.cycles[cid];
for (const auto& seg : cyc.segs) {
if (seg.normal_axis != in.face.axis || seg.normal_sign != in.face.sign) {
continue;
}
if (seg.run_axis != in.move.axis || seg.fixed_coord != fixed_coord) {
continue;
}
if (lower_coord < seg.lo || lower_coord >= seg.hi) {
continue;
}
out.cycle_id = cid;
out.period = cyc.len;
out.start_index = seg.prefix + unit_offset_on_segment(seg, lower_coord);
out.dir_sign = (seg.dir == plane_dir ? 1 : -1);
return out;
}
}
throw runtime_error("Failed to map robot to slice cycle");
}
long long earliest_same_cycle_face(const Robot& a, const Robot& b) {
long long len = a.period;
if (a.dir_sign == b.dir_sign) {
return (a.start_index == b.start_index) ? 0 : INF64;
}
long long t = 0;
return solve_linear_congruence(a.dir_sign - b.dir_sign, b.start_index - a.start_index, len, t)
? t
: INF64;
}
long long earliest_same_cycle_swap(const Robot& a, const Robot& b) {
if (a.dir_sign + b.dir_sign != 0) {
return INF64;
}
long long len = a.period;
long long t = 0;
return solve_linear_congruence(b.dir_sign - a.dir_sign,
a.dir_sign - (b.start_index - a.start_index), len, t)
? t
: INF64;
}
long long earliest_cross_axis_face(const Robot& a, const Robot& b) {
int other = 3 - a.inv_axis - b.inv_axis;
const auto& cyc_a = a.slice->cycles[a.cycle_id];
unordered_map<long long, long long> residues;
residues.reserve(cyc_a.segs.size() * 2 + 1);
for (const auto& seg : cyc_a.segs) {
if (seg.normal_axis != other || seg.run_axis != b.inv_axis) {
continue;
}
if (b.slice_coord < seg.lo || b.slice_coord >= seg.hi) {
continue;
}
long long key = ((long long)seg.fixed_coord << 1) | (seg.normal_sign == 1 ? 1LL : 0LL);
long long idx = seg.prefix + unit_offset_on_segment(seg, b.slice_coord);
residues.emplace(key, residue_to_face(a, idx));
}
long long best = INF64;
const auto& cyc_b = b.slice->cycles[b.cycle_id];
for (const auto& seg : cyc_b.segs) {
if (seg.normal_axis != other || seg.run_axis != a.inv_axis) {
continue;
}
if (a.slice_coord < seg.lo || a.slice_coord >= seg.hi) {
continue;
}
long long key = ((long long)seg.fixed_coord << 1) | (seg.normal_sign == 1 ? 1LL : 0LL);
auto it = residues.find(key);
if (it == residues.end()) {
continue;
}
long long idx = seg.prefix + unit_offset_on_segment(seg, a.slice_coord);
long long rb = residue_to_face(b, idx);
long long t = 0;
if (crt_two(it->second, a.period, rb, b.period, t)) {
best = min(best, t);
}
}
return best;
}
void solve() {
int n = 0, k = 0;
cin >> n >> k;
vector<Box> boxes(n);
for (int i = 0; i < n; ++i) {
for (int axis = 0; axis < 3; ++axis) {
cin >> boxes[i].lo[axis];
}
for (int axis = 0; axis < 3; ++axis) {
cin >> boxes[i].hi[axis];
}
}
vector<RobotInput> input(k);
for (int i = 0; i < k; ++i) {
string fs, ds;
cin >> input[i].cube[0] >> input[i].cube[1] >> input[i].cube[2] >> fs >> ds;
input[i].face = parse_axis_dir(fs);
input[i].move = parse_axis_dir(ds);
}
if (k < 2) {
cout << "ok\n";
return;
}
map<pair<int, int>, int> slice_index;
vector<Slice> slices;
for (const auto& r : input) {
int inv_axis = 3 - r.face.axis - r.move.axis;
int slice_coord = r.cube[inv_axis];
pair<int, int> key = {inv_axis, slice_coord};
if (!slice_index.count(key)) {
int id = (int)slices.size();
slice_index[key] = id;
slices.push_back(build_slice(boxes, inv_axis, slice_coord));
}
}
vector<Robot> robots;
robots.reserve(k);
for (const auto& r : input) {
int inv_axis = 3 - r.face.axis - r.move.axis;
int slice_coord = r.cube[inv_axis];
const Slice& sl = slices[slice_index[{inv_axis, slice_coord}]];
robots.push_back(map_robot(r, sl));
}
long long best = INF64;
for (int i = 0; i < k; ++i) {
for (int j = i + 1; j < k; ++j) {
const Robot& a = robots[i];
const Robot& b = robots[j];
long long cand = INF64;
if (a.inv_axis == b.inv_axis) {
if (a.slice_coord == b.slice_coord && a.slice == b.slice && a.cycle_id == b.cycle_id) {
cand = min(cand, earliest_same_cycle_face(a, b));
cand = min(cand, earliest_same_cycle_swap(a, b));
}
} else {
cand = min(cand, earliest_cross_axis_face(a, b));
}
best = min(best, cand);
}
}
if (best == INF64) {
cout << "ok\n";
} else {
cout << best << '\n';
}
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\title{ICPC World Finals 2020\\K. Space Walls}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
We have a union of axis-aligned unit cubes. Each robot starts on an exposed unit face, facing along one of the
two tangent axis directions of that face, and then keeps moving ``straight'' over the surface. We must find the
earliest time when either
\begin{itemize}[leftmargin=*]
\item two robots are on the same face at an integer time, or
\item two robots move across the same pair of adjacent faces in opposite directions during one time step.
\end{itemize}
\section*{Key Observations}
\begin{itemize}[leftmargin=*]
\item Let the current face normal be on axis $n$ and the current moving direction be on axis $d$.
The third axis $a$ is neither $n$ nor $d$.
During the whole motion, the coordinate on axis $a$ stays equal to its initial half-integer value.
So every robot is confined to one fixed plane $a = c + \tfrac12$.
\item Intersect the station with that plane. We obtain a union of unit squares on a 2D grid.
Every exposed cube face whose normal is orthogonal to axis $a$ becomes one boundary unit edge of this 2D union.
Moving straight on the 3D surface is exactly the same as walking along the boundary of this 2D union, one unit
edge per time step.
\item Therefore each robot moves on one directed boundary cycle of one 2D slice.
After choosing a fixed orientation of every cycle, the position of a robot is just
\[
s + \delta t \pmod L,
\]
where $L$ is the cycle length, $s$ is the starting offset on the cycle, and $\delta \in \{+1,-1\}$ tells whether
the robot follows the chosen orientation or the opposite one.
\item If two robots use the same invariant axis and the same slice, then they can collide only if they are on the
same boundary cycle.
If their invariant axes are different, then they can never swap locations; they can only meet on a common face.
\end{itemize}
\section*{Algorithm}
\subsection*{1. Build only the slices that are actually needed}
The invariant axis and slice coordinate of a robot are determined by its input face normal and initial moving
direction. There are at most $k$ distinct slices, so we build only those.
For one fixed slice:
\begin{enumerate}[leftmargin=*]
\item Take all station boxes intersecting that slice.
\item Project them onto the slice plane.
\item Coordinate-compress the rectangle borders on the two slice axes.
\item Mark the occupied compressed cells.
\end{enumerate}
\subsection*{2. Extract directed boundary cycles}
For every occupied compressed cell, each side adjacent to empty space contributes one directed primitive boundary edge.
The direction is chosen so that the occupied cell lies on the \emph{left} side of the edge.
At the end of a directed edge, the next edge on the same contour is found by the usual left-hand rule:
try \emph{left}, then \emph{straight}, then \emph{right}, then \emph{back}.
This decomposes all primitive edges into disjoint directed cycles.
Along each cycle we merge consecutive collinear primitive edges into one segment and store:
\begin{itemize}[leftmargin=*]
\item its direction,
\item the exposed face normal represented by this segment,
\item its coordinate interval,
\item its prefix length on the cycle.
\end{itemize}
\subsection*{3. Map every starting robot state to a cycle position}
The starting face is one unit sub-edge of exactly one segment in its slice.
Hence we can determine:
\begin{itemize}[leftmargin=*]
\item which cycle contains the robot,
\item the cycle length $L$,
\item the starting index $s$ of its current face on that cycle,
\item whether its motion agrees with the stored cycle orientation ($\delta = +1$) or not ($\delta = -1$).
\end{itemize}
\subsection*{4. Check every pair of robots}
\paragraph{Same invariant axis and same slice.}
They can interact only on the same cycle.
If the cycle is the same, then the face occupied by robot $i$ at time $t$ is
\[
p_i(t) \equiv s_i + \delta_i t \pmod L.
\]
\begin{itemize}[leftmargin=*]
\item Same-face collision: solve
\[
s_1 + \delta_1 t \equiv s_2 + \delta_2 t \pmod L.
\]
\item Swap collision: this is possible only when $\delta_1 = -\delta_2$.
Then robot $2$ must be exactly one step ahead of robot $1$ along robot $1$'s moving direction:
\[
p_2(t) - p_1(t) \equiv \delta_1 \pmod L.
\]
\end{itemize}
Both are linear congruences in one variable.
\paragraph{Different invariant axes.}
Assume robot $A$ uses axis $a$ and robot $B$ uses axis $b$, and let $c$ be the third axis.
They can meet only on faces orthogonal to axis $c$.
For a fixed robot, a cycle segment representing such faces runs along the other robot's invariant axis, so after fixing
the other robot's slice coordinate, that whole segment contributes at most one candidate face.
For robot $A$, scan all its cycle segments and collect all candidate common faces into a hash map:
\[
(\text{plane coordinate on axis } c,\ \text{sign of the normal}) \mapsto \text{time residue modulo } L_A.
\]
Do the same scan for robot $B$; whenever the same face appears in both scans, solve the two congruences
\[
t \equiv r_A \pmod{L_A}, \qquad t \equiv r_B \pmod{L_B}
\]
with CRT and keep the smallest solution.
\section*{Correctness Proof}
We prove that the algorithm returns the earliest collision time.
\paragraph{Lemma 1.}
For any robot, the coordinate on exactly one axis stays constant during the whole motion.
\paragraph{Proof.}
At every step, the current face normal axis and the current moving axis are two different coordinate axes.
The robot always moves over an edge shared by those two directions, so the third axis is not involved in the motion.
When the robot continues onto the next face, both the old face center and the new face center still have the same
half-integer coordinate on that third axis. Thus that coordinate is invariant forever. \qed
\paragraph{Lemma 2.}
Inside one fixed slice plane, the robot motion is exactly a walk along a boundary cycle of the 2D cross-section, moving
one boundary unit edge per time step.
\paragraph{Proof.}
Consider the intersection of the station with the invariant slice plane from Lemma~1.
Every cube cut by the plane contributes one unit square, so the cross-section is a union of grid squares.
An exposed 3D face orthogonal to the slice plane becomes a boundary unit edge of this union.
Now inspect one robot step locally near the crossed cube edge.
In the slice plane, this step is precisely the transition from one boundary unit edge to the next boundary unit edge of
the cross-section contour.
The ``cannot slip between cubes'' rule is exactly the statement that the walk follows the geometric boundary of the
occupied region, not a nonexistent gap through it.
Therefore the robot walks along one boundary cycle, one unit edge per time step. \qed
\paragraph{Lemma 3.}
After fixing an orientation of a boundary cycle, a robot on that cycle occupies position
$s + \delta t \pmod L$ at time $t$ for some constants $s$, $\delta \in \{+1,-1\}$ and cycle length $L$.
\paragraph{Proof.}
By Lemma~2 the robot advances by exactly one boundary unit edge per time step on one cycle of length $L$.
If the chosen cycle orientation matches the robot's actual traversal direction, the offset increases by $1$ each step;
otherwise it decreases by $1$ each step. Hence the formula follows. \qed
\paragraph{Lemma 4.}
For two robots on the same slice, the algorithm finds exactly all same-face and swap collisions between them.
\paragraph{Proof.}
Different boundary cycles of the same slice correspond to disjoint sets of exposed faces, so only robots on the same
cycle can interact.
For robots on one common cycle, Lemma~3 gives explicit formulas for both positions as functions of time.
A same-face collision happens exactly when the two formulas are equal modulo $L$, which is the first congruence solved
by the algorithm.
A swap collision on one cycle happens exactly when, at time $t$, robot $2$ occupies the unique neighboring cycle edge
that robot $1$ will enter at time $t+1$.
That is exactly the second congruence used by the algorithm.
So every and only valid same-slice collision is detected. \qed
\paragraph{Lemma 5.}
For two robots with different invariant axes, the algorithm finds exactly all collisions between them.
\paragraph{Proof.}
Such robots move in different slice planes, so a swap is impossible: one step between adjacent faces is always contained
in a single slice plane.
Therefore only same-face collisions matter.
Let the invariant axes be $a$ and $b$, and let $c$ be the third axis.
Any common face must be orthogonal to axis $c$, because that is the only face type lying in both slice planes.
For each robot, every relevant cycle segment yields at most one such face after fixing the other robot's slice
coordinate. The algorithm enumerates precisely those faces and computes, via Lemma~3, the unique time residue modulo the
robot's period when that face is occupied.
Thus a collision on a particular common face exists exactly when the two residues are compatible, which is exactly what
the CRT check tests. Therefore the algorithm finds every and only valid cross-slice collision. \qed
\paragraph{Theorem.}
The algorithm outputs the earliest collision time, or \texttt{ok} if no collision ever occurs.
\paragraph{Proof.}
By Lemmas~4 and~5, for every pair of robots the algorithm enumerates exactly all collision times involving that pair and
keeps the smallest one. Any collision among several robots contains at least one colliding pair, so the minimum over all
pairs is the global earliest collision time. If no pair yields a collision time, then no collision ever occurs, so
\texttt{ok} is correct. \qed
\section*{Complexity Analysis}
Let $S$ be the number of distinct slices used by the robots; clearly $S \le k$.
For one slice, there are at most $2n$ compressed coordinates on each slice axis, hence $O(n^2)$ compressed cells and
$O(n^2)$ primitive boundary edges.
Building one slice with the straightforward marking used in the implementation takes $O(n^3)$ time in the worst case
and $O(n^2)$ memory.
For one pair of robots, checking collisions scans only the segments on their own cycles, which is $O(n^2)$ in the worst
case.
Therefore the total complexity is
\[
O(Sn^3 + k^2 n^2)
\]
time and
\[
O(n^2)
\]
memory per slice.
With $n,k \le 100$, this easily fits.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item The cycle lengths can be large, and the CRT may combine two periods, so use 64-bit integers.
\item Boundary edges are directed so that occupied area stays on the left; this makes the successor rule uniform.
\item In the cross-slice case, the key of a common face is just
\[
(\text{coordinate of the plane orthogonal to the third axis},\ \text{sign of the normal}),
\]
because the two slice coordinates are already fixed by the robot pair.
\end{itemize}
\end{document}
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr long long INF64 = (1LL << 62);
struct AxisDir {
int axis;
int sign;
};
struct Box {
int lo[3];
int hi[3];
};
struct RobotInput {
int cube[3];
AxisDir face;
AxisDir move;
};
long long mod_norm(long long x, long long mod) {
x %= mod;
if (x < 0) {
x += mod;
}
return x;
}
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) {
x = (a >= 0 ? 1 : -1);
y = 0;
return llabs(a);
}
long long x1 = 0, y1 = 0;
long long g = ext_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
bool solve_linear_congruence(long long a, long long b, long long mod, long long& result) {
a = mod_norm(a, mod);
b = mod_norm(b, mod);
long long x = 0, y = 0;
long long g = ext_gcd(a, mod, x, y);
if (b % g != 0) {
return false;
}
long long a2 = a / g;
long long b2 = b / g;
long long mod2 = mod / g;
long long inv = mod_norm(x, mod2);
(void)a2;
result = mod_norm(inv * b2, mod2);
return true;
}
bool crt_two(long long r1, long long m1, long long r2, long long m2, long long& result) {
if (m1 == 0 || m2 == 0) {
return false;
}
long long x = 0, y = 0;
long long g = ext_gcd(m1, m2, x, y);
long long diff = r2 - r1;
if (diff % g != 0) {
return false;
}
long long mod2 = m2 / g;
long long mult = (diff / g) * mod_norm(x, mod2);
long long k = mult % mod2;
if (k < 0) {
k += mod2;
}
long long result128 = r1 + m1 * k;
long long lcm = m1 / g * m2;
long long ans = result128 % lcm;
if (ans < 0) {
ans += lcm;
}
result = ans;
return true;
}
AxisDir parse_axis_dir(const string& s) {
AxisDir out{};
if (s[0] == 'x') {
out.axis = 0;
} else if (s[0] == 'y') {
out.axis = 1;
} else {
out.axis = 2;
}
out.sign = (s[1] == '+') ? 1 : -1;
return out;
}
struct Slice {
struct PrimitiveEdge {
int sx = 0;
int sy = 0;
int dir = 0;
long long len = 0;
int normal_axis = -1;
int normal_sign = 0;
};
struct Segment {
int dir = 0;
int run_axis = -1;
int normal_axis = -1;
int normal_sign = 0;
int fixed_coord = 0;
int lo = 0;
int hi = 0;
long long prefix = 0;
long long length() const {
return (long long)hi - lo;
}
};
struct Cycle {
vector<Segment> segs;
long long len = 0;
};
int inv_axis = -1;
int slice_coord = 0;
int p0 = -1;
int p1 = -1;
vector<int> coord0;
vector<int> coord1;
vector<vector<char>> occ;
vector<PrimitiveEdge> edges;
vector<vector<array<int, 4>>> id_at;
vector<int> next_edge;
vector<Cycle> cycles;
static int dir_axis(int dir, int p0, int p1) {
return (dir % 2 == 0) ? p0 : p1;
}
static int dir_sign(int dir) {
return (dir < 2) ? 1 : -1;
}
pair<int, int> edge_end(int sx, int sy, int dir) const {
if (dir == 0) {
return {sx + 1, sy};
}
if (dir == 1) {
return {sx, sy + 1};
}
if (dir == 2) {
return {sx - 1, sy};
}
return {sx, sy - 1};
}
Segment make_segment(const PrimitiveEdge& e) const {
Segment seg;
seg.dir = e.dir;
seg.run_axis = dir_axis(e.dir, p0, p1);
seg.normal_axis = e.normal_axis;
seg.normal_sign = e.normal_sign;
if (e.dir == 0) {
seg.fixed_coord = coord1[e.sy];
seg.lo = coord0[e.sx];
seg.hi = coord0[e.sx + 1];
} else if (e.dir == 1) {
seg.fixed_coord = coord0[e.sx];
seg.lo = coord1[e.sy];
seg.hi = coord1[e.sy + 1];
} else if (e.dir == 2) {
seg.fixed_coord = coord1[e.sy];
seg.lo = coord0[e.sx - 1];
seg.hi = coord0[e.sx];
} else {
seg.fixed_coord = coord0[e.sx];
seg.lo = coord1[e.sy - 1];
seg.hi = coord1[e.sy];
}
return seg;
}
int next_id(int id) const {
const PrimitiveEdge& e = edges[id];
pair<int, int> endp = edge_end(e.sx, e.sy, e.dir);
int ex = endp.first;
int ey = endp.second;
const int order[4] = {(e.dir + 1) & 3, e.dir, (e.dir + 3) & 3, (e.dir + 2) & 3};
for (int nd : order) {
int cand = id_at[ex][ey][nd];
if (cand != -1) {
return cand;
}
}
return -1;
}
};
struct Robot {
int inv_axis = -1;
int slice_coord = 0;
int cycle_id = -1;
long long period = 0;
long long start_index = 0;
int dir_sign = 0;
const Slice* slice = nullptr;
};
Slice build_slice(const vector<Box>& boxes, int inv_axis, int slice_coord) {
Slice sl;
sl.inv_axis = inv_axis;
sl.slice_coord = slice_coord;
vector<int> plane_axes;
for (int axis = 0; axis < 3; ++axis) {
if (axis != inv_axis) {
plane_axes.push_back(axis);
}
}
sl.p0 = plane_axes[0];
sl.p1 = plane_axes[1];
struct Rect {
int u1, u2, v1, v2;
};
vector<Rect> rects;
for (const Box& box : boxes) {
if (box.lo[inv_axis] <= slice_coord && slice_coord < box.hi[inv_axis]) {
rects.push_back({box.lo[sl.p0], box.hi[sl.p0], box.lo[sl.p1], box.hi[sl.p1]});
sl.coord0.push_back(box.lo[sl.p0]);
sl.coord0.push_back(box.hi[sl.p0]);
sl.coord1.push_back(box.lo[sl.p1]);
sl.coord1.push_back(box.hi[sl.p1]);
}
}
sort(sl.coord0.begin(), sl.coord0.end());
sl.coord0.erase(unique(sl.coord0.begin(), sl.coord0.end()), sl.coord0.end());
sort(sl.coord1.begin(), sl.coord1.end());
sl.coord1.erase(unique(sl.coord1.begin(), sl.coord1.end()), sl.coord1.end());
const int w = (int)sl.coord0.size();
const int h = (int)sl.coord1.size();
sl.occ.assign(max(0, w - 1), vector<char>(max(0, h - 1), 0));
for (const Rect& rect : rects) {
int i1 = (int)(lower_bound(sl.coord0.begin(), sl.coord0.end(), rect.u1) - sl.coord0.begin());
int i2 = (int)(lower_bound(sl.coord0.begin(), sl.coord0.end(), rect.u2) - sl.coord0.begin());
int j1 = (int)(lower_bound(sl.coord1.begin(), sl.coord1.end(), rect.v1) - sl.coord1.begin());
int j2 = (int)(lower_bound(sl.coord1.begin(), sl.coord1.end(), rect.v2) - sl.coord1.begin());
for (int i = i1; i < i2; ++i) {
for (int j = j1; j < j2; ++j) {
sl.occ[i][j] = 1;
}
}
}
sl.id_at.assign(w, vector<array<int, 4>>(h));
for (int i = 0; i < w; ++i) {
for (int j = 0; j < h; ++j) {
sl.id_at[i][j].fill(-1);
}
}
auto add_edge = [&](int sx, int sy, int dir, long long len, int normal_axis, int normal_sign) {
Slice::PrimitiveEdge e;
e.sx = sx;
e.sy = sy;
e.dir = dir;
e.len = len;
e.normal_axis = normal_axis;
e.normal_sign = normal_sign;
int id = (int)sl.edges.size();
sl.edges.push_back(e);
sl.id_at[sx][sy][dir] = id;
};
for (int i = 0; i + 1 < w; ++i) {
for (int j = 0; j + 1 < h; ++j) {
if (!sl.occ[i][j]) {
continue;
}
if (j == 0 || !sl.occ[i][j - 1]) {
add_edge(i, j, 0, (long long)sl.coord0[i + 1] - sl.coord0[i], sl.p1, -1);
}
if (i + 1 == w - 1 || !sl.occ[i + 1][j]) {
add_edge(i + 1, j, 1, (long long)sl.coord1[j + 1] - sl.coord1[j], sl.p0, +1);
}
if (j + 1 == h - 1 || !sl.occ[i][j + 1]) {
add_edge(i + 1, j + 1, 2, (long long)sl.coord0[i + 1] - sl.coord0[i], sl.p1, +1);
}
if (i == 0 || !sl.occ[i - 1][j]) {
add_edge(i, j + 1, 3, (long long)sl.coord1[j + 1] - sl.coord1[j], sl.p0, -1);
}
}
}
sl.next_edge.assign(sl.edges.size(), -1);
for (int id = 0; id < (int)sl.edges.size(); ++id) {
sl.next_edge[id] = sl.next_id(id);
}
vector<char> vis(sl.edges.size(), 0);
for (int start = 0; start < (int)sl.edges.size(); ++start) {
if (vis[start]) {
continue;
}
vector<int> path;
int cur = start;
while (!vis[cur]) {
vis[cur] = 1;
path.push_back(cur);
cur = sl.next_edge[cur];
}
Slice::Cycle cyc;
for (int id : path) {
const auto& e = sl.edges[id];
Slice::Segment seg = sl.make_segment(e);
if (!cyc.segs.empty()) {
Slice::Segment& last = cyc.segs.back();
if (last.dir == seg.dir && last.normal_axis == seg.normal_axis &&
last.normal_sign == seg.normal_sign && last.fixed_coord == seg.fixed_coord) {
last.lo = min(last.lo, seg.lo);
last.hi = max(last.hi, seg.hi);
continue;
}
}
cyc.segs.push_back(seg);
}
long long pref = 0;
for (auto& seg : cyc.segs) {
seg.prefix = pref;
pref += seg.length();
}
cyc.len = pref;
sl.cycles.push_back(move(cyc));
}
return sl;
}
long long unit_offset_on_segment(const Slice::Segment& seg, int lower_coord) {
if (seg.dir == 0 || seg.dir == 1) {
return (long long)lower_coord - seg.lo;
}
return (long long)seg.hi - 1 - lower_coord;
}
long long residue_to_face(const Robot& robot, long long face_index) {
if (robot.dir_sign == 1) {
return mod_norm(face_index - robot.start_index, robot.period);
}
return mod_norm(robot.start_index - face_index, robot.period);
}
Robot map_robot(const RobotInput& in, const Slice& sl) {
Robot out;
out.inv_axis = sl.inv_axis;
out.slice_coord = sl.slice_coord;
out.slice = &sl;
int plane_dir = -1;
if (in.move.axis == sl.p0) {
plane_dir = (in.move.sign == 1 ? 0 : 2);
} else {
plane_dir = (in.move.sign == 1 ? 1 : 3);
}
int fixed_coord = in.cube[in.face.axis] + (in.face.sign == 1 ? 1 : 0);
int lower_coord = in.cube[in.move.axis];
for (int cid = 0; cid < (int)sl.cycles.size(); ++cid) {
const auto& cyc = sl.cycles[cid];
for (const auto& seg : cyc.segs) {
if (seg.normal_axis != in.face.axis || seg.normal_sign != in.face.sign) {
continue;
}
if (seg.run_axis != in.move.axis || seg.fixed_coord != fixed_coord) {
continue;
}
if (lower_coord < seg.lo || lower_coord >= seg.hi) {
continue;
}
out.cycle_id = cid;
out.period = cyc.len;
out.start_index = seg.prefix + unit_offset_on_segment(seg, lower_coord);
out.dir_sign = (seg.dir == plane_dir ? 1 : -1);
return out;
}
}
throw runtime_error("Failed to map robot to slice cycle");
}
long long earliest_same_cycle_face(const Robot& a, const Robot& b) {
long long len = a.period;
if (a.dir_sign == b.dir_sign) {
return (a.start_index == b.start_index) ? 0 : INF64;
}
long long t = 0;
return solve_linear_congruence(a.dir_sign - b.dir_sign, b.start_index - a.start_index, len, t)
? t
: INF64;
}
long long earliest_same_cycle_swap(const Robot& a, const Robot& b) {
if (a.dir_sign + b.dir_sign != 0) {
return INF64;
}
long long len = a.period;
long long t = 0;
return solve_linear_congruence(b.dir_sign - a.dir_sign,
a.dir_sign - (b.start_index - a.start_index), len, t)
? t
: INF64;
}
long long earliest_cross_axis_face(const Robot& a, const Robot& b) {
int other = 3 - a.inv_axis - b.inv_axis;
const auto& cyc_a = a.slice->cycles[a.cycle_id];
unordered_map<long long, long long> residues;
residues.reserve(cyc_a.segs.size() * 2 + 1);
for (const auto& seg : cyc_a.segs) {
if (seg.normal_axis != other || seg.run_axis != b.inv_axis) {
continue;
}
if (b.slice_coord < seg.lo || b.slice_coord >= seg.hi) {
continue;
}
long long key = ((long long)seg.fixed_coord << 1) | (seg.normal_sign == 1 ? 1LL : 0LL);
long long idx = seg.prefix + unit_offset_on_segment(seg, b.slice_coord);
residues.emplace(key, residue_to_face(a, idx));
}
long long best = INF64;
const auto& cyc_b = b.slice->cycles[b.cycle_id];
for (const auto& seg : cyc_b.segs) {
if (seg.normal_axis != other || seg.run_axis != a.inv_axis) {
continue;
}
if (a.slice_coord < seg.lo || a.slice_coord >= seg.hi) {
continue;
}
long long key = ((long long)seg.fixed_coord << 1) | (seg.normal_sign == 1 ? 1LL : 0LL);
auto it = residues.find(key);
if (it == residues.end()) {
continue;
}
long long idx = seg.prefix + unit_offset_on_segment(seg, a.slice_coord);
long long rb = residue_to_face(b, idx);
long long t = 0;
if (crt_two(it->second, a.period, rb, b.period, t)) {
best = min(best, t);
}
}
return best;
}
void solve() {
int n = 0, k = 0;
cin >> n >> k;
vector<Box> boxes(n);
for (int i = 0; i < n; ++i) {
for (int axis = 0; axis < 3; ++axis) {
cin >> boxes[i].lo[axis];
}
for (int axis = 0; axis < 3; ++axis) {
cin >> boxes[i].hi[axis];
}
}
vector<RobotInput> input(k);
for (int i = 0; i < k; ++i) {
string fs, ds;
cin >> input[i].cube[0] >> input[i].cube[1] >> input[i].cube[2] >> fs >> ds;
input[i].face = parse_axis_dir(fs);
input[i].move = parse_axis_dir(ds);
}
if (k < 2) {
cout << "ok\n";
return;
}
map<pair<int, int>, int> slice_index;
vector<Slice> slices;
for (const auto& r : input) {
int inv_axis = 3 - r.face.axis - r.move.axis;
int slice_coord = r.cube[inv_axis];
pair<int, int> key = {inv_axis, slice_coord};
if (!slice_index.count(key)) {
int id = (int)slices.size();
slice_index[key] = id;
slices.push_back(build_slice(boxes, inv_axis, slice_coord));
}
}
vector<Robot> robots;
robots.reserve(k);
for (const auto& r : input) {
int inv_axis = 3 - r.face.axis - r.move.axis;
int slice_coord = r.cube[inv_axis];
const Slice& sl = slices[slice_index[{inv_axis, slice_coord}]];
robots.push_back(map_robot(r, sl));
}
long long best = INF64;
for (int i = 0; i < k; ++i) {
for (int j = i + 1; j < k; ++j) {
const Robot& a = robots[i];
const Robot& b = robots[j];
long long cand = INF64;
if (a.inv_axis == b.inv_axis) {
if (a.slice_coord == b.slice_coord && a.slice == b.slice && a.cycle_id == b.cycle_id) {
cand = min(cand, earliest_same_cycle_face(a, b));
cand = min(cand, earliest_same_cycle_swap(a, b));
}
} else {
cand = min(cand, earliest_cross_axis_face(a, b));
}
best = min(best, cand);
}
}
if (best == INF64) {
cout << "ok\n";
} else {
cout << best << '\n';
}
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}