Jousting Tournament
There are N final positions, one of which will be occupied by the late knight of rank R. The other N-1 positions contain the ranks in array K in their original order. For each round i, the master removes the consecuti...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
There are $N$ final positions, one of which will be occupied by the late knight of rank $R$. The other $N-1$ positions contain the ranks in array $K$ in their original order. For each round $i$, the master removes the consecutive range of current positions $[S_i, E_i]$, keeps only the strongest knight in that range, and packs the remaining knights to the left. We must choose the insertion position of the late knight so that the number of rounds he personally wins is maximized.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observation
The sequence of rounds defines an ordered tree on the final $N$ positions: each leaf is one initial position, and each round creates one internal node whose children are the consecutive survivors currently inside the announced interval. This tree depends only on $(S_i, E_i)$, not on the ranks.
Consider an internal node whose leaf interval is $[l, r]$. If the late knight is inserted anywhere inside this interval, then the other knights participating in that node are exactly the original knights $K_l, K_{l+1}, \dots, K_{r-1}$. Hence the late knight wins this round if and only if \[ \max(K_l, K_{l+1}, \dots, K_{r-1}) < R. \] So every internal node is either:
good: every original knight in $K_l \dots K_{r-1}$ is weaker than $R$;
bad: otherwise.
For a leaf position $p$, the number of rounds won by the late knight is exactly the number of consecutive good ancestors of leaf $p$.
Building the Tree
We maintain the current survivors as a linked list of active slots and a Fenwick tree over the slots. For round $[S,E]$:
Use the Fenwick tree to find the active slots currently at positions $S$ and $E$.
Traverse that linked-list segment; those nodes become the children of a new internal node.
Replace the whole segment by the new node at its leftmost slot, and deactivate the remaining slots.
Each node becomes a child exactly once, so the total linked-list traversal is linear. The Fenwick operations contribute the $\log N$ factor.
Checking Good Nodes
Define \[ \text{strongPrefix}[i] = \#\{\,0 \le j < i : K_j > R\,\}. \] Then an internal node with leaf interval $[l,r]$ is good iff \[ \text{strongPrefix}[r] - \text{strongPrefix}[l] = 0. \] After building the tournament tree, we do one DFS from the root. If an internal node is good, its ``good-chain length'' is \[ 1 + \text{good-chain(parent)}; \] otherwise it is $0$. For each leaf, the answer is the good-chain length of its parent.
Complexity
Time: $O(N \log N)$.
Space: $O(N)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n;
vector<int> bit;
explicit Fenwick(int n_) : n(n_), bit(n_ + 1, 0) {}
void add(int idx, int val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
int kth(int k) const {
int idx = 0;
int step = 1;
while ((step << 1) <= n) step <<= 1;
for (; step > 0; step >>= 1) {
int next = idx + step;
if (next <= n && bit[next] < k) {
idx = next;
k -= bit[next];
}
}
return idx + 1;
}
};
struct Node {
int l = 0;
int r = 0;
int parent = -1;
vector<int> children;
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
vector<Node> nodes(N + C);
for (int i = 0; i < N; ++i) {
nodes[i].l = nodes[i].r = i;
}
Fenwick fw(N);
vector<int> slot_node(N), nxt(N, -1), prv(N, -1);
for (int i = 0; i < N; ++i) {
fw.add(i + 1, 1);
slot_node[i] = i;
if (i > 0) prv[i] = i - 1;
if (i + 1 < N) nxt[i] = i + 1;
}
int node_cnt = N;
for (int round = 0; round < C; ++round) {
int left_slot = fw.kth(S[round] + 1) - 1;
int right_slot = fw.kth(E[round] + 1) - 1;
int cur = left_slot;
vector<int> children;
while (true) {
children.push_back(slot_node[cur]);
if (cur == right_slot) break;
cur = nxt[cur];
}
int id = node_cnt++;
nodes[id].children = children;
nodes[id].l = nodes[children.front()].l;
nodes[id].r = nodes[children.back()].r;
for (int child : children) nodes[child].parent = id;
slot_node[left_slot] = id;
int after = nxt[right_slot];
cur = nxt[left_slot];
while (cur != after) {
fw.add(cur + 1, -1);
int next_cur = nxt[cur];
prv[cur] = nxt[cur] = -1;
cur = next_cur;
}
nxt[left_slot] = after;
if (after != -1) prv[after] = left_slot;
}
int root_slot = fw.kth(1) - 1;
int root = slot_node[root_slot];
vector<int> strong_prefix(N, 0);
for (int i = 0; i < N - 1; ++i) {
strong_prefix[i + 1] = strong_prefix[i] + (K[i] > R);
}
strong_prefix[N - 1] = strong_prefix[N - 1];
auto good = [&](int id) -> bool {
return strong_prefix[nodes[id].r] - strong_prefix[nodes[id].l] == 0;
};
vector<int> chain(node_cnt, 0), answer(N, 0);
vector<int> st = {root};
chain[root] = good(root) ? 1 : 0;
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int child : nodes[u].children) {
if (child < N) {
answer[child] = chain[u];
} else {
chain[child] = good(child) ? chain[u] + 1 : 0;
st.push_back(child);
}
}
}
int best_pos = 0;
for (int i = 1; i < N; ++i) {
if (answer[i] > answer[best_pos]) best_pos = i;
}
return best_pos;
}
int main() {
int N, C, R;
if (!(cin >> N >> C >> R)) return 0;
vector<int> K(max(0, N - 1)), S(C), E(C);
for (int i = 0; i < N - 1; ++i) cin >> K[i];
for (int i = 0; i < C; ++i) cin >> S[i] >> E[i];
cout << GetBestPosition(N, C, R, K.data(), S.data(), E.data()) << '\n';
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.