Hi everyone, my team participated in ICPC World Finals yesterday and had a lot of fun. However, we noticed that Problem N did not have many solves (only 1 in-contest and none on Kattis), even though our team thought the problem was very fun and doable. Probably, the reason was because numerical algorithms are harder to write in competitive programming languages like C++ and Java.

To help explain the solution better, I made a very concise, annotated Julia notebook that solves the problem in only 16 lines of code. Hopefully you find it conceptually interesting and helpful.

Here is the link to the notebook as a PDF. Alternatively, if you have Julia and Pluto.jl installed, you can run the notebook directly from the source .jl file at this GitHub Gist.

Here's also the Julia code as a standalone program, if you would like to run it on AtCoder or another place. I compressed this program slightly more, so it is only 13 lines of code, including imports and code to read input:

using LinearAlgebra

# Read input
d, n = [parse(Int, x) for x = split(readline())]
n = min(n, d + 1)
data = hcat([[parse(Float64, x) for x = split(readline())] for _ = 1:n]...)
points, dists = data[1:end - 1, :], data[end, :]

# Shift first point to the origin
base, rest = points[:, 1], points[:, 2:end] .- points[:, 1]

# Edge case: n = 1
if n == 1 (base[end] += dists[1]; println(join(base, " ")); exit(0)) end

# Compute linear equation coefficients
A = 2 .* rest'
b = [norm(p)^2 - d^2 + dists[1]^2 for (p, d) = zip(eachcol(rest), dists[2:end])]

