Competition Summary

• Overview
• Problem Details
  • Problem 1: Prime Number Identification
  • Problem 2: Range Maximum Queries
  • Problem 3: Dynamic Median Finding
    • 20 Point Solution
    • 100 Point Solution
  • Problem 4: Magic Stone Path Optimization
    • Basic Dynamic Programming Approach
  • Problem 5: Strategic Decision Making

Summer Training Competition Day1 Overview

Unexpectedly, our standard-to-advanced group competed with the advanced group using the same problem set!
Competition details:

• Full score: 500 points
• Our score: 325 points
• Rank: 5
• Rating change: +86

Performing at this level exceeded our expectations, though the score may have been somewhat inflated.Certainly not because the test data was too easy...

Problem Details

Problem 1: Prime Number Identification

This problem required identifying prime numbers, which can be efficiently solved using the Sieve of Eratosthenes algorithm. But why spend significant effort memorizing a non-optimal algorithm?

// Eulerian sieve implementation
void generatePrimes() {
	for(int i = 2; i <= n; i ++) {
		if(!isComposite[i]) {
			isComposite[i] = i;
			primeList[++ primeCount] = i;
		}
		for(int j = 1; j <= primeCount; j ++) {
			if(primeList[j] > isComposite[i] || primeList[j] > n / i) break;
			isComposite[i * primeList[j]] = primeList[j];
		}
	}
}

Received 100 points for this solution.

Problem 2: Range Maximum Queries

The problem required finding the maximum value in each interval, then recursively splitting the interval around this maximum value. This is a classic recursive problem that can be optimized using efficient range maximum query structures.As I'm not familiar with segment trees, I'm providing an ST table solution

void buildSparseTable() {
	for(int i = 1; i <= n; i ++)
		stTable[0][i].value = inputArray[i], stTable[0][i].position = i;
	int levels = log2(n) + 1;
	for(int i = 1; i <= levels; i ++)
		for(int j = 1; j <= n - (1 << i) + 1; j ++) {
			tableElement leftElement, rightElement;
			leftElement = stTable[i - 1][j], rightElement = stTable[i - 1][j + (1 << (i - 1))];
			if(leftElement.value < rightElement.value) stTable[i][j] = rightElement;
			else stTable[i][j] = leftElement;
		}
}

int findMaxPosition(int left, int right) {
	int length = right - left + 1;
	length = log2(length);
	if(stTable[length][left].value > stTable[length][right - (1 << length) + 1].value) return stTable[length][left].position;
	else return stTable[length][right - (1 << length) + 1].position;
}

void processDepth(int depth, int left, int right) {
	if(left > right) return ;
	int position = findMaxPosition(left, right);
	resultArray[position] = depth;
	if(position == left) processDepth(depth + 1, left + 1, right);
	else if(position == right) processDepth(depth + 1, left, right - 1);
	else {
		processDepth(depth + 1, left, position - 1);
		processDepth(depth + 1, position + 1, right);
	}
	return ;
}

Received 100 points for this solution.

Note: A talented competitor solved this problem using a monotonic stack approach without prior knowledge of Cartesian trees, and their code coincidentally implemented a Cartesian tree.

