Who sorry_dreamoon really is Hello everybody. So I was really bored tonight and looked at so many comments being like "[user:sorry_dreamoon,2015-02-18] is X" and then people arguing and disagreeing. Since I had nothing better to do, I decided to finally unravel the truth of who he actually is. Here is the full case and how I actually got to him, hope you enjoy! :D Selection ------------------ Let's start by the obvious. He managed to get first place in Div2 and he got second in Div1 (would've been first if the scores were static). So what we know is that he is really good. Let's look at the past 10 Div1 contests. It turns out that only 8 times it happened that someone with a rating of less than 2500 got in top5. This is 8 times out of 50 people being in top5. But he was second and almost first, so he is better than that. It turns out actually, that in the past 10 Div1 contests, only 2 times it happened that someone with rating less than 2500 got in top3. Combining this information with [user:sorr...

Full text and comments »

Chinese Postman Problem: How I Ran a 180 km Ultramarathon Through Every Street in My City Hello, Codeforces! A couple of years ago, a friend of mine told me that two cyclists had passed through every single street in the center region of the city I live in (Belo Horizonte, southeastern Brazil), on the [third try](https://www.strava.com/activities/1030665876/overview). <spoiler summary="First try"> After ~160 km, they had not completed 1/3 of the goal. [Strava link](https://www.strava.com/activities/976021527). <img src="/predownloaded/8a/53/8a53829f7d78e88808a3ff751b64406ec2fc0efd.png" style="width: 600.0px;max-width: 100.0%;max-height: 100.0%;"> </spoiler> <spoiler summary="Second try"> They were better prepared, but one of the guys was run over by a car (no big injuries). [Strava link](https://www.strava.com/activities/999450285). <img src="/predownloaded/85/8f/858fdcdcfda93cd1d9c7c59db7dbfad9e63d6ea2.png" style="width: 600.0px;max-width: 100.0%;max-height: 100.0%;"> </spoiler> <center> <img src="/predownloaded/8d/5c/8d5cfb677a361654105e49f36f214c35...

Full text and comments »

How to use Codeforces [GUIDE] I see a lot of newcomers struggling to use the website to it's fullest, so I decided to write a blog that has all important information about how to use Codeforces in a single place. I will update it with time, so feel free to write your suggestions/questions in case I missed something and I will be glad to add it to the post! I would like to thank [user:_Vanilla_,2022-02-05] and [user:mesanu,2022-02-05] for helping me write the blog, and [user:Monogon,2022-02-05], [user:down,2022-02-05] and [user:AlperenT,2022-02-05] for proofreading and giving suggestions. #### Navigating through pages  It's possible to navigate through most pages of Codeforces using the bar on the top, I will talk about what each tab does more in depth below: #### The Help Page The help page contains the answer to a lot of questions about Codeforces, such as rati...

Full text and comments »

Blogewoosh #7 Hello, codeforces! Long time no see, right? So maybe it's a good idea to try to return to my blogs slowly. This time the blog will be about a trick, which usually isn't necessary to solve a task, but can be useful to make implementation much more comfortable. Let's look at [this](https://codeforces.me/contest/932/problem/F) problem. It is about some DP on a tree in which we have to use convex hull trick to improve the complexity. The task requires merging two convex hulls with "smaller to bigger" trick. I recommend you to read the statement before reading the rest of the blog (and the [editorial](https://codeforces.me/blog/entry/57796) if you don't know how to solve it). [cut] $ $ So, how to merge two convex hulls? If we keep them in something like the set from C++, then we can just take every element from the smaller one and try to add it to the bigger one. Unfortunately, adding one element in this way requires some ifology and care. It's hard to implement it, especiall...

Full text and comments »

Please improve QoL for blogs I'm pretty sure I've spent more time writing blogs than contests on Codeforces. Over time, I've found plenty of rough edges. So this is a plea to the Codeforces team to fix them. I'm effectively going to say "please redo everything" over dozens of paragraphs, but I'll hopefully make the steps to the solution tangible and clear. If this is deemed way too ambitious, few improvements are better than none. [cut] <!-- --> ## Publication time So I write a post in the Codeforces UI, save a draft, update it a few times, think it's ready, and publish it. I open my brand new post and see: > ### Totally not a useless post > By [user:purplesyringa,2024-09-24], history, 3 days ago, In English Okay, wait, "3 days ago"? Oh, right, that's when I saved the first draft. Now people open the post, see "3 days ago", see 0 upvotes, and what do they think? That's right, they think it's garbage because no one's voted positive, so they skip the article. Maybe not everyone's like tha...

Full text and comments »

Likes in Posts and Comments Hello. Here's a small improvement for posts and comments. Likes can now be specified in their markup. Maybe this will be useful for organizing some kind of polls or collecting feedback. Here are some examples: Markup <br><small>Use square brackets instead of round</small> | Result - | - <small>Simple likes widget</small><br/>`(likes:1)` | <small>Same keys means same likes widgets</small><br/>`(likes:2)`<br/>`(likes:2)` | <br/> <small>Same keys and different groups can be used for exclusive choices</small><br/>`(likes:3,option1)`<br/>`(likes:3,option2)` | <br/> Yes, I know that this feature can be improved. I would prefer that we try to use it a little and understand what exactly is missing the most. Maybe we need to implement the fully functional polls. Let's do a small survey using the new feature. 1. What is your age range? * under 16: * 16-20: * 21-25: ...

Full text and comments »

Div. 3 problems should be easier Since the first div. 3 round there were 23 of them and probably some of you noticed that the rounds have become quite difficult for their target audience -- people with rating below 1600. More and more often only 3-4 problems out of 6-7 total are really being solved by the official participants, while the rest of the problems are only solved by 100-200 people many of whom participate out of competition. Not to be biased we can use such a tool as problem difficulty, a recent feature of codeforces. In the table below you can see round numbers, below -- amount of problems with difficulty 1600 and less in the particular round, below -- total amount of problems in the round.  Information in the right says that in average in a div. 3 round only 3.7 problems from about 7 in total have difficulty 1600 or less, which is only 55.8% of all problems of the round. Div. 3 announces allege that the rounds are going to b...

Full text and comments »

Avito Code Challenge 2018 Hi! I'm glad to invite you to take part in [contest:981] which starts on [contest_time:981]. Any participant can join the round and it will be rated for each participant. Hope to see you among the participants! Problems are prepared by me — Ildar Gainullin. This round is conducted on the initiative and support of [Avito](https://www.avito.ru/). Avito.ru is a Russian classified advertisements website with sections devoted to general good for sale, jobs, real estate, personals, cars for sale, and services. Avito.ru is the most popular classifieds site in Russia and is the third biggest classifieds site in the world after Craigslist and the Chinese website 58.com. Many thanks to Vladislav [user:winger,2018-05-24] Isenbaev, Grigory [user:gritukan,2018-05-24] Reznikov, Ivan [user:isaf27,2018-05-24] Safonov，Alexander [user:AlexFetisov,2018-05-24] Fetisov and Shiqing [user:cyand1317,2018-05-24] Lyu for the round testing, Nikolay [user:KAN,2018-05-24] Kalinin for helping me to...

Full text and comments »

Educational Codeforces Round 36 [Rated for Div. 2] Hello Codeforces! On [January 13, 16:05 MSK](https://www.timeanddate.com/worldclock/fixedtime.html?day=13&month=1&year=2018&hour=16&min=5&sec=0&p1=166) Educational Codeforces Round 36 will start. Series of Educational Rounds continue being held as [Harbour.Space University](https://harbour.space/) initiative! You can read the details about the cooperation between [Harbour.Space University](https://harbour.space/) and Codeforces in the <a href="http://codeforces.me/blog/entry/51208">blog post</a>. This round will be (traditionally now) **rated for Div. 2**. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally. You will be given **7 problems** and **2 hours** to solve them. The problems were prepared by Mikhail [user:PikMike,2018-01-12] Piklyaev, Ivan [user:BledDest,2018-01-12] Androsov, Sergey [user:sslotin,2018-01-13] Slotin and me....

Full text and comments »

Problem Topics Good Day to you! I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now &mdash; so here it is: <spoiler summary="aho"> http://www.spoj.com/problems/ADAJOBS/ URI 2226 (5) //[NICE][NUMBERS][DP] http://www.spoj.com/problems/SUB_PROB/en/ http://codeforces.me/contest/696/problem/D 8 http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force http://codeforces.me/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03] </spoiler> <spoiler summary="automat"> 6861 [LA] //CYK UVA 10679 //Suffix Automat http://www.spoj.com/problems/STRMATCH/ //Suffix Automat &mdash; trie might do too http://www.spoj.com/problems/NSUBST...

Full text and comments »

OCPC 2025 Winter — wrap Hi everyone! <center><a href="https://ocpc.camp"><img src="https://ocpc.camp/images/ocpc.svg" height="100px"></a> <a href="https://icpc.foundation/"><img src="/predownloaded/43/08/43086529a28ccb5c9f2f2eec560ffa85e09c6881.svg" height="100px"></a></center> <center> <b>Supported by</b><br> <a href="https://www.quantco.com/"><img src="https://ocpc.camp/images/quantco.svg" height="60px" style="margin: 10px 10px 10px 10px;"></a> <a href="https://ordercapital.com/"> <img src="https://ocpc.camp/images/OrCa.svg" height="60px" style="margin: 10px 10px 10px 10px;"> </a> <a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london"> <img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="60px" style="margin: 10px 10px 10px 10px;"></a> <a href="https://pinely.com/"> <img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="60px" style="margin: 10px 10px 10px 10px;"></a> </ce...

Full text and comments »

Codeforces Round #715 Editorial <strike>Note: I can't figure out how to place the tutorials inside spoilers. If someone is familiar with how CF spoilers work and can help I would really appreciate it. For now, be warned that the tutorials are visible by default (but everything else isn't)</strike> **UPD:** I figured out how to use spoilers! Also added implementations for all problems. Thanks for participating in our contest! [problem:1509A] Author: [user:Kuroni,2021-04-13] <br> First solve: [user:cfg0d,2021-04-16] at 00:01:02 <spoiler summary = "Hint"> How can you write the condition that $\frac{a_u + a_v}{2}$ is an integer in a more useful way? Think of the parities. </spoiler> <spoiler summary = "Tutorial"> [tutorial:1509A] </spoiler> <spoiler summary = "Comments from the authors">  </spoiler> [Implementation](https://codeforces.me/contest/1509/submission/113263196) [problem:1509B] Author: [user:Ari,2021-04-13] <br> First solve: [user:bl...

Full text and comments »

Sums and Expected Value — part 2 ### Instruction I recommend this blog also for red users. Read the theory and problems below, try to solve them. For solutions and extra insight/tips, watch my stream on Monday or watch the video later. If you aren't familiar with EV or summing problems, see part 1 first: [http://codeforces.me/blog/entry/62690] (http://codeforces.me/blog/entry/62690). I will stream a lecture on Monday at [14:00 CEST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=EV+lecture+2&iso=20181029T14&p1=262) &mdash; [https://www.youtube.com/watch?v=HDk6zQw0Rdo](https://www.youtube.com/watch?v=HDk6zQw0Rdo) (also [Twitch](https://www.twitch.tv/errichto)). I will go through theory and problems from this blog. ### Expected Value theory, part 2 We roll a 6-sided die. Remember, EV of square of the number of pips is something different than square of EV: $$E(X^2) = \frac{1+4+9+16+25+36}{6} = 15.166666\ldots$$ $$E(X)^2 = (\frac{1+2+3+4+5+6}{6})^2 = 3.5^2 = 12.25$$ Two events are ...

Full text and comments »

Codeforces Round 865 Happy Easter, Codeforces! <span style="color: white">Sadly the round will not be Easter themed :(</span> We ([user:arvindf232,2023-04-07], [user:culver0412,2023-04-07], [user:dbsic211,2023-04-07], [user:happy.potato,2023-04-07], [user:jerryliuhkg,2023-04-07]) are delighted to invite you to participate in [contest:1815] and [contest:1816], which will take place on [contest_time:1815]. Participants with a rating lower than 1900 will participate in Division 2, while participants with a rating of at least 1900 will participate in Division 1. **Notice the unusual starting time.** All the problems were authored and prepared by [user:arvindf232,2023-04-07], [user:culver0412,2023-04-07], [user:dbsic211,2023-04-07] and [user:happy.potato,2023-04-07]. Huge thanks to the following people, without whom the round would not be possible: - [user:Artyom123,2023-04-07] for excellent coordination and translation of statements. - [user:KAN,2023-04-07] for help with round preparation. - [user:j...

Full text and comments »

Educational Codeforces Round 96 [Rated for Div. 2] Hello Codeforces! On [contest_time:1430] [contest:1430] will start. **Note that the start time is unusual**. Series of Educational Rounds continue being held as [Harbour.Space University](https://harbour.space/) initiative! You can read the details about the cooperation between [Harbour.Space University](https://harbour.space/) and Codeforces in the <a href="http://codeforces.me/blog/entry/51208">blog post</a>. This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally. You will be given **6 or 7 problems** and **2 hours** to solve them. The problems were invented and prepared by Adilbek [user:adedalic,2020-10-10] Dalabaev, Alex [user:fcspartakm,2020-10-10] Frolov an...

Full text and comments »

April Fools Day Contest 2026 Editorial Thanks for participating! ### [2214A &mdash; Odd One Out](https://codeforces.me/contest/2214/problem/A) Idea: [user:flamestorm,2026-04-01] <spoiler summary="Solution"> You just need to output the arrow that only appears once. That arrow is **C2**. </spoiler> <spoiler summary="Code (Python)"> ~~~~~ print("C2") ~~~~~ </spoiler> <spoiler summary="Feedback"> - I liked it! </spoiler> ### [2214B &mdash; Are You Smiling?](https://codeforces.me/contest/2214/problem/B) Idea: [user:prvocislo,2026-04-01] <spoiler summary="Solution"> One unusual thing about the statement is the presence of a emoji. More precisely, a smiling, emoji. Okay, let's try to print a smiling emoji. However, the output should be a string of characters and numbers, so we cannot do it directly. There's one more suspicious thing in the statement &mdash; the $U+?=HAPPY$ equation. If we should print ?, what is the meaning of U? U+ often indicates that an unicod...

Full text and comments »

Codeforces Round #941 (Div. 1, Div. 2) Editorial [problem:1966A] <spoiler summary="Solution"> [tutorial:1966A] </spoiler> <spoiler summary="Code"> ~~~~~ t = int(input()) for tc in range(t): n, k = map(int, input().split()) cards = list(map(int, input().split())) ct = {} ans = n for c in cards: if c in ct: ct.update({c: ct[c] + 1}) else: ct.update({c: 1}) if ct[c] >= k: ans = k - 1 print(ans) ~~~~~ </spoiler> [problem:1966B] <spoiler summary="Solution"> [tutorial:1966B] </spoiler> <spoiler summary="Code"> ~~~~~ t = int(input()) for tc in range(t): n, m = map(int, input().split()) gr = [] for i in range(n): gr.append(input()) ans = "YES" if gr[0][0] != gr[n - 1][m - 1]: impossible = True for j in range(m - 1): if gr[0][j] != gr[0][j + 1] or gr[n - 1][j] != gr[n - 1][j + 1]: impossible = False if...

Full text and comments »

Complex FFT is not as bad as you think ... Probably. Hi everyone! As some of you _might_ already know, I don't like NTT. Primary reasons for this are: - I don't like modular arithmetic optimizations (Montgomery, etc). - I don't like NTT mods, and prefer good, old $10^9+7$. - I do like algebra of complex numbers. But, to my regret, the overwhelming mainstream in modern competitive programming is NTT. Primary reasons are: - It's allegedly faster. - It needs less memory. - It has no precision issues. - People don't like algebra of complex numbers. There is nothing I can do about the last, but today I'll address the first 3. Optimizing complex FFT was on my mind for quite some time, but I didn't really work on it _that much_ until the [blog](https://codeforces.me/blog/entry/142063) by [user:Qwerty1232,2025-04-24] on optimizing NTT has dropped, which motivated me to actually put some serious effort into this. In this blog, we will primarily focus on optimizations that are specific to complex arithmetic...

Full text and comments »

Codeforces Round #809 Editorial ## Some stats about the round <spoiler summary="Pre-contest predictions"> | Person | A | B | C | D1 | D2 | E | | ----- | ------ | -------- | -------- | -------- | -------- | -------- | | [user:BucketPotato,2022-07-17] | 900 | 1200 | 1400 | 1600 | 2000 | 2200 | | [user:lunchbox,2022-07-17] | 800 | 1300 | 1200 | 2000 | 2400 | 2300 | | [user:lce4113,2022-07-17] | 1000 | 1400 | 1400 | | | | | [user:lethan3,2022-07-17] | 800 | 1000 | 1200 | 1500 | 2000 | | | [user:Apple_Method,2022-07-17] | 800 | 1200 | 1200 | 2100 | 2500 | 2400 | | [user:izhang,2022-07-17] | 800 | 1200 | 1400 | 1600 | 2200 | | | [user:EnDeRBeaT,2022-07-17] | 800 | 1300 | 1500 | 1700 | 2000 | 2200 | | [user:Runtime-Terr0r,2022-07-17] | 800 | 1200 | 1400 | 1800 | | | | [user:AlperenT,2022-07-17] | 800 | 1100 | 1400 | 1900 | 2400 | 2200 | | | A | B | C | D1 | D2 | E | | ----- | ------ | -------- | -------- | -------- | -------- | -------- | | Average | 833 | 1211 | 1344 | 1775 | 2214 | 2260 | | Actual | 80...

Full text and comments »

Tourist Fan Montage As [user:tourist,2023-02-01]'s biggest fan, it was inevitable that I collected a substantial amount of tourist's pictures as the years went by. So now, I think I have enough of them and want to share them with the community. **Very Young Tourist**  **Young Tourist**  **Happy Tourist**  **Very Happy Tourist**  **Awkward Tourist**  **Anime Antagonist Tourist**  **Impostor Tourist**(No fucking way that's him)  **Teenager Tourist** ![ ](/predownloa...

Full text and comments »

Invitation to TLX Regular Open Contest #36 <p> Hello, Codeforces! </b> <img src="/predownloaded/2d/30/2d30c17aba8882b75b0b9b0aa7c222a519bcc7ba.png" style="width: 400.0px;float: right;margin: 0 1.0em 1.0em 1.0em;max-width: 100.0%;max-height: 100.0%;"> </p> We are excited to invite you to <b>TLX Regular Open Contest #36!</b> Key details: <ul> <li>Contest links: [TLX](https://tlx.toki.id/contests/troc-36)</li> <li> Time: [27th July 2024, 14:05 UTC](https://www.timeanddate.com/worldclock/fixedtime.html?msg=TLX%20Regular%20Open%20Contest%20%2336&iso=20240727T140500)</li> <li> Writer: [user:yz_,2024-07-25]</li> <li> Duration: 2 hours</li> <li> Problems: 7</li> <li> Scoring distribution: <b>100 &mdash; 200 &mdash; 350 &mdash; 400 &mdash; 450 &mdash; 550 &mdash; 700</b> </li> <li> <spoiler summary="The theme of the contest is related to..."></spoiler> </li> </ul> I would like to thank: <ul> <li> [user:Pyqe,2024-07-25] for coordinating...

Full text and comments »

Codeforces Round 982 (Div. 2) Hello Codeforces! Me and [user:yud08,2024-10-20] are excited to invite you to take part in [contest:2027], which starts on [contest_time:2027]. You will be given **5 problems** and **2 hours** to solve them. Two problems are divided into two subtasks. This round will be rated for all participants whose rating is **strictly below 2100**. The problems were authored by me and [user:yud08,2024-10-20], and prepared by me. We would like to thank: - [user:abc864197532,2024-10-20] and [user:vladithur,2024-10-20] for an amazing double coordination. - [user:Alexdat2000,2024-10-20] for translating the statements to Russian. - [user:BurnedChicken,2024-10-20] for LGM testing. - [user:BucketPotato,2024-10-20], [user:Fysty,2024-10-20], [user:alvingogo,2024-10-20], and [user:WiwiHo,2024-10-20] for red testing. - [user:sammyuri,2024-10-20], [user:anango,2024-10-20], [user:jay_jayjay,2024-10-20], [user:amsraman,2024-10-20], [user:Intellegent,2024-10-20], [user:valeriu,2024-10-20], [user:...

Full text and comments »

OCPC 2024 Winter — wrap Hi everyone! <center><a href="https://ocpc.mathos.unios.hr"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a> <a href="https://icpc.foundation/"><img src="https://ocpc.mathos.unios.hr/images/ICPC.svg" height="100px"></a></center> <center> <b>Sponsored by</b><br> <a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london"> <img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="50px" style="margin: 5px 5px 5px 5px;"></a> <a href="https://pinely.com/"> <img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="50px" style="margin: 5px 5px 5px 5px;"></a> </center> Yesterday marked the conclusion of the third [Osijek camp](https://ocpc.mathos.unios.hr) (also see the [announcement](https://codeforces.me/blog/entry/124573) on Codeforces). Similar to the last time, the camp was organized by Tähvend Uustalu ([user:-is-this-fft-,2024-02-26]) and m...

Full text and comments »

Please ban the users who use AI to participate in contests On the Global Round 31, user [user:Su_Zipei,2025-12-19] has just used AI to make it to the top 20 of the contest. Indeed, a smart contestant would not use overtly suspicious AI-generated code; those grey participants who rapidly solve the first six or seven problems in a competition can easily be identified as having used AI. A better approach is to obfuscate and polish the code provided by AI, or even rewrite it based on the AI's logic——for contestants with enough coding experience, this is quite straightforward. Clearly, compared to a 1200-rated player using AI to reach 1800, a 2400-rated player finds it easier to use AI to reach 3000. Still, we can find some evidence that is not so convincing. For those people who solve problem H1 fast enough, Kevin114514 uses 36 minutes, tourist uses 42 minutes, ecnerwala uses 32 minutes, while other pariticipants solves it even longer(~1h). However, Su_Zipei only solve it in 19 minutes, which is really, really fast. Another issue that req...

Full text and comments »

[Tutorial] Fully Dynamic Trees Supporting Path/Subtree Aggregates and Lazy Path/Subtree Updates Hey everyone! Usually when I post stuff on CF I just drop an external link to my blog, but this time I would like to also paste the same content natively on CF to see if it leads to more engagement. You can read the exact same article on my blog [here](https://mzhang2021.github.io/cp-blog/ds5/). Also, special thanks to [user:alien_lover,2022-06-10] and [user:gabrielwu,2022-06-10] for proofreading. --- ## Motivation We will solve **[this problem](https://dmoj.ca/problem/ds5)**. ## Prologue The original name of this problem is [SONE1](https://darkbzoj.cc/problem/3153), originating from the fiery depths of Chinese OI. Amazingly, the Chinese have figured out how to augment the link/cut tree to solve this problem (ref [1](https://www.cnblogs.com/clrs97/p/4403244.html), [2](https://blog.csdn.net/iamzky/article/details/43494481)). Maintaining subtree aggregates with a LCT isn't difficult, and there's a well-known [Codeforces article](https://codeforces.me/blog/entry/67637) ...

Full text and comments »

Kapun's algorithm I'd like to share this one unpopular but awesome algorithm that I only heard a mention of once. Kapun's algorithm finds a hash collision for moduli as large as $10^{18}$. I know, we have *lots* of algorithms that do much better than that (and I'm writing an article on that at the moment, keep tuned), but Kapun's algorithm is really surprising in its simplicity. That its correctness is so difficult to prove is of more surprise even. Here we go. A polynomial hash of a string $s$ is defined as $$ H(s) = s_0 b^0 + s_1 b^1 + s_2 b^2 + \dots + s_{n-1} b^{n-1} \pmod M. $$ We want to find two strings with the same polynomial hash using only two characters: $0$ and $1$. We can reformulate this problem in another way. Let $a_i = b^i \mod M$, then we want to find two distinct subsets of $a$ with the same sum modulo $M$. Now *forget about the modulus*: let's just find two subsets with the same sum. Firstly, when is this possible? There are $2^n$ possible subsets and $n(M - 1) -...

Full text and comments »

Osijek Competitive Programming Camp 2023 fall — wrap Hi everyone! <center><a href="https://ocpc.mathos.unios.hr"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a></center> <center> <b>Supported by</b><br> <a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london"> <img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="50px" style="margin: 5px 5px 5px 5px;"></a> <a href="https://icpc.foundation/"><img src="https://ocpc.mathos.unios.hr/images/ICPC.svg" height="70px" style="margin: 5px 5px 5px 5px;"></a> <a href="https://pinely.com/"> <img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="50px" style="margin: 5px 5px 5px 5px;"></a><br> <a href="https://artofproblemsolving.com/"><img src="https://ocpc.mathos.unios.hr/images/aops.svg" height="40px" style="margin: 5px 5px 5px 5px;"></a> <a href="https://www.wolfram.com/"> <img src="https://ocpc.mathos.unios.hr/images/wolfram.png" height="40...

Full text and comments »

Educational Codeforces Round 91 [Rated for Div. 2] Hello Codeforces! On [contest_time:1380] [contest:1380] will start. Series of Educational Rounds continue being held as [Harbour.Space University](https://harbour.space/) initiative! You can read the details about the cooperation between [Harbour.Space University](https://harbour.space/) and Codeforces in the <a href="http://codeforces.me/blog/entry/51208">blog post</a>. This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally. You will be given **6 or 7 problems** and **2 hours** to solve them. The problems were invented and prepared by Roman [user:Roms,2020-07-11] Glazov, Adilbek [user:adedalic,2020-07-11] Dalabaev, Vladimir [user:vovuh,2020-07-11] Petrov, Ivan [us...

Full text and comments »

Interesting Information-Theoretical Problem Recently, there was a local contest which I set a problem for (task 4 in [this pdf](https://drive.google.com/file/d/1-HvrkdEdsZFFiLmtKNUqEidtXAhyPfZO/view?usp=sharing)). The abridged problem statement is that you choose an array $A$ of length $N$ where the elements are $<2^X$. The grader will pick $[L,R]$ and return $A_L \oplus A_{L+1} \oplus \ldots \oplus A_R$, where $\oplus$ is the bitwise xor operation. You need to find **any** integer $z$ such that $L \leq z \leq R$. I set this in contest with the constraints of $N=2^{19}$ and $X=192 \approx \frac{(\log N)^2}{2}$ where you also had to answer queries quickly. <spoiler summary="Solution"> The main idea of my solution is to keep splitting the query range in half. Suppose we know that $l \leq L \leq R \leq r$. Let $m=\frac{l+r}{2}$. Then there are $3$ cases: 1. answer $m$ 2. recurse to $[l,m)$ 3. recurse to $(m,r]$ Let us put a bit on position $m$. If that bit is activated, then it is case 1. Otherwise, we need ...

Full text and comments »

Codeforces Beta Round #35 (Div. 2) и Codeforces Beta Round #36 <p> Всем доброго времени суток. </p> <p> Сегодня на Codeforces необычный день: сразу два раунда, днем, да еще со столь небольшим перерывом. А объясняется это тем, что сегодня в Саратове проходит IX Региональная командная олимпиада школьников по программированию, и задачи с нее (а они весьма неплохие) решено было дать на раунды Codeforces. </p> <p> По этой причине авторов у сегодняшних задач много. Не поленюсь перечислить весь состав жюри олимпиады, все члены которого хорошо знакомы вам как авторы задач на Codeforces. Это <font color="#0000ff"><u><a href="http://codeforces.me/profile/RAD">Артем Рахов</a></u></font>, <font color="#0000ff"><u><a href="http://codeforces.me/profile/NALP">Николай Кузнецов</a></u></font>, <font color="#0000ff"><u><a href="http://codeforces.me/profile/natalia">Наталья Бондаренко</a></u></font>, <font color="#0000ff"><u><a href="http://codeforces.me/profile/Gerald">Геральд Агапов</a></u></font>,<font color="#0000ff...

Full text and comments »

Codeforces Round #983 (Div. 2) ### Hello Codeforces! $\newline$ <spoiler summary="From AkiLotus"> > "<span style="color: red">K</span>aleidoscopic, this place still is. How long have I been away...?" Hi. Akik<span style="color: red">a</span>ze a.k.a. AkiLotus here. Four years have passed, lo<span style="color: red">n</span>g enou<span style="color: red">g</span>h huh? I h<span style="color: red">o</span>pe that after all these times, I am not too rusty to set good tas<span style="color: red">k</span>s for yo<span style="color: red">u</span> to enjoy, starting with <span style="color: red">t</span>his <span style="color: red">o</span>ne! <strong>See yo<span style="color: red">u</span> in the round!</strong> <span style="color: #ec3e9d"><i>"Waeeguyehy" is coming soon.</i></span> </spoiler> It's been a while, today [user:AkiLotus,2024-07-29] and I are delighted to invite you to participate in [contest:2032]. This round will be <strong>rated</strong> for all participants with a rating lower than <...

Full text and comments »

I started solving Project Euler [user:Radewoosh,2024-01-12] inspired me by [completing](https://codeforces.me/blog/entry/122793) Project Euler, and I recently [started](https://projecteuler.net/progress=ivanovmp), slow but steady, solving its problems. I don't mind anybody adding me as a friend on Project Euler, my friendship key is `2127163_HmDkRoxUDZa38znoBSPq2n4Prg996WEX`, please enter it on [this page](https://projecteuler.net/friends) if you're registered and you'd like to see me in your friend list. (Similarly, you'll appear in my friend list.) I also record the process and upload on Youtube because, according to the [rules](https://projecteuler.net/about), problems 1–100 are allowed for public analysis (although I'm afraid there won't be any serious or interesting problems in the first hundred). As for now, uploaded are: * [problems 1–3](https://youtu.be/k2rRnfDxDME); * [problems 4–12](https://youtu.be/oQ0AXSwlVog); * [problems 13–24](https://youtu.be/aOBgin-XGkQ); * [problems 25–36](https://youtu.be...

Full text and comments »

Top228 of comments with too negative feedback At one warm winter day I've said to my mother, that I'm going to drink with my friends, but I fooled her: actually I decided to go to a gym. Unfortunately it was closed. I was so sad about it and didn't know what to do: I couldn't return home, because if my mother only knew that I spend my time doing sports she would never give money for buying Jaguar! That's why I went to the nearest padik, turned on russian rap on my mobile phone and started to read some fresh blogs on Codeforces. It was such attractive occupation that I walked to blog of [user:Amir.bh,2015-01-25] with top100 best comments in English. I was greatly inspired by it and I found that this idea is not fully realized. So, it leads me to take one more cup of yazhka. And after that I made this rate. Top 228 comments with negative feedback: <b>1</b>: -600 [user:kursatbakis0,2015-01-24] http://codeforces.me/blog/entry/13997#comment-189443 <b>2</b>: -271 [user:Makkar,2015-01-24] http://codeforces.me/blog/entry/9907...

Full text and comments »

Welcome to Bingo-CP Hello Codeforces! Are you tired of only doing virtual contests? Want a more fun way to compete with friends, alone or on a team? Try Bingo-CP. ### What is Bingo-CP? Bingo-CP is a free web app that turns Codeforces practice into a quick social game. Problems are placed on an n×n bingo board. Teams of 1–4 players compete at the same time. The first team to complete any row, column, or diagonal wins. Try it: https://bingo-cp.vercel.app/home ### How to play **1.** Click "Create Match" as in the picture. **2.** Choose grid size (3×3 to 6×6), start time, duration, rating range, and mode. **3.** Add team members by Codeforces handle (1–4 each). **4.** Start the match. All teams solve at once. The first accepted submission claims the square for the team. **5.** First team to complete a row, column, or diagonal wins. Solves are detected automatically from Codeforces submissions, so no one needs to claim squares manually. ### Match options Start time and du...

Full text and comments »

Analysis of polynomial hashing Unfortunately, most derivations of the chance of polynomial hashing collision are invalid, wrong, or misleading, and finding reliable public sources with proofs is incredibly difficult. This article is a formal analysis of the method. The goal of this article is to complement well-known empirical facts with theory, provide boundaries on the probability of collision, justify common choices, and advise against certain popular parameters. There is no code in this article, and it's mostly theoretical. It's more of a summa of everything we know about polynomial hashing in integers rather than a guide for beginners. You'll probably find something of interest still. I do, however, describe some methods of cracking hashes, which I can provide code and additional explanation for if someone asks in the comments and some general guidelines in the last section of the present article. ## Table of contents - The concept of polynomial hashing - Classical justification of the coprimality r...

Full text and comments »

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 »

A Step-by-step Guide to Configure Topcoder Competitive Environment <h3><b>Step 1: Get a Topcoder account if you don't already have one.</b></h3> Address: http://www.topcoder.com/talent/ <img alt=" " src="/predownloaded/3d/4b/3d4b2c0adc4d14af81a96fd61ca41e5836a5e1fb.png" style="max-width: 100.0%;max-height: 100.0%;" /></p> Click on the "JOIN TOPCODER" button, and fill in the form to register. <img alt=" " src="/predownloaded/00/7f/007f49a53c95b30b66ba6bdd76453256665b35cb.png " style="max-width: 100.0%;max-height: 100.0%;" /></p> <h3><b>Step 2: Download and install Java Runtime Environment.</b></h3> Address: https://www.java.com/en/download/manual.jsp <h3><b>Step 3: Download the topcoder applet.</b></h3> Address: https://www.topcoder.com/contest/arena/ContestAppletProd.jnlp I strongly recommend you to put the above jnlp into the same folder of executable file "javaws" (Java Web Start Luncher). <img alt=" " src="/predownloaded/65/c4/65c4d4e5471e3ca6f9ca812f946f885cf2a35815.png" style="max-width: 100.0%;max-height: 100.0%;" ...

Full text and comments »

It is true that we are having fewer rated contests... _The story_: Five days since the last round and waiting for the next one makes me want to do something, and seeing posts a few days ago on "no upcoming contests", I somehow wanted to see if we really are having fewer contests. Below are the findings&#x2757; The data counts for all contests with a `div. [#]` included in their names and all global rounds. In specific, I counted their divisions, date, and participant number, and then visualized the data into two types of graphs: 1. Frequency count of rated contests by divisions, based on their month and year. 2. Average number of participants for a division in each month of year. #### Overall distribution <p align="center"> <img src="https://i.ibb.co/Dw7n8Ty/Screenshot-2024-10-04-at-17-13-44.png" alt="Image"> </p> There seems to be no clear trends of frequencies within a year (e.g., I was expecting there will be more during summer holidays), however, there is a faint decline in contests over the past two years &#x...

Full text and comments »

Invitation to TheForces Round #36 (Starters-Forces, TheForces Rated, Prizes!) Hello, Codeforces! <img src="https://s8.uupload.ir/files/9c2ddb60-6104-481a-92f9-964506ba27b2_w6xi.png" style="width: 600px; height: 600px;" alt="图片描述" /> We are happy to invite you to [**TheForces Round #36 (Starters-Forces)**](https://codeforces.me/contestInvitation/1b713966aec95ad27894354018c3c3523aef7fbb), which will take place on **[contest_time:105445]** <spoiler summary="What is TheForces Round?"> TheForces is a project uniting individuals with a shared interest in competitive programming contests. You can join our discord server with more than $2500$ members to communicate with founders and members of TheForces. In the other words TheForces rounds are series of educational contests for beginners to masters which are created by a group of CP lovers in the CF community, It's where anyone can propose and prepare his own interesting problems and receive money! Not to mention that we've already created **two** official codeforces Div($1 + 2$) rounds before ;) So...

Full text and comments »

Every Technique and Algorithm I Used to Become Grandmaster Hi everyone, I became grandmaster today so I decided to go down memory lane and review every problem I have ever done in a CodeForces contest to look back and see every technique and algorithm I had to use to become a grandmaster. I am not sure how useful this is, I mostly think it's fun to look at all the old solutions I wrote and how different it was from how I write code now. The main takeaway is that, as many people have said before, you don't need to know or memorize a bunch of advanced algorithms to become grandmaster. As you will see, there are many problems where I just used "ad hoc reasoning," meaning there's not a standard technique I used to solve the problem and you just need to make some clever mathematical observations to solve the problem. Also, there are many popular algorithms that I have never needed in a CodeForces contest despite being a grandmaster: - Sparse tables, Fenwick trees, and segment trees - String algos, like rolling hashes, Knuth-Morris-Pratt, suffix...

Full text and comments »

How not to read problem statements I wanted to write super-harsh blog but then I decided to split it into educational part and whining part. This is whining part. To read some cool stuff go [here](https://codeforces.me/blog/entry/62730). This one will also be educational on a slightly different topic. And there will be A LOT of harsh stuff. I'm not saying that I'm perfect. That round had some really bad problemsetting issues. Problem E was googleable, problem D had very weak tests against very stupid solution (so stupid that none of the authors and testers come up with it, moreover, it is so counter-intuitive that I don't know how so many people independently did it). In two constructive problems participants could look at jury's output, the feature of which I didn't know. And I'm sorry for these issues. BUT. [This comment](https://codeforces.me/blog/entry/62614#comment-466588) has very negative rating despite being so true. And no one are here to back me up. So I want to speak my truth as I always do. Let me ac...

Full text and comments »

Codeforces Trainings Season 1 Episode 10: Editorial #### **Welcome to The Editorial!** <img src="http://th04.deviantart.net/fs70/PRE/f/2013/078/b/f/mi_super_saiyan_god_remasterizado_by_salvamakoto-d5ymxyi.png" height="50%" width="50%" /> **Keep the upvotes piling up! muhehe** IZ.COMPLETE. ### A. Rasheda And The Zeriba [cut] $\ $ (difficulty: medium) The first question is: When is it possible to construct a (convex) polygon from sticks of given lengths $L_i$? This question is answered by what's sometimes known as Polygon inequality theorem, which states that the sufficient and necessary condition is for every $L_i$ to be strictly less than the sum of all other $L_i$. You can imagine that it works because for the endpoints of every side, the shortest path between them (equal to the length of that side) must be smaller than any other path, including the other one along the perimeter of the polygon; constructing such a polygon, even a convex one, is pretty easy, just imagine it as having sticks linked to each other that...

Full text and comments »

MathMash — Round 36 Hello Codeforces! I'm glad to announce that we will be having [**Round $36$**](https://www.mathmash.org/contest.php?id=36) of [**MathMash**](https://www.mathmash.org/) today at [**$17:00$ UTC**](https://www.timeanddate.com/worldclock/fixedtime.html?msg=MathMash%20-%20Round%2036&day=16&month=10&year=2018&hour=17&min=00&sec=00). The round has been prepared by [**Snpushpita**](https://www.mathmash.org/profile.php?user=Snpushpita) and [user:DrSwad,2018-10-15]. The round will consist of $8$ problems, to be solved within $2$ hours. Points distribution for the problems are decided as `500-750-1250-1500-1750-2250-2500-2500` We're inviting you all to join us in the contest. Hopefully we'll have a fun and successful round. <hr> A few details about the contest: - In order to participate in the contest, you need to register first. Kindly follow [**this link**](https://www.mathmash.org/contests.php) to do so. Registration deadline has been removed from the contests. So now, you...

Full text and comments »

Разбор VK Cup 2015 — Finals Всем спасибо за участие! Задачи следуют в порядке, в котором они шли на оригинальном соревновании. [problem:562A] -------------- (в трансляции: [problem:566C]) Формализуем задачу. Нам дано необычное определение расстояния по дереву: $\rho(a, b) = dist(a, b)^{1.5}$. У каждой вершины есть её вес $w_i$. Нужно как-то так выбрать место $x$ для проведения соревнования, чтобы минимизировать сумму взвешенных расстояний от всех вершин до неё: $f(x) = w_1 \rho(1, x) + w_2 \rho(x, 2) + \ldots + w_n \rho(x, n)$. Давайте изучим свойства функции $f(x)$. Мысленно разрешим себе ставить точку $x$ не только в вершины дерева, но и в любую точку на ребре, доопределив естественным образом расстояние от точки внутри ребра до всех остальных вершин (например, середина ребра длины $4$ находится на обычном расстоянии $2$ от концов ребра). **Утверждение 1**. На любом пути $x \in [a, b]$ в дереве функция $\rho(i, x)$ является выпуклой вниз. Действительно, функция $dist(i, x)$ на любом пути выгляд...

Full text and comments »

Inconsistent times and TLE with C++17 (64bit) vs. C++17 Hi, while submitting [problem:1535F] for the previous educational round I did observe a strange behaviour. I submitted the **absolutely same** code several times:  As you can see, submitting with **C++17** was AC every single time. Submitting with **C++17 (64bit)** lead to timeouts on different testcases, like 18, 27 or 32 but also to several AC with all testcases 18,27,32 only needing <300ms in 64bit. I read my code about 20 times now checking for out of bounds errors or stupid mistakes. I have no random numbers generated. I also did several tests by generating a big number of random testcases with both 64bit and 32bit locally, but I couldn't reproduce this behaviour. I got consistent times all around. Now I'm clueless and want to ask whether someone has an idea why this happens. - AC 32bit: [submission:118502792] - AC 64bit: [submission:118503021] - TLE Testcase 18 64bit: [submission:118502885]...

Full text and comments »

Codeforces Round 1025 (Div. 2) Editorial Thank you for your participation! We hope you enjoyed the problems! We would love to hear your feedback! Please share your thoughts in the comments. <br> <spoiler summary="How did you find the contest?"> - Great: - Good: - Average: - Bad: - Trash: </spoiler> <spoiler summary="Which problem was your favorite?"> - A: - B: - C1: - C2: - C3: - D: - E: - F: </spoiler> <spoiler summary="Which problem did you find the least enjoyable?"> - A: - B: - C1: - C2: - C3: - D: - E: - F: </spoiler> <br> [problem:2109A] Idea by [user:MOUFLESS,2025-05-17], prepared by [user:MO...

Full text and comments »

Ukrainian Teams on IOI and BOI From 10th to 16th May, Ukrainian Selection Camp for the IOI (International Olympiad in Informatics), BOI (Balkan Olympiad in Informatics) was held in Wrocław, Poland. Thanks to University of Wrocław and [user:gawry,2024-05-21] for the second time for help in organising the selections! We are very grateful to Sergey Kolodyazhnyy for creating powerful online judge [Eolymp](https://eolymp.com/en). Also, I would like to thank [user:oleh1421,2024-05-21] and [user:kostia244,2024-05-21] for preparing amazing problems. Maryna, Ilona and [user:Melissa_14,2021-12-21] for looking after the participants and Federation of Olympic Programming of Ukraine presented by [user:arsijo,2024-05-21] for coordinating the entire process. So, on **IOI** Ukrainian Team will be represented by: - Andrii Smutchak([user:xGaz_,2024-05-19]) — 2nd time at IOI(IOI 23 Silver), 0 attempts left - Ihnat Zharikhin([user:Ignut,2023-11-08]) — 1st time at IOI, 0 attempts left - Denys Tereshchenko([user:TheQuant...

Full text and comments »

Yandex.Algorithm Finals Hello from Berlin! Get ready for some action as participants are ready to battle for Grand Prize of 300000 russian roubles and coveted title of Yandex.Algorithm champion Stay tuned for live commentaries If you have any questions about the competition feel free to ask. Competition starts at 11:30 CET, about an hour from now. Currently participants set up their PCs -0:33 &mdash; We have quite tough field this year including ACM ICPC World Champions, TCO, GCJ and IOI winners. ~snarknews,2014-08-01 had provided some info on finalists [here](http://yandex2014.snarknews.info/index.cgi?data=yandex/2014/finalists&year=2014&contest=yandex&class=yandex2014) -0:10 &mdash; Contest is delayed for 10 minutes -0:09 &mdash; You can follow live results [here](http://contest.yandex.ru/contest/507/standings/) -0:05 &mdash; Currently contest area is filled with several journalists and cameramen 0:01 &mdash; Contest had been started, participants reading problems atm 0:11 &mdash;...

Full text and comments »

Improvement of the functionality of test scripts in Polygon Good night/dawn/morning/day/dusk/evening/night, Codeforces! Today I am glad to present you the latest features of the [Polygon](https://polygon.codeforces.com/) &mdash; the system for creation and preparation of programming problems and contests. All Codeforces Rounds are made using Polygon. New features are concentrated around test script.  #### Part one. Test autonumeration The first new feature allows you to automatically numerate tests. Instead of this ~~~~~ gen_n 5 10 1 > 57 gen_n 5 10 2 > 58 gen_n 5 10 3 > 59 gen_n 5 10 4 > 60 gen_n 5 10 5 > 61 ~~~~~ you can now write this ~~~~~ gen_n 5 10 1 > $ gen_n 5 10 2 > $ gen_n 5 10 3 > $ gen_n 5 10 4 > $ gen_n 5 10 5 > $ ~~~~~ Dollar sign, used to mark autonumeration, stands for the first unused test index. So, for example: ~~~~~ gen 1 > $ gen 2 > $ gen 4 > $ gen 5 > $ gen 3 > 3 ~~~~~ will be translated to...

Full text and comments »

[Tutorial] Everything about unordered_map **UPD:** Tricks to make `unordered_map` faster added. Hi! ##### What is `unordered_map`? It is a data structure like `map` but it is more than 4 times faster than `map`.you can use it in C++11 with including `#include<unordered_map>`.for example: ~~~~~ #include<unordered_map> using namespace std; int main(){ unordered_map<int,int>mp; mp[5]=12; mp[4]=14; cout<<mp[5]<<' '<<mp[4]<<endl;//prints: 12 14 } ~~~~~ Lets explain it more. ##### How it works? Focus on `unordered_set` for simplify.You can imagine that it has vector of vector like `vector<vector<type> > mp`. Every time you insert value `V` in that, it calculate its `hash`(I will explain how it works), let `hash(V)=K`; it inserts `V` into `mp[K]` (formally it calls `mp[K].push_back(V)`).When you call `mp.count(V)` it searchs for `V` in `mp[K]`. ##### `map` VS `unordered_map` (and `set` VS `unordered_set`) **1-`unordered_map` is more than 4 times faster** Focus on problem [problem:527E], ...

Full text and comments »

Codeforces Round #660 Editorial [problem:1388A] Idea: [user:Denisov,2020-07-30] <spoiler summary="Tutorial"> [tutorial:1388A] </spoiler> <spoiler summary="Solution (Karavaev1101)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int q; cin >> q; while(q--){ int n; cin >> n; if(n <= 30){ cout << "NO" << endl; } else{ cout << "YES" << endl; if(n == 36 || n == 40 || n == 44){ cout << 6 << ' ' << 10 << ' ' << 15 << ' ' << n - 31 << endl; } else{ cout << 6 << ' ' << 10 << ' ' << 14 << ' ' << n - 30 << endl; } } } } ~~~~~ </spoiler> [problem:1388B] Idea: [user:Karavaev1101,2020-07-30] <spoiler summary="Tutorial"> [tutorial:1388B] </spoiler> <spoiler summary="Solution (Karavaev1101)"> ~~~~~ #include <bit...

Full text and comments »

Issue with checker in ER189E Unfortunately, I have found out that the checker for problem E of Codeforces Educational Round 189 did not correctly verify the case when a circle does not cover any points. I am very sorry for this issue &mdash; I was not the person writing that checker, but proofreading it and fixing all of the bugs is my responsibility as the coordinator of the round, and I failed. After discussing the issue with authors and analyzing the submissions, I have decided that dropping the constraint from the statement altogether, without any changes to verdicts during the round is the best course of action: **the amount of changes in the scoreboard, compared to the situation if checker were working correctly, is negligible (perhaps even zero)**. <spoiler summary="My reasoning for this"> There are two categories of people which might get affected by this decision: - people who have got Accepted without satisfying this condition. I believe (and this is corroborated by 10 random solutions I checke...

Full text and comments »

[Feature request] Past locations and organizations in user social settings Codeforces allows users to choose their locations and organizations in "Social" tab in profile settings.  If configured, this information is shown in user profile to everyone and also includes user into filtered rating list of selected country, city and organization. This is a nice functionality, but I've always felt that this is incomplete. People tend to change locations and organizations over time, but currently there can be only one location and only one organizaton. But which one to choose? There are multiple options that seem reasonable - Your current location/organization - Location/organization/team where you had peak performance - Your alma mater - Your origin/place of birth From what I've seen different people resolve this ambiguity in different ways. This has it's impact on filtered rating lists. You will see a person in organization in these cases: - Active user who is currently in ...

Full text and comments »

yet another CP extension for VSCode hello all -- if you happen to be in the market for a new competitive programming extension and use VSCode, may i humbly suggest my new [extension](https://purduecpu.com/extension)? i think it is relatively feature complete, but it's still in alpha (especially for languages other than C++) and may have some kinks that need working out. it theoretically supports C++, Java, Python, and Rust (and it's very easy to add more). i created this because i was dissatisfied that most existing solutions can't import a bunch of test cases from a directory then run them in parallel. i also believe it has a cooler UI than other extensions. as usual, i didn't think it would take this long when i started... if you encounter any difficulties, please let me know on [github](https://github.com/canislupaster/cpu-vscode). **thanks for taking a look!**  ### Realtime Input/Output unlike other test runners for VSCode, w...

Full text and comments »

Yandex Cup 2024! Hello Codeforces!
 ------------ We are delighted to invite you to participate in Yandex Cup 2024!
Yandex Cup is a championship in six different tracks: - [Algorithm](https://yandex.com/cup/algorithm/)❤️ - [Backend](https://yandex.com/cup/backend/) - [Analytics](https://yandex.com/cup/analytics/) - [Mobile development](https://yandex.com/cup/mobile/) (iOS and Android tracks) - [Frontend](https://yandex.com/cup/frontend/) - [Machine Learning](https://yandex.com/cup/ml/) (Self-Driving Cars and Music information retrieval tracks) This year, as a pilot project, we are inviting schoolchildren (so far only from Russia) to participate in the Algorithm and Analytics tracks.
 The championship consists of three stages. Schedule ------------  The stages and dates are different for Machine Learning and Mobile Development. More details about the terms and conditions can be found on the track's pages. ...

Full text and comments »

Codeforces Round 921 (Div. 1, Div. 2) Editorial I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that we can improve upon them the next time. #### [2A. We Got Everything Covered!](https://codeforces.me/contest/1925/problem/A) Author: [user:JaySharma1048576,2024-01-27] <spoiler summary="Hint 1"> The smallest length for such a string is $n\cdot k$. </spoiler> <spoiler summary="Tutorial"> The smallest length possible for such a string is $n\cdot k$. <spoiler summary="Why?"> To have the string $\texttt{aaa}\ldots\texttt{a}$ as a subsequence, you need to have at least $n$ characters in the string as $\texttt{a}$. Similarly for all $k$ different characters. So, that gives a total length of at least $n\cdot k$. </spoiler> In fact, it is always possible to construct a string of length $n\cdot k$ that satisfies this property. One such string is $(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)\ldots n$ times where $a_i$ is the $i^{th}$ letter of English alph...

Full text and comments »

on minimizing the expected number of recursive calls for segment tree For the longest time, this comment https://codeforces.me/blog/entry/112755#comment-1004966 was bugging me (the part about how the 'complete' segment tree is 20% slower (complete, because it’s a complete binary tree)). Instead of benchmarking, this blog calculates the expected number of recursive calls visited between segment tree implementations. Thanks to [user:camc,2025-03-03] for giving valuable feedback. This blog will study 2 implementations of segment trees. <spoiler summary="'standard' segment tree"> ~~~~~ void dfs(int v, int l, int r) { // [l, r) if (r - l == 1) { return; } int m = (l + r + 1) / 2; dfs(2 * v, l, m); dfs(2 * v + 1, m, r); } // dfs(1, 0, n); ~~~~~ </spoiler> And <spoiler summary="'complete' segment tree"> ~~~~~ int split(int l, int r) { int pw2 = 1 << __lg(r - l); return min(l + pw2, r - pw2 / 2); } void dfs(int v, int l, int r) { // [l, r) if (r - l == 1) { return; } int m = split(l, r); dfs(2 ...

Full text and comments »

IOI 2025 China Team Selection — Current Standings Hi, everyone. The first stage of the IOI 2025 China Team Selection began yesterday. The top 50 participants from the 2024 National Olympiad in Informatics (NOI) will compete for a spot on the Chinese national team for IOI 2025. The rule of selecting CHN team this year: + Homework (10%): also known as mutual tests, where the students were asked to prepare a task (5%), and participate in the contests made by other students (5%) + First stage (<b>CTT</b>; 54%; Dec 3, 2024 &mdash; Dec 5, 2024): three contests in classic olympiad format, where each contest worthes 18% of the score. Top 30 participants will advance to the final stage. + Final stage (<b>CTS</b>; 36%; Jan 20, 2025 &mdash; Jan 22, 2025): two contests in classic olympiad format, where each contest worthes 18% of the score. The current scoreboard can be found [here](https://docs.google.com/spreadsheets/d/11Sh6zczubJ9eJxgSkyBcDL_EaZhHuwbyyZNlkLx1Avc). Past problems of the China IOI Team Selections can be found her...

Full text and comments »

Advice needed (this is more of a vent post but if i'll read any suggestions in the comments) For the last 6 months, I felt like I've had some horrendous luck/consistency with my contests: - [contest:2124]: Misread [problem:2124E], lost a ton of time. **(-63)** - [contest:2129]: Decent contest, could be more optimized but overall it's not bad. **(+40)** - [contest:2127]: Absolute disaster, somehow managed to save myself by still clearing 5 problems. **(-71)** - [contest:2135]: Good contest, no catastrophic errors. **(+78)** - [contest:2147]: [problem:2147C] costed me a lot of time and 4 penalties. **(-47)** - [contest:2152]: Got lucky with [problem:2152F], [problem:2152E] was a bit slower than what I wanted. **(+60)** - [contest:2159]: Misread a condition in [problem:2159C] ($a_i \le n$ instead of $a_i \le 10^{9}$), dropped around 110 places from that. **(+4)** - [contest:2161]: Lost an unreasonably absurd amount of time on implementing [problem:2161E]. **(+5)** - [conte...

Full text and comments »

[Tutorial] Quick start in solving problems on GPU + CPU Hello, codeforces! Do you have modern GPU and CPU and want to calculate something with them, but you don't know how to do it? Dont be upset, because you can read this blog and run your first GPU program on your AMD/Intel/NVIDIA GPU. I will describe an installation process and then we will dive into the C++ code. As an example, we will calculate a lot of mazes for [Bug Game](https://codeforces.me/blog/entry/115144) in parallel. For doing this in simple way, we will use library [Boost.Compute](https://www.boost.org/doc/libs/1_80_0/libs/compute/doc/html/index.html), which is a C++ STL-style wrapper over OpenCL library. [cut] ... Installation for MacOS (Apple M1 Pro) ================== As [user:Gosunov,2023-06-10] said, `OpenCL` and `g++` are pre-installed on `MacOS`. Everything that you have to do is install `Boost` with command `brew install boost`. After this you will be able to compile your program with command `g++ -std=c++17 -O3 -I/opt/homebrew/Cellar/boost/1.81.0_1/...

Full text and comments »

Разбор Codeforces Round 990 (Div. 2 + Div. 1) ### Div2A Alyona is happy when there are no unfinished layers &mdash; that is, in front of her is a perfect square with odd side length. Since the order of pieces is fixed, it is enough to keep track of the total current size $s$ of the puzzle, and after each day check, if the $s$ is a perfect square of an odd number. The easiest way to do that is to create an additional array containing $1^2, 3^2, 5^3, ..., 99^2$, and check after each day, whether $s$ is in this array. <spoiler summary="Code"> ~~~~~ NT = int(input()) sqs = set() k = 1 while k * k <= 100 * 1000: sqs.add(k * k) k += 2 for T in range(NT): n = int(input()) a = list(map(int, input().split())) answer = 0 cursum = 0 for t in a: cursum += t if cursum in sqs: answer += 1 print(answer) ~~~~~ </spoiler> ### Div2B Find the character which appears the lowest number of times &mdash; if tied, take the earlier character in the alphabet. Find the character which appears the highe...

Full text and comments »

The most outrageous cheating in the history of Huawei Challenge  I am writing this because I believe that prohibited collaboration occurred during this Challenge and affected the prize positions. To state my personal conclusion plainly: I believe this is cheating, not merely a collection of innocent coincidences. The final positions relevant to the accounts discussed in this post were: | Rank | Handle | Final score | Result of my public-data review | |---:|---|---:|---| | 2 | [user:IceKylin,2026-08-28] | 16808.628 | Historical team with [user:candy0014,2026-08-28] named “IceKylin 0339 team”; all-time runtime/score leads with [user:candy0014,2026-08-28] and [user:Retired_Zhisheng,2026-08-28] | | 3 | [user:mahiro_zcy,2026-08-28] | 16757.390 | Repeated all-time runtime/score correlation with [user:mojo__hugo,2026-08-28]; repeated timing correlation with [user:Zinc-acetate,2026-08-28]; weak close event with [user:Mango2011,2026-08-28] | | 4 | [user:Zinc-acetate,2026-08-...

Full text and comments »

IOI 2017, первый тур <center><a style="font-size:20pt;" href="http://scoreboard.ioi2017.org/Ranking.html">Таблица результатов</a></center> <spoiler summary="Краткий обзор задач"> [Nowruz](http://jonathanirvin.gs/files/ioi2017/day1/nowruz-ISC.pdf) &mdash; это первая со времён канадского maze в 2010 году задача на IOI с открытыми тестами. Забавный факт состоит в том, что nowruz, как и maze, это задача про клетчатый лабиринт. Дано клетчатое поле, в котором некоторые клетки свободны, и нужно оставить от них связное подмножество клеток, образующее дерево (в том смысле, что от любой клетки до любой есть единственный путь). Требуется максимизировать количество листов в получившемся дереве. Оценка линейно зависит от количества листов, при этом в тесте дано, сколько умеет жюри, и результат жюри считается за полный балл на тесте. Говорят, оптимизационная задача, в которой есть много разных подходов, по ощущениям приятнее того же канадского maze. [Wiring](http://jonathanirvin.gs/files/ioi2017/day1/wiring-ISC.p...

Full text and comments »

BOI 2022  This weekend, the **Baltic Olympiad in Informatics 2022** (BOI 2022) is going to take place! BOI is a programming contest for secondary school students from countries around or close to the Baltic sea. This year, around 70 contestants from Denmark, Estonia, Finland, Germany, Iceland, Latvia, Lithuania, Norway, Poland, Sweden and our guest countries Israel and Ukraine will compete against each other, solving difficult problems of algorithmic nature. Each participating country sends 6 contestants from their national olympiads which take place in the months beforehand. The contest consists of two days, Saturday and Sunday, on each of which the contestants have 5 hours to solve 3 problems of varying difficulty. Each problem is worth 100 points that are distributed into multiple subtasks with different constraints that allow the participants to earn partial scores. During the contest, each participant receives the...

Full text and comments »

Surprise Language Round #7: editorial #### [problem:470A] As usual, the first problem tests competitors' ability to do basic math, and in this case it is even easier than the sample &mdash; without any loops. <pre>^'0- &#36 1+*3*1+.</pre> #### [problem:470B] This problem uses more advanced language concepts &mdash; loop, conditional execution and even named variables! Variables are convenient to use as loop counters and result accumulators, so as to avoid stack manipulations for the same purpose. [cut] An if-then-else in FALSE looks like this: <pre>(true/false condition on top of stack) &#36; [(then statements)] ? ~ [(else statements)] ?</pre> Solution: <pre>0n: {number of 6s found uninterrupted so far} 0r: {true, if 666 found} [^&#36 1_=~] [ '6= &#36 [n; 1+ n:] ? ~ [0n:] ? n; 2 > r; | r: ] # % r; &#36 ["YES"] ? ~ ["NO"] ?</pre> #### [problem:470C] This problem can be solved in two ways. You could read numbers, store them to named variables and de...

Full text and comments »

Implicit Prime Factorisation Those of us who have been doing cp for a long time, have come to love the representation of numbers as an infinite prime power vector i.e. $$n = \prod p_i^{e_i} = [e_1, e_2, \ldots ] = v_n$$ Where $n$ is a number and $p_i$ is the $i$ th prime number. This has many useful properties for problems, such as mapping $$n \times m \sim v_n + v_m$$ $$n / m \sim v_n - v_m$$ $$n \mid m \sim v_n \le v_m$$ $$\gcd(n, m) \sim \min(v_n, v_m)$$ $$lcm(n, m) \sim \max(v_n, v_m)$$ All the above operations are done elementwise. However in some cases, the problem authors may forbid you from factorising the numbers, by perhaps increasing $n$ to around $10^{36}$ where there isn't any simple factorisation algorithm to do it in reasonable time. However using effective prime factorisation, we can use these properties freely on a set of numbers. If this set contained all integers, then it would require us to truly prime factorise the integer. However, we only need to use these operations on a subset...

Full text and comments »

ICPC NERC Huawei Challenge — Cloud Scheduling Challenge [<img src="/predownloaded/50/6e/506e22d11e9f49d4ad8882c6c1877b5989589e60.png" align="right" style="height: 260px; margin: 10px;" alt="text"/>](https://youtu.be/29_RwCFtHFw) Всем привет! Присоединяйтесь к грандиозному онлайн турниру **ICPC NERC Cloud Scheduling Challenge**, который пройдет при поддержке Huawei на платформе Codeforces с **12 по 20 декабря 2020**! <center style="margin: 1.5em;"> <a href="https://codeforces.me/contests/1460" style="font-size: 15.0px;padding: 8.0px 14.0px;background-color: rgb(226, 36, 14);color: white;">Регистрация</a></center> В течение недели лучшие программисты будут решать задачу, основанную на проблемах облачных систем. С подобной задачей имеют дело разработчики облачного сервиса Huawei Cloud. Участникам предстоит найти оптимальный алгоритм составления расписания для разнообразных операций в облаке, минимизируя одновременно значения двух штрафных функций. Необходимо найти разумный баланс, в зависимости от входных данных. Примеры возможны...

Full text and comments »

TheForces Rounds Editorials Here's the editorials of [TheForces Rounds](https://t.me/TheForcesOfficial): <spoiler summary="Round 1"> <spoiler summary="Problem A"> For a number $x$, as long as $2\le x$, it can be squared to any large number. For $0$ and $1$, the square of both numbers is equal to themselves. So just compare $0$ and $1$. <spoiler summary="Code"> ~~~ void elysia() { cin >> n; bool flag=true; for(int i=1;i<=n;++i) { cin >> a[i]; a[i]=min(a[i],2ll); if(i!=1&&a[i]<a[i-1]) flag=false; } if(flag) cout << "YES" << endl; else cout << "NO" << endl; } ~~~ </spoiler> </spoiler> <spoiler summary="Problem B"> Consider the number of times each $a_i$ is XOR in the answer. for $a_i$, calculated $i(n-i+1)$ times in the answer. Two same XOR will disappear, so checking is this an odd number then done. <spoiler summary="Code"> ~~~ void elysia() { int answer=0; cin >> n; for(int i=1;i<=n;++i) { cin >> a[i]; ...

Full text and comments »

Registration for Volga Summer Camp 2020 is opened We are glad to inform you that **Volga Summer Camp 2020** – open competitive programming camp – will take place on July 7-18. It is organised by NUST MISIS together with P.G. Demidov Yaroslavl State University with the support of SIT (Schaffhausen Institute of Technology). At the moment a lot of events are held in the remote mode and our camp is not an exception. This year it will be conducted online. Teams of up to 3 members are invited to join.  There are two levels of difficulty (two divisions): - DivC welcomes teams, getting ready for the semi-final of ICPC. Half of the time they are going to deal with quarter-final ICPC contests, and the rest of it will be dedicated to private thematic contests. The focus of our lessons will be on coordinate compression, number theory, probability problems, network flow in graph theory. - DivB is for teams aiming directly at ICPC final. All the contests her...

Full text and comments »

Need help with renaming friends into followers/following Hi. Sometimes it seems like all you have to do is change a couple of inscriptions on the site and that's it. But it's not that simple. For example, I decided to change my friends to followers/subscribers. In fact, the relation we have here is more like a following or a subscription than a friendship. But there's a tiny issue. Sometimes this relationship is used in the interface in one direction (we are talking about those who follow us). Then everything is easy in this case, we can mention them as your followers. Sometimes, it's about those you're following. Then a little more difficult. The best thing that I came up with and advised me is the term "following". But replacing "Friends Standings" with "Following Standings" (or "Followings Standings"?) looks so-so. Likewise, what was "Friends Rating Changes" and will it be "Following Rating Changes" (or "Followings Rating Changes")? Looks really clumsy. <img src="/predownloaded/36/47/3647c874b773ccf43da98b960e04f3a12a5b8...

Full text and comments »

Codeforces Round #262 (Div. 2) Editorial [problem:460A] В этой задаче нужно было промоделировать то, что написано в условии. Также можно показать, что ответом является формула $n + \lfloor\frac{n - 1}{m - 1}\rfloor$, где под $\lfloor x \rfloor$ понимается целая часть числа $x$. [submission:7536107] [problem:460B] Заметим, что $S(x)$ может принимать только целые значения и $ 1 \le S(x) \le 81 $. Переберем $S(x)$ от $1$ до $81$, и посчитаем значение выражения $ B*S(x)^{A} + C$. Затем, если сумма цифр полученного числа совпадает с $S(x)$, число положительное и оно меньше $10^9$, то оно является решением. В этой задаче могли возникнуть проблемы из-за использования встроенной в C++ функции pow() [submission:7536153] [problem:460C] Заметим, что ответ положительное число, не превосходящее $10^9+10^5$. Найдем ответ, используя бинарный поиск по ответу. Действительно, мы можем проверять за $O(n)$ можно ли достичь определенной высоты. Для этого идем слева направо. Для текущего цветка посчитаем какое минимальное кол...

Full text and comments »

ALL CodeForces Rounds Tutorial <html> <body> <br /><br /> >>>>>>>**Hi I just Say Really Sorry For Delay in UPD This Blog...!**<br /><br /><br /> <u>This is not Complete</u> , but i try to find <b>all Tutorial codeforces round</b> and posted here , thanks in advance :D <br /><br />This post will <b> <span class="Apple-style-span" style="border-collapse: collapse;color: rgb(255,0,0);font-family: verdana , arial , sans-serif;font-size: 12.0px;"> UPD</span></span></b> after each contest . <span>If anyone have or writes any editorial that's</span> <b> <span> <span class="Apple-style-span" style="border-collapse: collapse;color: rgb(255,0,0);font-family: verdana , arial , sans-serif;font-size: 12.0px;"> not in here</span></span></b> , Plz post here for ALL . <br /><br /><b>UPD </b> &nbsp;: Table1 updated : in Future!!! <br /><br /><b>UPD </b>&nbsp;: Table2 updated : CF # 118 ...to... CF # 169 added .<br /><br /> </p><hr /><br /></p> <div align="justify"> <br /><br /><b><s...

Full text and comments »

Are there any learning materials of polynomial minimum cost flow algorithms? Many people think they know how to solve the min-cost-max-flow problem, but most of them only know how to solve it with pseudo-polynomial time algorithm (although it usually runs very fast). And in [this blog](https://min-25.hatenablog.com/entry/2018/03/19/235802), min_25 provided a counter case generator, most people's MCMF algorithm runs in $O(2^{\frac n 2}n^2\log n)$ on it. <spoiler summary="the counter case"> ``` 42 421 1 2 1 0 1 3 3 0 1 4 5 0 1 5 10 0 1 6 20 0 1 7 40 0 1 8 80 0 1 9 160 0 1 10 320 0 1 11 640 0 1 12 1280 0 1 13 2560 0 1 14 5120 0 1 15 10240 0 1 16 20480 0 1 17 40960 0 1 18 81920 0 1 19 163840 0 1 20 327680 0 1 21 655360 0 2 22 5242880 0 2 23 5242880 1 2 24 5242880 3 2 25 5242880 7 2 26 5242880 15 2 27 5242880 31 2 28 5242880 63 2 29 5242880 127 2 30 5242880 255 2 31 5242880 511 2 32 5242880 1023 2 33 5242880 2047 2 34 5242880 4095 2 35 5242880 8191 2 36 5242880 16383 2 37 5242880 32767 2 38 5242880 65535 2 39 5242880 131071...

Full text and comments »

World Finals: Dress Rehearsal Live 13:59 &mdash; ~Petr,2013-07-02's [blog](http://petr-mitrichev.blogspot.ru/2013/07/acm-icpc-2013-world-finals-practice.html) for today 12:15 &mdash; That's it for Dress Rehearsal. Tune in tommorow. Bye-bye, see you soon 12:07 &mdash; Contest is over. Results should be availabe shortly 12:00 &mdash; Peking University  11:31 &mdash; I now accept requests for team photos ;) 11:28 &mdash; NRU ITMO:  11:25 &mdash; Taiwan National:  11:23 &mdash; SPb State: ![ ](https://lh4.googleuse...

Full text and comments »

[Unofficial Editorial] — 1930G Hello codeforcers, since the editorial for [problem:1930G] is not out yet, and I found the problem to be pretty cute, I decided to write this blog. Note: 1. I will refer to "prefix maximum array" as PMA for the sake of brevity. 2. By "possible" PMA, I mean a PMA which can be generated by some valid partial pre-order traversal. Let us firstly make a couple of general observations: <ol> <li> If element $u$ occurs as a prefix maximum in any possible PMA, then the values of all its ancestors must be less than $u$. </li> <li> If elements $i, j$ $(i < j)$ occur as adjacent prefix maximums in any possible PMA, then we have two cases: <ul> <li><u> $i$ is an ancestor of $j$</u> : Here, $i$ must be the largest (indexed) ancestor of $j$.</li> <li><u> $i$ is not an ancestor of $j$</u>: Here, let $c$ be the first node on the path from $lca(i, j)$ to $i$. $i$ must be the largest (indexed) node in the subtree of $c$ and $i$ must be larger (indexed) than the largest (indexed) ancestor ...

Full text and comments »

Codeforces Round #479 (Div. 3) Hello! [contest:977] will start on [May 6 (Sunday) at 14:05 (UTC)] (http://www.timeanddate.com/worldclock/fixedtime.html?day=6&month=5&year=2018&hour=17&min=5&sec=0&p1=166). It will be the first Div.3 round in the history of Codeforces. You will be offered 6 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests &mdash; just like you will be upset if many solutions fail after the contest is over. [Remember] (/blog/entry/59228) t...

Full text and comments »

Running a College Club (Somewhat Successfully) #It’s just a club https://www.youtube.com/watch?v=GzPqp1gWfe4&t=633s If it is, don’t read ahead. You lack passion for running it. Just think of it, what in this modern world has been accomplished without passion. Nothing. People really loved something, were driven by something and that is why pursued it. Not just because it was a means to an end. If it was, it didn’t end up as great. It fulfils a mission that you truly believe in and want to spread. You really are happy when the members of the club succeed or even surpass you. You just become selfless and give yourself to the club. This is when the club thrives. You think what’s best for the club, not for you. You are the Mother, (he he he). College Clubs (in India) are rarely run by passionate people. They just want to maintain what had happened last year, or keep doing the same kind of stuff. It’s never new. The issue is that, the majority of the people’s purpose for being in the club is getting an LoR from their faculties...

Full text and comments »

Strong orientations, and a nice proof of Robbins' theorem **NOTE:** As always, you can also read this on [my blog](https://danielz.fyi/thoughts/strong-orientations)! --- ## Introduction Per [Wikipedia](https://en.wikipedia.org/wiki/Strong_orientation): > In [graph theory](https://en.wikipedia.org/wiki/Graph_theory), a **strong orientation** of an undirected graph is an assignment of a direction to each edge that makes it into a [strongly connected graph](https://en.wikipedia.org/wiki/Strongly_connected_graph "Strongly connected graph"). A natural question that follows: *which undirected graphs have a strong orientation?* ## Robbins' theorem Robbins' theorem states that the set of graphs with strong orientations is precisely the set of *bridgeless* graphs. *Lemma.* This condition is necessary (i.e. any graph with a bridge cannot have a strong orientation). *Proof.* This picture should make the argument clear:  If the edge is di...

Full text and comments »

Invitation to ICPC de Tryst and CodeMod 2022 (ANCC, IIT Delhi) Hello Codeforces! The Algorithms and Coding Club, IIT Delhi (ANCC) in collaboration with Tryst, IIT Delhi, will host the following two events and would like to invite you all for the same: - ICPC De Tryst on [Friday April 15, 2022 at 21:00 IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=ICPC+De+Tryst&iso=20220415T21&p1=176&ah=4). - CodeMod on [Sunday April 17, 2022 at 09:00 IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=CodeMod&iso=20220417T09&p1=176&ah=3). Participation is open to all, but the prizes are only for Indian college students. We encourage everyone to participate in these contests. --- ## ICPC de Tryst $\textbf{ICPC de Tryst}$ is an ICPC style team contest where you would be given 7-9 problems to solve in the span of 4 hours, for teams of 1-3 members. $\textbf{Details}$: - Each participant is allowed to use their own laptop. - Participants will be required to submit their code on Codeforces and will receive a verdi...

Full text and comments »

HCW '19 Team Round Editorial This is an editorial blog for [contest:102279]. Any further question can be asked in the comments, I'll try to answer all the questions. Please, do not private message or email me, your question could be the same as others', and I really hate to answer one question multiple times. >:( [problem:102279A] ------------------ Author: [user:low_,2019-07-22]. <spoiler summary="Tutorial"> To solve the problem, you'll only need to note that in $(N+1)$-th turn: Seo moved through exactly $(N+1)*V_s$ property, that is exactly $V_s$ full round of the board, so that he end up in $1$ afterwards. The same happens with B21 and Lowie. After that, the game keeps repeating itself. We can conclude that: if there isn't any event of one paying other in the first $3*(N+1)$ turns, it will never happen, so we can output $3000000000$. Otherwise, we can find the first event of it by brute force in $O(3*(N+1))$ time complexity. Maximum time complexity: $O(3*(N+1))$. </spoiler> [problem:102279B]...

Full text and comments »

Ineffable — simple command-line grader for personal use <center> <img src="http://codeforces.me/predownloaded/f4/3d/f43d1d912eca2f8c25b30418f592eb7717eaf88f.png"> </center> Hello Codeforces, I want to share with you a simple tool that I've been using for a while now that I named "Ineffable". # What is ineffable? Simple command-line grader for local grading of solutions for problems of competitive programming contests. It is written in Python and it uses `timeout` Perl library to limit resources (time and memory limits) of program being tested. It works on Ubuntu, and I guess it should work on any Linux/Unix system as long as Python and Perl are installed. # Screenshots   (Original quote is "Success consists of going from failure to failure without loss of enthusiasm") # Installation Run the following commands on your terminal: ...

Full text and comments »

Round #874 (Div. 3) — some statistics <img src="/predownloaded/07/e7/07e7ad4bd50ecd89752d2201070960f87acefb9f.png" style="width: 400px; margin-left: auto; margin-right: auto; display: block;" /> <img src="/predownloaded/63/d3/63d3ccc84aebe979404ee105d95a91645e46ea73.png" style="width: 600px; margin-left: auto; margin-right: auto; display: block;" /> <img src="/predownloaded/2b/41/2b41f20a0f1a1b0b8a6417c865fd34e0ea3df15e.png" style="width: 500px; margin-left: auto; margin-right: auto; display: block;" /> <img src="/predownloaded/14/57/14573f4a4eb09902aaea95330179bfd69f030b4d.png" style="width: 600px; margin-left: auto; margin-right: auto; display: block;" /> <img src="/predownloaded/86/c9/86c914a818132252f07b043cbf67026414d9ab4f.png" style="width: 600px; margin-left: auto; margin-right: auto; display: block;" /> <img src="/predownloaded/26/66/2666fb43ad8e9337d9cceed2aadbff3113be3917.png" style="width: 700px; margin-left: auto; margin-right: auto; display: block;" /> <img src="/predownloaded/81/63/8163a5bb9ae...

Full text and comments »

Sorted list of IOI participants by codeforces max rating 1.  [user:matthew99,2017-06-09] 3100 2.  [user:Reyna,2017-06-09] 2771 3.  [user:geniucos,2017-06-09] 2762 4.  [user:yutaka1999,2017-06-09] 2704 5.  [user:jiaqiyang,2017-06-09] 2671 6.  [user:arsijo,2017-06-09] 2638 7.  [user:Enchom,2017-06-09] 2630 8.  [user:Narenji58,2017-06-09] 2613 9.  [user:kefaa,2017-06-09] 2606 10.  [user:pacu,2017-06-09] 2594 11. ![ ]...

Full text and comments »

Пошаговый разбор для новичков. Codeforces Round 1102 (Div. 2) Всем Привет!  Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать свой первый пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи. Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую пр...

Full text and comments »

Hack me! (CF Round #263, Div. 2) Welcome again! I decided to split statistics for both division. Post for first division <strike>will be added later</strike> is <a href="http://codeforces.me/blog/entry/13572">here</a>. So, let's look at hacks in [contest:462]. <small><strike>Some statistics are missing &mdash; I have some problems with downloading all data (Codeforces seems little crowded today). They will be also added later.</strike></small> **Update**: Europe went asleep, so I added missing stats. [cut] <h3>Stats</h3> Problem | Successful hacks | Unsuccessful hacks | Other | Sum | :---:|:---:|:---:|:---:|:---:| [problem:462A] | 5 (17%) | 25 (83%) | 0 (0%) | 30 | [problem:462B] | 1193 (71%) | 188 (11%) | 306 (18%) | 1687 | [problem:462C] | 0 (0%) | 55 (36%) | 98 (64%) | 153 | ### Fastest hackers Problem | Time | Hacker | Defender | Hack :---:|:---:|:---:|:---:|:---:| [problem:462A] | 00:50:08 | [user:ak.bewildered,2014-08-26] | [user:abdohammam95,2014-08-26] | <a href="http://codefo...

Full text and comments »

NowCoder Summer Multi-School Training Camp 2025 Hello, Codeforces! As the official team of NowCoder (China's leading programming competition platform), we are pleased to introduce the 2025 NowCoder Summer Multi-School Training Camp! This annual event has been running for eight years. Since the summer of 2018, we have collaborated with top competitors from algorithmic competitions such as ICPC, NOI, and IOI, aiming to enhance participants' programming skills through competitions, lectures, and exchanges, and to prepare for upcoming competitions like ICPC and CCPC in the second half of the year; simultaneously, we seek to foster learning and exchange among university training teams worldwide. <center> <h2 style="border-bottom: 1px solid #000;">Details</h2> </center> 1. **Schedule**. Consistent with last year, this year's training camp will consist of ten ICPC-style competitions, starting on [Tuesday, 15 July 2025<sup title="timezone offset" style="font-size:8px;" data-immersive-translate-walked="24cdac9c-eeae-41da-aef2-9dcf...

Full text and comments »

NEF & ROHSTPC Hello friends! <img src="/predownloaded/36/a8/36a8f8392e9ed1ea75715400c943949f8ad4c6dc.png" align="right" style="height: 235px; margin: 10px;" alt="text"/> <a href="https://youtu.be/ZuzBPpBy-sE" style="font-size: 15.0px;padding: 8.0px 14.0px;background-color: rgb(100, 65, 165);color: white;">ICPCLive broadcast</a> <a href="http://nerc.itmo.ru/archive/2019/standings.html" style="font-size: 15.0px;padding: 8.0px 14.0px;background-color: rgb(55, 109, 171);color: white;">Standings</a> <a href="http://nerc.itmo.ru/archive/2019/nerc-2019-statement.pdf" style="font-size: 15.0px;padding: 8.0px 14.0px;background-color: rgb(55, 109, 171);color: white;">Problems</a> This weekend we'll hold two large-scale final stages of important Championships in the region: ICPC Northern Eurasia Finals 2019 and Russia Open High School Team Programming Contest. Competitions are traditionally held at several places: in St. Petersburg, Barnaul, Almaty, Tbilisi and Kremenchuk. School tea...

Full text and comments »

About the programming languages **This post is no longer relevant; it has become significantly outdated. You should read the post at [https://codeforces.me/blog/entry/121114](https://codeforces.me/blog/entry/121114)**. <p> Later you'll be introduced to the rules of the Codeforces contests, which differ from those of <a href="http://en.wikipedia.org/wiki/ACM-ICPC#Contest_rules">ACM-ICPC</a>, TopCoder, GCJ, and I hope they'll bring some difference to the world of programming competitions. Most of the official competitions will be carried out according to these rules, though there will be more traditional contests. For example, Codeforces Beta Round #1 will be carried out according to the familiar <a href="http://en.wikipedia.org/wiki/ACM-ICPC#Contest_rules">ACM-ICPC</a> rules. For some time testing will be based on Windows, but things might change in future, fortunately, the system supports testing on different platforms, even within one contest. </p> <p> At the present time the ...

Full text and comments »

Balkan Olympiad in Informatics 2014 Problems — Day 2 So, day 2 passed and the tasks were quite good again. I'm quite sad that I couldn't get the gold but it was a nice competition. #### Problem 1 &mdash; Ephesus You are given a string of N letters. Let's observe a k-partitioning of this string, that is we divide it in k parts (numbered 1, 2, ... k), and each of those parts is a substring of the string. The first part starts from the beginning of the string, the second starts immediately after the end of the first and so on. Every letter of the text is in exactly one of those parts and each part has at least one letter, that is the parts are non-intersecting, not empty and all of them together exhaust the given string. Now you are asking the question "How many are the different k-partitions such that the k parts are strictly increasing in lexicographical order", that is the parts are such that the first is the smallest lexicographically, the second is the next smallest and so on. Let **Xk** be the answer for k. This problem is ev...

Full text and comments »

Академический университет: бакалавриат (<s>20 лет</s> 2 года спустя) Буквально несколько дней назад закончилась сессия. Как и мой первый год в Академическом университете и третий год в жизни бакалавриата... А потому хочется поделиться некоторыми впечатлениями. И, по возможности, дополнить и без того весьма полный [пост](http://codeforces.me/blog/entry/17837) от Пети Смирнова, рассказать о каких-то изменениях в жизни бакалавриата. О том, как всё начиналось ------------------ Для начала хочется рассказать о том, как всё начиналось, и кто у нас вообще учится в Академическом университете. В нашем году был набор 47 человек. Среди поступивших 14 человек &mdash; призёры и победители Всероса, причём двое по математике и один по физике. Также четверо &mdash; победители олимпиад 1 уровня (призёра для поступления не хватит). Оставшиеся 29 человек поступали по ЕГЭ. В текущем же году набор составит уже 36 человек. По уровню подготовки, как видно, люди действительно поступали совсем разные. Однако всё это было учтено при подготовке программы. В ча...

Full text and comments »

Solving Code Jam Qualification Round. In Excel. So, the qualification round was upon us, and it's a nice way to have some fun. In the past two years I've been writing solutions in multiple languages. In both of them I used Excel for one problem. Without any use of VBA of course, as it would've been too boring. This year I decided to go nuclear and use Excel for everything. I managed to get 100 points. Here are the notes on this glorious experience. [cut] . So, how does this works overall? In Excel you can import data, particularly from text. You can also specify separator, which is usually space, which means the numbers will spread out over the columns. Then you can write formulas to calculate the output row for every test, and if they're presented sequentially in one column, you can easily select them and copy-paste into any text editor. Let's deal with the easiest problem first in terms of implementation in Excel &mdash; D. X is in column A, R is in column B, C is in column C. Use simple formula: ~~~~~ =IF(A2="", "", "...

Full text and comments »

Variety of solutions depending on constraints Suppose the input for a problem is positive integer N and answer happens to be 1/N. Here is what happens for different constraints on N. You decide which version is the hardest. 1. `N <= 10^9` Everyone does math and all solutions look like ~~~~~ cout << 1.0 / N ~~~~~ 2. `N <= 10^6` You see solutions from above but some contestants decide to use iterative approach, something like ~~~~~ double ans = 1.0; for (int i = 2; i <= N; i++) ans = ans * (i - 1) / i; ~~~~~ 3. `N <= 10^5` Mostly solutions from above, but some contestants use recursion (maybe with memoization) ~~~~~ double f(int N) { if (N == 1) return 1.0; return f(N - 1) * (N - 1) / N; } ~~~~~ 4. `N <= 500` Solutions from above, but some contestants go with O(N^3) dynamic programming instead 5. `N <= 109` Contestants think there is a typo and go with first solution 6. `N <= 100` Some contestants realize that you can precompute all answers ...

Full text and comments »

ICPC Challenge 2021: Marathon (powered by Huawei) <img src="/predownloaded/aa/57/aa577c257884a5ae68792513c31d9f64fd7bff5f.png" align="right" style="height: 260px; margin: 10px 30px 20px;" alt="text"/> <img src="/predownloaded/02/dc/02dcda21c933a1536fbe26510139bb80aedca1c8.png" align="right" style="height: 140px; margin: 5px 30px 20px;" alt="text"/> Hello everyone! We invite you to participate in the **ICPC Challenge powered by Huawei** that will run from **[12pm CST May 26](https://www.timeanddate.com/worldclock/fixedtime.html?msg=ICPC+Challenge+2021%3A+Marathon+&iso=20210526T12&p1=33) — 12pm CST May 30, 2021**. The Challenge problem is based on a real-world industrial topic, providing participants the opportunity to learn about cutting-edge technologies, and is open to the global community. <center style="margin: 1.5em;"> <a href="https://codeforces.me/contests/1524" style="font-size: 15.0px;padding: 8.0px 14.0px;background-color: rgb(226, 36, 14);color: white;">Join Challenge</a></center> The Challenge problem will...

Full text and comments »

How not to perform well on life(With how not to perform well on ICPC bonus) First of all, for a long time I wanted to write this blog but I keep delaying it and finally here I am. After seeing [user:matthew99,2017-08-23]'s blog I decided to my time has come. I really wanted to write like him but my English skills aren't enough to use "you would" dozens of times. So I will explain how I didn't perform well in my life, and if you do same things you will end up succeed at failing in your life. And it's very important to say at this point, I'm very bad at English, so if you're disgusted you can stop right there and I'm truly sorry about it. **TLDR** : I am a loser. I was a regular student before high school. I interested with math olympiads little bit but I didn't get even a national medal just a several contests. By the way I won a The New iPad. So I am passing that times and coming to high school. In our country national eliminations goes like that, paper based elimination at may, national OI at december, team selection contest at march/april. High s...

Full text and comments »

TheForces Round #36 (Starters-Forces) Editorial [A](https://codeforces.me/gym/105445/problem/A) Idea:[user:Mathmodel,2024-10-25] <spoiler summary="Hints"> <spoiler summary="Hint 1"> Divide $n$ to odd and even </spoiler> <spoiler summary="Hint 2"> How we can represent palindrome string ? <spoiler summary="Answer"> $$\displaystyle s=[\text{segment}](\text{median})[\text{segment reversed}]$$ </spoiler> </spoiler> <spoiler summary="Hint 3"> Denote the sum of segment is $f$ and sum of medians is $h$ then $m=2f+h$ </spoiler> <spoiler summary="Hint 4"> Focus on median when $n$ is even and use the symmetric property </spoiler> <spoiler summary="Hint 5"> See the $\min$ and $\max$ case for odd and even $n$ </spoiler> </spoiler> <spoiler summary="Analysis"> For odd values of $n$ we can re-express string $s$ as $$s_1s_2...s_{\lceil \frac{n}{2} \rceil}...s_n$$ Note that $s_1+s_2+...+s_{\lfloor \frac{n}{2} \rfloor}=s_{\lceil \frac{n}{2} \rceil+1}+....+s_n$ , so we can assume the sum as $f$...

Full text and comments »

What if tourist goes rainboy mode? (Simulation) DISCLAIMER: NO TOURISTS AND RAINBOYS WERE PINGED Ah yes, two names that most people on Codeforces have heard -- <b>t<span style="color:red;">ourist</span></b> and <b><span style="color:purple;">rainboy</span></b>, one known as the CP Legend, and one as the user who does everything reverse. Such a great idea to put them together &mdash; a hypothetical user with the same ability as <b>t<span style="color:red;">ourist</span></b>, and solves problems the <b><span style="color:purple;">rainboy</span></b> way. _For those unaware of the "rainboy way", it means solving the problems in reverse order. In particular, if he cannot solve the final problem, he solves no problems in the contest._ Unfortunately, <b><span style="color:purple;">rainboy</span></b> had not yet reached red, peaking at 2398 rating. How far can this user go? We shall simulate this user through all the contests that tourist and rainboy took part in comparably, which adds up to 60 contests from [contest:745] to [cont...

Full text and comments »

List of All Petrozavodsk Contests Like my last blog [List of All Open Cup Contests](https://codeforces.me/blog/entry/84466). I made this list for all contests from Petrozavodsk Training Camp, containing the standings, upsolving links and statements. The upsolving links of Petrozavodsk Summer 2020 are private, yandex.contest logins are needed. I will update the link if other sources found. And thanks to the efforts of [Baekjoon Online Judge](https://www.acmicpc.net/), most contests from winter 2015 to winter 2020 can be solved without private logins. For some of the rest contests, opentrains logins are needed. And for some of the rest contests, I found several other sources to virtual participant using [Virtual Judge](https://vjudge.net/), [Codeforces gyms](https://codeforces.me/gyms) and [Programmers club of PetrSU](http://acm.petrsu.ru/). For some of the rest contests, I could not find any public sources and maybe someone could help with it (I believe problems in Warsaw U Contests are from old POI or PA). ...

Full text and comments »

MCO 2025 Editorial [problem:606535A] Problem idea: [user:MGod,2025-04-26]<br> Problem preparation: [user:zscoder,2025-04-26] <spoiler summary="Solution"> **Observation 1:** We denote the string at time $t$ to be $S(t)$. Then $S(t) = S(t-1) + S(t-2)$ where $+$ represents string concatenation. **Proof:** We proceed using mathematical induction. The base case $t=2$ can be easily proven by hand. For our inductive step, we wish to show that $S(t) = S(t-1) + S(t-2)$, given that the observation is true time $t-1$. We can split the string $S(t-1)$ into two sections, which are $S(t-2)$ and $S(t-3)$. By definition, performing the operation of replacing $1$ with $10$ and $0$ with $1$ on each of these parts will make the two parts $S(t-1)$ and $S(t-2)$ respectively, which in turn results in $S(t) = S(t-1) + S(t-2)$. **Subtask 1: $Q=1, r \leq 300 000$** The binary string can be generated by brute force, manually performing the operations until the length of the string exceeds $300 000$. The number ...

Full text and comments »

Алгоритм Монтгомери: (A × B) % N Вступление ================== Недавно мне рассказали про некое «преобразование Монтгомери», которое якобы сводит вычисления по произвольному модулю к вычислениям по модулю $2^k$. Звучит интересно: во всяких вычислениях по простому модулю самое долгое место — как раз взятие по модулю после каждой операции. Но как именно преобразование работает, не рассказали. Повезло, что я живу в эпоху интернета и любую интересующую меня тему могу с тем или иным успехом загуглить.[cut]  Гугл рассказал, что штука называется «алгоритм Монтгомери», описана на [википедии](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%BE%D0%BD%D1%82%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%B8) и итмошных [вики-конспектах](https://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%9C%D0%BE%D0%BD%D1%82%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%B8). Оба описания мне не очень понравились, потому что (хоть и объясняют, что делать) пок...

Full text and comments »

Teams going to ACM ICPC World Finals 2018 I think it's good time for collecting teams that are going to WF this year. Let's complete the table together :) Europe ====== | Count | Country | Region | University | Member 1 | Member 2 | Member 3 | | ----- | ------- | ------ | ---------- | -------- | -------- | -------- | | 1 | Belarus | NEERC | Belarusian State University | [user:progmatic,2018-04-12] | [user:Fedosik,2018-04-12] | [user:vilcheuski,2018-04-12] | | 2 | Estonia | NEERC | University of Tartu | [user:oml1111,2018-04-12] | [user:hoomas,2018-04-12] | [user:k__mas,2018-04-12] | | 3 | Kazakhstan | NEERC | Kazakh-British Technical University | [user:Zharaskhan,2018-04-12] | [user:AeonHQ,2018-04-12] | [user:NurlashKO,2018-04-12] | | 4 | Russia | NEERC | Moscow Aviation Institute | [user:mingaleg,2018-04-12] | [user:SirRembocodina,2018-04-12] | [user:i.trofimow,2018-04-12] | | 5 | Russia | NEERC | Moscow Institute of Physics & Technology | [user:Golovanov399,2018-04-12] | [user:Kostroma,2018-04-12] | [user:I_hate_A...

Full text and comments »

Euristica '18 Announcement [**Programming Club, IIT Indore**](https://pclubiiti.github.io) is proud to announce **IIT Indore's** inaugural Programming Fest, [__Euristica '18__](https://euristica.in), sponsored by **Arcesium**. The event was realised thanks to the amazing amounts of effort put in by our team across several weeks.  The domain of events we will be organising spans across Competitive Programming, Application Development, Cyber Security and Machine Learning. Prizes netting ₹300K is up for grabs as well! The fest kicks off on __Friday, 23rd March 2018__, and will continue until __Sunday, 8th April 2018__. We've put lots of love and effort into making the problem statements of every contest, and we hope that you enjoy solving them as much as we enjoyed making them :) The events are planned as follows:- - **Divide By Zero 6.0** &mdash; Euristica's flagship short programming contest - **Hackathon** &mda...

Full text and comments »

Завершилась летняя школа «Сазанка 2016»: взгляд гостя, результаты, фотографии С 1-го по 11-е августа прошла международная летняя студенческая школа по программированию &mdash; в живописном месте, на базе отдыха «Домостроитель» на берегу Волги. В ней приняло участие около 60 участников. В этом году школа проводилась Центром олимпиадной подготовки Саратовского государственного университета в 7-й раз. Руководитель &mdash; известный здесь Михаил Мирзаянов. Мне посчастливилось побыть два дня на школе в качестве репортера. Меня встречает Михаил [user:MikeMirzayanov,2016-08-12] Мирзаянов. &mdash; Сейчас идет тренировка, в два часа будет обед. &mdash; Как проходит обычный день? &mdash; Завтрак, лекция, контест с перерывом на обед, разбор, дорешивание. Вечером отдых &mdash; сегодня по плану ЧГК, завтра сауна с арбузами и забегами в Волгу. На лекциях [user:MikeMirzayanov,2016-08-12] прочитал следующие темы: 1. Паросочетания и смежные задачи. Теорема Бержа. Паросочетания в двудольных графах. Алгоритм Куна и его свойства. 2. Оптимизационные трюки...

Full text and comments »

Inconvenience with source code preview on Codeforces blog posts **First note: All observations are from my computer screen with the resolution of 1366 × 768. OS is Windows 10, browsing Codeforces using Google Chrome and coding using Code::Blocks 17.12. People with high-end computers/monitors or different software usages might experience differently or less inconvenient, yet the problem itself is still there.** *TL;DR: The source codes presented through the "block code" format in Codeforces blog post should be made slightly smaller in terms of font size, and with less line spacing. A suggestion might be making it similar to the source code presented in the submission pages.* Many problem setters prefer showcasing model solutions on spoilers and direct sourcecode-formatting on blog posts (most notable ones are PikMike and Vovuh). I myself particularly enjoy this design, since the source code is collapsible and you won't lose the editorial tab you're watching (clicking any external links normally will not open it in a new tab, so sometimes it'd ...

Full text and comments »

Codeforces Round #372 Editorial We hope everyone enjoyed the problems. Here is the editorial for the problems. I tried to make it more detailed but there might be some parts that might not be explained clearly. [Div. 2 A &mdash; Crazy Computer](http://codeforces.me/contest/716/problem/A) ------------------ Prerequisites : None This is a straightforward implementation problem. Iterate through the times in order, keeping track of when is the last time a word is typed, keeping a counter for the number of words appearing on the screen. Increment the counter by $1$ whenever you process a new time. Whenever the difference between the time for two consecutive words is greater than $c$, reset the counter to $0$. After that, increment it by $1$. Time Complexity : $O(n)$, since the times are already sorted. <spoiler summary="Code (O(n))"> ~~~~~ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #def...

Full text and comments »

Does World want to know only what America wants? Do you want to be controlled by USA point of view? You might be thinking why America wants this? Let's see how Russia vs Ukraine will help the USA. This will increase the fear of Russia in Europe. Now more countries will buy weapons. Who will sell? America. You might have heard that Germany after WW2, the first time is going to invest this heavily **$100 billion dollars** for Defense. Who will get the benefit? America. Who will be destroyed? Ukraine. Economically, Russia will be impacted(That is why America wants to prolong this war and by manipulating the sentiments they want civilians to fight to extend this and affect Russia economically). **One arrow two targets for the USA**. Russian attack can not be justified by a pic but do you support this type of fairness? ![ ](https://i.ibb.co/yfMxt0q/Whats-App-Image-2022-03-02-at-14-36-08.jpg") This way America might be controlling your elections as well by using social media platforms like Facebook/Twitter/Google/Youtube. Does your country really want to be controlled by U...

Full text and comments »

Archive of the Short Lived Regime of Hacker 79XD #### [WARNING: Consumption of the following data is at YOUR OWN risk] The following is a provisional archive of the all Announcements (as images) created both by Codeforces and by the 79XD during the short-term takeover by 79XD (especially if you didn't have time to read them). (Even if we know that this wasn't a real security breach)... <spoiler summary="1">   </spoiler> <spoiler summary="2">  </spoiler> <spoiler summary="3">   </spoiler> <spoiler summary="4">  </spoiler> #### BY 79XD <spoiler summary="5"> ![ ](/predownloaded/...

Full text and comments »

Всем спасибо! Статистику по раундам я начал собирать по двум причинам:<br/> 1) было очень интересно узнать процент решений, упавших на системных тестах<br/> 2) хотелось попробовать что-нибудь написать в связке **javascript** + **DOM** + **Chrome Extension** <br/> <br/> Ничего из перечисленного я тогда не знал, и после ряда экспериментов, чтения сэмплов и форумов появился [Первый Пост](/blog/entry/9858).<br/> Примечателен тот факт, что через три часа рейтинг этого поста был в районе **-7**. В этот момент показалось, что процент упавших решений был интересен только мне.<br/> Спустя сутки, стало понятно: все-таки, есть участники, кому это интересно ( **+123** ).<br/> <br/> Благодаря вашей поддержке, а также замечаниям и пожеланиям, статистика продолжала развиваться.<br/> Мой Javascript-skill вырос c "Below Hello World!" до "Above Hello World!", а ваши плюсы заставляли работать над новым функционалом и исправлять найденные баги.<br/> Но даже после того, как в статистике [появились графики](/bl...

Full text and comments »

Hack me! — Year 2014 in review! (part 2.) Merry Christmas everyone! One round behind us, one more to go in this year. It's time for the second part of my little summing-up (last post can be found [here](/blog/entry/15326)). Now we will show all most accurate hackers. We will count the accuracy as the: $$\frac{\#successfulhacks}{\#allhacks}$$ Because there were a lot of flawless hackers, below we show only hackers with at least 10 successful hacks &mdash; still there were 36 of them! The full list of hackers' accuracy can be found [here](http://test.weaselcrow.com/pro/cf/ahack2014/). Also, below this table there is updated list of best hackers by summarized points, also the full list was updated [here](http://test.weaselcrow.com/pro/cf/hack2014/). [cut] <div></div> ### Accuracy rank | handle | accuracy | best rounds | points | :---:|:---:|:---:|:---:| 1 | [user:hetanglianyi,2014-12-25] | 100.0% | <small>[contest:462] [+19-0]</small> | 1900 (+19-0) | 2 | [user:bmerry,2014-12-25] | 100.0% | <small>[c...

Full text and comments »

Codeforces Round #462 Editorial Hi, all! This is not [user:Tommyr7,2018-02-14], but the **impostor** behind the round again (guess who I am? :P). The statements are written by me. Thank you, everyone, and hope you've all enjoyed the round! Any feedback on problems and tutorials are welcome — we look forward to doing even better in the future! Here are some of the detailed tutorials! ### Tutorials ### [problem:934A] **Author** [user:quailty,2018-02-14] / **Preparation** [user:quailty,2018-02-14] / **Tutorial** [user:quailty,2018-02-14] <spoiler summary="Tutorial"> [tutorial:934A] </spoiler> <spoiler summary="Solution (quailty)"> ~~~~~ #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF=(1LL<<60)-1; ll a[55],b[55]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=m;i++) scanf("%lld",&b[i]); ll res=INF; for(int i=1;i<=n;i++) { ll now=-INF; ...

Full text and comments »

[GYM] ACM ICPC Vietnam National Second Round Editorial Below is very short description of solutions to problem that I can solve. Because it is "short description", for most problems, there is no proof of correctness. Proving the solutions is up to you. [problem:100541A] This is the most simple problem in the set. **Observations:** - If you buy stock, you're better to buy as much as possible. - If you buy stock on the i-th day, then you will always sell every stock on some j-th day, where j > i and the price of the stock on the j-th day is maximal. Now we have an algorithm that runs in time O(N): - Initialize f(i) to be the maximum value of the stock price from i-th day to N-th day. - For each value of i from 1 to N, try to buy stock on i-th day, and find the value that you will sell these stocks using f(i+1). [problem:100541B] **Observation:** - There's only small number of different values of [N/i]. In fact, we can prove that there's only O(sqrt(N)) different values: Using the above observation, we have a O...

Full text and comments »

Unofficial list of IZhO 2023 participants The first day of IZhO 2023 is going to be at 2nd of February. I want to make a list of participants, can you please share the Codeforces handles of participants and their country? The list is sorted by Codeforces rating, but there might be changes due to current rounds. Thank you! <table> <thead> <tr> <th> CF Rank </th> <th> CF Handle </th> <th> Country </th> </tr> </thead> <tr> <td> 1 </td> <td> [user:syrtin,2023-01-28] </td> <td> Kazakhstan</td> <tr> <td> 2 </td> <td> [user:Tekor,2023-01-28] </td> <td> Kazakhstan</td> <tr> <td> 3 </td> <td> [user:StupidGuy13,2023-01-28] </td> <td> Georgia</td> <tr> <td> 4 </td> <td> [user:drdilyor,2023-01-28] </td> <td> Uzbekistan</td> <tr> <td> 5 </td> <td> [user:erankyun,2023-01-28] </td> <td> Armenia</td> <tr> <td> 6 </td> <td> [user:Zhabka,2023-01-28] </td> <td> Kazakhstan</td> <tr> <td> 7 </td> <td> [user:amunduzbaev,2023-01-28] </td> <td> Kyrgyzstan</td> <tr> <td> 8 </td> <td> [user:kitsune...

Full text and comments »

Online LCA и подвешивание деревьев друг за друга. O(log n) Наименьший общий предок и подвешивание деревьев друг за друга (Online) && (O(log n)). ================== ### Постановка задачи: **Дается изначально лес подвешенных деревьев. Дальше следуют запросы двух видов:** - Найти наименьшего общего предка двух вершин a и b, или вывести то, что они в разных деревьях. - Провести ребро между вершиной u и вершиной v. Гарантируется, что вершины u и v в разных деревьях, а также что, вершина u это корень дерева. (Получается после проведения ребра между вершиной u и v, они сольются в одно дерево, корнем которого будет корень дерева, в котором была вершина v)  _*Пример соединения двух деревьев, путем проведения ребра между двумя вершинами, выделенными красным*_ Решение: ------------------ Напомню, что задачу о нахождении **LCA** ( _Lowest Common Ancestor_ ) сводится к задаче **RMQ** ( _Range minimum query_ ), или по-русски, минимум на отрезке. Более подробно про эт...

Full text and comments »

MIT Informatics Tournament 2025 Spring Invitational **Update (5/8):** The Finals Round has concluded (here are links to [gym](https://codeforces.me/gym/105870/standings) & [editorial](https://codeforces.me/gym/105870/attachments/download/31412/MITIT_2025_Finals_Editorial.pdf)). Editorials and problems for [Qualification Round 1](https://codeforces.me/gym/105822) and [Qualification Round 2](https://codeforces.me/gym/105837) are in the gym. Congratulations to all of our finalists! 1. [user:hos.lyric,2025-05-09] (405, 13:32:43) &mdash; $1500 2. [user:tourist,2025-05-09] (400, 05:50:33) &mdash; $1000 3. [user:benq,2025-05-09] (340, 05:41:11) &mdash; $500 4. [user:A_G,2025-05-09] (310, 05:52:27) 5. [user:Kevin114514,2025-05-09] (310, 09:29:36) 6. [user:ksun48,2025-05-09] (305, 06:32:42) 7. [user:gamegame,2025-05-09] (305, 06:51:14) 8. [user:rainboy,2025-05-09] (305, 07:16:58) 9. [user:jeroenodb,2025-05-09] (300, 04:57:25) 10. [user:errorgorn,2025-05-09] (300, 05:51:34) 11. [user:ecnerwala,2025-05-09] (300, 05:53:09) 12. ...

Full text and comments »

CF X-Users : Website For X-Users ! ### WEBSITE DOWN #### UPDATE : 27 AUG 2020. 0. As you all might have noticed on the [Leaderboard](https://cf-x-user.herokuapp.com/leaderboards), we have people with <strong>times_caught</strong> more than $4$. I wonder when will they get a ban from Codeforces. 1. Added a new feature for people to **report X-Users**, the solutions which were mangled or clever enough to bypass MOSS. These things go under manual validation for now, but if confirmed it will give +100 X-Rating Gain to the X-User, also this incident would be mentioned on their profile as "<strong>Notoriety</strong>". 2. I have added an **Appeal** section. People who are badly affected or people who think that someone is impersonating them can add an appeal. i would remove those X-Users but for X-Users with <strong>times_caught</strong> $>$ $2$, appeal won't help much. But i would see if anything can be done. ### Introduction <strong>What is a X-User?</strong> Its just a person, who's solution gets s...

Full text and comments »

IIOT — Open Contests 2021/22 For the fifth time, the _International Informatics Olympiads in Teams_ will be mirrored into online contests. These contests, of a **lower** difficulty level than those of the IOI, are intended for teams of 4 contestants from the same high school. However, everyone is welcome to participate to the mirror contests, especially if you are considering to join officially the IIOT in the future!  More specifically, we allow: - several teams from the same school (also in the official contest) - teams participating only in some contests (also in the official contest) - smaller teams (also in the official contest) and larger teams - teams of students from different schools and non-students - changes in team members between contests The mirror contests timing will be USACO-like: it will be open for 27 hours but you will be able to compete for up to **3 hours** (you can decide when to "start" your time window, ...

Full text and comments »

Fast modular multiplication Consider the following problem: given three integers $x$, $y$ и $m$, $0 \leqslant x,y < m < 2^{32}$, calculate $xy\bmod m$. The easy way is just to multiply these numbers and apply the modulo operation: ~~~~~ uint32_t prod(const uint32_t x, const uint32_t y, const uint32_t m) { return x * y % m; } ~~~~~ As you might have guessed, this solution is wrong. The thing is that an overflow is possible in such a procedure: the operation `x * y` is performed in the type` uint32_t`, and in fact the intermediate result of this operation will not be $xy$, but $xy\bmod2^{32}$. If after that we take the result modulo $m$, it may differ from the correct one: $$ \left(xy\bmod2^{32}\right)\bmod m\ne xy\bmod m. $$ The way out is simple — you need to multiply in a larger type: ~~~~~ uint64_t prod_uint64(const uint64_t x, const uint64_t y, const uint64_t m) { return x * y % m; } ~~~~~ If you do this, then, since $xy<2^{64}$, this product will definitely not overflow, and after tak...

Full text and comments »

Codeforces Beta Round #36 <h3>General</h3><br>It was normal codeforces contest except the IO: input.txt/output.txt. I didn't know the IO change before contest began and I got upset. I used an unaccustomed fstream library in the contest, but I should use freopen as below code. (if C++)<br><br>&nbsp;&nbsp;&nbsp; freopen("input.txt", "r", stdin);<br>&nbsp;&nbsp;&nbsp; freopen("output.txt", "w", stdout);<br><br><br><h3>A Extra-terrestrial Intelligence </h3>Simple problem, calculate the interval length between first two '1's, then check if all interval lenghs are equal.<br>I failed to read the statement <i>"It’s guaranteed that the given record sequence contains at least three 1s"</i> at the beginning, then I stopped for a little.<br><br><br><h3>B Fractal </h3>This is also a simple problem, simple iteration is good because the input size is very small.<br>But I stuck at compilation error of vector&lt;string&gt; substitution, then I lost about 10 mins. This upset me. My C++ compiler MinGW outputs compilation error at...

Full text and comments »