Hi Codeforces! I am a member of the reasoning team at OpenAI. We are especially excited to see your interest in the OpenAI o1 model launch, many of us being Codeforces users ourselves (chenmark, meret, qwerty787788, among others). Given the curiosity around the IOI results, we wanted to share the submissions that scored 362.14—above the gold medal threshold—from the research blog post with you. These were the highest scoring among 10,000 submissions, so still a ways to go until top human performance, but we aspire to be there one day.

The following C++ programs (including comments!) are written entirely by the model. Special thanks to PavelKunyavskiy for maintaining the IOI mirror, which we used to check our scores. We hope you enjoy taking a look!

nile (100/100)

• Submission (100/100)

message (79.64/100)

• Submission (79.64/100; subtask 1 and partial credit on subtask 2)

tree (30/100)

• Submission 1 (17/100; subtasks 1 and 4)
• Submission 2 (13/100; subtask 2)

hieroglyphs (44/100)

• Submission 1 (34/100; subtasks 1, 2, and 4)
• Submission 2 (10/100; subtask 3)

mosaic (37/100)

• Submission 1 (22/100; subtasks 1, 2, and 4)
• Submission 2 (20/100; subtasks 1, 3, and 5)

sphinx (71.5/100)

• Submission 1 (50/100; 50% partial credit on all subtasks)
• Submission 2 (43/100; subtasks 1, 2, and 3)

Lastly, we hope you find the new model magical and delightful—we can’t wait to hear about the amazing things you’ll build with it. (But please don’t use it to cheat on Codeforces!)

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. :)

Hey Codeforces!

The Elimination Round of the CROC 2016 Championship will take place on Friday, March 18 at 16:35 UTC. After our last round, Yang Liu (desert97), Michael Kural (pi37) and I realized that we haven't had enough, so we joined forces with Kevin Sun (ksun48) and Daniel Chiu (waterfalls) to prepare another problem set for you guys. Our contest will be for combined divisions and consist of seven problems. And although only those who pass the Qualification Round can participate officially, the round will be open to and rated for all Codeforces users. As always, we'll be taking the tractor to Bovinia for some farmland algorithmic adventures with Farmer John, Bessie and her best friend Elsie!

Before we begin, we'd like to thank GlebsHP for doing a wonderful job as contest coordinator—we'd be hopeless without you. We would also like to thank MikeMirzayanov and the Codeforces staff for creating the awesome Codeforces and Polygon platforms. And finally, we're immensely grateful to abacadaea for providing one of the problem ideas and to winger and AlexFetisov for test solving our round.

Formally, there will be two rounds on the same problem set (both rated):

• CROC 2016 — Elimination Round: for registered Championship participants who have passed the Qualification,
• CROC 2016 — Elimination Round (Rated Unofficial Edition): for all others.

To take part in the official round you have to be registered for the Championship and solve at least one problem in Qualification round. Both the elimination round and its unofficial edition will be rated. The only difference is that the top 50 participants in the official round will be invited to join the Finals in Moscow. Finalists will be responsible for organizing their trip (tickets, hotel, visas and so on). Each participant may claim reimbursement for transportation expenses not exceeding ~135 USD. Invitations should be accepted no later than March 25.

We hope you enjoy our problems and our cow-flavored text even more than you did last time! Good luck!

UPD1: System testing is delayed because we are investigating some technical issues.

UPD2: The editorial has been posted here. Thanks for participating!

UPD3: Since last ~15 minutes judging system was incorrectly configured for F in the contest "CROC 2016 — Elimination Round" (it is interesting story how it happened), you may appeal your rating change if it affected you much. If you have submitted a solution for F in last 15 minutes and you have strong arguments why incorrect verdict (WA/RE on the test 1) significantly affected your place, please write MikeMirzayanov to make your participation unrated. Sorry about the issue. You can do it before March, 19, 23:59 (UTC).

UPD4: I'd like to congratulate the winners of each round, as well as the top 50 in the Elimination Round for progressing to the CROC 2016 Championship Finals! In addition, Petr and jqdai0815 deserve a special shoutout for solving all seven problems!

CROC 2016 — Elimination Round

1. Petr
2. tourist
3. vepifanov
4. rng_58
5. I_love_Tanya_Romanova

CROC 2016 — Elimination Round (Rated Unofficial Edition)

1. jqdai0815
2. anta
3. Alex_2oo8
4. NaiveNaive
5. eddy1021

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!