Hey Codeforces,

I made a post on AoPS that I thought you guys might find interesting. The original context was math contests in the US, but I think much of it applies to CS (and more generally) too.

Hey AoPS, it’s good to be back. I’m feeling a little sentimental right now, but I guess that’s alright—it’s been six years since I first found you, and it’s been a long journey since. I was a sixth grader then, just starting Mathcounts, unsure if I’d even make the school team. I fell in love with For The Win! (Alpha) and played it during lunch break, after school, even the morning before Mathcounts Nats. In ninth and tenth grade, I scoured the Olympiad fora, wondering if there existed some magic advice that could propel me all the way to MOP. I was chasing after the mathematical footsteps of my Exeter friends then, always feeling a few steps behind. And now I’ve graduated high school. Contests are over for me. It’s pencils down.

Thank you, AoPS, for the community that has made me fall in love with math, that let me hear about this school called Phillips Exeter Academy, that let me know how big I could dream. Thank you for playing Mafia and Beat the Mod with me, for showing me all the beautiful combinatorics, algebra, and number theory, for trolling with me on FTW, Fun Factory, and MathIM.¹ Over the years that I’ve known you, AoPS, I’ve done some things right and some things wrong. And I’ve learned a lot along the way. I’m here because I feel an urge to give a few tidbits back, to share some restless thoughts—thoughts I wish I’d known earlier and still don’t hear too often. These reflections are for myself as much as they are for you.

I’ll start with contests. Don’t train for them. Study math, computer science, physics, or whatever because you enjoy studying the subject, not for the sake of ego or competition. I wasn’t always great about this. In tenth grade, before my last shot at JMO, I constantly compared myself to my friends in Math Club. The olympiad loomed over me as I struggled through practice tests and problem sets. I felt dumb, inadequate, a failure each time I couldn’t solve a problem. I learned facts about symmedians and Miquel points without appreciating their greater geometric context. Not only did I enjoy math less, I also did bad math. You should rarely feel as if you’re training for a particular competition. Do math for the sake of math, please. And if you find yourself feeling pressure from a contest, try not to forget why you chose to pursue math in the first place.²

In the end, contest results don’t define you. In eleventh grade, I soared higher than thought I could in the contest world—I made USAPhO and USNCO, a combinatorics-heavy USAMO placed me into Blue MOP, and I won gold at the IOI in Kazakhstan. I felt weightless, giddy, as if I were plunging downwards on a rollercoaster ride. But the ride only lasts for a moment, and the amusement park closes soon. As senior year neared, I wasn’t sure what to expect beyond the drudgery of college apps. It felt like game over because I’d already beaten the boss. And what remained was a void that I couldn’t quite fill because I had such little anchoring outside of the contest world. Contests are fun, but outside of the amusement park, life moves on.

I received a piece of advice when I was younger (that I still hear passed around): “Don’t learn higher math in high school—you’ll have all of college to do that.” I followed this advice faithfully, but looking back, it feels so wrong. Why limit yourself to solving elementary problems when there’s so much more? Contests provide such a narrow scope and arbitrary lines—problems that fit neatly into one of four subjects, solvable within 4.5 hours. Go read a textbook on algebra or analysis instead. Take a break from USACO training. You could learn to spin up a web app or take a MOOC on machine learning. Personally, contest problems now feel like a comfort food, something to be weaned off of.

Stepping further out, there’s more to life than just math, computer science, or other technical pursuits. That’s obvious, but there is a subtler point that took me a while to appreciate. One afternoon, while taking a break from Club Running, my jogging group skipped stones into the Exeter River. A friend asked me then: “Alex, why do you troll so much?” I flicked my pebble in and watched it skip thrice. Breaking the crisp silence after the pebble’s last plop, I said on an impulse: “To hide myself.” It was September my eleventh grade year when I made that confession, to them and to myself. Like all of my Mathcounts friends, I trolled, told people my name was Charlie and that I came from Mexico. While I maintained my outlandish facade, no one could judge the real me.

It’s meaningful, it really is, to let yourself feel vulnerable. One late night at SPARC, about a month before I skipped stones that day, was the first time I let anyone know that I hadn’t been having a great time at Exeter. There’s the fake smile that came whenever someone asked about Exeter, followed by “It’s awesome!” before I’d wax on about the people, the academics, the resources, or something.³ There was also the burnout, the frustration, and the loneliness that more defined my Exeter experience then. Letting some SPARClers understand this little piece of me—that felt awesome. Although I won’t forget those tense moments between the rustling of test booklets and “Pencils down!”, it is memories like these that I hold to and cherish.

