This article will be written in English. Later I will explain why. My grammar is poor. Please ignore possible mistakes.
Abstract : This article contains gossips of CSP-J and some solutions of CSP-S with more formal language.
Hello. This is a stupid guy who scored no more than 110 points in several simulation tests of CSP-S before CSP-J2/S2.
Thanks to GESP, I had no need to participate in CSP-S1, and that's why I didn't see that 'have no egg'. CSP-J1 is easy. No need to write about that.
I expected CSP-J2 to be about the same difficulty as the one last year, due to the reduction of elementary school students. But I was wrong.
I restarted the computer, entered Linux, configurated a new contest with the four problems and started reading the statement in no time. T1 is so easy. Though bucket sorting has better efficiency, the sort function is enough. Coding speed values more. T2 is so easy. Sort. Find that guy's rank. Simulate the seat ordering. And we're done. I even spent 1 minute to debug. T3 is so easy. We need only 1 minute to think. An obvious dp with some obvious optimization. No CE and no WA in first run, making me happy. 15 minutes have passed. Oh T4 is so easy too. Surprise. An obvious sort and backpacking problem (is it called that?). Done in another 10 minutes. Oh wow, 3 hours left.
I started writing a diary following after the code of T4. I remembered two IMOSL problems that I didn't solve a few days ago. I started solving them. Thirty minutes passed and I solved 2/3 of one of those. I presented the remaining unproven lemma to any possible readers of that diary. And I gave up on that problem. After that I started exploring Linux. I found a myriad of hotkeys. Boring. I didn't really remember what I done, they should be recorded in the code. Anyone who is interested in that may find my code by searching keyword Antimatter Dimensions. Also I discovered three interesting phrases. a large number of numbers, namespace's name and caps lock's cap. After that I switched back to Windows and found that the time zone is interesting. Though with UTC+8, the time is 8 hour backwards. I should use UTC-8 and switch the date one day forward. I wrote about 4kb to introduce nutrimatic.org and Antimatter Dimensions to any possible readers. All the things I mentioned above took up about 11kb memory. Also, I wrote all those things with English. That's why I'd like to write English here too.
Good times passed. Now die.
CSP-S2. Start reading statement. T1. Why is the threshold \frac{n}{2}? Intuition told me that choosing the best group for everyone will produce at most one illegal group, which is an important property. One can easily find that nobody will have to choose a worst group in a desired configuration. That's because if not, then the other two group will both contain more than \frac{n}{2} people, summing up more than n people, absurd. Now distribute everyone into the best option. If no group contain more than \frac{n}{2} people then we are done. Denote the best value and second best value of each people a_i, b_i. Without loss of generality let the oversized group be the first group and all people with a_i in the first group be the ones with indices in a set I\subseteq\{1,...,n\}. Now a correct greedy algorithm will let the |I|-\frac{n}{2} people in I with the least value of a_i-b_i switch to the second best option. After this, the first group will contain exactly \frac{n}{2} people and no other group will be oversized, providing a legal choice for everyone. Now we prove that it is optimal. Firstly, one can easily find that the ones with best choice in group two and three will stay in their optimal choice in the best plan. Now, to provide a legal plan, at least |I|-\frac{n}{2} people should leave group one. Since a_i-b_i\ge 0, the result is proven. The above proof can be demonstrated within five minutes of thought. Coding and testing. Passed.
T2. With exploration, one can easily find that:
$\texttt{Proof.}\ \ \ $Consider the Kruskal algorithm. Simply simulating the steps should give this clear result. Details are omitted.
With this result, one can easily come up with a $O(nk2^k\log\left(nk\right)+m\log m)$ solution. With merge sort of two ordered arrays, $O(nk2^k+m\log m+kn\log n)$ can be obtained. In fact it can be further optimized by applying the lemma several times in the $2^k$ choices of additional nodes by storing only the minimal spanning tree of each option. Then the merge sort merges only $O(n)$ length arrays. I wrote a solution with complexity $O(nk2^k+m\log m+kn\log n)$. And I became stupid. My code added the `if(cnt >= n + kcnt - 1) break;` in the minimal spanning tree part, but I didn't write `++cnt;`, making the code slower than expected. Scored 80 on luogu. Adding this line gives 100.
T3. I have no idea about string problems, and I wrote something completely unreasonable and wrong during contest. I stupid guy. A solution using AC automaton should be easy to think of. I only scored 45 points. I don't know why it is so low.
T4. I only have 2 minutes left since I spent almost two hours on writing the wrong solution of T3. I quickly wrote a $O(n!)$ brute force and I tested the first sample. It passed. I saved the code and submitted it, leaving an exe in the folder. Hilarious. Also, due to some stupid mistakes, I didn't score the 8 points.
Therefore I scored 225 points in all. I stupid guy.
This article contains 5789 characters in all.