My winning theory in IOI 2018 & 2019 — Why I won 2 golds in IOI Dear Codeforces community.<br /> According to [IOI 2019 Results](http://stats.ioinformatics.org/results/2019), I got the 25th place and got successful gold medals twice in a row.<br /> Although it was pretty close to the gold-medal border (only 6.14pts / 600 difference) and it was lower performance than IOI 2018, which I participated when I was orange in Codeforces, I had many chances to get more points in this IOI, even for top 10. Since there are not so many people who have got two gold medals in IOI (and there were many requests like "I want [user:E869120,2019-08-14] to talk about how to get gold in IOI" like [this comment](https://codeforces.me/blog/entry/66909?#comment-510127) and [this comment](https://codeforces.me/blog/entry/66909?#comment-513129)). I want to write something about IOI, which may be useful for people who will participate in IOI next year and also some years later.<br /> <br /> <br /> ### A. First of all At...

Full text and comments »

Atcoder Beginner Contest 171 — Unofficial English Editorial Hi all, [Atcoder Beginner Contest 171](https://atcoder.jp/contests/abc171) was today. I wrote an unofficial English editorial. Hope it helps! ### [A: αlphabet](https://atcoder.jp/contests/abc171/tasks/abc171_a) We simply write an if statement. Runtime: $\mathcal{O}(1)$. <spoiler summary="Sample code"> ~~~~~ char x = in.next().charAt(0); if (x >= 'A' && x <= 'Z') out.println("A"); else out.println("a"); ~~~~~ </spoiler> ### [B: Mix Juice](https://atcoder.jp/contests/abc171/tasks/abc171_b) We want to buy the cheapest fruits, so we can sort the array and then pick the first $K$ fruits. Runtime: $\mathcal{O}(N \log N)$. <spoiler summary="Sample code"> ~~~~~ int n = in.nextInt(), k = in.nextInt(); int[] p = in.readIntArray(n); Util.safeSort(p); // this shuffles and sorts to avoid hacks long answer = 0; for (int i = 0; i < k; i++) { answer += p[i]; } out.println(answer); ~~~~~ </spoiler> ### [C: One Quadrillion and One Dalmatia...

Full text and comments »

More and More Suspicious Participants in AtCoder Beginner Contests! Hello, CodeForces. As I can't find any discussion thread in AtCoder, and the announcements of AtCoder contests are also posted here, I decided to post this blog in CodeForces. Last time (ABC355), I [reported](https://codeforces.me/blog/entry/129765?#comment-1151921) a suspicious participant [toyuzuko](https://atcoder.jp/users/toyuzuko) who solved problem ABCD in 51 seconds. They also did the similar thing in ABC354. This time (ABC356), there are much more suspicious participants. The average first-AC time (in seconds) of ABC347~ABC353 is in the following table: |Contest|A|B|C|D|E|F|G| |:-|:-|:-|:-|:-|:-|:-|:-| |ABC347|21|45|93|244|177|300|824| |ABC348|15|37|72|302|236|495|430| |ABC349|23|67|54|116|598|139|634| |ABC350|26|47|102|74|240|489|335| |ABC351|22|23|106|352|199|122|902| |ABC352|27|43|49|90|196|989|188| |ABC353|24|79|172|88|206|1161|313| |(minimum)|15|23|49|74|177|122|188| |(prefix sum)|15|38|87|161|338|460|648| Note that to get first-AC in a problem...

Full text and comments »

Hello maroonrk announcement Hello, Codeforces! I have news today: I joined the AtCoder team and started working as an admin. It does not mean I take [user:rng_58,2020-03-07]'s place right now. I'm just a beginner as an admin, so, for the time being, we will hold contests together, and I will learn how to do it. For this year, I don't stop participating in all AtCoder contests(especially AGCs) and aim to get a ticket for the WTF2021. I will mainly supervise ARC-level contest (and Japanese local contests). From next year, I'll start checking submitted problems from all writers and organize contests as main admin. Tomorrow's ARC-level contest is the first contest coordinated by me (with the help of [user:rng_58,2020-03-07]). I'm looking forward to your participation!

Full text and comments »

AtCoder Beginner Contest 133 English Solutions Since AtCoder often doesn't release English editorials to their beginner contests, I thought I'd write up my solutions. Feel free to add a comment if anything was unclear! A &mdash; T or T ------------------ Our alternatives here are sending all $N$ people on the train, for a total of $N \cdot A$ yen, or using the taxi, for a total of $B$ yen. We should thus print the minimum of these two values. Code: https://atcoder.jp/contests/abc133/submissions/6265526 B &mdash; Good Distance ------------------ We reword the problem slightly: for how many points $y$ and $z$ is $\sum_{k=1}^D (y_i-z_i)^2$ a perfect square? Given the small input constraints, we know that this sum is going to be at most $10 \cdot (20-20)^2 = 16000$. Hence, we can simply compute a list of all perfect squares less than $16000$ and iterate over all $\dbinom{N}{2}$ pairs of points. For each pair of points, we compute the summation and check if it is equal to any of our squares. If so, we increment th...

Full text and comments »

Personal FAQ I often receive direct messages, many of which I ignore, though I do respond to some. Here, I’ve decided to write down answers to some frequently asked questions. Going forward, I will likely continue to ignore most messages. If you really want a response, I think I can at least give some kind of reply if you support me with a positive amount via https://github.com/sponsors/maspypy. I will probably not respond to most of the comments that this article will receive. However, if there’s something interesting, I may add it to the article. ### Are there any tips for improvement? Such overly common questions are best asked to tools like ChatGPT. ### Are there any introductory articles I should read? Are there any books on competitive programming? Please search the internet using keywords like "codeforces, tutorial", "competitive programming book". ### What should I do to aim for IOI or ICPC? Since I have absolutely no experience with these, I recommend asking some...

Full text and comments »

Atcoder Beginner Contest 132 — Unofficial English Editorial Hi all, [Atcoder Beginner Contest 132](https://atcoder.jp/contests/abc132) was today. Atcoder only publishes Japanese editorials for beginner contests, so I wrote an unofficial English editorial. Hope it helps! ### [A: Fifty-Fifty](https://atcoder.jp/contests/abc132/tasks/abc132_a) After sorting the input, a "good" string will look like "AABB". Therefore, we simply sort and check for this format. <spoiler summary="Sample code"> ~~~~~ char[] s = in.next().toCharArray(); Arrays.sort(s); out.println(s[0] == s[1] && s[2] == s[3] && s[1] != s[2] ? "Yes" : "No"); ~~~~~ </spoiler> ### [B: Ordinary Number](https://atcoder.jp/contests/abc132/tasks/abc132_b) It suffices to simply check every range of 3 and see if its middle element should be counted. A simple way is to sort each range of 3 and check that the middle element remains in the middle. Runtime: $\mathcal{O}(n)$. <spoiler summary="Sample code"> ~~~~~ int n = in.nextInt(); int[] p = new int[n]; for (int i =...

Full text and comments »

I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3> # Mathematics Stuff - [Number Theory in Competitive Programming [Tutorial]](https://codeforces.me/blog/entry/46620) - [Number of points on Convex hull with lattice points](https://codeforces.me/blog/entry/62183) - [FFT, big modulos, precision errors.](https://codeforces.me/blog/entry/48465) - [Number of ways between two vertices](https://codeforces.me/blog/entry/19078) - [Mathematics For Competitive Programming](https://codeforces.me/blog/entry/76938) - [FFT and NTT](https://codeforces.me/blog/entry/19862) - [Burnside Lemma](https://codeforces.me/blog/entry/51272) - [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.me/blog/entry/76836) - [On burnside (again)](https://codeforces.me/blog/entry/64860) - [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.me/blog/entry/55912) - [Probabili...

Full text and comments »

Atcoder Beginner Contest 174 — Unofficial English Editorial Hi all, [Atcoder Beginner Contest 174](https://atcoder.jp/contests/abc174) was today. I wrote an unofficial English editorial. Hope it helps! ### [A: Air Conditioner](https://atcoder.jp/contests/abc174/tasks/abc174_a) We simply write an if statement. Runtime: $\mathcal{O}(1)$. <spoiler summary="Sample code"> ~~~~~ int x = in.nextInt(); out.println(x >= 30 ? "Yes" : "No"); ~~~~~ </spoiler> ### [B: Distance](https://atcoder.jp/contests/abc174/tasks/abc174_b) We can loop through all the points, and test each one. To avoid potential rounding errors, it's simplest to check $x^2 + y^2 \le D^2$, so we can keep everything in integers. Runtime: $\mathcal{O}(N)$. <spoiler summary="Sample code"> ~~~~~ int n = in.nextInt(); long d = in.nextInt(); d = d * d; Point[] points = Point.readPoints(in, n); int answer = 0; for (Point p : points) { if (p.x * p.x + p.y * p.y <= d) answer++; } out.println(answer); ~~~~~ </spoiler> ### [C: Repsept](h...

Full text and comments »

April Fools Day Contest 2021 — ZS Edition Hi everyone, April Fools is near and as usual we have an [April Fools Day Contest](https://codeforces.me/blog/entry/88840) on Codeforces this year. In addition to that, I usually try to host some form of mini April Fools Contest for my friends every year (or almost every year). This year, I am trying to host a bigger April Fools Day contest than usual and I invite everyone to participate! In view of the April Fools contest on Codeforces, the round will begin at [31 March 10pm (GMT+8)](https://www.timeanddate.com/worldclock/fixedtime.html?msg=April+Fools+Day+Contest+2021+%28ZS%29&iso=20210331T22&p1=122) and lasts for exactly $24$ hours (and thus it will end ~35 minutes before the CF April Fools round). The contest will consist of several unusual tasks, and I hope that everyone will at least find something interesting. The problems will not be sorted by increasing order of difficulty (if the word difficulty is even applicable), so it is **highly advisable** to read (and try!)...

Full text and comments »

Pro Tips - get them while they are free More tips to use while studying under my tutoring [here](https://um-nik.notion.site/Pro-Tips-8b923b0dc7c94770824bdf4184afc43c). ## Stop caring about the rating Unless there are prizes involved, your position in the standings makes no difference. I can feel awful after winning a contest if I know that I could solve one more problem. Or I can feel OK losing a bunch of rating points knowing that I solved everything I could.  Because rating is just a number. It is highly volatile and it depends on other people, not only on your skill. But solving problems is totally up to you. And you should evaluate yourself not based on some random metric, but on your honest feeling whether you performed up to your expectations. Your sense of self should be under your control, don't get hung up on some imaginary value, you cannot reduce your progress to a single number. ## Don't use more than one account Rating is just a number. Do not be afraid to lose your colour. You’ll get it back in no t...

Full text and comments »

Atcoder Beginner Contest 143 — Unofficial English Editorial Hi all, [Atcoder Beginner Contest 143](https://atcoder.jp/contests/abc143) was today. I wrote an unofficial English editorial. Hope it helps! ### [A: Curtain](https://atcoder.jp/contests/abc143/tasks/abc143_a) The curtains can cover a maximum of $2B$. So either they don't cover the whole window and the remainder is $A-2B$, or they do and the remainder is $0$. So the answer is $\max(0, A-2B)$. Runtime: $\mathcal{O}(1)$. <spoiler summary="Sample code"> ~~~~~ int a = in.nextInt(), b = in.nextInt(); out.println(Math.max(0, a - 2 * b)); ~~~~~ </spoiler> ### [B: TAKOYAKI FESTIVAL 2019](https://atcoder.jp/contests/abc143/tasks/abc143_b) We can simply loop through every pair (taking care not to double count) and add the health points restored. Runtime: $\mathcal{O}(N^2)$. <spoiler summary="Sample code"> ~~~~~ int n = in.nextInt(); int[] d = in.readIntArray(n); long answer = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { answ...

Full text and comments »

Report: Contest-Time Solution Hints Linked to NotOnlySuccess I am writing this blog to report a competitive-integrity issue involving the Codeforces user [user:NotOnlySuccess,2026-08-09] and a website associated with their content. The main issue is simple: **problem-specific solution material and hints for an ongoing Codeforces contest were made available before the contest ended.** # 1. Solution material published before the contest ended During [Codeforces Round 1116 (Div. 1, Div. 2)](https://codeforces.me/blog/entry/155668), an article titled [CF Round 1116 (Div. 1+2)](https://mp.weixin.qq.com/s/P3QJqmQFRsLlW9GX_y_8YQ) was published on a WeChat public account at August 10, 2026, 00:37 (UTC +8). The Codeforces contest ended at August 10, 2026, 01:05 (UTC +8). Therefore, the article was publicly available **28 minutes before the contest ended**.  The article already contained problem-specific solution material. For readers who do not understand Chinese...

Full text and comments »

AtCoder Beginner Contest 141 — Unofficial Editorial [AtCoder Beginner Contest 141](https://atcoder.jp/contests/abc141 ) has just finished, and this is an unofficial editorial. You can check [my solutions](https://atcoder.jp/contests/abc141/submissions?f.Task=&f.Language=&f.Status=&f.User=ouuan), but I used lots of defines in my codes, and they're hard to read. ## [C &mdash; Attack Survival](https://atcoder.jp/contests/abc141/tasks/abc141_c ) Let $cnt[i]$ be the number of times the player $i$ correctly answered a question. The player $i$ survived if and only if $q-cnt[i]<k$. ## [D &mdash; Powerful Discount Tickets](https://atcoder.jp/contests/abc141/tasks/abc141_d ) First, you have to know $\left\lfloor\frac{x}{2^k}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac x 2\right\rfloor}{2^{k-1}}\right\rfloor$(when both $x$ and $k$ are positive integers and $k\ge 1$). In fact, it is true that $\left\lfloor\frac{\left\lfloor\frac{x}{y}\right\rfloor}{z}\right\rfloor=\left\lfloor\frac{x}{yz}\right\rfloor$ (when $x$, $y$, $z$ are...

Full text and comments »

AtCoder Beginner Contest 151 English Solutions #A &mdash; Next Alphabet The easiest way to deal with this problem is probably to convert the given character to an integer, add one, and convert it back. If you absolutely can't do that, a somewhat more annoying implementation would involve iterating through the alphabet, waiting until you find the given letter, using a boolean variable to store that the letter has been found, and printing the letter on the next iteration of the loop. (However, iterating over the alphabet is itself nasty unless you have conversion from letters to integers, so this approach is rather pointless unless your language just doesn't support the first method, though in that case you should probably switch languages anyway.) Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc151/submissions/9440245) --- #B &mdash; Achieve the Goal In total, we need to earn $NM$ points. We subtract the points earned so far and determine whether this is a valid score for the final ...

Full text and comments »

AtCoder Beginner Contest 169 Unofficial Editorial I just did my first ABC in a while, so I decided to write up and share my solutions below. Feel free to leave questions in the comments! There were several questions this round that had the potential to create precision issues; however, the solutions below give approaches that sidestep those errors altogether. Sadly, I think compiling and testing my A prevented me from winning the round :( #A &mdash; Multiplication 1 Just multiply the numbers and print them out. It's not that hard. Time Complexity: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc169/submissions/13800320) --- #B &mdash; Multiplication 2 This turns out not to be quite as easy as the last problem. Multiplying numbers this large is actually a challenge in C++ because the result is likely to be greater than $2^{63}$, and thus will cause long long overflow. Thus, in C++, we can't just multiply the numbers and check if the result is greater than $10^{18}$. One possible appr...

Full text and comments »

Competitive Programming Roadmap (target: [gray, blue]) tl;dr ------------------ - Competitive programming roadmap [here](https://drive.google.com/file/d/16Jydn250Ue7K7hOfzLxw4p5jFF4ZCqWT/view?usp=sharing). - It should be suitable both for newcomers and for people with some experience with CP: let's say, up to blue on Codeforces. - It contains ~ 100 "must-know" problems about various topics: ad-hoc, STL, binary search, DP, number theory, graphs. - There are solution sketches at the bottom, don't feel guilty reading them if stuck. Why? ------------------ Many people new to Codeforces seek advice about how to get better / which problems to try. Other people are stuck on gray / green even after solving a lot of problems. This roadmap aims to be a solution. My take: to be good at competitive programming, you have to know "what to think" and "how to think" when you try a problem. - "What to think": you have to know a decent amount of standard problems / techniques. Sometimes, a problem requires steps / observations that seem ob...

Full text and comments »

AtCoder Beginner Contest 172 English Solutions #A &mdash; Calc Just directly print the given sum. Time Complexity: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14750143) --- #B &mdash; Minor Change The answer is simply the number of positions $i$ for which $S[i] \neq T[i]$. This is because we must make a move fixing each of those position, and each move can only make $S[i] = T[i]$ for one new position. Thus, we can iterate through the positions and count those where $S$ and $T$ differ, printing the total as our answer. Time Complexity: $O(|S|)$. [Click here for my submission.](https://atcoder.jp/contests/abc172/submissions/14750027) --- #C &mdash; Tsundoku We apply two pointers. Iterate over the number of books to be read from desk A in decreasing order, starting with the greatest number of those books we could read without exceeding $K$ minutes. Maintain the sum of all books to be read from desk A. Then, while we can do so without exceeding $K$ minutes, add ...

Full text and comments »

Atcoder Beginner Contest 183 — Unofficial English Editorial Hi all, [Atcoder Beginner Contest 183](https://atcoder.jp/contests/abc183) was today. I wrote an unofficial English editorial. Hope it helps! ### [A: ReLU](https://atcoder.jp/contests/abc183/tasks/abc183_a) We simply write an if statement. Runtime: $\mathcal{O}(1)$. <spoiler summary="Sample code"> ~~~~~ int x; re(x); if (x < 0) { x = 0; } ps(x); ~~~~~ </spoiler> ### [B: Billiards](https://atcoder.jp/contests/abc183/tasks/abc183_b) The trick is to reflect $G$ over the x-axis, so the desired path becomes a straight line. Then it's a matter of simple math to compute the intersection of that line with the x-axis. Runtime: $\mathcal{O}(1)$. <spoiler summary="Sample code"> ~~~~~ double x1, y1, x2, y2; re(x1, y1, x2, y2); y2 *= -1; double r = -y2 / (y1 - y2); double ans = x1 * r + x2 * (1 - r); ps(ans); ~~~~~ </spoiler> ### [C: Travel](https://atcoder.jp/contests/abc183/tasks/abc183_c) Because $N$ is so small, we can simply try all $(N-1)!$ o...

Full text and comments »

[Tutorial] On Applications of CDQ Divide & Conquer _This tutorial is nominated for the [blog posts competition](https://codeforces.me/blog/entry/149422) from [user:cadmiumky,2026-02-07]. Thanks to him for this initiative!_ _Also thanks to [user:Ghos007,2026-02-08], [user:dima210121012101,2026-02-08], [user:dmitryAdams,2026-02-08] and ChatGPT for proofreading this post and giving useful feedback._ --- CDQ Divide & Conquer is an interesting algorithmic technique that nobody talks about (at least in Russian CP community). However, it is quite powerful, as it often provides unexpectedly clean solutions to seemingly tedious problems. In this tutorial, I will discuss different contexts where this method is useful. I also want to collect what I have seen about this technique on the Internet in one place and add my own insights. Credit to [robert1003's blog](https://robert1003.github.io/2020/01/31/cdq-divide-and-conquer.html) where I first learned this method. The main idea of this technique is to calculate the **influence/contr...

Full text and comments »

[Tutorial] A Way to Practice Competitive Programming : From rating 1000 to 2000 Dear Codeforces Community.<br /> <br /> Today I want to share some ways to practice competitive programming and getting rating. I think this is helpful for those who is practicing competitive programming hardly but rating is sluggish. (By the way, on July 17th, I have a project of competitive programming said CombNaf in Japan. I did a lecture about this. Great thanks to the CombNaf's organizer is [user:Nafmo2,2017-07-17].)<br /> <br /> I will write this by **4 steps**: rating **<font color="grey">1000</font> --> <font color="green">1250</font>**, **<font color="green">1250</font> --> <font color="aqua">1500</font>**, **<font color="aqua">1500</font> --> <font color="blue">1750</font>**, **<font color="blue">1750</font> --> <font color="purple">2000</font>**, in Codeforces Rating System.<br /> <br /> Before writing about each step, I wrote it as premise: You don't have to do this way. This is just a way to practice. Ways to practice is different among people, so I think this may n...

Full text and comments »

AtCoder Beginner Contest 076 Hello Codeforces!<br /> <br /> I'm quite excited to invite you to [AtCoder Beginner Contest 076](https://abc076.contest.atcoder.jp/) which will held on [Saturday, October 28th 21:00 JST](https://www.timeanddate.com/worldclock/fixedtime.html?iso=20171028T2100&p1=248) and lasts for 100 minutes.<br /> <br /> The round problems are created by me ([user:E869120,2017-10-27]) and [user:square1001,2017-10-27].<br /> <br /> This contest will have four problems and it is **rated** for contestants whose rating is below 1200. The same as before, contestants whose rating is more than or equal to 1200 can take part out of competition.<br /> <br /> The scoring is: 100 &mdash; 200 &mdash; 300 &mdash; 400.<br /> <br /> I hope you can have fun during the contest. Good luck and have fun, wish you high rating!<br /> <br /> See you tomorrow!<br /> <br /> <br /> UPD 1: The editorial is [here](https://img.atcoder.jp/abc076/editorial.pdf). Thank you for participating!<br /> <br /> **UPD 2: Co...

Full text and comments »

AtCoder Beginner Contest 164 Announcement We will hold AtCoder Beginner Contest 164. - Contest URL: https://atcoder.jp/contests/abc164 - Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200426T2100&p1=248 - Duration: TBD (around 2 hours) - Number of Tasks: 6 - Writer: kyopro_friends, [user:Kmcode,2020-04-25], [user:latte0119,2020-04-25], [user:smeke,2020-04-25], ynymxiaolongbao, wo01 - Rated range: ~ 1999 The point values will be 100-200-300-400-500-600. We are looking forward to your participation! Addition: About the Unrated ABC163 We are sorry for the inconvenience. The server down during the last contest was caused by a sudden access to the ALB, and we found that we could solve this problem by doing Pre-Warming. Also, the bug where the problem statement does not show up has been resolved by changing the caching algorithm. The problem with submissions showing up as IE (Internal Error) was due to the Judge server's scoring algorithm being different than in the past. This too h...

Full text and comments »

Atcoder Beginner Contest 146 -- Unofficial English Editorial Hi all, [Atcoder Beginner Contest 146](https://atcoder.jp/contests/abc146) was today. I wrote an unofficial English editorial. Hope it helps! ### [A: Can't Wait for Holiday](https://atcoder.jp/contests/abc146/tasks/abc146_a) We simply find the index in the week, and print $7-i$ (taking care to order the days correctly so Sunday gives us $7$ as the output). Runtime: $\mathcal{O}(1)$. <spoiler summary="Sample code"> ~~~~~ String w = "SUNMONTUEWEDTHUFRISAT"; // this is sort of a bad way to do this String s = in.next(); int i = w.indexOf(s) / 3; out.println(7 - i); ~~~~~ </spoiler> ### [B: ROT N](https://atcoder.jp/contests/abc146/tasks/abc146_b) We can simply loop through the string and increment each character by $N$, taking care to subtract $26$ if we go past the end of the alphabet. Runtime: $\mathcal{O}(|S|)$. <spoiler summary="Sample code"> ~~~~~ int n = in.nextInt(); char[] s = in.next().toCharArray(); for (int i = 0; i < s.length; i++) { s[i]...

Full text and comments »

AtCoder Beginner Contest 137 English Solutions Although AtCoder seems to be getting back to posting English editorials, I'm continuing to release some myself in case having the extra explanations helps some people. (Sidenote: Some of the provided submissions come from after the contest itself, because I had to leave midway through, before I got the chance to debug my E or write my F.) --- #A &mdash; +-X Just use your language's max function. As $A$ and $B$ are small, we don't need to worry about integer overflow. Runtime: $O(1).$ [Click here for my submission.](https://atcoder.jp/contests/abc137/submissions/6802607) --- #B &mdash; One Clue Let's try to find the minimum and maximum values in the answer. It's fairly easy to see that all integers between them will also be in the set. To find the minimum possible position of a black stone, we place $K$ black stones such that $X$ is at the maximum position. Then, the minimum position will thus be $X-K+1$, as we have $K-1$ black stones to the left of $X$....

Full text and comments »

Unofficial ACL Beginner Contest Editorial ### [A &ndash; Repeat ACL](https://atcoder.jp/contests/abl/tasks/abl_a) <spoiler> Easy programming-language-knowledge check typical of the first task of AtCoder beginner contests. The following is a passing Kotlin submission: ``` fun main() { val k = readLine()!!.toInt() val ans = "ACL".repeat(k) println(ans) } ``` </spoiler> ### [B &ndash; Integer Preference](https://atcoder.jp/contests/abl/tasks/abl_b) <spoiler> Assume there is an integer in both ranges and call it $x$. Note that both $x \ge \max(A, C)$ and $x \le \min(B, D)$ must therefore be true. Thus $x$ exists if and only if $\max(A, C) \le \min(B, D)$ is true. This is the standard formula for finding the overlap of two ranges. </spoiler> ### [C &ndash; Connect Cities](https://atcoder.jp/contests/abl/tasks/abl_c) <spoiler> Note that the initial network of cities can be divided into one or more *components*, where any city of a component can reach any other city in that component follow...

Full text and comments »

AtCoder Beginner Contest 128 — Unofficial English Editorial Hello Codeforces! Did you enjoy the [AtCoder Beginner Contest 128](https://atcoder.jp/contests/abc128)? A Japanese editorial is [already out](https://img.atcoder.jp/abc128/editorial.pdf), but unfortunately there is no English editorial, so I translated it into English experimentally. Note that this is an unofficial one; AtCoder has no responsibility for this editorial. Also, I didn't do proofreading at all, so it might contain many typos. Moreover, this is the first experience I write such kind of editorial, so the English may not be clear, may be confusing, or even contain mistakes. Any minor corrections (including grammatical one) or improvement suggestions are welcome. Please do not hesitate posting a comment about it. ## A: Apple Pie For simplicity, you can cut all the apples into pieces in advance. As a result, you will have $3A+P$ pieces of apple. By using all these pieces as much as you can make apple pie, you will get maximum number of apple pies. The maximum ...

Full text and comments »

AtCoder Beginner Contest 129 — Unofficial English Editorial Hello Codeforces! Did you enjoy the [AtCoder Beginner Contest 129](https://atcoder.jp/contests/abc129)? As usual, there was only [Japanese editorial](https://img.atcoder.jp/abc129/editorial.pdf) published, so I translated it into English again. **Disclaimer.** Note that this is an unofficial editorial and AtCoder has no responsibility for this. Also, I didn't do proofreading at all, so it might contain many typos. Moreover, this is the second experience I write such kind of editorial, so the English may not be clear, may be confusing, or even contain mistakes. Any minor corrections (including grammatical one) or improvement suggestions are welcome. Please do not hesitate posting a comment about it. ## A: Airplane There are 6 orders to visit the airports, so you can try all of them and look for the minimum value. However, if you realized that each cost of a route is equal to the sum of two integers out of the given three, you could also obtain an answer by subtracting ...

Full text and comments »

touristream 011: Codeforces Round 670 (Div. 2) + Educational 95 Hey there! During my last stream ([link to YouTube](https://www.youtube.com/watch?v=JU3HY5GLVnY)), besides the expected SNSS Round 5, I did Codeforces Round 669 (Div. 2) virtually trying to explain most of my thoughts in the process. I'd say it went pretty well! Tomorrow I'll hold another stream solving the most recent Codeforces Div. 2 rounds: [Round 670](https://codeforces.me/contest/1406) and [Educational 95](https://codeforces.me/contest/1418). I might also do today's [AtCoder Beginner Contest 178](https://atcoder.jp/contests/abc178). I'm planning to go live right after Educational 95 finishes &mdash; that is, around [19:45 MSK](https://www.timeanddate.com/worldclock/fixedtime.html?msg=touristream+011&iso=20200914T1945&p1=3396). A question is, given that I will do both Round 670 and Educational 95, which one should I do first? [Vote here](https://strawpoll.com/jp3zdqq4c) :) As usual, the stream will be live on [my Twitch](https://www.twitch.tv/the__tourist), make s...

Full text and comments »

Unofficial AtCoder Beginner Contest 237 Editorial ### [A &ndash; Not Overflow](https://atcoder.jp/contests/abc237/tasks/abc237_a) <spoiler> Note that $N$ has to be read as a signed 64-bit integer type. You could check it by either doing to comparison manually, or casting back and forth between the signed 32-bit integer type. Time complexity: $O(1)$ </spoiler> ### [B &ndash; Matrix Transposition](https://atcoder.jp/contests/abc237/tasks/abc237_b) <spoiler> Simply construct a $W$-by-$H$ matrix, assign $B_{i, j} = A_{j, i}$ for all relevant $i, j$, then output it. Alternatively, if you use Python, the `numpy` library installed in AtCoder gives a really short implementation, as noted in this user editorial: https://atcoder.jp/contests/abc237/editorial/3344 Time complexity: $O(HW)$ </spoiler> ### [C &ndash; kasaka](https://atcoder.jp/contests/abc237/tasks/abc237_c) <spoiler> Note that for a string to be a palindrome, it must start with the same number of contiguous `a`s as it ends with. If there are less con...

Full text and comments »

AtCoder Beginner Contest 139 English Solutions #A &mdash; Tenki This is a fairly simple task--just iterate over all positions in the strings and count the ones where S[i] = T[i]. Runtime: $O(|S|)$. [Click here for my submission.](https://atcoder.jp/contests/abc139/submissions/7247680) --- #B &mdash; Power Socket Note that we already have one socket, so we need to fill $B-1$ more sockets. Additionally, each new outlet we add will take up one socket and add $A$ sockets, resulting in a net addition of $A-1$ sockets. We thus need to create at least $B-1$ sockets where each outlet gives us $A-1$ sockets, making our answer $\lceil \frac{B-1}{A-1} \rceil$. Since most programming languages use floor division, we can also express this as $\lfloor \frac{A+B-3}{A-1} \rfloor$. Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc139/submissions/7249379) --- #C &mdash; Lower We essentially use two pointers. Maintain the starting position at zero. Then, while the next position isn't hi...

Full text and comments »

AtCoder Beginner Contest 135 English Solutions #A &mdash; Harmony Without loss of generality, let $A < B$. Then, we have three cases: - $K$ is less than $A$. This gives $A - K = B - K$, which gives $A = B$, which is false. - $K$ is greater than $B$. This gives $K - A = K - B$, which is also false. - $K$ is between $A$ and $B$. This gives $K - A = B - K$, which gives $2K = A+B$. Thus, we must have $2K=A+B$. If $A+B$ is odd, there is thus no solution. If $A+B$ is even, our answer is $\frac{A+B}{2}$. It is easy to verify that this number is indeed between $A$ and $B$. Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc135/submissions/6560205) --- #B &mdash; 0 or 1 Swap Let $K$ be the number of positions $i$ at which $p_i \neq i$ (using 1-indexing). If $K = 0$, the answer is yes, as we can simply leave the permutation as is. If $K = 2$, the answer is also yes: swap the two misplaced elements. (Notice that we can never have $K = 1$, as if any element is put in the wrong posi...

Full text and comments »

Эффективная реализация умножения Карацубы с авто-векторизацией **В данном блоге приводится эффективная реализация умножения Карацубы двух многочленов.** [cut] $$\text{ }$$ Всем привет! Давным-давно меня попросил один человек научить его находить миллионное число Фибоначчи абсолютно точно на C++ за секунду. Эта задача была [успешно решена](https://ideone.com/qO88bh) умножением Карацубы. После этого я попробовал сдавать стандартные задачи вроде "сопоставить одну строку из символов $\text{ATGC}$ к каждой позиции другой строки и найти позицию с максимальным числом совпадений" алгоритмом Карацубы, и они успешно сдавались с двукратным запасом по времени. Было много реализаций, но в итоге [user:MrDindows,2020-02-24] помог написать самую эффективную из всех, которые придумывались, и я решил поделиться ей. Идея умножения Карацубы ================== Пусть у нас есть два многочлена $a(x)$ и $b(x)$ равной длины $2n$ и мы хотим их умножить. Представим их как $a(x) = a_0(x) + x^n \cdot a_1(x)$ и $b(x) = b_0(x) + x^n \cdot b_1(x)$. Теперь посчит...

Full text and comments »

ACL Contest 2 Announcement **This contest is CANCELLED.** **Please read updates for details** We will hold ACL Contest 2. - Contest URL: https://atcoder.jp/contests/acl2 - Start Time: TBD - Duration: 150 minutes - Number of Tasks: 6 - Writer: [user:maroonrk,2020-09-25], [user:yosupo,2020-09-25] - Tester: [user:maroonrk,2020-09-25], [user:yosupo,2020-09-25], [user:sigma425,2020-09-25] - Rated range: 1200 &mdash; 2799 The point values will be 300-600-700-900-1300-1900. The concept of this contest is the same as ACL1, so you may refer to the [announcement](https://codeforces.me/blog/entry/82806) of ACL1 for more details. We are looking forward to your participation! **UPD**: We decided to postpone the contest. The new date is not confirmed, but it is likely to be 3rd October. The reason for this sudden decision is the collision of the problem with **today's Japanese contest** ([problem](https://yukicoder.me/problems/no/1241)). This task is almost the same as our E. We thought if w...

Full text and comments »

AtCoder Beginner Contest 136 English Solutions #A &mdash; Transfer First, we compute the resulting amount of water in Cup 1. Observe that this is equal to $min(A, B+C)$. Let this value be $D$. Then, the amount transferred from Cup 2 to Cup 1 is simply $D - A$, so the amount remaining in Cup 2 is $C - D + A$. Time complexity: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc136/submissions/6682058) --- #B &mdash; Uneven Numbers There are several efficient ways to approach this problem. One is to simply to count the one-, three-, and five-digit numbers less than or equal to $N$. However, because of the small maximum on $N$, a more naive approach works. Simply iterate over every value from $1$ to $N$, count its digits, and add one to the answer if the count is odd. (We can count a number's digits by repeatedly adding one to the count and dividing the number by ten until it reaches zero.) Time complexity: $O(N \log N)$. Note that $O(\log N)$ is possible with the more efficient approach. ...

Full text and comments »

AtCoder Beginner Contest 140 English Solutions #A &mdash; Password We have $N$ choices for each of the three characters in our password. This gives us a total of $N \cdot N \cdot N = N^3$ possible passwords. We can thus print $N \cdot N \cdot N$ as our answer. Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc140/submissions/7380201) --- #B &mdash; Buffet We can solve this with a brute-force simulation, simply implementing the procedure given in the problem. Iterate over the dishes in the order specified by array $A$, and when we eat dish $i$, add $B[i]$ to our answer, plus $C[i-1]$ if we just ate dish $i-1$. Note that since we'll eat every dish once, we could also just add the sum of array $B$ to our answer as we read it in, iterating over $A$ only to add values from $C$ where necessary. My solution implements this approach. Runtime: $O(N)$. [Click here for my submission.](https://atcoder.jp/contests/abc140/submissions/7383059) --- #C &mdash; Maximal Value We're giv...

Full text and comments »

We will hold AtCoder Beginner Contest 213 We will hold AtCoder Beginner Contest 213.[user:physics0523,2021-08-07] - Contest URL: https://atcoder.jp/contests/abc213 - Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210808T2100&p1=248 - Duration: 100 minutes - Number of Tasks: 8 - Writer: kyopro_friends, [user:Nyaan,2021-08-07] - Tester: [user:sugarrr,2021-08-07], [user:physics0523,2021-08-07] - Rated range: ~ 1999 - The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

Full text and comments »

AtCoder Beginner Contest 144 English Solutions #A &mdash; 9x9 We can simply directly implement the procedure given in the problem. Print $AB$ if $A$ and $B$ are less than $10$ and $-1$ otherwise. One particularly fast way to do this is to use the ternary operator, which takes a boolean expression and two values as inputs and returns the first value if the expression is true and the second value otherwise. In C++, this looks like $\texttt{A < 10 && B < 10 ? A*B : -1}$. Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc144/submissions/8146605) --- #B &mdash; 81 Since we're only considering pairs of numbers from one through nine, we can simply iterate over every pair of numbers from one to nine and check if each pair multiplies to $N$. As soon as we find such a pair, we output Yes and exit the program. If we reach the end of the loop, we can then print No, since we've checked every possible pair and found that none of them work. Notice that we could also iterate over all number...

Full text and comments »

AtCoder Beginner Contest 130 — Unofficial English Editorial Hello Codeforces! Did you enjoy the [AtCoder Beginner Contest 130](https://atcoder.jp/contests/abc130)? As usual, there was only [Japanese editorial](https://img.atcoder.jp/abc130/editorial.pdf) published, so I translated it into English. Um, actually it's already three days after the contest, it might be a bit late, but well, whatever? **Disclaimer.** Note that this is an unofficial editorial and AtCoder has no responsibility for this. Also, I didn't do proofreading at all, so it might contain many typos. Moreover, this is the third experience I write such kind of editorial, so the English may not be clear, may be confusing, or even contain mistakes. Any minor corrections (including grammatical one) or improvement suggestions are welcome. Please do not hesitate posting a comment about it. ## A: Rounding You can implement it straightforward: print $0$ if $X < A$, and print $10$ if $x >= A$. An example code is shown in List 1: Listing 1. Example Code of Rounding...

Full text and comments »

Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288） Announcement We will hold Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）. - Contest URL: https://atcoder.jp/contests/abc288 - Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230204T2100&p1=248 - Duration: 100 minutes - Number of Tasks: 8 - Writer: [user:leaf1415,2023-02-02], [user:cn449,2023-02-02], [user:chokudai,2023-02-02], [user:nok0,2023-02-02], [user:PCTprobability,2023-02-02], [user:m_99,2023-02-02] - Tester: kyopro_friends, [user:math957963,2023-02-02] - Rated range: ~ 1999 The point values will be 100-200-300-400-500-500-600-600. Since this contest is used as a qualification round for a local event, the style of problems is modified a bit. - Up to task C is usual. - (the style of tasks D-Ex in this contest) is between (the style of tasks D-Ex in usual ABC) and (the style of earlier tasks in usual ARC). - Tasks in the middle of this contest are slightly harder than usual. Later tasks are not too difficult. We are looki...

Full text and comments »

AtCoder Beginner Contest 146 English Solutions #A &mdash; Can't Wait for Holiday The only approach here is the trivial one--compare the input to each of the possible seven values and print the appropriate answer for each of them. One reasonably fast way to implement this is to create an array $A$ containing the seven inputs, with "SUN" in position zero and "SAT" in position six. Then, we compare $S$ to each value in the array and, upon finding the value $i$ such that $A[i] = S$, we print $7-i$. This is valid because the next Sunday after the day represented by our input would come in position seven. Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8604159) --- #B &mdash; ROT N Again, the only real solution here is to directly implement the approach given in the problem statement. However, character arithmetic gives us a fairly nice way to do so. For each character in $S$, we can compute the position of the corresponding letter in the alphabet by taking $S[i]$ minus...

Full text and comments »

AtCoder Beginner Contest 158 English Solutions It's been a while since I've done one of these! --- #A &mdash; Station and Bus After parsing the problem statement, we see that we simply need to determine whether the two companies each operate at least one station, since if this is the case, those stations will be connected, and otherwise, if one company operates every station, no connections will be built. This is now a fairly easy task---one way to do it is to check whether every character in the string is the same, printing No if this is the case and Yes otherwise. Alternatively, we can directly compare $S$ to "AAA" and "BBB", rejecting if the input is one of these strings and accepting otherwise. There are a wide variety of approaches, but they're all essentially equivalent. Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc158/submissions/10587980) --- #B &mdash; Count Balls Given the large limits on $N, A,$ and $B$, a brute force simulation will be vastly too slow---we need...

Full text and comments »