// A competitor's solution (comments by the original author)
#include<bits/stdc++.h>//Apparently requires monotonic stack? Each number is the left or right first greater than it child (take the smaller one)
using namespace std;
const int N = 1e5 + 10;
int n, values[N], depths[N], leftBounds[N], rightBounds[N], adjacencyList[N], totalEdges, startNode;
stack< int > s;
struct edge{
	int destination, previous;
}edges[N * 2];
void findBounds(){
	for(int i = 1; i <= n; i++){ 
		leftBounds[i] = rightBounds[i] = 1e6;
	} 
	for(int i = 1; i <= n; i++){//Find first greater elements on both sides
		while(!s.empty() && values[i] > values[s.top()]){
			int currentIndex = s.top();
			rightBounds[currentIndex] = i;//First greater to the right
			s.pop(); 
		}
		if(!s.empty()){
			int currentIndex = s.top();
			leftBounds[i] = currentIndex;//First greater to the left
		}
		s.push(i);
	}
}
void addEdge(int origin, int destination){
	edges[++totalEdges].destination = destination;
	edges[totalEdges].previous = adjacencyList[origin];
	adjacencyList[origin] = totalEdges;
}
void traverseGraph(int currentNode){
	for(int i = adjacencyList[currentNode]; i != 0; i = edges[i].previous){
		int nextNode = edges[i].destination;
		depths[nextNode] = depths[currentNode] + 1;
		traverseGraph(nextNode);
	}
}
int main(){
	freopen("tower.in", "r", stdin);
	freopen("tower.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &values[i]);
   findBounds(); 
   for(int i = 1; i <= n; i++){//Build graph
   	int leftBound = leftBounds[i], rightBound = rightBounds[i], parent = 0; 
		if(leftBound == 1e6 && rightBound == 1e6) startNode = i;
		else{
			if(leftBound == 1e6) addEdge(rightBound, i);
			else if(rightBound == 1e6) addEdge(leftBound, i);
			else{
				if(values[leftBound] > values[rightBound]) addEdge(rightBound, i);
				else addEdge(leftBound, i);
			}
		}
	}
	traverseGraph(startNode); 
	for(int i = 1; i <= n; i++){
		if(i == 1) printf("%d", depths[i]);
		else printf(" %d", depths[i]);
	}
	printf("\n");
	return 0;
} 
/*
7
1 3 2 7 5 6 4
*/

Respect to the master...

Problem 3: Dynamic Median Finding

20 Point Solution

This problem clearly required maintaining a dynamic median, which naturally leads to using two heaps (a min-heap and a max-heap).

#define priority_queue p_q
p_q < int , vector < int > , greater < int > > minHeap;//Min-heap
p_q < int , vector < int > , less < int > > maxHeap;//Max-heap, storing the median
int bestMedian = -1;
for(int left = 1; left <= n - k + 1; left ++) {//Left endpoint
	maxHeap.push(inputArray[left]);
	for(int right = left + 1; right <= n; right ++) {//Right endpoint
		if(inputArray[right] > maxHeap.top()) minHeap.push(inputArray[right]);
		else maxHeap.push(inputArray[right]);
		int currentLength = right - left + 1;
		while(maxHeap.size() > (currentLength + 1) / 2) {
			minHeap.push(maxHeap.top());
			maxHeap.pop();
		}
		while(maxHeap.size() < (currentLength + 1) / 2) {
			maxHeap.push(minHeap.top());
			minHeap.pop();
		}
		if(currentLength >= k) bestMedian = max(bestMedian, maxHeap.top());
	}
	while(!maxHeap.empty()) maxHeap.pop();
	while(!minHeap.empty()) minHeap.pop();
}
printf("%d", bestMedian);

However, this approach has a time complexity of O(n²log n), which is insufficient for full points.

100 Point Solution

When dealing with medians, we should consider that only the relative ordering matters, not the absolute values. We can transform each element based on a candidate median value x. For each element, we can convert values ≤ x to -1 and values > x to 1, creating a new sequence (let's call it b_i). Here's a key insight: For an interval [l, r], if the sum of b_i from l to r is greater than 0, then the median of [l, r] must be ≥ x.

This leads us to a binary search approach on x. For each candidate x, we compute the prefix sums of the b array and maintain prefix minimums. For intervals of length ≥ k, we can check the difference between the current prefix sum and the minimum prefix sum in the valid range.

bool checkCandidate(int x) {
	for(int i = 1; i <= n; i ++) {
		if(inputArray[i] >= x) transformedArray[i] = 1;
		else transformedArray[i] = -1;
		prefixSum[i] = prefixSum[i - 1] + transformedArray[i];
	}
	int minPrefix = 1e9;
	for(int i = k; i <= n; i ++) {
		minPrefix = min(minPrefix, prefixSum[i - k]);//Prefix minimum
		if(prefixSum[i] - minPrefix > 0) return 1;//If interval sum > 0, x could be median
	}
	return 0;
}

Received 20 points for this solution.

Problem 4: Magic Stone Path Optimization

This problem immediately suggested a dynamic programming approach. I implemented a DP solution that worked partially.

Basic Dynamic Programming Solution

The DP state was straightforward: dp[i][j] represents the minimum energy consumed after taking i steps and using j magic stones. This approach organizes states by the number of magic stones used to avoid dependency issues. However, I mistakenly placed the magic stone dimension as the ennermost loop instead of the outermost. Additionally, to find the optimal solution, we need to process the array in both forward and backward directions. The reason for this is illustrated in the following diagram:

In this scenario, the optimal solution is: Move from position 1 to 3 in one step, use one magic stone to jump to position 8, then backtrack to position 6, and use the second magic stone to reach the destination. Without backtracking, it's impossible to reach the destination in two steps.However, I only processed in the forward direction...

This demonstrates the numerous details in this problem, and the leniency of the test data.
Accepted solution (95 points):

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 5;
int n, m, c;
int positions[maxn];
int dp[maxn][23];

int main() {
	scanf("%d%d%d", &n, &m, &c);
	for(int i = 1; i <= n; i ++) scanf("%d", &positions[i]);
	memset(dp, 0x7f, sizeof dp);
	dp[1][0] = 0;
	for(int stones = 0; stones <= c; stones ++) {
		for(int i = 1; i <= n; i ++) {
			for(int step = 1; step <= m; step ++) {
				if(i + step <= n) dp[i + step][stones] = min(dp[i + step][stones], dp[i][stones] + 1);
				if(stones < c) dp[positions[i]][stones + 1] = min(dp[positions[i]][stones + 1], dp[i][stones]);
			}
		}
		for(int i = n; i >= 1; i --) {
			for(int step = 1; step <= m; step ++) {
				if(i - step >= 1) dp[i - step][stones] = min(dp[i - step][stones], dp[i][stones] + 1);
				if(stones < c) dp[positions[i]][stones + 1] = min(dp[positions[i]][stones + 1], dp[i][stones]);
			}
		}
	}
	int bestResult = 0x7f7f7f7f;
	for(int stones = 0; stones <= c; stones ++)
		bestResult = min(bestResult, dp[n][stones]);
	printf("%d", bestResult);
	return 0;
}

侥幸提 95 p t s 95pts 95pts

Problem 5: Strategic Decision Making

This problem was beyond my current knowledge scope...