Thank you, AoPS, for leading me down this path, to all these memories. Thank you for taking the time to read this. I hope you’ll remember something and carry it with you. Feel free to comment; ask me anything you want. I hope you’ll learn something about yourself from doing math, competing in contests, and interacting with the community here. You guys have taught me so much; I’ll be forever grateful. And finally, I hope you enjoyed understanding this little piece of me.

¹ Amusingly, one particular game was my first interaction with Codeforces users chaotic_iak, Yoshiap, ksun48, and betaveros.

² Of course, contests are wonderful in providing direction and giving a little extra push. And I notably leave out college in my list of “bad motivations,” because I do think contests help a lot with that, especially if math is your thing. However, people also get into college for research, crew, and poetry.

³ Today, I can more honestly say that Exeter is indeed amazing. :)

Привет, Codeforces!

Отборочный этап чемпионата КРОК 2016 состоится в пятницу 18-го марта в 19:35 (московское время).

После нашего крайнего раунда, Yang Liu (desert97), Michael Kural (pi37) и я поняли, что мы еще не завязали с подготовкой раундов. Мы объединили усилия с Kevin Sun (ksun48) и Daniel Chiu (waterfalls) чтобы предложить еще один раунд для вас.

Этот раунд будет сразу для обоих дивизионов и будет состоять из 7 задач. Те из вас, кто прошел Квалификацию и зарегистрирован на Чемпионат примут участие в официальной редакции, остальные — в неофициальной (открытой для всех). Обе редакции будут рейтинговыми. Как всегда, вас ждет путешествие на тракторе в Бовинию с фермерско-алгоритмическими приключениями в компании фермера Джона, Бесси и ее лучшего друга Элси!

Перед стартом хочется поблагодарить GlebsHP за блестящую работу в роли координатора. Глеб, без тебя не было бы никакой надежды провести этот раунд! Так же наша благодарность MikeMirzayanov и всей команде Codeforces за создание клевых платформ Codeforces и Polygon. Наконец, мы безмерно благодарны abacadaea за помощь с идеями задач, а winger и AlexFetisov за прорешку раунда.

Формально, будут проведены два раунда на одном и том же комплекте задач (оба раунда рейтинговые):

• КРОК 2016 — Отборочный Раунд: для зарегистрированных на Чемпионат участников, кто прошел Квалификацию,
• КРОК 2016 — Отборочный Раунд (рейтинговая неофиц. редакция): для всех остальных.

Вы можете принять участие в Раунде официально, если на момент регистрации в нем вы зарегистрированы на Чемпионат и решили в Квалификации хотя бы одну задачу. Еще раз напомним, что независимо от формы участия, ваш рейтинг будет обновлен по результатам раунда. Единственная различие — в случае успешного выступления официальные лучшие 50 участников будут приглашены на Финал в Москву. Организация поездки (билеты, гостиница, виза и всё остальное) — это полностью забота финалистов. Участникам Финала КРОК-2016 будут покрыты транспортные расходы на сумму не более 10000 рублей (предполагается проезд обыкновенным купейным вагоном, либо, по согласованию, эконом-перелет самолетом). До 25-го марта необходимо будет подтвердить желание и возможность принять участие в Финале. Участники Финала будут бороться за призы:

• 1 место — 100000 рублей
• 2 местo — 70000 рублей
• 3 местo — 50000 рублей

Мы еще обновим пост информацией о разбалловке.

Надеемся, что вам понравятся задачи и наши коровоориентированные тексты. Удачи!

UPD3: Так как примерно 15 последних минут соревнования тестирующая система некорректно обрабатывала попытки по F в раунде "КРОК 2016 — Отборочный Раунд" (и это отдельная интересная история как так вышло), вы можете обжаловать ваше изменение рейтинга, если влияние этого инцидента на ваш результат велико. Если вы отсылали F в последние 15 минут и имеете веские аргументы почему некорректный вердикт (WA/RE на тесте 1) сильно повлиял на ваше место, то напишите MikeMirzayanov и ваше участие можно будет сделать нерейтинговым. Приносим извинения за эту накладку. Апелляцию надо написать до 02:59 20-го марта (московское время).

