2023.10.19 Full Simulation Exam Summary

• Overview
  • Schedule
    • Exam Results
    • Exam Reflection
• Problems
  • T1
    • T2
    • T3
    • T4

Overview

Schedule

8 : 00 ∼ 8 : 20 \qquad 8:00\sim 8:20 8:00∼8:20 Read through the problem statements, and got a general idea of each question in my mind, thinking briefly. The exam felt very formal, which was largely due to the PDF problem statement. I decided to be more conservative today and try not to fail any problems, hoping to gain confidence for CSP-S. Then I started with T1.

8 : 20 ∼ 9 : 20 \qquad 8:20\sim 9:20 8:20∼9:20 I quickly had an idea for T1, which seemed correct, with a theoretical time complexity of O(n log n). I wrote it quickly, but after testing the sample input, I found an error. Debugging revealed that it was incorrect. I felt a bit discouraged but adjusted quickly. I spent 10 minutes without progress and then wrote a brute-force DP approach. After that, I thought of an O(n√n) solution and implemented it. It matched the brute-force version, but after some testing, the brute-force approach turned out to be incorrect. Within one hour, I had written two incorrect algorithms, which made me laugh.

9 : 20 ∼ 10 : 40 \qquad 9:20\sim 10:40 9:20∼10:40 During the initial reading, I noticed that there were many partial points available, such as the O(n√n) solution for T1, which could earn 80 points, possibly even more if well-implemented. I decided to focus on gathering partial points first, which might place me high in the rankings. I moved on to T2. The initial idea for T2 was correct (using a union-find structure), but I wasn't sure how to assign offsets to the entire structure. I decided to write a brute-force approach first. The brute-force approach involved building a graph and performing a topological sort, which I implemented quickly. However, during the process, I heard that someone else had been stuck by a common algorithm, which made me doubt my initial union-find idea, but I continued with the topological sort. After some debugging, I replaced the topological sort with BFS, which passed the sample test case. I added a long segment tree to handle the 10-point chain case, which passed after one attempt. I then verified it against BFS.

10 : 40 ∼ 11 : 20 \qquad 10:40\sim 11:20 10:40∼11:20 I reviewed T1 and T2, but still couldn't figure them out. I decided to write a brute-force solution for T3. I tried to derive the formula and realized that the O(n³) solution could be optimized to O(n²), which would allow passing the n ≤ 10 case. I derived a formula for the star graph and implemented it, verifying it with a few tests before moving on.

11 : 20 ∼ 11 : 40 \qquad 11:20\sim 11:40 11:20∼11:40 I glanced at T4, but had no idea how to proceed. I tried to think about T1 and T2 again but failed to find a solution until the end of the exam.

Exam Results

90 + 70 + 50 + 0 = 210 , Rank: + ∞ \qquad 90+70+50+0=210,Rank:+\infty 90+70+50+0=210,Rank:+∞. T1 unexpectedly earned 10 additional points, and other questions did not have any failures. I noticed that others solved T2 more than T1, but I didn't solve either, which made me feel a bit disappointed. Near the end, I realized that I should have considered enumerating multiples instead of divisors for T1. Once I understood the multiple enumeration approach, I realized I had missed the key insight. For T2, if I had considered the heuristic merging strategy or the weighted union-find structure, I might have solved it.

Exam Reflection

\qquad I managed to collect some partial points, but I still missed several opportunities.

\qquad Today's approach was very cautious. I prepared the data generation and verification templates beforehand, aiming to verify each problem. This helped prevent any failures. However, I still missed several points that I should have known, such as considering multiples for T1, using heuristic merging for T2, and handling the len=1 case for T4.

\qquad It's good that I didn't figure it out now; I can consider it as experience. I must remember these insights during the CSP-S competition!

Problems

T1

\qquad A straightforward problem where we need to enumerate the greatest common divisor (gcd) and check if the number of its multiples is at least k. The complexity is harmonic series, approximately O(n log n).

T2

\qquad The 60 points are easy to get (maybe?), where we can perform a brute-force BFS after building the graph each time. Initiallly, I used topological sorting, which somehow worked after some adjustments. The key part involves maintaining connected components using a union-find structure, keeping track of their endpoints. When modifying values, we can directly udpate the segment tree. The key insight here is the use of heuristic merging—merging smaller sets into larger ones and updating the smaller set's elements. This results in a time complexity of O(n log n).

\qquad Core code:

void merge(int x, int y, LL z) {
	int fx = Find(x), fy = Find(y);
	if(son[fx].size() > son[fy].size()) {
		LL cha = val[x] - z - val[y];
		for(auto p : son[fy]) val[p] += cha, son[fx].emplace_back(p);
		son[fy].clear(), bin[fy] = fx;
	}
	else {
		LL cha = val[y] - val[x] + z;
		for(auto p : son[fx]) val[p] += cha, son[fy].emplace_back(p);
		son[fx].clear(), bin[fx] = fy;
	}
}

T3

\qquad Partial points for this problem are easy to obtain. By bringing Wu to the sum, we can run a DFS while tracking the minimum edge weight. This gives us O(n²n!) and 35 points easily.

\qquad For a star graph, we can assume that the largest edge weight should be assigned to smallest node value, and the smallest edge weight to the largest node value. After implementing and verifying, this assumption holds.

\qquad For the optimal solution, the constraints suggest using a bitmask. We consider the edges that have already been processed. If a mask has k bits set, we use the (k+1)-th largest edge weight. The process can be implemented using either method, with a time complexity of O(2^{n-1} × n).

\qquad Core code (adding edges from largest to smallest):

for(int i = 0; i < (1 << m) - 1; i ++) {
	int num = 1, Now = i;
	while(Now) num ++, Now -= (Now & (-Now));
	for(int j = 1; j <= n; j ++) bin[j] = j, sum[j] = w[j];
	for(int j = 1; j <= m; j ++) {
		if((i >> (j - 1)) & 1) merge(Edge[j].st, Edge[j].ed);//merge and update sum
	}
	for(int j = 1; j <= m; j ++) {
		if(!((i >> (j - 1)) & 1)) {
			dp[i | (1 << (j - 1))] = min(dp[i | (1 << (j - 1))], dp[i] + a[num] * sum[Find(Edge[j].st)] * sum[Find(Edge[j].ed)]);
		}
	}
}

T4

\qquad Didn't know how to solve it at all...