Introduction

This is a walkthrough of the solution to the competitive programming task Kunai from the Asia-Pacific Informatics Olympiad (APIO) 2012 programming competition.

Kunai is one of my favorite competitive programming problems, and since I couldn't find a tutorial for it online, I decided to write one.¹ It is a fairly advanced task that I first encountered as a beginner at an IOI training camp in 2019. I was too inexperienced to solve it at the time, but the problem has stuck with me since.

Problem statement

There are $n$ ninjas on a $w \times h$ grid². Each ninja shoots a kunai³ in some direction: up, down, left, or right. If two kunais are at the same point at the same time, they disappear. Your task is to calculate the total number of grid squares the kunais have passed through after a sufficient amount of time has passed.

Here's a simulation of the first sample input:

First sample input, consisting of $n=5$ ninjas and their kunais.

In the above case, there are five ninjas at distinct positions on the grid, each shooting a kunai. The first pair of kunais collides at time step $t=0.5$ and a second at $t=2$. The last remaining kunai exits the grid from the top without colliding.

Before proceeding, I suggest you take a stab at the problem—it has great subtasks! You can read the task description and submit solutions here.

Solution

At a high level, the solution to the task splits into two main parts. First, we need to be able to efficiently simulate the travel of kunais through the grid, including their collisions. Then, using these flight paths, we need to find the total number of unique squares the kunais have passed through. Note that each square is only counted once even if multiple kunais pass through it.

Here's an animation of the second sample input, showing the flight paths of kunais:

Second sample input, consisting of $n=12$ ninjas and their kunais.

Part one: Finding collisions

First, let's find when each kunai will collide with another. All kunais start from distinct positions and head either up, down, left, or right. Each of them will either collide with another and vanish or exit the grid. To figure out when the paths of two kunais will intersect, let's examine all possible collisions.

All six collision types with relevant lines.

There are six different types of collisions, and all of them require two ninjas to lie on the same line (drawn in light gray) for their kunais to collide. For a horizontal collision, two ninjas need to share the same y-coordinate—for a vertical collision, they need to share the same x-coordinate. For diagonal collisions, ninjas need to share the same value of $x+y$ or $x-y$, depending on the collision type. Although the grid has $\mathcal O(h + w)$ lines in total, only $\mathcal O(n)$ have ninjas on them.

Let's focus on one line specifically, placing all ninjas on the same line, facing either the positive or the negative direction. Here's an example:

Simplified problem setup with $n=22$ ninjas and their kunais on a single line.

Let's call two adjacent kunais facing each other a candidate pair. From the above animation, we see that on a single line, all candidate pairs will eventually collide. Once a candidate pair collides and disappears, neighboring kunais might form a new candidate pair, also bound to collide. We can keep track of these pairs and simulate their collisions in temporal order. After each collision, we check if a new candidate pair is formed and keep track of it.

This process captures all collisions on the line:

1. Find the set of initial candidate pairs.
2. Process the pairs in ascending order of time.
3. At each collision, check if a new candidate pair is formed.
4. Repeat until no pairs remain.

After this loop, any remaining kunai exits the grid without colliding.

Single-line simulation with $n=22$ ninjas and their kunais. Candidate pairs are connected with red lines.

We have an algorithm that works for a single line. Above, we ran the algorithm on a horizontal line, but it works just as well for vertical and diagonal ones. For example, consider the right-moving and up-moving kunais whose starting positions share the same value of $x-y$. We'll order them by $x+y$: moving right increases this value while moving up decreases it. In these coordinates, the kunais behave exactly as they do on the horizontal line.

The ideas from the algorithm can be extended to process collisions on all lines with ninjas. When we consider multiple lines simultaneously, candidate pairs are no longer guaranteed to collide, since either kunai might disappear in an earlier collision on another line.

The final algorithm looks like this:

1. Initialize the set of candidate pairs for all lines.
2. Process the pairs in ascending order of time.
3. At each collision, clean up any invalid pairs and check if new candidate pairs are formed.
4. Repeat until no pairs remain.

