--- Page 1 --- Competitive Programming with Large Reasoning Models OpenAI Abstract We show that reinforcement learning applied to large language models (LLMs) significantly boosts performance on complex coding and reasoning tasks. Additionally, we compare two general-purpose reasoning models OpenAI o1 and an early checkpoint of o3 with a domain-specific system, o1- ioi, which uses hand-engineered inference strategies designed for competing in the 2024 International Olympiad in Informatics (IOI). We competed live at IOI 2024 with o1-ioi and, using hand-crafted test-time strategies, placed in the 49th percentile. Under relaxed competition constraints, o1-ioi achieved a gold medal. However, when evaluating later models such as o3, we find that o3 achieves gold without hand-crafted domain-specific strategies or relaxed constraints. Our findings show that although specialized pipelines such as o1-ioi yield solid improvements, the scaled-up, general-purpose o3 model surpasses those results without relying on hand-crafted inference heuristics. Notably, o3 achieves a gold medal at the 2024 IOI and obtains a CodeForces rating on par with elite human competitors. Overall, these results indicate that scaling general-purpose reinforcement learning, rather than relying on domain-specific techniques, offers a robust path toward state-of-the-art AI in reasoning domains, such as competitive programming. Introduction Competitive programming is widely recognized as a challenging benchmark for evaluating reasoning and coding proficiency [2]. Solving complex algorithmic problems demands advanced computational thinking and problem solving skills. Moreover, these problems are also objectively gradable, making it an ideal testbed to assess the reasoning capabilities of AI systems. Recent work on program synthesis with large language models [1] has demonstrated that even rela- tively general models, ranging from 244M to 137B parameters, can generate short Python scripts from natural language instructions. Importantly, performance improves log-linearly with model size, and fine- tuning significantly boosts accuracy. Concurrently, Codex [2], an early code-focused LLM, excelled at Python program generation and powered GitHub Copilot. Further progress came from AlphaCode [7], which tackled competitive programming tasks using large-scale code generation and heuristics at in- ference, and the subsequent AlphaCode2[6], whose improvements nearly doubled AlphaCode s solved problems and placed it in the 85th percentile on the CodeForces platform. Both AlphaCode systems used large-scale sampling of up to a million candidate solutions per problem before selecting their top 10 submissions with a hand-engineered test-time strategy. Since then, significant progress has been made in harnessing reinforcement learning to improve LLMs reasoning skills. This has led to the emergence of large reasoning models (LRMs): language models trained via reinforcement learning to reason and think through extended chains of thought. In particular, OpenAI s o1 [4, 12] and its soon-to-be-released successor o3 [13] use chain-of-thought reasoning to tackle intricate tasks such as mathematics and coding. Work by DeepSeek-R1 [3] and Kimi k1.5 [15] independently illustrates how learning chain-of-thought boosts performance on both mathematical and programming challenges. An open question is how domain-specific, hand-engineered inference strategies compare to learned approaches that models generate and execute on their own. We have three systems available that can shed light on this question: o1, o1-ioi, and early checkpoints of o3. OpenAI o1 was the first large rea- soning model and used general purpose methods to improve programming performance. Building on this foundation, o1-ioi was a fine-tuned system tailored to compete in the 2024 International Olympiad in Informatics (IOI) and used test-time strategies similar to those used in the AlphaCode system. This specialization led to strong performance improvements on both the 2024 IOI and competitive program- ming platforms such as CodeForces. Subsequent advances led to the development of o3, which has Contributions listed in Appendix A arXiv:2502.06807v2 [cs.LG] 18 Feb 2025 --- Page 2 --- significantly advanced the reasoning capabilities of AI models. Unlike o1-ioi or AlphaCode, o3 does not depend on coding-specific test-time strategies defined by humans. Instead, we found that complex test- time reasoning strategies emerged naturally from end-to-end RL, leading to unprecedented performance on competitive programming benchmarks. This report provides a high-level overview of the importance of reasoning in coding tasks such as competitive programming, the progress of OpenAI s large reasoning models in programming ability, and our evaluation methodology and results on various competitive programming and coding benchmarks. OpenAI o1 We start with OpenAI o1, a large language model trained with reinforcement learning to tackle complex reasoning tasks. By generating an extended internal chain of thought before answering [16], o1 resembles a human who methodically works through a challenging problem step by step. Reinforcement learning refines this chain-of-thought process, helping the model identify and correct errors, break down complex tasks into manageable parts, and explore alternate solution paths when an approach fails. These in- context reasoning capabilities substantially boost o1 s overall performance on a wide range of tasks. Additionally, OpenAI o1 is trained to use external tools [14], especially for writing and executing code in a secure environment.1 This capability lets o1 verify whether its generated code compiles, passes provided test cases, and meets other correctness checks. By testing and refining its outputs, o1 iteratively improves its solutions over the course of a single sample. 2.1 CodeForces Benchmark CodeForces is a programming competition website that hosts live contests. It is internationally com- petitive and frequented by some of the best competitive programmers in the world. To assess our models competitive programming abilities, we simulated CodeForces contests under conditions that closely mirrored real competitions. This included using the full test suite for each problem and enforcing appropriate time and memory constraints for solutions. Our evaluation focused on Division 1 contests from 2024 and December 2023, ensuring all test contests occurred after the data cut-off for both pretraining and RL. Additionally, we conducted a contamination check as a sanity measure, leveraging the OpenAI embedding API to verify that test problems had not been seen during training. gpt4o o1-preview o1 Codeforces rating 808 11th 1258 62nd 1673 89th Codeforces rating percentile Figure 1: Comparing reasoning LLMs OpenAI o1-preview and o1 to gpt-4o on CodeForces. We compared o1 against a non-reasoning LLM (gpt-4o) and an earlier reasoning model (o1-preview). Figure 1 shows how both o1-preview and o1 dramatically outperform gpt-4o, highlighting the effectiveness of reinforcement learning for complex reasoning. The o1-preview model achieved a CodeForces rating of 1258 (62nd percentile) up from gpt-4o s 808 (11th percentile). Further training pushed o1 s rating to 1673 (89th percentile), establishing a new milestone for AI performance in competitive programming. 1https: platform.openai.com docs assistants tools code-interpreter --- Page 3 --- In Appendix B we provide additional details of which problems our models can solve and how ratings were calculated. OpenAI o1-ioi During our development and evaluation of OpenAI o1, we found that increasing both the amount of reinforcement learning (RL) compute and test-time inference compute consistently improved model per- formance. Figure 2: Additional RL training and additional test-time compute improves competitive mathematics performance. As shown in Figure 2, scaling RL training and extending test-time inference led to marked gains, highlighting the importance of optimizing these two compute dimensions to push performance beyond conventional LLM pretraining. Building on these insights, we created the o1-ioi system for competing at the 2024 International Olympiad in Informatics (IOI). In addition to continued RL training targeted at coding tasks, o1-ioi incorporates specialized test-time inference strategies engineered for competitive programming. 3.1 Coding RL Fine-tuning Our first step extended the reinforcement learning phase of OpenAI o1, focusing on coding tasks. By dedicating additional training compute to programming problems, we bolstered the model s ability to plan, implement, and debug more involved solutions. Concretely: 1. We resumed RL training from the OpenAI o1 checkpoint. 2. We specifically emphasized challenging programming problems, helping the model improve C generation and runtime checks. 3. We guided the model to produce outputs in the IOI submission format. This added focus on coding allowed o1-ioi to write and execute C programs during inference. The model improved its reasoning by iteratively running and refining solutions, thereby strengthening both its coding and problem-solving skills. 3.2 o1-ioi Test-time Strategy At a high level, we divided each IOI problem into its constituent subtasks, sampled 10,000 solutions from o1-ioi for each subtask, and then employed a clustering- and reranking-based approach to decide which solutions from this set to submit. --- Page 4 --- Problem formulation For o1-ioi we chose to attempt to solve the individual subtasks of each problem separately, as the scoring for IOI is done on a subtask-by-subtask basis and gives each competitor the maximum score over all of their attempts on each subtask. To do this, we divided each IOI problem into its composite subtasks (using the divisions laid out in the scoring guide for each problem). This was done simply by creating one version of the document for each subtask with the information about the other subtasks removed. Clustering We clustered the generated solutions based on their outputs on model-generated test in- puts. For each subtask, we first prompted the model to write random test input generators in C given the problem specification and subtask. We used these generators to generate 256 random test inputs. To ensure the validity of these test inputs, we then prompted the model to write test input validators in C that check, given a test input, whether it satisfies the subtask constraints. Finally, we accepted each test input that passes at least 75 of the validators. For each subtask, we generated 256 of these random test case inputs, and then clustered based on their outputs for these test cases. Any programs that matched each other s outputs on all test inputs would be placed in the same cluster. Reranking We then implemented the reranking core of our test-time compute strategy. We scored each solution based on: The quality of the solution according to a learned scoring function. Errors on model-generated test inputs. Failing the provided public test cases. Each cluster was given a score defined as the average score of the samples it contained minus a penalty for each time a sample submission was attempted from that cluster. The weights of all of these penalties were tuned by random search on solutions to previous years IOI problems, by directly simulating the submission process. Submission We then submitted up to 50 (the maximum number allowed for human competitors) of these solutions in a round-robin fashion over subtasks, starting from the hardest. We selected the top- ranked solution in the top-ranked cluster for each given subtask. When a subtask was solved (meaning that the maximum score was attained), we ceased sampling on that subtask. When submitting solutions to any subtask that was a strict superset of a solved subtask, we would filter out any solutions that did not match the outputs on test inputs of the solved constituent subtasks, allowing us to rapidly narrow down candidate solutions on harder subtasks by rejecting those that would almost certainly have failed easier subtasks. 3.3 CodeForces Benchmark Once again, we simulated CodeForces contests to evaluate o1-ioi s coding abilities, closely mirroring contest conditions with the complete test suite for each problem and appropriate time and memory restrictions for solutions. Figure 3 shows that o1-ioi reached a CodeForces rating of 1807, outperforming 93 of competitors demonstrating clear improvements from additional RL training on coding tasks. When we applied a simple filter rejecting any solution that failed public tests, the rating rose to 2092 (96th percentile). Our complete test-time strategy pushed performance even further, attaining a rating of 2214 (98th percentile). These results confirm that domain-specific RL fine-tuning paired with advanced selection heuristics can significantly boost competitive programming outcomes. 3.4 IOI 2024 Live Competition The o1-ioi system participated in the 2024 International Olympiad in Informatics (IOI) under the same conditions as human contestants. It had ten hours to solve six challenging algorithmic problems and was allowed up to 50 submissions per problem. We show the results in Figure 4. During the competition, our system generated 10,000 candidate solutions for each problem, and selected 50 submissions using our test-time selection strategy. This strategy prioritized submissions based on their performance on the IOI public test cases, model-generated test cases, and a learned scoring function. The model scored 213 points, placing it in the 49th percentile of the competition. --- Page 5 --- o1 o1-ioi o1-ioi public test filtering o1-ioi full-test-time strategy Codeforces rating 1673 89th 1807 93rd 2092 96th 2214 98th Codeforces rating percentile Figure 3: Further training OpenAI o1 on coding tasks and incorporating test-time strategies improves performance. Random (50-submissions) Hand-crafted (50-submissions) Random (10K Submissions) Submission Strategy Score 362.14 IOI Performance by Submission Strategy Figure 4: Performance of o1-ioi competing at IOI 2024. In comparison, selecting 50 random submissions would have yielded an average score of only 156 points, indicating that the selection strategy contributed nearly 60 additional points under the compe- tition s constraints. When the submission limit was relaxed to 10,000 per problem, the model s performance improved dramatically. Without employing any test-time selection strategy, it achieved a score of 362.14, surpassing the gold medal threshold and demonstrating the model s potential. We show samples that yielded the 362.14 score in Appendix C. OpenAI o3 Building on the insights gained from o1 and o1-ioi, we explore the limits of reinforcement learning (RL) training alone, without relying on human-engineered test-time strategies. While o1-ioi achieved strong --- Page 6 --- results by combining additional RL fine-tuning with carefully designed test-time inference pipelines, its success hinged on human intervention to define and implement these strategies. We sought to explore the performance of a model even further trained with RL with the ability to autonomously develop and execute its own test-time reasoning strategies. To this end, we obtained access to early checkpoints of o3 [13] to evaluate on competitive programming tasks. 4.1 CodeForces Benchmark We evaluate an early checkpoint of the o3 model on our CodeForces benchmark set, where each prompt includes the problem description, constraints, and any available sample test cases. o1 o1-ioi o3 Codeforces rating 1673 89th 2214 98th 2724 99.8th Codeforces rating percentile Figure 5: Performance of OpenAI o3 on the CodeForces benchmark. As shown in Figure 5, further RL training provided a significant improvement over both o1 and the full o1-ioi system. Notably, the transition from the o1-ioi model to o3 resulted in a rating increase from 2214 (98th percentile) to 2724 (99.8th percentile), reflecting a substantial leap in competitive programming performance. This improvement demonstrates o3 s ability to solve a wider range of complex algorithmic problems with higher reliability, pushing its capabilities closer to top-tier human competitors on CodeForces. In addition to its significantly improved problem-solving capabilities, we observe that o3 demonstrates more insightful and deliberate chains of thought. The model not only writes and executes code to validate its solutions against public test cases, it also refines its approach based on these verifications. Figure 6 shows an advanced test-time strategy discovered by o3: for problems where verification is nontrivial, it often writes simple brute-force solutions trading efficiency for correctness then cross-checks the outputs against its more optimized algorithmic implementations. This self-imposed validation mechanism lets o3 catch potential errors and improve the reliability of its solutions. 4.2 IOI 2024 Benchmark Although we competed in IOI 2024 using o1-ioi, we retrospectively evaluated a checkpoint of o3 on the same six IOI 2024 problems to compare performance under identical conditions. As with o1-ioi, we strictly adhered to the official IOI rules, which permit a maximum of 50 submissions per problem. The o3 results on the IOI 2024 were produced by a later version of o3 than the CodeForces results, and included additional fresher training data. IOI 2024 occurred after the training cut-off for this model, and we additionally confirmed with search that the IOI test problems are not contaminated with the training set. Sampling Approach. Unlike o1-ioi, which sampled solutions separately for each subtask, we adopted a different approach when evaluating o3: sampling from a single prompt containing the original problem --- Page 7 --- Figure 6: o3 testing its own solution. This reflects a sophisticated reasoning strategy that partially implements the hand-designed test-time strategy used for o1-ioi in IOI 2024. statement. Additionally, while o1-ioi generated 10K solutions per subtask, for o3 we sampled only 1K solutions per problem. Selection strategies also differed between the two models. Whereas o1-ioi relied on a complex, human- defined test-time strategy (3.2) to select solutions, o3 followed a much simpler approach. Specifically, we selected the top 50 solutions with the highest test-time compute from 1,024 samples per problem. Despite this streamlined method, o3 produced robust solutions capable of covering many, if not all, subtasks without the need for subtask-specific prompts, manual partitioning, or intricate submission strategies. o1-ioi (50-Submissions) o1-ioi (10K-Submissions) O3 (50-Submissions) Submission Strategy Score 362.14 395.64 IOI Performance by Submission Strategy Figure 7: IOI 2024 scores under different submission strategies. Even without human-engineered heuristics or relaxed submission limits, o3 outperforms o1-ioi and surpasses the gold threshold with just 50 submissions. --- Page 8 --- Results. Figure 7 presents the final scores. The IOI scoring system is subtask-based, with a maximum total of 600 points in the 2024 contest. The gold medal threshold was approximately 360 points. Key results include: o1-ioi scored 213 points with 50 submissions, improving to 362.14 points with 10K submissions, just above the gold medal cutoff. o3 achieved 395.64 points, surpassing the gold threshold even under the 50-submission limit. These results demonstrate that o3 outperforms o1-ioi without relying on IOI-specific, hand-crafted test-time strategies. Instead, the sophisticated test-time techniques that emerged during o3 training, such as generating brute-force solutions to verify outputs, served as a more than adequate replacement and eliminated the need for the hand-engineered clustering and selection pipelines required by o1-ioi. Overall, the IOI 2024 findings confirm that large-scale RL training alone can achieve state-of-the-art coding and reasoning performance. By independently learning to generate, evaluate, and refine solutions, o3 surpasses o1-ioi without dependence on domain-specific heuristics or clustering-based methods. Software Engineering Evaluations We have demonstrated how reasoning significantly enhances LLM performance in competitive program- ming, where solving complex algorithmic challenges requires deep logical thinking. However, we also sought to evaluate the impact of reasoning on real-world coding tasks. To this end, we tested our models on two datasets: the HackerRank Astra2 dataset and SWE-bench verified3 [5, 11]. 5.1 HackerRank Astra The HackerRank Astra dataset is composed of 65 project-oriented coding challenges, each crafted to simulate real-world software development tasks. These challenges cover a range of frameworks, including React.js, Django, and Node.js, allowing for hands-on experience in building features and applications. What sets this dataset apart is its focus on assessing problem-solving skills in complex, multi-file, long- context scenarios that mirror actual development environments. Unlike typical competitive programming datasets, HackerRank Astra does not provide public test cases, which prevents us from relying on hand- crafted test-time tactics. Evaluating performance with this dataset reveals whether reasoning abilities enhance success in algorithmic problem solving alone, or extend to more practical, industry-related coding tasks. Figure 8 presents performance metrics such as pass 1 (the probability of successfully completing a task on the first attempt) and average scores (the mean proportion of test cases passed). The results illustrate the impact of chain-of-thought reasoning, with the o1-preview model achieving a 9.98 im- provement in pass 1 and a 6.03-point gain in average score compared to GPT-4o. Further fine-tuning through reinforcement learning enhances o1 s performance, yielding a pass 1 of 63.92 and an average score of 75.80 a 3.03 increase in pass 1 over o1-preview. These metrics demonstrate o1 s enhanced reasoning and adaptability, enabling it to address complex, industry-relevant software development tasks effectively. 5.2 SWE-Bench Verified SWE-bench Verified is OpenAI s preparedness team s human-validated subset of SWE-bench that more reliably evaluates AI models ability to solve real-world software issues. This validated set of 500 tasks fixes certain issues with SWE-bench such as incorrect grading of correct solutions, under-specified prob- lem statements, and overly specific unit tests. This helps ensure the benchmark accurately grades model capabilities. To illustrate performance on this software task, we display the results presented in the o1 system card [4] as well as results from an early o3 checkpoint [13]. Because o1-preview was not trained to use code execution or file editing tools, the best-performing open-source scaffold at the time of initial implementation, Agentless was used. Unlike for IOI, no specialized test-time strategies was used for SWE-Bench verified. All models are given 5 tries to generate a candidate patch. If the model fails after 2www.hackerrank.com ai astra 3https: openai.com index introducing-swe-bench-verified --- Page 9 --- gpt-4o o1-preview o1 Models Percentage ( ) 50.91 60.89 63.92 69.52 75.55 75.80 HackerRank Astra Pass 1 ( ) Avg Score ( ) Figure 8: HackerRank Astra evaluation. 5 attempts, it is considered an incorrect attempt. All evaluations are averaged over 3 trials. We do not penalize the model for system failures (e.g., container hangs or grading failures), and we retry these rollouts until we can record a valid attempt. gpt4o o1-preview o1 o3 Models Percent Correct 33.2 41.3 48.9 71.7 SWE-bench Verified Figure 9: SWE-bench evaluation. As illustrated in Figure 9, o1-preview demonstrates an 8.1 performance improvement on SWE-bench compared to gpt-4o, showcasing notable advancements in reasoning capabilities. With additional rein- forcement learning compute applied during training, o1 achieves a further 8.6 improvement. Notably, o3, which was trained with significantly greater compute resources than o1, delivers an impressive 22.8 improvement over o1. These results underscore that enhanced reasoning skills extend beyond competitive programming challenges, proving their applicability to real-world tasks like software engineering. --- Page 10 --- Conclusion Through the o-series large reasoning models, we demonstrate that chain-of-thought reasoning is a pow- erful strategy for improving performance in coding tasks, from competitive programming benchmarks such as CodeForces and IOI to complex software engineering challenges like SWE-bench and Astra. Our findings highlight that increasing reinforcement learning training compute, coupled with enhanced test-time compute, consistently boosts model performance to nearly match the best humans in the world. Given these results, we believe o-series large reasoning models will unlock many new use cases for AI in science, coding, math, and many other fields. A Authorship, credit attribution, and acknowledgments Data Preparation: Borys Minaiev, Ignasi Clavera, Lorenz Kuhn, Nat McAleese, Oleg M urk, Szymon Sidor IOI Model Training: Ahmed El-Kishky, Mostafa Rohaninejad Sampling Infrastructure: Andre Saraiva, Hunter Lightman, Vineet Kosaraju, Wenda Zhou Test-time Strategy: Alexander Wei, Daniel Selsam, David Dohan, Francis Song, Ignasi Clavera, Max Schwarzer, Rhythm Garg, Rui Shu Evaluation: Andre Saraiva, Ignasi Clavera, Lorenz Kuhn, Nat McAleese Leadership: Jakub Pachocki, Jerry Tworek, Lukasz Kaiser, Mark Chen o3 Model Development o3 contributors [13]. Acknowledgments: We are grateful to the IOI committee for allowing us to enter our model, o1-ioi, in the 2024 International Olympiad in Informatics. We also extend our thanks to Wael Ewida, a member of the IOI technical committee, for hosting a portal that enabled us to submit our solutions under the same conditions as the contestants. Additionally, we appreciate the support of those who contributed to and maintained our sandboxed code execution, including Taylor Gordon, Oleg Boiko, John Rizzo, Paul Ashbourne, Leo Liu, Alexander Prokofiev, and Scottie Yan. We also extend our gratitude to Chris Orsinger and Michelle Fradin for their contributions to data efforts. Finally, we would like to express our sincere gratitude to everyone involved in the reinforcement learning reasoning efforts for o1 and o3, whose dedication and expertise were instrumental in advancing this work. B Additional CodeForces Details In order to compare our models to human competitive programmers, we simulate contests. This section provides details of how the simulation is performed, how the overall score and ratings are calculated, as well as the per-contest results. B.1 Data For our test set we use Division 1 contests from late 2023 and 2024, all of which occurred after the o3 training set data cut-off. As a redundant additional check, we used embedding search to confirm that the test problems have not been seen by the model during training. We excluded one contest that contained an interactive problem for which grading was inconvenient, but otherwise included all post- cut-off Division 1 problems to which we had access at the time. During training we used a validation set of primarily Division 2 problems; when that set indicated that performance was very strong we built and evaluated the Division 1 set presented here. --- Page 11 --- B.2 Grading We run the complete set of tests for each problem, and have confirmed that our test environment closely matches the official CodeForces grading service, including by manually submitting solutions for the hardest problems to the official CodeForces graders. Following AlphaCode [6] we allow the model to make 10 independent submissions against the full test set and mark a problem as solved if any one of those 10 passes. This is close to but not strictly the same as the human affordance, as human participants see only the results of the pre-tests during the competition. However in Division 1 contests the pre-tests are typically strong (highly correlated with full tests), and in our results the number of failures before a passing submission is typically small (see 1). We did not have access to labels for which test cases were pre-tests. B.3 Thinking Time Competitors receive a higher score for submitting their solutions faster. Because models can think in parallel and simultaneously attempt all problems, they have an innate advantage over humans. We elected to reduce this advantage in our primary results by estimating o3 s score for each solved problem as the median of the scores of the human participants that solved that problem in the contest with the same number of failed attempts. We could instead use the model s real thinking time to compute ratings. o3 uses a learned scoring function for test-time ranking in addition to a chain of thought. This process is perfectly parallel and true model submission times therefore depend on the number of available GPU during the contest. On a very large cluster the time taken to pick the top-ranked solutions is (very slightly more than) the maximum over the thinking times for each candidate submission. Using this maximum parallelism assumption and the sequential o3 sampling speed would result in a higher estimated rating than presented here. We note that because sequential test-time compute has grown rapidly since the early language models, it was not guaranteed that models would solve problems quickly compared to humans, but in practice o3 does. B.4 Estimated Rating The CodeForces rating system is described by the creator in three blog posts [8, 9, 10]. Ratings are similar to the Elo system and satisfy the property that if competitor A has rating RA and competitor B has rating RB then the probability that A ranks better than B any final contest standings is estimated as RB RA To find the model rating we first calculate the rank of the model in each of the test contest from the total contest score (described above) and then directly maximize the likelihood of the observed rankings and human ratings with respect to the model rating using the equation above. We average to ensure that contests with more participants are not over-weighted. We validated that this recovers known human ratings based on their contest performance and also gives similar values to linearly predicting participant rating from their average solve rate. B.5 Percentile performance Codeforces maintains a global leaderboard of active participants, and an estimated rating can be used to compare to that group. We can also directly compare the solve rate of o3 in our test contests to the other participants in those contests. Figure 10 shows both these comparisons. Each point is a person that competed in at least 8 of the test contests. We show their average solve rate over contests that they entered against their rating, as well as the rating thresholds for key performance levels. The very best human competitors remain much stronger than o3, with solve rates in excess of 85 , but both ratings and solve rates indicate that o3 would rank among the top 200 active participants worldwide. B.6 Per Problem Breakdown --- Page 12 --- top 200 top 10 top 1 top 1 worldwide o3 vs top active competitors solve rate ( ) codeforces rating o3 Figure 10: o3 would place among the best human competitive programmers in the world. Here we show the average solve rate and current rating for participants that entered at least 8 of our 12 unseen test contests. Horizontal lines show performance thresholds from the global CodeForces leaderboard of active competitors. The very best humans still solve more problems than AI, for now. Table 1: We estimate our CodeForces rating from simulated contest participation. Here we show a detailed breakdown of o3 performance per-problem. problem problem rating pass 1 (no ranking) pass 10 (no ranking) failed submissions pass 10 (ranking 1162) Contest 1909 - 23 Dec 23 - Pinely Round 3 (Div. 1 Div. 2) score: 7,220 1909 A 1156 1162 1.00 solved 1909 B 1066 1162 1.00 solved 1909 C 1075 1162 1.00 solved 1909 D 1099 1162 1.00 solved 1909 E 703 1162 1.00 solved 1909 F1 57 1162 0.40 solved 1909 F2 0 1162 0.00 not solved 1909 G 3 1162 0.03 not solved 1909 H 0 1162 0.00 not solved 1909 I 0 1162 0.00 not solved Contest 1916 - 30 Dec 23 - Good Bye 2023 score: 8,920 1916 A 1157 1162 1.00 solved 1916 B 1133 1162 1.00 solved 1916 C 1145 1162 1.00 solved 1916 D 483 1162 1.00 solved 1916 E 6 1162 0.05 solved 1916 F 369 1162 0.98 solved 1916 G 0 1162 0.00 not solved 1916 H1 1059 1162 1.00 solved 1916 H2 1045 1162 1.00 solved Contest 1919 - 06 Jan 24 - Hello 2024 score: 6,214 1919 A 1161 1162 1.00 solved Continued on the next page --- Page 13 --- problem problem rating pass 1 (no ranking) pass 10 (no ranking) failed submissions pass 10 (ranking 1162) 1919 B 1141 1162 1.00 solved 1919 C 499 1162 1.00 solved 1919 D 25 1162 0.20 solved 1919 E 6 1162 0.05 solved 1919 F1 1090 1162 1.00 solved 1919 F2 227 1162 0.89 solved 1919 G 0 1162 0.00 not solved 1919 H 0 1162 0.00 not solved Contest 1942 - 30 Mar 24 - CodeTON Round 8 (Div. 1 Div. 2, Rated, Prizes!) score: 8,701 1942 A 1157 1162 1.00 solved 1942 B 1157 1162 1.00 solved 1942 C1 999 1162 1.00 solved 1942 C2 525 1162 1.00 solved 1942 D 1061 1162 1.00 solved 1942 E 347 1162 0.97 solved 1942 F 0 1162 0.00 not solved 1942 G 239 1162 0.90 solved 1942 H 0 1162 0.00 not solved Contest 1943 - 16 Mar 24 - Codeforces Round 934 (Div. 1) score: 3,427 1943 A 116 1162 0.65 solved 1943 B 1 1162 0.01 not solved 1943 C 160 1162 0.77 solved 1943 D1 848 1162 1.00 solved 1943 D2 14 1162 0.11 solved 1943 E1 0 1162 0.00 not solved 1943 E2 0 1162 0.00 not solved 1943 F 0 1162 0.00 not solved Contest 1951 - 06 Apr 24 - Codeforces Global Round 25 score: 9,396 1951 A 1157 1162 1.00 solved 1951 B 1150 1162 1.00 solved 1951 C 1155 1162 1.00 solved 1951 D 875 1162 1.00 solved 1951 E 1009 1162 1.00 solved 1951 F 53 1162 0.37 solved 1951 G 34 1162 0.26 solved 1951 H 1 1162 0.01 not solved 1951 I 0 1162 0.00 not solved Contest 1965 - 27 Apr 24 - Codeforces Round 941 (Div. 1) score: 3,891 1965 A 1143 1162 1.00 solved 1965 B 1064 1162 1.00 solved 1965 C 313 1162 0.96 solved 1965 D 690 1162 1.00 solved 1965 E 0 1162 0.00 not solved 1965 F 0 1162 0.00 not solved Contest 1967 - 30 Apr 24 - Codeforces Round 942 (Div. 1) score: 3,871 1967 A 1088 1162 1.00 solved 1967 B1 1154 1162 1.00 solved 1967 B2 1149 1162 1.00 solved 1967 C 1116 1162 1.00 solved 1967 D 9 1162 0.08 solved 1967 E1 0 1162 0.00 not solved 1967 E2 0 1162 0.00 not solved 1967 F 0 1162 0.00 not solved Contest 1975 - 25 May 24 - Codeforces Round 947 (Div. 1 Div. 2) score: 5,959 Continued on the next page --- Page 14 --- problem problem rating pass 1 (no ranking) pass 10 (no ranking) failed submissions pass 10 (ranking 1162) 1975 A 1161 1162 1.00 solved 1975 B 1091 1162 1.00 solved 1975 C 492 1162 1.00 solved 1975 D 9 1162 0.08 solved 1975 E 80 1162 0.51 solved 1975 F 12 1162 0.10 solved 1975 G 0 1162 0.00 not solved 1975 H 0 1162 0.00 not solved 1975 I 0 1162 0.00 not solved Contest 1984 - 09 Jun 24 - Codeforces Global Round 26 score: 12,255 1984 A 1161 1162 1.00 solved 1984 B 1158 1162 1.00 solved 1984 C1 914 1162 1.00 solved 1984 C2 768 1162 1.00 solved 1984 D 193 1162 0.84 solved 1984 E 849 1162 1.00 solved 1984 F 918 1162 1.00 solved 1984 G 0 1162 0.00 not solved 1984 H 138 1162 0.72 solved Contest 2002 - 11 Aug 24 - EPIC IoT Round August 2024 (Div. 1 Div. 2) score: 8,981 2002 A 1161 1162 1.00 solved 2002 B 1152 1162 1.00 solved 2002 C 1096 1162 1.00 solved 2002 D1 1067 1162 1.00 solved 2002 D2 805 1162 1.00 solved 2002 E 232 1162 0.89 solved 2002 F1 12 1162 0.10 solved 2002 F2 7 1162 0.06 not solved 2002 G 143 1162 0.73 solved 2002 H 0 1162 0.00 not solved Contest 2006 - 30 Aug 24 - Codeforces Round 969 (Div. 1) score: 2,757 2006 A 945 1162 1.00 solved 2006 B 1149 1162 1.00 solved 2006 C 811 1162 1.00 solved 2006 D 2 1162 0.02 not solved 2006 E 4 1162 0.03 not solved 2006 F 0 1162 0.00 not solved C IOI Submissions This section presents the solutions generated by o1-ioi during the 2024 International Olympiad in Infor- matics. C.1 Nile All 100 possible points for Nile were scored in a single submission. include "nile.h" include bits stdc .h using namespace std; struct UF{ vector int parent, sizee, minIndex; vector array long long, 2 singledPat; singledPat[0] min d[i] for i mod 2 0 in block, singledPat[1] for i mod 2 1 in block vector long long singledBr; singled bridging --- Page 15 --- vector long long singled; singled in block }; long long sumSingledGlobal 0; int findRoot(UF u, int x){ if(u.parent[x] x) return x; u.parent[x] findRoot(u, u.parent[x]); return u.parent[x]; } void updateSingled(UF u, int r){ if(u.sizee[r] u.singled[r] 0; } else { long long val min(u.singledPat[r][u.minIndex[r] if(val LLONG_MAX) val 0; if no such node found, singled 0? u.singled[r] val; } } void unionNodes(UF u, int a, int b){ a findRoot(u, a); b findRoot(u, b); if(a b) return; already in the same component sumSingledGlobal - u.singled[a]; sumSingledGlobal - u.singled[b]; union by size if(u.sizee[a] u.sizee[b]) swap(a, b); u.parent[b] a; int newSize u.sizee[a] u.sizee[b]; int newMinIndex min(u.minIndex[a], u.minIndex[b]); array long long, 2 newSingledPat; newSingledPat[0] min(u.singledPat[a][0], u.singledPat[b][0]); newSingledPat[1] min(u.singledPat[a][1], u.singledPat[b][1]); long long newSingledBr min(u.singledBr[a], u.singledBr[b]); u.sizee[a] newSize; u.minIndex[a] newMinIndex; u.singledPat[a] newSingledPat; u.singledBr[a] newSingledBr; updateSingled(u, a); sumSingledGlobal u.singled[a]; } void addBridging(UF u, int x, long long val){ int r findRoot(u, x); sumSingledGlobal - u.singled[r]; if(u.sizee[r] u.singledBr[r] min(u.singledBr[r], val); updateSingled(u, r); } else { block size is even, singled 0 anyway, bridging won t matter because singledBr is for odd sized block. but bridging might matter if block size becomes odd in future merges, so store singledBr as well. --- Page 16 --- u.singledBr[r] min(u.singledBr[r], val); singled is 0 anyway } sumSingledGlobal u.singled[r]; } std::vector long long calculate_costs( std::vector int W, std::vector int A, std::vector int B, std::vector int E){ int N W.size(); int Q E.size(); vector int idx(N); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [ ](int a, int b){return W[a] W[b];}); vector long long sortedW(N), d(N); for(int i 0; i N; i ) { sortedW[i] W[idx[i]]; d[i] (long long)A[idx[i]] - (long long)B[idx[i]]; } long long sumB 0; for(int i 0; i N; i ) sumB B[idx[i]]; struct Edge{ long long diff; int idx;}; vector Edge edges; edges.reserve(N-1); for(int i 0; i N-1; i ) { edges.push_back({sortedW[i 1] - sortedW[i], i}); } sort(edges.begin(), edges.end(), [ ](const Edge a, const Edge b){return a.diff b.diff;}); vector pair long long, int bridging; bridging.reserve(N-2); for(int i 1; i N-1; i ) { long long val sortedW[i 1] - sortedW[i-1]; bridging.push_back({val, i}); } sort(bridging.begin(), bridging.end(), [ ](auto a, auto b){return a.first b.first;}); vector pair long long, int queriesVec; queriesVec.reserve(Q); for(int i 0; i Q; i ) queriesVec.push_back({(long long)E[i], i}); sort(queriesVec.begin(), queriesVec.end(), [ ](auto a, auto b){return a.first b.first;}); UF u; u.parent.resize(N); u.sizee.resize(N); u.minIndex.resize(N); u.singledPat.resize(N); u.singledBr.resize(N); u.singled.resize(N); for(int i 0; i N; i ) { u.parent[i] i; u.sizee[i] 1; u.minIndex[i] i; u.singledPat[i][0] (i u.singledPat[i][1] (i u.singledBr[i] LLONG_MAX; --- Page 17 --- u.singled[i] d[i]; singled d[i] because block size 1 is odd } sumSingledGlobal 0; for(int i 0; i N; i ) { sumSingledGlobal u.singled[i]; } vector long long result(Q); int posE 0; index in edges int posB 0; index in bridging for(int i 0; i Q; i ) { long long D queriesVec[i].first; int qidx queriesVec[i].second; while(posE (int)edges.size() edges[posE].diff D) { unionNodes(u, edges[posE].idx, edges[posE].idx 1); posE ; } while(posB (int)bridging.size() bridging[posB].first D) { int x bridging[posB].second; addBridging(u, x, d[x]); posB ; } long long costVal sumB sumSingledGlobal; result[qidx] costVal; } return result; } C.2 Message This solution achieved a score of 79.64 out of 100, with full marks awarded for subtask 1 and partial credit received for subtask 2. include "message.h" include bits stdc .h using namespace std; extern std::vector bool send_packet(std::vector bool A); void send_message(std::vector bool M, std::vector bool C) { vector int safe_cols; vector int sabotage_cols; for (int i 0; i 31; i ) { if (!C[i]) safe_cols.push_back(i); else sabotage_cols.push_back(i); } Step 1: send the first 4 packets with distinct sequences. vector vector bool first4results; first4results.reserve(4); for (int p 0; p 4; p ) { vector bool A(31, false); for (int i 0; i 16; i ) { int col safe_cols[i]; --- Page 18 --- int bit (i p) 1; p-th bit of i, i is the index in safe subset A[col] bit; } for (int col : sabotage_cols) { A[col] false; } std::vector bool B send_packet(A); first4results.push_back(B); } Now identify known safe column from the results of these 4 calls. vector string colSequences(31, string(4, 0 )); for (int c 0; c 31; c ) { for (int r 0; r 4; r ) { colSequences[c][r] first4results[r][c] ? 1 : 0 ; } } map string, vector int seqToCols; for (int c 0; c 31; c ) { seqToCols[colSequences[c]].push_back(c); } int knownSafeCol -1; for (auto kv : seqToCols) { if (kv.second.size() 1) { int col kv.second[0]; check if col is in safe subset. Because known safe column must be a safe column. if (find(safe_cols.begin(), safe_cols.end(), col) ! safe_cols.end()) { also check if the sequence is one of the distinct sequences for safe subset. The index in the safe subset is i, the sequence is 4 bits representing i. string seq kv.first; int val 0; for (int i 0; i 4; i ) { if (seq[i] 1 ) val (1 i); } check if val is 16. if (val 16) { knownSafeCol col; break; } } } } if (knownSafeCol -1) { If not found, pick a safe column that has a distinct sequence anyway. But for correctness, we require knownSafeCol to be found. If not found, our method has a problem. } Step 2: store sabotage subset s bits in the known safe column in next 31 calls. The other 15 safe columns store message bits if available. int S M.size(); message length. int offset 0; offset in M. for (int i 0; i 31; i ) { vector bool A(31, false); int sabotageBit C[i]; A[knownSafeCol] sabotageBit; store sabotage subset s bit i in known safe column. for (int c : safe_cols) { if (c knownSafeCol) continue; skip known safe column because we used it for sabotage subset. int col c; if (offset S) { A[col] M[offset]; --- Page 19 --- offset ; } else { A[col] false; } } for (int sc : sabotage_cols) { A[sc] false; } std::vector bool B send_packet(A); We do not store B because we do not need to adapt further. Actually, we can store B if we want to adapt but the solution does not require further adaptation. } Step 3: store message length in the next 11 calls in the known safe column. The other 15 safe columns store more message bits if available. int L S; length in integer form. vector int lengthBinary(11, 0); for (int i 0; i 11; i ) { lengthBinary[i] (L i) 1; } for (int i 0; i 11; i ) { vector bool A(31, false); int bit lengthBinary[i]; A[knownSafeCol] bit; store length bit i in known safe column. for (int c : safe_cols) { if (c knownSafeCol) continue; skip known safe column. int col c; if (offset S) { A[col] M[offset]; offset ; } else { A[col] false; } } for (int sc : sabotage_cols) { A[sc] false; } std::vector bool B send_packet(A); } Step 4: store the rest of the message in subsequent calls using all 16 safe columns. int messageLeft S - offset; how many bits are left to store. int fullColumns 16; number of safe columns. int messageRows (messageLeft fullColumns - 1) fullColumns; how many rows needed. for (int r 0; r messageRows; r ) { vector bool A(31, false); for (int i 0; i fullColumns offset i S; i ) { int col safe_cols[i]; A[col] M[offset i]; } offset fullColumns; for (int sc : sabotage_cols) { A[sc] false; } std::vector bool B send_packet(A); } } std::vector bool receive_message(std::vector std::vector bool R) { --- Page 20 --- int n R.size(); vector bool result; message to return. if (n 4) { return result; } Step 1: from the first 4 rows in R, find the known safe column. vector string colSequences(31, string(4, 0 )); for (int c 0; c 31; c ) { for (int r 0; r 4 r n; r ) { if (r n) { colSequences[c][r] R[r][c] ? 1 : 0 ; } } } map string, vector int seqToCols; for (int c 0; c 31; c ) { seqToCols[colSequences[c]].push_back(c); } int knownSafeCol -1; for (auto kv : seqToCols) { if (kv.second.size() 1) { int col kv.second[0]; check if the sequence is one of the binary representations from 0..15 because safe subset s sequences are distinct and in that range. string seq kv.first; int val 0; for (int i 0; i 4; i ) { if (seq[i] 1 ) val (1 i); } if (val 16) { knownSafeCol col; break; } } } if (knownSafeCol -1) { If none found, that means sabotage overcame the method or we made an error. } Step 2: from next 31 rows in known safe column, read sabotage subset. vector bool sabotageSubset(31, false); int sabotageStart 4; for (int i 0; i 31 sabotageStart i n; i ) { sabotageSubset[i] R[sabotageStart i][knownSafeCol]; } Step 3: from next 11 rows in known safe column, read length. vector bool lengthBits(11, false); int lengthStart sabotageStart 31; for (int i 0; i 11 lengthStart i n; i ) { lengthBits[i] R[lengthStart i][knownSafeCol]; } int messageLength 0; for (int i 0; i 11; i ) { messageLength (lengthBits[i] i); } Step 4: identify safe columns from sabotage subset. vector int safe_cols; for (int i 0; i 31; i ) { if (!sabotageSubset[i]) safe_cols.push_back(i); --- Page 21 --- } Step 5: read message from the next (31 11) rows other safe columns and from subsequent rows using all safe columns. vector bool message; int offset 0; offset in message. int sabotageRowStart 4; int sabotageRows 31; for (int r sabotageRowStart; r sabotageRowStart sabotageRows r n; r ) { for (int c : safe_cols) { if (c knownSafeCol) continue; skip known safe column. if (offset messageLength) { message.push_back(R[r][c]); offset ; } } } int lengthRowStart sabotageRowStart sabotageRows; 4 31 35. int lengthRows 11; for (int r lengthRowStart; r lengthRowStart lengthRows r n; r ) { for (int c : safe_cols) { if (c knownSafeCol) continue; skip known safe column. if (offset messageLength) { message.push_back(R[r][c]); offset ; } } } int restRowStart lengthRowStart lengthRows; 4 31 11 46. int fullColumns 16; number of safe columns. int messageLeft messageLength - offset; int rowsForMessage (messageLeft fullColumns - 1) fullColumns; number of rows needed. for (int r restRowStart; r restRowStart rowsForMessage r n; r ) { for (int i 0; i fullColumns offset messageLength; i ) { int col safe_cols[i]; message.push_back(R[r][col]); offset ; } } The message is now in vector message. If offset messageLength, we did not get all bits. but we should. return message; } C.3 Tree A total of 30 points were scored on Tree across two separate submissions. C.3.1 Submission 1 The first submission achieved a score of 17 out of 100, with points earned from subtasks 1 and 4. include "tree.h" include bits stdc .h using namespace std; static int NGlobal; --- Page 22 --- static vector int parentGlobal; static vector int weightGlobal; static vector long long deltaGlobal; static vector int leafCountGlobal; static vector int sortedByLeafCount; We ll store node indices sorted by leaf count. static vector long long prefixDelta, prefixDeltaTimesLeafCount; prefix sums in sorted order by leaf count. static long long sumAllDelta; static vector vector int childrenGlobal; int computeLeafCountRec(int v){ if (childrenGlobal[v].empty()){ leaf leafCountGlobal[v] 1; return 1; } else { int sum 0; for (int c : childrenGlobal[v]) sum computeLeafCountRec(c); leafCountGlobal[v] sum; return sum; } } void init(std::vector int P, std::vector int W){ int N (int)P.size(); NGlobal N; parentGlobal P; weightGlobal W; if (N 0) return; childrenGlobal.assign(N, {}); for (int i 1; i N; i ) childrenGlobal[parentGlobal[i]].push_back(i); leafCountGlobal.resize(N); computeLeafCountRec(0); vector int deg(N,0); for (int i 1; i N; i ) deg[parentGlobal[i]] ; deltaGlobal.resize(N); for (int i 0; i N; i ){ if (parentGlobal[i] -1){ root if (deg[i] 0) { leaf root deltaGlobal[i] weightGlobal[i]; } else { internal root deltaGlobal[i] - (long long)weightGlobal[i]; } } else { if (deg[i] 0) { leaf deltaGlobal[i] (long long)weightGlobal[parentGlobal[i]] (long long)weightGlobal[i]; } else { internal deltaGlobal[i] (long long)weightGlobal[parentGlobal[i]] - (long long)weightGlobal[i]; } } } sortedByLeafCount.resize(N); iota(sortedByLeafCount.begin(), sortedByLeafCount.end(), 0); sort(sortedByLeafCount.begin(), sortedByLeafCount.end(), [](int a, int b){ return leafCountGlobal[a] leafCountGlobal[b]; }); prefixDelta.resize(N,0); prefixDeltaTimesLeafCount.resize(N,0); --- Page 23 --- sumAllDelta 0; for (int i 0; i N; i ) sumAllDelta deltaGlobal[i]; long long runningDeltaTimesLeaf 0; long long runningDelta 0; for (int i 0; i N; i ){ int idx sortedByLeafCount[i]; long long valDeltaTimesLeaf deltaGlobal[idx] (long long)leafCountGlobal[idx]; runningDeltaTimesLeaf valDeltaTimesLeaf; runningDelta deltaGlobal[idx]; prefixDeltaTimesLeafCount[i] runningDeltaTimesLeaf; prefixDelta[i] runningDelta; } } long long query(int L, int R){ if (NGlobal 0) return 0; no nodes long long a R L; floor of R L. int left -1; int right NGlobal; while (right - left 1){ int mid (left right) 2; int node sortedByLeafCount[mid]; if ((long long)leafCountGlobal[node] a) left mid; else right mid; } int idx left; idx is the last index where b[i] a. long long sumA 0; sum of delta[i] b[i] for nodes with b[i] a. if (idx 0) { sumA prefixDeltaTimesLeafCount[idx]; sum_{i: b[i] a} delta[i] b[i] } long long sumPrefixDeltaWhereLessOrEqual 0; if (idx 0) sumPrefixDeltaWhereLessOrEqual prefixDelta[idx]; else sumPrefixDeltaWhereLessOrEqual 0; long long sumDeltaWhereBGreater sumAllDelta - sumPrefixDeltaWhereLessOrEqual; long long LLL (long long)L; long long RRR (long long)R; long long partA LLL sumA; long long partB RRR sumDeltaWhereBGreater; long long cost partA partB; return cost; } C.3.2 Submission 2 Submission 2 achieved 13 of 100 points on subtask 2. include "tree.h" include bits stdc .h using namespace std; struct Pt { long long x; long long y; }; struct PWL { long long L, R; vector Pt pts; sorted by x --- Page 24 --- }; int NGlobal; int PGlobal[2005]; int wGlobal[2005]; vector int childrenGlobal[2005]; PWL GGlobal[2005]; define the helper functions as static. static long long evalPWL(const PWL f, long long x) { if (f.pts.empty()) return LLONG_MAX 2; no function if (x f.pts.front().x) { return f.pts.front().y; domain out, but we prefer front. } if (x f.pts.back().x) { return f.pts.back().y; domain out, but prefer back. } int left 0, right f.pts.size()-1; while (left 1 right) { int mid (left right) 2; if (f.pts[mid].x x) return f.pts[mid].y; if (f.pts[mid].x x) left mid; else right mid; } if (f.pts[left].x x x f.pts[right].x) { long long x1 f.pts[left].x; long long y1 f.pts[left].y; long long x2 f.pts[right].x; long long y2 f.pts[right].y; if (x1 x2) return y1; long double slope (long double)(y2 - y1) (long double)(x2 - x1); long double valf (long double) y1 slope (x - x1); long long vali (long long) llround(valf); return vali; } else { return LLONG_MAX 2; } } struct ChildState { int idx; child index in local array long long x; current x in child s domain int seg; segment in child s function long double slope; long long nextBound; }; static PWL combineChildren(const vector PWL childF, long long L, long long R) { int d childF.size(); if (d 0) { PWL f; f.L L; f.R R; f.pts {{L, 0}, {R, 0}}; return f; } long long sumDomainL (long long)d L; long long sumDomainR (long long)d R; vector ChildState cs(d); priority_queue pair long double, int , vector pair long double, int , greater pair long double, int pq; for (int i 0; i d; i ) { cs[i].idx i; cs[i].x L; int seg 0; int n childF[i].pts.size(); while (seg n-1 childF[i].pts[seg 1].x L) seg ; --- Page 25 --- cs[i].seg seg; long double slope 0; if (seg 1 n) { long long dx childF[i].pts[seg 1].x - childF[i].pts[seg].x; long long dy childF[i].pts[seg 1].y - childF[i].pts[seg].y; slope dx! 0?(long double)dy dx:0; } else { slope 0; } cs[i].slope slope; if (seg 1 n) cs[i].nextBound min((long long)childF[i].pts[seg 1].x, R); else cs[i].nextBound R; pq.push({slope, i}); } long long sum sumDomainL; long long cost 0; for (int i 0; i d; i ) { cost evalPWL(childF[i], L); } vector Pt fpts; fpts.push_back({sum, cost}); while (!pq.empty() sum sumDomainR) { auto top pq.top(); long double slope top.first; vector int group; while (!pq.empty() abs(pq.top().first - slope) 1e-9) { group.push_back(pq.top().second); pq.pop(); } if (group.empty()) break; long long inc LLONG_MAX; for (int idx : group) { long long newInc cs[idx].nextBound - cs[idx].x; if (newInc inc) inc newInc; } if (inc 0) { for (int idx : group) { pq.push({cs[idx].slope, idx}); } break; } long long feasibleInc inc; if (sum (long long)group.size() inc sumDomainR) { feasibleInc (sumDomainR - sum) (long long) group.size(); } if (feasibleInc 0) { for (int idx : group) { pq.push({cs[idx].slope, idx}); } break; } sum sum group.size() feasibleInc; long double dcost slope feasibleInc group.size(); cost (long long) llround((long double)cost dcost); fpts.push_back({sum, cost}); for (int idx : group) { --- Page 26 --- cs[idx].x feasibleInc; if (cs[idx].x cs[idx].nextBound) { const PWL g childF[idx]; int seg cs[idx].seg; if (cs[idx].x R) { cs[idx].slope 1e9; saturate cs[idx].nextBound R; } else { seg ; cs[idx].seg seg; int n g.pts.size(); if (seg 1 n) { long long dx g.pts[seg 1].x - g.pts[seg].x; long long dy g.pts[seg 1].y - g.pts[seg].y; long double slopeC dx! 0?(long double)dy dx:0; cs[idx].slope slopeC; cs[idx].nextBound min((long long)g.pts[seg 1].x, R); } else { cs[idx].slope 0; cs[idx].nextBound R; } } } } for (int idx : group) { if (cs[idx].x R) { pq.push({cs[idx].slope, idx}); } } } vector Pt unify; unify.push_back(fpts[0]); for (int i 1; i fpts.size(); i ) { if (fpts[i].x unify.back().x) { unify.back().y min(unify.back().y, fpts[i].y); } else unify.push_back(fpts[i]); } vector Pt final; if (!unify.empty()) final.push_back(unify[0]); for (int i 1; i unify.size()-1; i ) { long long x1 final.back().x; long long y1 final.back().y; long long x2 unify[i].x; long long y2 unify[i].y; long long x3 unify[i 1].x; long long y3 unify[i 1].y; long double slope1 (x2! x1)? (long double)(y2-y1) (x2-x1) : 1e9; long double slope2 (x3! x2)? (long double)(y3-y2) (x3-x2) : 1e9; if (abs(slope1 - slope2) 1e-9) { unify linear, skip unify[i] } else { final.push_back(unify[i]); } } if (!unify.empty()) final.push_back(unify.back()); PWL result; result.L sumDomainL; result.R sumDomainR; result.pts final; return result; --- Page 27 --- } static PWL parentFormula(const PWL f, long long wVal, long long L, long long R) { vector long long candVal; candVal.push_back(L); candVal.push_back(R); for (auto p : f.pts) { if (p.x L p.x R) candVal.push_back(p.x); } if (f.L L f.L R) candVal.push_back(f.L); if (f.R L f.R R) candVal.push_back(f.R); for (int i 0; i (int)f.pts.size()-1; i ) { long long sx f.pts[i].x; long long sy f.pts[i 1].x; long long dx sy - sx; long long dy f.pts[i 1].y - f.pts[i].y; long double a dx! 0? (long double)dy dx:0; slope in s domain if (a wVal a -wVal) { long long inL max(sx, (long long)L); long long inR min(sy, (long long)R); if (inL inR) { candVal.push_back(inL); candVal.push_back(inR); } } } sort(candVal.begin(), candVal.end()); candVal.erase(unique(candVal.begin(), candVal.end()), candVal.end()); vector Pt pts; for (auto val : candVal) { long long bestCost LLONG_MAX 2; if (val f.L val f.R) { int left 0, right f.pts.size()-1; while (left 1 right) { int mid (left right) 2; if (f.pts[mid].x val) left mid; else right mid; } if (f.pts[left].x val val f.pts[right].x) { long long x1 f.pts[left].x; long long y1 f.pts[left].y; long long x2 f.pts[right].x; long long y2 f.pts[right].y; long double slope (x2! x1? (long double)(y2 - y1) (long double)(x2 - x1) : 0); if (slope wVal slope -wVal val x1 val x2) { long double costf (long double) y1 slope (long double)(val - x1); long long c (long long) llround(costf); bestCost min(bestCost, c); } } } for (auto p : f.pts) { long long s p.x; long long c p.y wVal llabs(val - s); if (c bestCost) bestCost c; } pts.push_back({val, bestCost}); } sort(pts.begin(), pts.end(), [](const Pt a, const Pt b){return a.x b.x;}); --- Page 28 --- vector Pt unify; unify.push_back(pts[0]); for (int i 1; i pts.size(); i ) { if (pts[i].x unify.back().x) { unify.back().y min(unify.back().y, pts[i].y); } else unify.push_back(pts[i]); } vector Pt final; if (!unify.empty()) final.push_back(unify[0]); for (int i 1; i unify.size()-1; i ) { long long x1 final.back().x; long long y1 final.back().y; long long x2 unify[i].x; long long y2 unify[i].y; long long x3 unify[i 1].x; long long y3 unify[i 1].y; long double slope1 x2! x1? (long double)(y2-y1) (x2-x1) : 1e9; long double slope2 x3! x2? (long double)(y3-y2) (x3-x2) : 1e9; if (abs(slope1 - slope2) 1e-9) { unify linear, skip unify[i] } else { final.push_back(unify[i]); } } if (!unify.empty()) final.push_back(unify.back()); PWL result; result.L L; result.R R; result.pts final; return result; } static void computeG(int node, long long L, long long R) { for (int c : childrenGlobal[node]) { computeG(c, L, R); } if (childrenGlobal[node].empty()) { leaf PWL result; result.L L; result.R R; if (L 0 0 R) { long long valL wGlobal[node] llabs(L); long long val0 wGlobal[node] 0; 0 long long valR wGlobal[node] llabs(R); result.pts.clear(); result.pts.push_back({L, valL}); result.pts.push_back({0, val0}); result.pts.push_back({R, valR}); } else { long long valL wGlobal[node] llabs(L); long long valR wGlobal[node] llabs(R); result.pts.clear(); result.pts.push_back({L, valL}); result.pts.push_back({R, valR}); } GGlobal[node] result; } else { vector PWL childF; for (int c : childrenGlobal[node]) { childF.push_back(GGlobal[c]); } --- Page 29 --- PWL f combineChildren(childF, L, R); PWL p parentFormula(f, wGlobal[node], L, R); GGlobal[node] p; } } void init(std::vector int P, std::vector int W) { NGlobal W.size(); for (int i 0; i NGlobal; i ) { PGlobal[i] P[i]; wGlobal[i] W[i]; } for (int i 0; i NGlobal; i ) childrenGlobal[i].clear(); for (int i 1; i NGlobal; i ) { childrenGlobal[P[i]].push_back(i); } } long long query(int L, int R) { computeG(0, L, R); long long ans LLONG_MAX; for (auto p : GGlobal[0].pts) { if (p.y ans) ans p.y; } return ans; } C.4 Hieroglyphs A total of 44 points was scored on Hieroglyphs across two separate submissions. C.4.1 Submission 1 In the first submission, a score of 34 out of 100 points was achieved, distributed across subtasks 1, 2, and 4. include "hieroglyphs.h" include bits stdc .h using namespace std; std::vector int ucs(std::vector int A, std::vector int B) { int N (int) A.size(); int M (int) B.size(); if (N 0 M 0) { std::vector int ret; return ret; } const int MAX_VAL 200001; static int cntA[200002], cntB[200002]; for (int i 0; i 200002; i ) { cntA[i] 0; cntB[i] 0; } for (int i 0; i N; i ) cntA[A[i]] ; for (int i 0; i M; i ) cntB[B[i]] ; static int cVal[200002]; for (int i 0; i 200002; i ) { if (cntA[i] 0 cntB[i] 0) { cVal[i] min(cntA[i], cntB[i]); --- Page 30 --- } else { cVal[i] 0; } } long long sumC 0; for (int x 0; x 200002; x ) { sumC cVal[x]; } if (sumC 0) { std::vector int ret; return ret; } Precompute earliest and latest occurrences in A and B for all x. static int earliestA[200002], latestA[200002], earliestB[200002], latestB[200002]; for (int i 0; i 200002; i ) { earliestA[i] -1; latestA[i] -1; earliestB[i] -1; latestB[i] -1; } for (int i 0; i N; i ) { int letter A[i]; if (earliestA[letter] -1) earliestA[letter] i; latestA[letter] i; } for (int i 0; i M; i ) { int letter B[i]; if (earliestB[letter] -1) earliestB[letter] i; latestB[letter] i; } Now intervals for cVal[x] 1. struct Interval { int letter; int eA, lA, eB, lB; }; vector Interval intervals; for (int x 0; x 200002; x ) { if (cVal[x] 1) { Interval I; I.letter x; I.eA earliestA[x]; I.lA latestA[x]; I.eB earliestB[x]; I.lB latestB[x]; intervals.push_back(I); } } sort intervals by eA. std::sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b){ return a.eA b.eA; }); Balanced tree keyed by eB, store lB as well. vector int segmentTree(4 (M 5), -1); auto update [ ](int idx, int start, int end, int pos, int val, auto f) - void { if (start end) { segmentTree[idx] val; return; --- Page 31 --- } int mid (start end) 2; if (pos mid) f(idx 2, start, mid, pos, val, f); else f(idx 2 1, mid 1, end, pos, val, f); segmentTree[idx] max(segmentTree[idx 2], segmentTree[idx 2 1]); }; auto query [ ](int idx, int start, int end, int l, int r, auto f) - int { if (r start end l) return -1; if (l start end r) { return segmentTree[idx]; } int mid (start end) 2; int leftVal f(idx 2, start, mid, l, r, f); int rightVal f(idx 2 1, mid 1, end, l, r, f); return max(leftVal, rightVal); }; vector Interval intervalsSortedByLA intervals; sort(intervalsSortedByLA.begin(), intervalsSortedByLA.end(), [](const Interval a, const Interval b){ return a.lA b.lA; }); int j 0; for (int i 0; i intervals.size(); i ) { auto x intervals[i]; int eAx x.eA; remove intervals from data structure where lA[y] eAx. while (j intervalsSortedByLA.size() intervalsSortedByLA[j].lA eAx) { auto y intervalsSortedByLA[j]; remove y from segment tree keyed by eB[y]. update(1, 0, M-1, y.eB, -1, update); j ; } query in B dimension: find if there s an interval y with eB[y] lB[x] and lB[y] eB[x]. int minB x.eB; eB[x] int maxB x.lB; lB[x] if (minB maxB) { If eB[x] lB[x], no intersection possible. } else { query in the segment tree range [0, maxB] to find the maximum lB[y]. int maxVal query(1, 0, M-1, 0, maxB, query); if (maxVal minB) { found intersection with a letter y where cVal[y] 1. std::vector int ret; ret.push_back(-1); return ret; } } add x to data structure keyed by eB[x]. update(1, 0, M-1, x.eB, x.lB, update); } If no intersection found among cVal 1 intervals, proceed with chain method. The chain method code. static vector int posAarr[200002]; static vector int posBarr[200002]; for (int i 0; i 200002; i ) { posAarr[i].clear(); --- Page 32 --- posBarr[i].clear(); } for (int i 0; i N; i ) { if (cVal[A[i]] 0) posAarr[A[i]].push_back(i); } for (int i 0; i M; i ) { if (cVal[B[i]] 0) posBarr[B[i]].push_back(i); } struct QItem { int letter; int pos; }; struct QComp { bool operator()(const QItem a, const QItem b) const { if (a.pos b.pos) return a.letter b.letter; return a.pos b.pos; } }; priority_queue QItem, vector QItem , QComp pq; static int posAarrIdx[200002]; static int occInAarr[200002]; for (int x 0; x 200002; x ) { posAarrIdx[x] 0; occInAarr[x] 0; if (cVal[x] 0 posAarr[x].size() 0) { QItem item; item.letter x; item.pos posAarr[x][0]; pq.push(item); } } static int TAlpha[200002]; for (int x 0; x 200002; x ) { if (cVal[x] 0) TAlpha[x] cntB[x] - cVal[x]; else TAlpha[x] 0; } static int freqAlpha[200002]; freq in B up to posB0. for (int x 0; x 200002; x ) freqAlpha[x] 0; int posB0Alpha -1; { int i 0; for (; i M; i ) { int letter B[i]; if (cVal[letter] 0) { freqAlpha[letter] ; if (freqAlpha[letter] TAlpha[letter]) { freqAlpha[letter]--; break; cause posB0Alpha i-1 } } } posB0Alpha i-1; if (i M) posB0Alpha M-1; } --- Page 33 --- vector int U; U.reserve(sumC); int posB -1; int usedCount 0; auto updatePosB0Alpha [ ](int letter, auto freqAlpha, auto TAlpha, int posB0Alpha, int M) { int i posB0Alpha 1; while (i M) { int l B[i]; if (cVal[l] 0) { freqAlpha[l] ; if (freqAlpha[l] TAlpha[l]) { freqAlpha[l]--; break; } } i ; } posB0Alpha i-1; }; while (!pq.empty() usedCount sumC) { QItem item pq.top(); pq.pop(); int letter item.letter; int posAVal posAarr[letter][posAarrIdx[letter]]; auto barr posBarr[letter]; int idx (int) (std::lower_bound(barr.begin(), barr.end(), posB 1) - barr.begin()); if (idx (int) barr.size()) { posAarrIdx[letter] ; if (posAarrIdx[letter] posAarr[letter].size()) { QItem newItem; newItem.letter letter; newItem.pos posAarr[letter][posAarrIdx[letter]]; pq.push(newItem); } continue; } else { int posBVal barr[idx]; TAlpha[letter] ; int oldPosB0Alpha posB0Alpha; vector pair int,int freqChanges; int startIndex posB0Alpha 1; int i startIndex; while (i M) { int l B[i]; if (cVal[l] 0) { freqAlpha[l] ; freqChanges.push_back({l, i}); if (freqAlpha[l] TAlpha[l]) { freqAlpha[l]--; freqChanges.pop_back(); break; } } i ; } --- Page 34 --- int newPosB0Alpha i-1; if (posBVal newPosB0Alpha) { U.push_back(letter); usedCount ; posB posBVal; occInAarr[letter] ; posAarrIdx[letter] ; if (occInAarr[letter] cVal[letter] posAarrIdx[letter] posAarr[letter].size()) { QItem newItem; newItem.letter letter; newItem.pos posAarr[letter][posAarrIdx[letter]]; pq.push(newItem); } posB0Alpha newPosB0Alpha; } else { TAlpha[letter]--; for (auto fc : freqChanges) { freqAlpha[fc.first]--; } posB0Alpha oldPosB0Alpha; posAarrIdx[letter] ; if (posAarrIdx[letter] posAarr[letter].size()) { QItem newItem; newItem.letter letter; newItem.pos posAarr[letter][posAarrIdx[letter]]; pq.push(newItem); } continue; } } } if (usedCount sumC) { std::vector int ret; ret.push_back(-1); return ret; } return U; } C.4.2 Submission 2 In the second submission, the model scored 10 points on subtask 3. include "hieroglyphs.h" include bits stdc .h using namespace std; std::vector int ucs(std::vector int A, std::vector int B) { int N (int)A.size(); int M (int)B.size(); int a0 0, a1 0; --- Page 35 --- for (int i 0; i N; i ) { if (A[i] 0) a0 ; else if (A[i] 1) a1 ; } int b0 0, b1 0; for (int i 0; i M; i ) { if (B[i] 0) b0 ; else if (B[i] 1) b1 ; } int Z min(a0, b0); int O min(a1, b1); If Z 0 and O 0, universal subsequence is the empty sequence. if (Z 0 O 0) { return {}; } vector int zeroPosA; zeroPosA.reserve(a0); for (int i 0; i N; i ) if (A[i] 0) zeroPosA.push_back(i); vector int zeroPosB; zeroPosB.reserve(b0); for (int i 0; i M; i ) if (B[i] 0) zeroPosB.push_back(i); vector int prefixOnesA(N 1, 0); for (int i 1; i N; i ) prefixOnesA[i] prefixOnesA[i-1] (A[i-1] 1); vector int prefixOnesB(M 1, 0); for (int i 1; i M; i ) prefixOnesB[i] prefixOnesB[i-1] (B[i-1] 1); auto getOnesAfterZero [ ](vector int zeroPos, vector int prefixOnes, int totalOnes, int z) { if (z 0) return totalOnes; else { if (z-1 (int)zeroPos.size()) return 0; safety int pos zeroPos[z-1]; int onesUsed prefixOnes[pos 1]; int onesAfter totalOnes - onesUsed; return onesAfter; } }; vector int fAval(Z 1), fBval(Z 1); for (int z 0; z Z; z ) { fAval[z] getOnesAfterZero(zeroPosA, prefixOnesA, a1, z); fBval[z] getOnesAfterZero(zeroPosB, prefixOnesB, b1, z); } vector int cZ(Z 1); for (int z 0; z Z; z ) cZ[z] min(fAval[z], fBval[z]); vector int onePosA; onePosA.reserve(a1); for (int i 0; i N; i ) if (A[i] 1) onePosA.push_back(i); vector int onePosB; onePosB.reserve(b1); for (int i 0; i M; i ) if (B[i] 1) onePosB.push_back(i); vector int prefixZerosA(N 1, 0); for (int i 1; i N; i ) prefixZerosA[i] prefixZerosA[i-1] (A[i-1] 0); vector int prefixZerosB(M 1, 0); for (int i 1; i M; i ) prefixZerosB[i] prefixZerosB[i-1] (B[i-1] 0); auto getZerosAfterOne [ ](vector int onePos, vector int prefixZeros, int totalZeros, int w) { if (w 0) return totalZeros; else { --- Page 36 --- if (w-1 (int)onePos.size()) return 0; safety int pos onePos[w-1]; int zerosUsed prefixZeros[pos 1]; int zerosAfter totalZeros - zerosUsed; return zerosAfter; } }; vector int gAval(O 1), gBval(O 1); for (int w 0; w O; w ) { gAval[w] getZerosAfterOne(onePosA, prefixZerosA, a0, w); gBval[w] getZerosAfterOne(onePosB, prefixZerosB, b0, w); } vector int cO(O 1); for (int w 0; w O; w ) cO[w] min(gAval[w], gBval[w]); vector int U; U.reserve(Z O); int zUsed 0; int oUsed 0; auto canPlaceZero [ ](int zUsed, int oUsed) { if (zUsed Z) return false; int c cZ[zUsed 1]; constraint for the next zero in U. int onesLeft O - oUsed; return onesLeft c; }; auto canPlaceOne [ ](int zUsed, int oUsed) { if (oUsed O) return false; int c cO[oUsed 1]; constraint for the next one in U. int zerosLeft Z - zUsed; return zerosLeft c; }; for (int i 0; i Z O; i ) { bool placeZ canPlaceZero(zUsed, oUsed); bool placeO canPlaceOne(zUsed, oUsed); if (!placeZ !placeO) { return {-1}; } else if (placeZ !placeO) { U.push_back(0); zUsed ; } else if (!placeZ placeO) { U.push_back(1); oUsed ; } else { int cZc cZ[zUsed 1]; int cOc cO[oUsed 1]; bool canPickZero false; bool canPickOne false; { int newZUsed zUsed 1; int newOUsed oUsed; int onesLeft O - newOUsed; int zerosLeft Z - newZUsed; bool feasible true; if (Z newZUsed) { check cZ in range [newZUsed 1..Z] int maxZConstraint cZ[newZUsed 1]; if (onesLeft maxZConstraint) feasible false; --- Page 37 --- } if (O newOUsed) { check cO in range [newOUsed 1..O] int maxOConstraint cO[newOUsed 1]; if (zerosLeft maxOConstraint) feasible false; } canPickZero feasible; } { int newZUsed zUsed; int newOUsed oUsed 1; int onesLeft O - newOUsed; int zerosLeft Z - newZUsed; bool feasible true; if (Z newZUsed) { int maxZConstraint cZ[newZUsed 1]; if (onesLeft maxZConstraint) feasible false; } if (O newOUsed) { int maxOConstraint cO[newOUsed 1]; if (zerosLeft maxOConstraint) feasible false; } canPickOne feasible; } if (canPickZero !canPickOne) { U.push_back(0); zUsed ; } else if (!canPickZero canPickOne) { U.push_back(1); oUsed ; } else if (canPickZero canPickOne) { if (cZc cOc) { U.push_back(0); zUsed ; } else if (cOc cZc) { U.push_back(1); oUsed ; } else { if ((Z - zUsed) (O - oUsed)) { U.push_back(0); zUsed ; } else { U.push_back(1); oUsed ; } } } else { return {-1}; } } } Validate U with constraints. vector int zeroPositions, onePositions; zeroPositions.reserve(Z); onePositions.reserve(O); for (int i 0; i (int)U.size(); i ) { if (U[i] 0) zeroPositions.push_back(i); else onePositions.push_back(i); } for (int z 0; z Z; z ) { --- Page 38 --- int pos (z 0) ? -1 : zeroPositions[z-1]; int onesRight (int)onePositions.size() - (int)(std::lower_bound(onePositions.begin(), onePositions.end(), pos 1) - onePositions.begin()); if (onesRight cZ[z]) { return {-1}; } } for (int w 0; w O; w ) { int pos (w 0) ? -1 : onePositions[w-1]; int zerosRight (int)zeroPositions.size() - (int)(std::lower_bound(zeroPositions.begin(), zeroPositions.end(), pos 1) - zeroPositions.begin()); if (zerosRight cO[w]) { return {-1}; } } auto isSubsequence [ ](const std::vector int C, const std::vector int X) { int idx 0; for (int i 0; i (int)X.size() idx (int)C.size(); i ) { if (X[i] C[idx]) idx ; } return idx (int)C.size(); }; if (!isSubsequence(U, A) !isSubsequence(U, B)) { return {-1}; } return U; } C.5 Mosaic A total of 42 points were scored on Mosaic across two separate submissions. C.5.1 Submission 1 The first submission achieved a score of 22 out of 100, with points distributed across subtasks 1, 2, and 4. include "mosaic.h" include bits stdc .h using namespace std; std::vector long long mosaic(std::vector int X, std::vector int Y, std::vector int T, std::vector int B, std::vector int L, std::vector int R) { int N X.size(); int Q T.size(); if(N 0) { return vector long long (Q, 0LL); } Step 1: fill A (N N array, store as char 0 1) vector unsigned char A; A.resize((size_t)N (size_t)N); fill top row for(int j 0; j N; j ) { A[0 N j] X[j]; --- Page 39 --- } fill left column for(int i 0; i N; i ) { A[i N 0] Y[i]; } fill rest for(int i 1; i N; i ) { for(int j 1; j N; j ) { A[i N j] (1 - A[(i-1) N j]) (1 - A[i N j-1]); } } Step 2: compute prefix sums in P (N 1) (N 1) array vector int P; P.resize((size_t)(N 1) (size_t)(N 1)); initialize P with 0 s std::fill(P.begin(), P.end(), 0); for(int i 0; i N; i ) { int baseRow (i 1) (N 1); int prevRow i (N 1); for(int j 0; j N; j ) { P[baseRow (j 1)] P[prevRow (j 1)] P[baseRow j] - P[prevRow j] (A[i N j]); } } Step 3: answer queries using P vector long long C; C.resize(Q); for(int k 0; k Q; k ) { int top T[k]; int bottom B[k]; int left L[k]; int right R[k]; long long blackCount (long long)P[(bottom 1) (N 1) (right 1)] - (long long)P[(top) (N 1) (right 1)] - (long long)P[(bottom 1) (N 1) left] (long long)P[(top) (N 1) left]; C[k] blackCount; } return C; } C.5.2 Submission 2 The model scored 20 points in the second submission on subtasks 1, 3, and 5. include "mosaic.h" include bits stdc .h using namespace std; We ll implement the mosaic function as specified. std::vector long long mosaic(std::vector int X, std::vector int Y, std::vector int T, std::vector int B, std::vector int L, std::vector int R) { int N X.size(); int Q T.size(); If N 1, the mosaic is just tile(0,0), queries are easy. --- Page 40 --- if (N 1) { vector long long result(Q); for (int q 0; q Q; q ) { subrectangle T..B x L..R is always T 0,B 0,L 0,R 0 if we have queries. if (T[q] 0 B[q] 0 L[q] 0 R[q] 0) { black tile count is 1 if X[0] 1 or Y[0] 1, and X[0] Y[0], else 0. The problem states X[0] Y[0], so tile(0,0) is black if X[0] 1. if (X[0] 1) result[q] 1; else result[q] 0; } else { no other queries are possible if N 1, but if they are, the subrectangle is empty or out of range. result[q] 0; } } return result; } Precompute prefix sums for X and Y. vector long long prefixX(N 1, 0), prefixY(N 1, 0); for (int i 1; i N; i ) { prefixX[i] prefixX[i-1] X[i-1]; prefixY[i] prefixY[i-1] Y[i-1]; } Determine alpha mod 2 and beta mod 2 from tile(1,1). C[1,1] 1 if X[1] and Y[1] are 0, else 0. int c11 0; if (N 1) { if (X.size() 1 Y.size() 1 X[1] 0 Y[1] 0) c11 1; else c11 0; } else { c11 0; but N 1 scenario is handled above. } int alphaMod2, betaMod2; if (c11 1) { alphaMod2 0; betaMod2 0; } else { alphaMod2 0; betaMod2 1; } define functions to count even and odd in a range. auto countEvenInRange [ ](int a, int b){ if (b a) return 0LL; long long A a; long long B b; long long evenCount ((long long)B 2) 2 - ((long long)A 1) 2; return evenCount; }; auto countOddInRange [ ](int a, int b){ if (b a) return 0LL; long long A a; long long B b; long long oddCount ((long long)B 1) 2 - (long long)A 2; return oddCount; }; Now for each query, compute the black tile count. std::vector long long result(Q); for (int q 0; q Q; q ) { long long t T[q]; long long b B[q]; long long l L[q]; --- Page 41 --- long long r R[q]; long long count 0; if T 0, add black tile from row0 and columns L..R. if (t 0 r l) { long long sumRow0 prefixX[r 1] - prefixX[(int)l]; sum of X[L..R] count sumRow0; } if L 0, add black tile from column0 and rows T..B. if (l 0 b t) { long long sumCol0 prefixY[b 1] - prefixY[(int)t]; sum of Y[T..B] count sumCol0; } if T 0 and L 0, subtract tile(0,0) if black. if (t 0 l 0 r 0 b 0) { if (X[0] 1) { count - 1; } } add black tile from the interior submatrix T max(T,1)..B x L max(L,1)..R. int Tprime max((int)t, 1); int Lprime max((int)l, 1); if (Tprime b Lprime r) { long long evenI countEvenInRange(Tprime, (int)b); long long oddI countOddInRange(Tprime, (int)b); long long evenJ countEvenInRange(Lprime, (int)r); long long oddJ countOddInRange(Lprime, (int)r); long long interiorCount 0; if (alphaMod2 betaMod2) { black tile appear when i interiorCount evenI evenJ oddI oddJ; } else { black tile appear when i interiorCount evenI oddJ oddI evenJ; } count interiorCount; } result[q] count; } return result; } C.6 Sphinx A total of 71.5 points were scored on Sphinx across two separate submissions. C.6.1 Submission 1 The first submission achieved a score of 50 out of 100, with 50 partial credit earned on all subtasks. include "sphinx.h" include bits stdc .h int perform_experiment(std::vector int E); std::vector int find_colours(int Nx, std::vector int Xx, std::vector int Yx) { int N Nx; --- Page 42 --- std::vector std::vector int adj(N); int M Xx.size(); for (int i 0; i M; i ) { int u Xx[i], v Yx[i]; adj[u].push_back(v); adj[v].push_back(u); } struct UnionFind { std::vector int parent, rank; UnionFind(int n) : parent(n), rank(n, 0) { for (int i 0; i n; i ) parent[i] i; } int findp(int x) { if (parent[x] x) return x; parent[x] findp(parent[x]); return parent[x]; } void unite(int x, int y) { x findp(x); y findp(y); if (x y) return; if (rank[x] rank[y]) parent[x] y; else if (rank[x] rank[y]) parent[y] x; else {parent[y] x; rank[x] ;} } } uf(N); auto connectedComponentsInSubset [ ](const std::vector int subset) { static std::vector int visited; visited.assign(N, -1); for (int v : subset) visited[v] 0; int count 0; for (int v : subset) if (visited[v] 0) { count ; std::queue int q; q.push(v); visited[v] 1; while(!q.empty()) { int u q.front(); q.pop(); for (int w : adj[u]) { if (visited[w] 0) { visited[w] 1; q.push(w); } } } } return count; }; auto queryMonochromComps [ ](const std::vector int S) { std::vector int Earr(N); static std::vector int visited2; visited2.assign(N, -1); std::vector int Sset(N, 0); for (int v : S) Sset[v] 1; for (int i 0; i N; i ) Earr[i] (Sset[i] 1) ? -1 : N; int res perform_experiment(Earr); std::vector int compInput; compInput.reserve(N - S.size()); for (int i 0; i N; i ) if (Sset[i] 0) compInput.push_back(i); int compCount 0; --- Page 43 --- if (!compInput.empty()) compCount connectedComponentsInSubset(compInput); else compCount 0; int monos res - compCount; return monos; }; std::vector int c(N 1, 0); c[0] 0; no vertices, connectedComponents(0) 0. for (int k 1; k N; k ) { std::vector int S; S.reserve(k); for (int i 0; i k; i ) S.push_back(i); c[k] queryMonochromComps(S); } for (int k 1; k N; k ) { int v k-1; int merges c[k-1] 1 - c[k]; if (merges 0) merges 0; safety. auto findMerges [ ](auto self, std::vector int roots, int merges) - void { if (merges 0) return; if (merges (int)roots.size()) { for (int r : roots) { uf.unite(v, r); } return; } else { if (roots.size() merges) { for (int r : roots) { uf.unite(v, r); } return; } else { int half roots.size() 2; std::vector int left(roots.begin(), roots.begin() half); std::vector int right(roots.begin() half, roots.end()); std::vector int S2; S2.reserve(1 v); S2.push_back(v); for (int r : left) { for (int i 0; i v; i ) { if (uf.findp(i) r) { S2.push_back(i); } } } std::vector int Earr(N); std::vector int Sset2(N, 0); for (int i : S2) Sset2[i] 1; for (int i 0; i N; i ) Earr[i] (Sset2[i] 1) ? -1 : N; int res perform_experiment(Earr); std::vector int compInput; compInput.reserve(N - S2.size()); static std::vector int visited2; visited2.assign(N, -1); for (int i 0; i N; i ) visited2[i] 0; for (int i : S2) visited2[i] -1; compInput.clear(); for (int i 0; i N; i ) if (visited2[i] 0) compInput.push_back(i); int compCount 0; if (!compInput.empty()) { --- Page 44 --- for (int ip : compInput) visited2[ip] 0; re-mark for BFS. for (int ip : compInput) if (visited2[ip] 0) { compCount ; std::queue int q; q.push(ip); visited2[ip] 1; while(!q.empty()) { int u q.front(); q.pop(); for (int w : adj[u]) { if (visited2[w] 0) { visited2[w] 1; q.push(w); } } } } } else compCount 0; int monos2 res - compCount; int mergesInLeft left.size() 1 - monos2; self(self, left, mergesInLeft); self(self, right, merges - mergesInLeft); } } }; std::set int distinctRoots; for (int i 0; i v; i ) distinctRoots.insert(uf.findp(i)); std::vector int rootsVec(distinctRoots.begin(), distinctRoots.end()); findMerges(findMerges, rootsVec, merges); } std::vector int rootID(N, -1); std::vector int colorID(N, -1); int nextID 0; for (int i 0; i N; i ) { int r uf.findp(i); if (rootID[r] -1) { rootID[r] nextID ; } colorID[i] rootID[r]; } return colorID; } C.6.2 Submission 2 Submission 2 achieved 43 points on subtasks 1, 2, and 3. include "sphinx.h" include bits stdc .h using namespace std; int perform_experiment(vector int E); vector int find_colours(int N, vector int X, vector int Y) { We ll store adjacency. vector vector int adj(N); vector vector bool adjMatrix(N, vector bool (N, false)); --- Page 45 --- for (int i 0; i (int)X.size(); i ) { int u X[i]; int v Y[i]; adj[u].push_back(v); adj[v].push_back(u); adjMatrix[u][v] adjMatrix[v][u] true; } vector int final_colors(N, -1); vector int unassigned; for (int i 0; i N; i ) unassigned.push_back(i); define group testing functions. function query_count_in_T: how many in T have color x. auto query_count_in_T [ ](const vector int T, int x) { vector int E(N, x); vector int inT(N, 0); for (int v : T) { E[v] -1; inT[v] 1; } int R perform_experiment(E); number c of connected components in the rest. vector int complement; for (int i 0; i N; i ) if (!inT[i]) complement.push_back(i); BFS for c. vector int visited(N, 0); int ccount 0; for (int v : complement) { if (!visited[v]) { ccount ; stack int st; st.push(v); visited[v] 1; while (!st.empty()) { int node st.top(); st.pop(); for (int nb : adj[node]) { if (!inT[nb] !visited[nb]) { visited[nb] 1; st.push(nb); } } } } } int c ccount; int countx (int)T.size() - (R - c); return countx; }; function find vertices in T with color x. auto find_vertices_in_T_with_color_x [ ](vector int T, int x) { vector int result; vector int S T; int count query_count_in_T(S, x); while (count 0) { int l 0; int r S.size() - 1; while (l r) { int mid (l r) 2; vector int part(S.begin() l, S.begin() mid 1); --- Page 46 --- int cpart query_count_in_T(part, x); if (cpart 0) { r mid; } else { l mid 1; } } int found S[l]; result.push_back(found); remove found from S. auto it find(S.begin(), S.end(), found); if (it ! S.end()) S.erase(it); count query_count_in_T(S, x); } return result; }; auto find_independent_set_heuristic [ ](vector int verts) { vector int best; We ll use a random approach. for (int rep 0; rep 10; rep ) { vector int attempt; vector int local verts; random_shuffle(local.begin(), local.end()); for (int v : local) { bool can true; for (int u : attempt) { if (adjMatrix[u][v]) { can false; break; } } if (can) attempt.push_back(v); } if (attempt.size() best.size()) best attempt; } return best; }; vector int U unassigned; while (!U.empty()) { vector int T find_independent_set_heuristic(U); vector int assignedInT; vector int S T; while (!S.empty()) { bool foundX false; for (int x 0; x N; x ) { if (S.empty()) break; int countx query_count_in_T(S, x); if (countx 0) { vector int found find_vertices_in_T_with_color_x(S, x); for (int v : found) { final_colors[v] x; assignedInT.push_back(v); } for (int v : found) { auto it find(S.begin(), S.end(), v); if (it ! S.end()) S.erase(it); } foundX true; --- Page 47 --- } } if (!foundX) { If no color found for S, we can t assign those vertices. But maybe it s impossible. break; } } remove T from U. set int assignedSet(assignedInT.begin(), assignedInT.end()); vector int newU; for (int v : U) { if (assignedSet.find(v) assignedSet.end()) newU.push_back(v); } U newU; } return final_colors; } References [1] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021. [2] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021. [3] DeepSeek-AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025. [4] Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai o1 system card. arXiv preprint arXiv:2412.16720, 2024. [5] Carlos E Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. Swe-bench: Can language models resolve real-world github issues? arXiv preprint arXiv:2310.06770, 2023. [6] Leblond, R emi and Gimeno, Felix and Altch e, Florent and Saade, Alaa and Ruddock, Anton and Tallec, Corentin and Powell, George and Grill, Jean-Bastien and Miku la, Maciej and Lochbrun- ner, Matthias and others. Alphacode 2 technical report. https: storage.googleapis.com deepmind-media AlphaCode2 AlphaCode2_Tech_Report.pdf, December 2023. Accessed: 2025- 01-14. [7] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, R emi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Science, 378(6624):1092 1097, 2022. [8] Mike Mirzayanov. Codeforces rating system. https: codeforces.com blog entry 102, 2010. [9] Mike Mirzayanov. Open codeforces rating system. https: codeforces.com blog entry 20762, 2016. [10] Mike Mirzayanov. Codeforces: Soon we will change the rating calculation for new accounts. https: codeforces.com blog entry 77890, 2020. --- Page 48 --- [11] OpenAI. Introducing swe-bench verified. https: openai.com index introducing-swe-bench-verified , August 2024. Accessed: 2025-01-14. [12] OpenAI. Learning to reason with llms. https: openai.com index learning-to-reason-with-llms , September 2024. Accessed: 2025-01-14. [13] OpenAI. Openai o3 system card. Technical Report, 2025. [14] Timo Schick, Jane Dwivedi-Yu, Roberto Dess ı, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. Advances in Neural Information Processing Systems, 36:68539 68551, 2023. [15] Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, et al. Kimi k1.5: Scaling reinforcement learning with llms. arXiv preprint arXiv:2501.12599, 2025. [16] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824 24837, 2022.