# Least-norm solution
Q, R = qr(A')
value = vcat(R' \ b, zeros(d - (n - 1)))

# Shift so that the norm equals dists[1]
value[end] += sqrt(max(0, dists[1]^2 - norm(value)^2))

# Output answer
println(join(Q * value + base, " "))

Background

During Facebook Hacker Cup Round 2 today, Problem D caught my attention. It reminded me of a particular data structure called a kinetic tournament, which is not very well known in this community. However, it offers an extremely clean and slick solution to the problem, in my opinion.

I first learned about this data structure from dragonslayerintraining, who described a variant of it in this Codeforces blog comment. Since the data structure is so interesting, I feel like it deserves a longer explanation, some template code, and more examples. That's why I am writing this blog post.

Kinetic Tournaments

Briefly, the functionality of the data structure is a mix between a line container, i.e., "convex hull trick", and a segment tree.

Suppose that you have an array containing pairs of nonnegative integers, $$$A[i]$$$ and $$$B[i]$$$. You also have a global parameter $$$T$$$, corresponding to the "temperature" of the data structure. Your goal is to support the following queries on this data:

• update(i, a, b): set $$$A[i] = \text a$$$ and $$$B[i] = \text b$$$
• query(s, e): return $$$\displaystyle \min_{s \leq i \leq e} A[i] * T + B[i]$$$
• heaten(new_temp): set $$$T = \text{new_temp}$$$
  • [precondition: new_temp >= current value of T]

(For simplicity, we set A[i] = 0 and B[i] = LLONG_MAX for uninitialized entries, which should not change the query results.)

This allows you to essentially do arbitrary lower convex hull queries on a collection of lines, as well as any contiguous subcollection of those lines. This is more powerful than standard convex hull tricks and related data structures (Li-Chao Segment Tree) for three reasons:

• You can arbitrarily remove/edit lines, not just add them.
• Dynamic access to any subinterval of lines, which lets you avoid costly merge small-to-large operations in some cases.
• Easy to reason about and implement from scratch, unlike dynamic CHT.

The tradeoff is that you can only query sequential values (temperature is only allowed to increase) for amortization reasons, but this happens to be a fairly common case in many problems.

Here's the kicker. If you implement the data structure correctly, you get the following time complexities:

• query: $$$O(\log n)$$$
• update: $$$O(\log n)$$$
• heaten: $$$O(\log^2 n)$$$ [amortized]

(The runtime complexity might actually be $$$O(m \alpha(m) \log^2 n)$$$ instead of $$$O(m \log^2 n)$$$ if your updates include both adding and removing lines, and you're also very careful about constructing an example. See the discussion below from Elegia about Davenport-Schinzel sequences.)

Implementation

How does it work? With kinetic tournaments, you essentially build a min segtree as usual, but you add a global priority queue that stores whenever a "contract" breaks. We can put this in the analogy of increasing temperature. For every node, you store the temperatures at which that node "melts", meaning that the minimum value changes from one child to the other. Then, you can just keep popping events from this priority queue as your data structure heats up.

However, this unfortunately can be slow if you're not careful, which isn't good enough, especially if you have many concurrent lines (might give you quadratic runtime, depending on implementation of priority queue). Luckily, there's a neat implementation trick that circumvents the priority queue and prevents this possible quadratic runtime. In every node of the segment tree, you store the minimum temperature at which any part of its subtree could melt. This fits in naturally with the segment tree definition.

To optimize the data structure, you do not recompute at every certificate failure. Instead, whenever the user calls heaten(), you batch all of the recompute operations and recursively rebuild only the parts of the segment tree that changed, once.

The runtime analysis follows from comparing the data structure to computing a convex hull by divide-and-conquer (thanks dragonslayerintraining!). The number of times each node "melts" is bounded at most by the number of leaves in its subtree. This is because you can never have two lines, $$$A$$$ and $$$B$$$, such that $$$A(x_1) < B(x_1)$$$, $$$A(x_2) > B(x_2)$$$, and $$$A(x_3) < B(x_3)$$$, where $$$x_1 < x_2 < x_3$$$. In other words, as you increase temperature, the number of recalculations is at most $$$O(n \log n)$$$. Combining this with the fact that we have to walk down the segment tree, which has logarithmic depth, every time we do a recalculation, this yields a final amortized time complexity of $$$O(\log^2 n)$$$ for each "heaten" operation.

Code

You can find my implementation of a modified kinetic tournament here:

https://ekzlib.netlify.app/view/kinetic_tournament.cpp

It defines a single struct with template type (~100 LoC), which has a plug-and-play interface that you can use in your own solutions, and no global variable pollution. Example usage:

int N = 2;
kinetic_tournament<long long> kt(N);

kt.update(0, 2, 10);  // 2t + 10
kt.update(1, 4, 1);   // 4t + 1

kt.heaten(1);         // t = 1
kt.query(0, 0);       // => 2*1 + 10 = 12
kt.query(1, 1);       // => 4*1 + 1 = 5
kt.query(0, 1);       // => min(2*1 + 10, 4*1 + 1) = 5

kt.heaten(5);         // t = 5
kt.query(0, 0);       // => 2*5 + 10 = 20
kt.query(1, 1);       // => 4*5 + 1 = 21
kt.query(0, 1);       // => min(2*5 + 10, 4*5 + 1) = 20

I've verified this implementation on Problem D from Facebook Hacker Cup Round 2, titled "Log Drivin' Hirin'". In this problem, you can simply sort the queries and nodes in order of increasing "carelessness", and the kinetic tournament finishes the task. Full solution is available below. It runs in less than 5 seconds on the entire test input.

using namespace std;

typedef long long LL;

#define MAXN 1000013
#define MAXM 1000013
#define MOD 1000000007

int T;
int N, M, K;
int P[MAXN], L[MAXN], H[MAXN], X[MAXM], Y[MAXM];
vector<int> adj[MAXN];
int in[MAXN], out[MAXN], t = 0;
LL depth[MAXN];

template <typename T = int64_t>
class kinetic_tournament {
	const T INF = numeric_limits<T>::max();
	typedef pair<T, T> line;

	size_t n;         // size of the underlying array
	T temp;           // current temperature
	vector<line> st;  // tournament tree
	vector<T> melt;   // melting temperature of each subtree

	inline T eval(const line& ln, T t) {
		return ln.first * t + ln.second;
	}

	inline bool cmp(const line& line1, const line& line2) {
		auto x = eval(line1, temp);
		auto y = eval(line2, temp);
		if (x != y) return x < y;
		return line1.first < line2.first;
	}

	T next_isect(const line& line1, const line& line2) {
		if (line1.first > line2.first) {
			T delta = eval(line2, temp) - eval(line1, temp);
			T delta_slope = line1.first - line2.first;
			assert(delta > 0);
			T mint = temp + (delta - 1) / delta_slope + 1;
			return mint > temp ? mint : INF;  // prevent overflow
		}
		return INF;
	}

	void recompute(size_t lo, size_t hi, size_t node) {
		if (lo == hi || melt[node] > temp) return;

		size_t mid = (lo + hi) / 2;
		recompute(lo, mid, 2 * node + 1);
		recompute(mid + 1, hi, 2 * node + 2);

		auto line1 = st[2 * node + 1];
		auto line2 = st[2 * node + 2];
		if (!cmp(line1, line2))
			swap(line1, line2);
		st[node] = line1;

		melt[node] = min(melt[2 * node + 1], melt[2 * node + 2]);
		if (line1 != line2) {
			T t = next_isect(line1, line2);
			assert(t > temp);
			melt[node] = min(melt[node], t);
		}
	}

	void update(size_t i, T a, T b, size_t lo, size_t hi, size_t node) {
		if (i < lo || i > hi) return;
		if (lo == hi) {
			st[node] = {a, b};
			return;
		}
		size_t mid = (lo + hi) / 2;
		update(i, a, b, lo, mid, 2 * node + 1);
		update(i, a, b, mid + 1, hi, 2 * node + 2);
		melt[node] = 0;
		recompute(lo, hi, node);
	}

	T query(size_t s, size_t e, size_t lo, size_t hi, size_t node) {
		if (hi < s || lo > e) return INF;
		if (s <= lo && hi <= e) return eval(st[node], temp);
		size_t mid = (lo + hi) / 2;
		return min(query(s, e, lo, mid, 2 * node + 1),
			query(s, e, mid + 1, hi, 2 * node + 2));
	}

public:
	// Constructor for a kinetic tournament, takes in the size n of the
	// underlying arrays a[..], b[..] as input.
	kinetic_tournament(size_t size) : n(size), temp(0) {
		assert(size > 0);
		size_t seg_size = ((size_t) 2) << (64 - __builtin_clzll(n - 1));
		st.resize(seg_size, {0, INF});
		melt.resize(seg_size, INF);
	}

	// Sets A[i] = a, B[i] = b.
	void update(size_t i, T a, T b) {
		update(i, a, b, 0, n - 1, 0);
	}

	// Returns min{s <= i <= e} A[i] * T + B[i].
	T query(size_t s, size_t e) {
		return query(s, e, 0, n - 1, 0);
	}

	// Increases the internal temperature to new_temp.
	void heaten(T new_temp) {
		assert(new_temp >= temp);
		temp = new_temp;
		recompute(0, n - 1, 0);
	}
};

void read_p(int* X, int lim) {
	for (int i = 0; i < K; i++)
		cin >> X[i];
	LL A, B, C;
	cin >> A >> B >> C;
	for (int i = K; i < lim; i++)
		X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % i) + 1;
}

void read_input(int* X, int lim) {
	for (int i = 0; i < K; i++)
		cin >> X[i];
	LL A, B, C, D;
	cin >> A >> B >> C >> D;
	for (int i = K; i < lim; i++)
		X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % D) + 1;
}

void read_x(int* X, int lim, int mod) {
	for (int i = 0; i < K; i++)
		cin >> X[i];
	LL A, B, C;
	cin >> A >> B >> C;
	for (int i = K; i < lim; i++)
		X[i] = ((A * X[i - 2] + B * X[i - 1] + C) % mod) + 1;
}

void dfs(int n, LL d) {
	in[n] = t++;
	depth[n] = d;
	for (int v : adj[n]) {
		dfs(v, d + L[v]);
	}
	out[n] = t;
}

void solve() {
	cin >> N >> M >> K;
	read_p(P, N);
	read_input(L, N);
	read_input(H, N);
	read_x(X, M, N);
	read_input(Y, M);

	for (int i = 0; i < N; i++) {
		// deallocate memory for adj
		vector<int> temp;
		swap(temp, adj[i]);
		in[i] = out[i] = -1;
		depth[i] = 0;
	}

	for (int i = 1; i < N; i++) {
		--P[i];
		adj[P[i]].push_back(i);
	}

	t = 0;
	dfs(0, 0);

	kinetic_tournament<> kt(N);
	vector<pair<int, pair<bool, int> > > events;
	LL ans = 1;
	for (int i = 0; i < M; i++) {
		--X[i];
		events.push_back({Y[i], {true, i}});
	}
	for (int i = 0; i < N; i++) {
		if (adj[i].size()) { // not a leaf
			events.push_back({H[i], {false, i}});
		} else { // leaf
			kt.update(in[i], depth[i], 0);
		}
	}

	sort(events.begin(), events.end());
	for (auto p : events) {
		int temp = p.first;
		kt.heaten(temp);
		if (p.second.first) { // query
			int qi = p.second.second;
			int n = X[qi];
			LL val = kt.query(in[n], out[n] - 1) - temp * depth[n];
			ans = (ans * ((val + 1) % MOD)) % MOD;
		}
		else { // update
			int n = p.second.second;
			LL val = kt.query(in[n], out[n] - 1) - temp * depth[n];
			kt.update(in[n], depth[n], val);
		}
	}

	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	freopen("D.txt", "r", stdin);
	freopen("D.out", "w", stdout);

	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cerr << tc << endl;
		cout << "Case #" << tc << ": ";
		solve();
	}

	cout.flush();
	return 0;
}