Here's a simulation of the final algorithm with active candidate pairs connected with red lines.

Final algorithm with $n=12$ ninjas and their kunais. Candidate pairs connected with red lines.

Again, any remaining kunais exit the grid with no collisions. When a kunai disappears, we need to clean up any active candidate pairs involving it and check whether the neighboring kunais form a new candidate pair.

In the implementation of the above algorithm, we build a balanced binary search tree for each line to efficiently find neighbors when considering new candidate pairs. Furthermore, we use a priority queue data structure for storing candidate pairs, allowing us to quickly find the pair that collides next. There are $\mathcal{O}(n)$ collisions in total, each yielding only a constant number of new candidate pairs, bringing the total time complexity of the first part to $\mathcal{O}(n \log n)$.

Part two: Counting squares

We have found the lifespan of each kunai, so we know where each kunai starts and where it disappears or exits the grid. We have to find out which grid squares the kunais pass through in this process. More formally, we have $n$ line segments and we need to know the number of unique grid squares they intersect with.

This is a variation of a well-known competitive programming problem, and it can be solved with a sweep line algorithm. Before the sweep, we merge overlapping line segments—for both the horizontal and vertical line sets—to avoid double counting. After the deduplication, the answer equals exactly the number of squares covered by horizontal segments, plus the number covered by vertical segments, minus the number covered by both.

We use a sweep line algorithm that processes the following types of events: "horizontal line started", "horizontal line ended", and "vertical line". We proceed in ascending order of x-coordinates and use a segment tree to keep track of "active" horizontal lines—which enables efficiently counting the intersections for each vertical line.

Conclusion

We've covered the main ideas in the full solution to the task Kunai. Carefully implementing these ideas is a tedious task and usually results in an exceptionally long implementation for an olympiad-level task. Nevertheless, I like the way the task combines many key algorithms behind a shockingly simple problem statement.

Implementation

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

const int N = 1 << 18;

int seg_p[N * 2], seg_x[N * 2];

void seg_add(int k, int x) {
	k += N;
	seg_p[k] = (seg_x[k] += x) > 0;
	while (k /= 2)
		seg_p[k] = seg_p[k * 2] + seg_p[k * 2 + 1];
}

int seg_query(int l, int r) {
	int a = 0;

	for (l += N, r += N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1)
			a += seg_p[l++];
		if (r % 2 == 0)
			a += seg_p[r--];
	}

	return a;
}

struct Line {
	int mX, mY;
	int cX, cY;
	int f1, f2;
};

vector<Line> lines{
	{1,  0, 1, -1, 0, 1},
	{-1, 0, 1, -1, 2, 3},
	{1,  0, 1,  1, 0, 3},
	{1,  0, 1,  1, 1, 2},
	{1,  0, 0,  1, 0, 2},
	{0, -1, 1,  0, 1, 3},
};

struct P {
	int m, i;

	auto operator<=>(const P&) const = default;
};

map<int, set<P>> pt[6];

struct Pair {
	int t, i1, i2;

	auto operator<=>(const Pair&) const = default;
};

priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
vector<Pair> events;

struct Event {
	int x, t, y1, y2;

	auto operator<=>(const Event&) const = default;
};

vector<Event> e;