I wrote problem 603E - Pastoral Oddities for the recent Codeforces round and was pleasantly surprised to see so many different solutions submitted in addition to my own (14611571). Even though I proposed the problem, I learned a lot by reading the submissions after the contest! Since I think these other approaches illustrate some beautiful techniques, I would like to share them with you guys. Below, I describe three different solution ideas by jqdai0815, winger, and malcolm, respectively. (If you haven't read the editorial yet, I suggest that you do so before continuing, since some of the observations and definitions carry over.)

Solution 1: jqdai0815

Like my original solution, this approach uses a link-cut tree to maintain an online MST. The main idea is the following observation: In a tree with an even number of vertices, an edge can be removed if and only if it separates the graph into two even-sized components. Thus we assign each edge a parity—even if removing it creates two even-sized components and odd if removing it creates two odd-sized components. Note that our answer is the maximum-weight odd edge in the minimum spanning tree. To apply this observation to our original problem, we can initialize our tree by linking all of its vertices together with infinite weight edges.

Now consider the operation of adding an edge connecting u and v to this minimum spanning tree. This consists of finding the maximum-weight edge on the path between u and v, and replacing it with our new edge if the new edge has a smaller weight. If we replace the edge, we have to update the parities of the edges in the new tree. Note that our new edge has the same parity as the old edge. In addition, all the edges not on path u-v in the old tree keep their parity. Now, consider the edges on path u-v. If we removed an even edge, then their parities also stay the same. Otherwise, the parities of all edges on this path get flipped. Thus we can store edges as vertices on the link-cut tree and support path updates with lazy propagation to maintain the parity of each edge.

To find the answer after adding each edge, observe that our answer never increases when we add a new edge. Thus we can use an STL set to store the current set of edges, and iterate down from our previous answer until we find an odd edge. Due to this step and the link-cut tree, this algorithm runs online in amortized . jqdai0815 wrote a succinct implementation here: 14604705.

Solution 2: winger

During testing, winger found this solution which uses divide-and-conquer to solve the problem offline in . We divide-and-conquer with respect to time by recursively solving subproblems of the form "Find all answers from time l to time r, given that these answers lie in the interval [lo, hi]." To do this, we first find the answer for m = (l + r) / 2, adding edges and maintaining connected components a la Kruskal's until there are no more odd-sized components. Once we have the answer ans_m for m, we can call the same function to solve the problem in [l, m - 1], given that the answers lie in [ans_m, hi], and the problem in [m + 1, r], given that the answers lie in [lo, ans_m].

In order to make the complexity work out, we have to keep the edges that we added earlier between levels of recursion—that is, we enter the problem with our union-find data structure already containing the edges with time less than l and weight less than lo. Before calling the next levels of recursion, we insert edges into the union-find data structure to make this condition hold. To make returning to a previous state of the union-find possible, we keep track of all the changes that we make. Thus in a single level of recursion, we do one set of modifications on the union-find to compute ans_m, then rollback, one set of modifications to satisfy the precondition for the interval [l, m - 1] × [ans_m, hi], then rollback, and finally one set of modifications to satisfy the precondition for the interval [m + 1, r] × [lo, ans_m].

The edges we use when computing our answer for m and for deeper levels of the recursion either have time in [l, r] or weight in [lo, hi], hence each edge appears in at most two separate instances of the recursion at each level. Since there are levels, edges appear a total of times. We process them in per edge, thus we have the desired complexity of . Below is a diagram illustrating this idea with edges represented as points (time, weight). (The big box represents the current level of recursion, while the red/blue highlights represent the next level.)

subscriber implemented the same idea here: 14601511.

Solution 3: malcolm

Finally, malcolm had another offline divide-and-conquer solution that ran in using a segment tree. In this solution, we first sort the edges by weight and then find the answers for the queries from last to first. We build a segment tree over all of the queries and do a DFS on it, visiting the right child before visiting the left. Simultaneously, we maintain a union-find data structure that supports rollback. Before we look at the details of this algorithm, we make the observation that if an edge i is used in the optimal solution at time j, then edge i should be present in the union-find in the time interval [i, j].

The DFS works as follows: At each internal node of the segment tree, we add all edges assigned to that node to the union-find before visiting its children. When we leave that node, we rollback the union-find to its initial state. At each leaf, we find the answer for the time value represented by the leaf. We process edges in order of increasing weight, starting from where we left off in the previous leaf. Suppose we are at the leaf representing time j. We compute the answer for j by adding edges as we do in Kruskal's algorithm until we have no more odd-sized components, making sure to only add the ones that appear before time j. When we add edge i to the union-find, we also update the segment tree over the interval [i, j - 1], adding edge i to the set of nodes covering this range. Thus we know when to add edge i to the union-find later in our DFS. Again, before leaving this leaf, we rollback our union-find to its initial state.

Each edge appears in the segtree times, so the overall complexity of this algorithm is . You can look at malcolm's code here: 14600443.

EDIT: Thanks to mmaxio for pointing out that due to rollbacks, we can only have instead of amortized O(α(n)) as the time complexity for our union-find operations. To get , we can use union by size (merging smaller into larger) or by rank (merging shorter into taller) to achieve a non-amortized bound on the maximum height of the tree.

By the way, if anyone has questions about these solutions, feel free to ask!