Conclusion

I hope to see more of this interesting data structure pop up in competitive programming! Hopefully this explanatory blog post is useful for you, and please let me know if you find any errors.

Hello all,

Like you, I enjoy solving Codeforces problems on the go. However, sometimes I am not working on my computer with all my environment and setup. There are many automated problem parsers and test runners to help make solving Codeforces problems painless, but they all require a complicated installation process.

About a year ago, I was introduced to CS Academy, which I thought had an amazing interface for solving problems. It shows the problems and your code side-by-side, and you can automatically run your program on the example test cases. Also, there is auto-saving in case you accidentally close your window. Why can't we have this for Codeforces?

I couldn't find anything on the web that was easy to set up and fun to use, so I made my own online workspace at wkspace.herokuapp.com.

Here are some features:

• No sign-up or installation required
• Parses Codeforces problems and displays them side-by-side with code
• One click to run your code on all example test cases (for non-interactive problems)
• One click to submit your code to Codeforces (if logged in)
• Auto-saving of code in the cloud
• List workspaces you have recently edited
• Share a read-only paste of your code by link
• Support for new versions of the most common languages (C, C++, Python, Java, Ruby)
• Configurable themes (Monokai, Dawn, Solarized)
• Configurable keybindings (Vim, Emacs)

I have been using and developing this myself for the past year, and it is fairly stable now, so I would like to share it with you. Please let me know if you have any feedback on how to improve it!

