This blog is so dead
Last year today, I created this blog. I can’t believe that time has passed by so fast, I still remember how I wanted to keep the blog active and post every one / two weeks.
I completely forgot about my blog during summer vacation and was kind of busy with LIT / club stuff so I haven’t posted for 4 months. I actually did type some things but didn’t feel like posting them so this is going to be very long.
End of School Year 24-25
School
It was kind of funny that the Quarter 1 Recap turned out to be my only post about school. This was the aspect of life I worried about the most when I moved to the United States this year, and thus I decided to put this part in the beginning.
And it turned out to be much better than I originally imagined. While there was several setbacks, I eventually managed to keep a good GPA. Luck was certainly a significant factor here; I originally had an A- in science because I’m mad zro but my GOATED science teacher decided that my grade was close to an A so bumped my grade up. The rest of my teachers were all nice and none of them were too harsh on grading, so I might not have achieved what I had with different teachers. Hopefully I could be as lucky in sophomore year and the rest of high school 🙏.
I also got to know many interesting people (mostly from Math Team / LexMACS though, which may be problematic…) Thankfully school (at least freshman year) wasn’t as stressful as I imagined it would be.
Competitive Programming
This was also very important to me (as the current tag with the most posts). This blog was originally intended for myself to record my performances and reflect upon my weaknesses after contests, but I later decided to write about other stuff like math and school since those were interesting experiences worth reflecting as well.
I was also pretty lucky this year during important contests (e.g. USACO, codeforces isn’t that important so my rating went down) now that I think about it.
Math
I kind of just gave up on this later in the year (didn’t really practice much after AIME) but I still went to math team and got to know many people which was nice. I hope I could participate in more competitions next year (I didn’t go to PuMAC because my math wasn’t good enough to make it, and ARML because it’s the same time as camp) and hopefully get top 10 in something since it feels very good. I also hope to qualify for USAJMO but I don’t really have as strong of a desire to make / do good in oly as many other people in math team, which could make myself less motivated to grind.
Start of School Year 25-26
This will only be about school since I haven’t been doing a lot of competitive programming nor math (I bombed the math team tryouts which was kind of deserved to be honest).
Basically now I’m taking AP Bio, AP Calculus BC, AP Computer Science A, AP World History, Honors Spanish II, Composition and Arranging (music), and Honors Literature & Composition II (but we have honors for all so nobody cares).
My teachers are all pretty nice at least as of now (I probably got lucky again), although my GPA might be below 4.0 this year because I have a B+ in literature and my A is borderline for both biology and world history. I’m also kind of worried about spanish although my grade isn’t that bad yet because I’m taking it with a bunch of freshmen who have 2 more years of spanish experience than I do (they started learning in middle school), so I feel there’s some sort of knowledge / experience gap no matter how much I try.
Our club (LexMACS, you should join if you’re in Lexington!) also had our first meeting which went okay I guess considering that it is our first year and we’re just sophomores. Hopefully most of the people will remain active.
Lexington Informatics Tournament 2025
It actually went pretty well. There were some issues but overall they didn’t impact the contest too much. I picked & prepared most of the problems for Standard Round and created F and H. The quality of the problems itself is ok (at least people didn’t criticize it a lot), but unfortunately some of the testcases were a bit weak.
Here I will share the editorial for problem F and H, as well as my take on AI / cheating
Tyger Sort (~2200)
I personally liked this problem because the solution code is short yet the problem is not too easy & does not rely on a lot of knowledge.
Editorial Here
Let’s examine the process of Tyger sort. For example, consider the permutation [4, 2, 5, 1, 6, 3, 7]. After performing Tyger sort, the permutation becomes [1, 2, 4, 5, 3, 6, 7]. Notice how the elements to the right of the smallest element (in this case 1) are still “stuck” at the right, since they would never be swapped past the minimum (which is moved last) before terminating.
More formally, we can redefine the Tyger sort process as follows:
- Find the minimum (let it be m)
- Split the original array into three parts: L = array of elements to the left of m, m itself, and R = elements to the right of m
- Create a new array A and put m in the front
- Perform Tyger sort on L and add the result to the end of A
- Perform Tyger sort on R and add the result to the end of A
- Return A.
For example, TygerSort([4, 2, 5, 1, 6, 3, 7]) = [1] + TygerSort([4, 2, 5]) + TygerSort([6, 3, 7]).
As it turns out, we can construct a (not completely filled) heap using a similar process (with the minimum value being the root of the subtree). In this heap, the original array is the inorder traversal and the array formed after TygerSort is the preorder traversal!
So now our problem is equivalent to
Given the preorder traversal of a heap, construct a possible heap and output its inorder traversal, or report that it’s impossible
This problem is much easier. We can maintain a stack of possible parents of the current node. We repeatedly pop the top element of the stack until the top element is smaller than the current one. Then make the top element the parent of the current node and remove it from the stack. Since the current node is a leaf, we push it into the stack twice (it can have two children). This stack must be non-decreasing since the original last element is smaller than the new elements. If the stack is empty and a node is parentless, it is impossible to construct a heap with such a preorder traversal.
Notably, there’s also another clean solution (which is short and also involves stacks). It produces the same output as this one but I guess is harder to prove / generalize so I won’t put it here.
You can use a similar interpretation to prove that the number of permutations that can be TygerSorted into increasing order is the catalan sequence.
Portals (~2700)
Unfortunately I don’t know how to create 2700 rated problems so this one is kind of standard and requires advanced algorithms. A lot of teams got a score of 700 as they didn’t solve this one, but sadly ChatGPT could (probably the $200 version? since it couldn’t solve when I tested). While being the hardest, this was also the least favorite problem I have ever created (not that I have many).
Editorial Here
First, we need to deal with the fact that there can be N^3 edges total (since two portals can share the same edges), or perhaps O(N^2) if we ignore enough repeating edges. We can solve this with the segment tree for graph problems trick.
If there wasn’t the “multiple of a1/a2” constraint, we can add a “special” node for each portal. Then, we can add edges from the corresponding ranges in the bottom part of the graph to the special node, as well as edges from the special node to the ranges in the top part.
Now we add in the “multiple” constraint. For each integer s from 1 to N, since only the multiples of s matter, we can create such a graph for each s while sharing the individual nodes (those representing ranges [1, 1], [2, 2], …, [N, N]). So now we can represent the graph with O(NlogN) nodes and O(MlogN) edges. The problem turns into
Given a directed graph and a node d, process Q queries nodes x and y. For each query, output whether it is possible to go from x to d and y to d without sharing any special nodes
We reverse the edges in the graph, so that we now go from d to x and y. Consider the dominator tree of this graph, we now try to prove that it is possible to not share special nodes if and only if the path from d to lca(x, y) in the dominator tree does not contain any special nodes.
The first direction is trivial (the path contains special nodes -> it is impossible). Let the special node be s; since s dominates both x and y, every path must go through s.
Now the goal is to prove that if the path doesn’t contain any special nodes a construction is possible. After we prove this, we can just use the solution above to construct the dominator tree in O(N(log^2N)) and perform LCA for each query in O(logN).
We can consider splitting each ticket node t into s_t and e_t, and create an edge of capacity 1 from s_t to e_t. Let the capacities of the remaining edges be 1. Additionally, create a sink node that has edges of capacity 1 from x and y. Since none of the special nodes dominate both x and y, the minimum cut of this graph is 2. Therefore, by the max-flow min-cut theorem, the maximum flow of this graph is also 2, meaning that there’s two paths from d to the sink that don’t share any special nodes, which also means that it’s possible to construct two paths (from d to x and d to y) that don’t share special nodes.
My Take on AI / Cheating
Well there isn’t really much to say. My opinion is probably going to be similar to the majority and there isn’t really any innovative idea here, so it is just going to be me yapping.
This year, we had a cheating (i.e. using AI to solve problems) rate of over 30% in LIT Standard round. Some people were not aware that AI was not allowed, but after we made the rule crystal clear by making announcements and adding (in bolded text) this to the top of the standard round page, the cheating rate did not drop.
What’s perhaps the most heartbreaking is that many of these cheaters beat a lot of legitimate participants, which could potentially discourage them, or even at an extreme, make them to cheat as well. And it has been noted that a lot of these cheaters are repeated offenders (cheated in other contests as well), which feels weird to me because why would you want to keep cheating just to get caught again and again?
Maybe they thought that one day they would get good enough at cheating to escape the consequences. But what is the point of wasting 3 hours pasting problems into ChatGPT, altering the code to make it look human (not understanding anything at all), and submitting hoping that the solution is correct?
I have always hated cheaters who used AI (or just cheaters in general actually), especially after they got better than me. Although people keep saying that rating is just a number and I hope I do as well, in reality I just couldn’t convince myself into not caring about this “number.” Every time I do bad I blame myself first, but then when I realize that there was over 100 cheaters ranked above me I would be very disappointed (most are removed after the contest though, thanks Mike!)
It’s very unlikely that you reading this are a cheater but if you are, I hope that you can realize your mistakes and never cheat again. It does not help you at all long term, and I know this blog is not capable of changing anything (I hope it is), and you should stop doing these competitions if you don’t love them enough to even solve problems legitimately. What you are doing would only hurt those who truly enjoy competitive programming and does not do you any good (well maybe your resume, but WHO cares about codeforces ratings)
Also I want to talk about Meta Hacker Cup Round 1 which just took place a few days ago. People keep complaining about cheaters and whining that plagiarism checks aren’t completed. What I want to say is that due to its special format (only submitting output), plagiarism checks can’t really be done and cheaters would probably not be removed unfortunately. They ask you to submit your code but you can always just submit a brute force / even a blank file and claim that you accidentally submitted the wrong thing. Also based opinion: if you only solved A1A2B1 you shouldn’t make Round 2 anyway so stop complaining. I understand that this is contradictory to what I just said and I would probably think differently if my performance wasn’t as good as it was (top 100).
Goals for this School Year
After a year, I’ve become even lazier so I will just list my main goals consisely
- Make USACO Camp
- Top 10 in a Platinum contest
- Codeforces Grandmaster
- AtCoder Yellow (1 Dan+)
- Make USAJMO
- Get top 10 in some math competition
- Make PRIMES (?)
- Make USAAIO Round 2 and get something
- Make USAPHO (not camp, also I’m not that good at physics so I don’t expect to get anything)
- Make NACLO Invitational
- 4.0+ GPA
- Play table tennis maybe I haven’t for over a year and probably got significantly worse