int main() {
	int w, h;
	cin >> w >> h;

	int n;
	cin >> n;

	vector<int> x(n), y(n), d(n);

	for (int i = 0; i < n; ++i) {
		cin >> x[i] >> y[i] >> d[i];
	}

	// Part 1

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 6; ++j) {
			auto a = lines[j];
			if (d[i] == a.f1 || d[i] == a.f2) {
				int m = x[i] * a.mX + y[i] * a.mY;
				int c = x[i] * a.cX + y[i] * a.cY;

				if (j < 4)
					m *= 2;

				pt[j][c].insert({m, i});
			}
		}
	}

	for (int j = 0; j < 6; ++j)
		for (auto& [c, v] : pt[j]) {
			auto p = *begin(v);

			for (auto& u : v)  {
				if (u != p && d[p.i] == lines[j].f1 && d[u.i] == lines[j].f2) {
					int t = u.m - p.m;

					pq.push({t, p.i, u.i});
				}

				p = u;
			}
		}


	vector<int> dead_at(n, -1);

	while (!pq.empty()) {
		events.clear();

		while (!pq.empty() && (events.empty() || pq.top().t == events.back().t)) {
			events.push_back(pq.top());

			if (dead_at[events.back().i1] != -1 || dead_at[events.back().i2] != -1)
				events.pop_back();

			pq.pop();
		}

		for (auto z : events) {
			for (auto i : {z.i1, z.i2}) {
				if (dead_at[i] != -1)
					continue;

				dead_at[i] = z.t;

				for (int j = 0; j < 6; ++j) {
					auto a = lines[j];

					if (d[i] != a.f1 && d[i] != a.f2)
						continue;

					int m = x[i] * a.mX + y[i] * a.mY;
					int c = x[i] * a.cX + y[i] * a.cY;

					if (j < 4)
						m *= 2;

					auto &S = pt[j][c];
					auto it = S.lower_bound({m, 0});

					it = S.erase(it);

					if (it == end(S) || it == begin(S))
						continue;

					auto x1 = *prev(it);
					auto x2 = *it;

					if (d[x1.i] == a.f1 && d[x2.i] == a.f2
						&& dead_at[x1.i] == -1 && dead_at[x2.i] == -1) {
						pq.push({x2.m - x1.m, x1.i, x2.i});
					}
				}
			}
		}
	}

	// Part 2

	for (int i = 0; i < n; ++i) {
		int ex = x[i];
		int ey = y[i];

		int t = dead_at[i] == -1 ? 1e9 : dead_at[i] / 2;

		if (d[i] == 0)
			ex += t;
		if (d[i] == 1)
			ey -= t;
		if (d[i] == 2)
			ex -= t;
		if (d[i] == 3)
			ey += t;

		ex = max(1, min(ex, w));
		ey = max(1, min(ey, h));

		int ox = x[i];
		int oy = y[i];

		if (oy == ey) {
			e.push_back({min(ox, ex),     1, oy, oy});
			e.push_back({max(ox, ex) + 1, 0, oy, oy});
		} else {
			e.push_back({ox, 2, min(ey, oy), max(ey, oy)});
		}
	}

	ranges::sort(e);

	vector<int> yv;
	for (auto &u : e)
		for (auto y : {u.y1, u.y2})
			yv.push_back(y);


	ranges::sort(yv);
	yv.erase(unique(begin(yv), end(yv)), end(yv));

	auto get_y = [&](int y) {
		return lower_bound(begin(yv), end(yv), y) - begin(yv);
	};

	long a = 0;

	for (int i = 0, j = 0, k = 0; i < (int)e.size(); i = j, k = i) {
		while (j < (int)e.size() && e[i].x == e[j].x)
			++j;

		for (; k < j && e[k].t == 0; ++k)
			seg_add(get_y(e[k].y1), -1);
		for (; k < j && e[k].t == 1; ++k)
			seg_add(get_y(e[k].y1), +1);

		for (int maxy = 0; k < j && e[k].t == 2; ++k) {
			int y1 = e[k].y1;
			int y2 = e[k].y2;

			y1 = max(y1, maxy + 1);

			if (y1 > y2)
				continue;

			a += y2 - y1 + 1 - seg_query(get_y(y1), get_y(y2));

			maxy = max(maxy, y2);
		}

		if (j < (int)e.size())
			a += 1l * seg_p[1] * (e[j].x - e[i].x);
	}

	cout << a << endl;
}

Footnotes

1. Writing this tutorial also served as a great opportunity to make some artisanal HTML Canvas animations. ↩

2. In this task, $1 \le n\le 100,000$ and $1\le h, w \le 1,000,000,000$. ↩

3. A kunai is a Japanese dagger-shaped tool that is also used as a weapon. See here. ↩