Note: The code is open source and available at https://github.com/ekzhang/wkspace.

Thanks to Herman Došilović for making the Judge0 API, which is used in this project.

Hello everyone!

I would like to invite you to participate in the Plano West High School Programming Contest online round. It will be held on Saturday, February 9th at 15:00 EST.

The contest will be 3 hours long and scored by the sum of points for problems solved (harder problems worth more points). There will be a wide range of problem difficulties, from Codeforces Div3 level to about Div1 B/C. Competitors in the second and third divisions will most likely find it interesting.

The problems have been prepared by students at my school: me (ekzhang), Vincent Huang (tastymath75025), Autumn Tan, Wuyou Xie, Sam Ziegelbein, and Timothy Qin. We would also like to thank Kevin Meng (mtr361) and Maxwell Jiang (rocketscience) for helping test the round.

Please visit this link to register for the contest. The round will be held on HackerRank (binary scoring will be used), and a live scoreboard will be available.

Good luck and and have fun!

UPD: Contest starts in 10 minutes!

UPD 2: Contest is over, thanks to everyone for participating! We encourage you to try upsolving the problems; the model solutions, test data, and a PDF of the problem packet are available here: https://tinyurl.com/pwshpc

I recently submitted twice to problem 865C/866C (same problem), Gotta Go Fast.

http://codeforces.net/contest/866/submission/30954904

http://codeforces.net/contest/865/submission/30956252

The first submission got wrong answer on test 1 on Codeforces. But I tested the solution both locally and on Ideone, and the answer was correct.

In the second submission my only change was adding the following one "useless" line of code to a for loop:

if (hi > 2 && hi < 1) cout << "this should never run" << endl;

It got AC.

My question is, why is this happening? I've tried debugging it locally and looking at the assembly, but there are no bugs when it runs on my local machine or on Ideone; it's only acting strangely on Codeforces. I've been staring at this code for many hours now thinking it might be undefined behavior, but I've tried many slightly different submissions (with long double, without the call to min) that work just fine without the extra useless if statement.

Tl;dr: I am utterly confused and would greatly appreciate if you could help me find where my UB is, or if there's some other problem with floating-point precision :-)

Thanks!

Four team members from the US:

• Zhezheng Luo (C_SUNSHINE)
• Dhruv Rohatgi (pacu)
• Ben Qi (Benq)
• Eric Zhang (ekzhang)

Hi, I am currently trying an O(n(sqrt n)(lg n)) to problem 375D using Mo's Algorithm and a Fenwick Tree. My initial solution got a time limit exceeded on test case 53, so I tried to optimize it.

To optimize, I made a couple of changes to my check() function, that is called every time the Mo's Algorithm window is slid 1 tree node. I was thinking that this would make the algorithm run faster since check is the part that is run the most (n^1.5 lg n times).

My second submission didn't end up working. In fact, somehow, my new submission got TLE on test case 5, which the previous code could solve in 150ms!

Can someone help me figure out what could've happened that would make this attempted optimization run 10x slower?

Original Submission: http://codeforces.net/contest/375/submission/18813131

Second Submission: http://codeforces.net/contest/375/submission/18813311

Diff: https://www.diffchecker.com/nhyeayxp

Thank you very much!

Hi, could someone help me on this problem? I keep getting WA on test case 74, and I can't figure out why. This is my latest submission without debugging code.

My code works like this: I first turn all the replies into [L, R] ranges on the bottom row. Then I take all the "yes" replies, and use all of them to get an initial, single [lo, hi] bound on the exit node. I sort the "no" replies in ascending order of L, then iterate through them, while updating lo. If at any time, lo > hi, we can end the loop.

For each of the "no" replies, check if there's any gap between lo and L. If there is, those gaps are all possible exits, and deal with them like that. Regardless, set lo to be max(lo, R + 1) at the end of every loop, as we've handled all possible nodes  ≤ R.

At the end of the program, do some casework, and output different answers based on that.

The program works for the first 73 cases, but it outputs "Data not sufficient!" for test case 74, which is incorrect. Help finding the bug would be greatly appreciated!