Codeforces Round #225 Привет всем! Мы приглашаем вас поучаствовать в Codeforces Round #225, который состоится в понедельник 20-го января в 19:30 по московскому времени. Это третий раунд, где я участвую в качестве автора (другие два: Codeforces Round #198 и Codeforces Round #191 (Div. 2)). Если вы посмотрите мои прошлые раунды, то увидите, что главный герой задач — Яхуб. Один из авторов этого раунда — ... Яхуб... реальный человек, с которого взят главный герой задач. Знакомьтесь, Rares Buhai ([user:rares.buhai,2014-01-18]), он же Яхуб. Он является автором задач Div. 2 C / Div. 1 A, Div. 1 D и Div. 1 E. Скорей всего, задачи покажутся вам интересными, поскольку их автор два раза становился золотым медалистом [IOI] (http://ioi.eduardische.com/people/2688) (и он может участвовать еще два раза). Все остальные задачи готовил я. Они мне нравятся, но я буду не объективным, если скажу, что они интересные. Посмотрим, что скажут участники после контеста :) Как и в прошлый раз, будет небольшой спо...

Full text and comments »

Codeforces Round #191 (Div. 2) Welcome to another Codeforces Round! **Please note that the time of round #191 was changed. Contest will start at [Thursday 12:30 UTC](http://timeanddate.com/worldclock/fixedtime.html?day=4&month=7&year=2013&hour=16&min=30&sec=0&p1=166).** My name is Linh ([user:ll931110,2013-07-02]). I'm from Vietnam, and I'm glad to present to you my first Codeforces round. It is for Div 2 only; however, I welcome participants from Div. 1 to participate and enjoy challenging problems. I hope this would be a pleasant gift for those who are going to IOI 2013 (and participants from World Finals), which will take place in just a couple of days. This round is prepared by me and [user:florin.elfus,2013-07-02] (from Romania). Also, I would like to thank the Codeforces team who puts efforts on making Codeforces and Polygon possible. Happy solving! **UPD1**: The score of problems in this round will be dynamic. The problems will be sorted in increasing difficulty order, at least in our perspect...

Full text and comments »

Codeforces Round #191 — Tutorial [problem:327A] I’ll present here the O(N ^ 3) algorithm, which is enough to solve this task. Then, for those interested, I’ll show a method to achieve O(N) complexity. **O(N ^ 3) method:** The first thing to observe is that constrains are slow enough to allow a brute force algorithm. Using brute force, I can calculate for each possible single move the number of 1s resulting after applying it and take maximum. For consider each move, I can just generate with 2 FOR loops all indices i, j such as i <= j. So far we have O(N ^ 2) complexity. Suppose I have now 2 fixed vaIues i and j. I need to calculate variable cnt (initially 0) representing the number of ones if I do the move. For do this, I choose another indice k to go in a[] array (taking O(N) time, making the total of O(N ^ 3) complexity). We have two cases: either k is in range [i, j] (this means i <= k AND k <= j) or not (if that condition is not met). If it’s in range, then it gets flipped, so we add to count variable 1 – ...

Full text and comments »

Educational Codeforces Round 83 [Rated for Div. 2] Hello Codeforces! On [contest_time:1312] [contest:1312] 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://mirror.codeforces.com/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 **7 problems** and **2 hours** to solve them. The problems were invented and prepared by Roman [user:Roms,2020-03-08] Glazov, Adilbek [user:adedalic,2020-03-08] Dalabaev, Vladimir [user:vovuh,2020-03-08] Petrov, Ivan [user:Bl...

Full text and comments »

Educational Codeforces Round 58 [Rated for Div. 2] Hello Codeforces! On [contest_time:1101] [contest:1101] 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://mirror.codeforces.com/blog/entry/51208">blog post</a>. This round will be **rated for the participants with rating lower than 2100**. It will be held on extented ACM 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 **7 problems** and **2 hours** to solve them. The problems were invented and prepared by Roman [user:Roms,2019-01-10] Glazov, Adilbek [user:adedalic,2019-01-10] Dalabaev, Vladimir [user:Vovuh,2019-01-10] Petrov, Ivan [us...

Full text and comments »

Educational Codeforces Round 20 Hello Codeforces! On [April 28, 18:05 MSK](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Educational+Codeforces+Round+20&iso=20170428T1805&p1=166) will be held Educational Codeforces Round 20. Series of Educational Rounds continue being held as Harbour.Space university initiative! You can read the details about the cooperation between Harbour.Space and Codeforces in the <a href="http://mirror.codeforces.com/blog/entry/51208">blog post</a>. Here is the special message from Harbour.Space University for **girls from India**: <b><i>Harbour.Space University offers a unique opportunity to win a FULL SCHOLARSHIP for #womenintechIndia and join our amazing Data Science, Computer Science or Cyber Security Master's Programme in Barcelona, Spain! Follow [this link](http://in.harbour.space/data-science/scholarship-women-in-tech-india/) to complete the application form.</i></b> <div style="text-align:center"><img src ="http://mirror.codeforces.com/predownloaded/b5/00/b500f462d444675...

Full text and comments »

Codeforces Round 991 (Div 3) — Video Tutorial **Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.** ### [2050A &mdash; Line Breaks](https://mirror.codeforces.com/contest/2050/problem/A) <spoiler summary="Video"> <iframe width="800" height="450" src="https://www.youtube.com/embed/svlEFTXQKDk?si=jcZOA1U80QNOKQb5&amp;start=191" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe> </spoiler> ### [2050B &mdash; Transfusion](https://mirror.codeforces.com/contest/2050/problem/B) <spoiler summary="Video"> <iframe width="800" height="450" src="https://www.youtube.com/embed/svlEFTXQKDk?si=jcZOA1U80QNOKQb5&amp;start=444" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; e...

Full text and comments »

Unofficial AtCoder Beginner Contest 191 Editorial ### [A &ndash; Vanishing Pitch](https://atcoder.jp/contests/abc191/tasks/abc191_a) <spoiler> The ball is invisible when it's between $V \cdot T$ and $V \cdot S$ meters away, inclusive. Thus the answer is `Yes` if $D < V \cdot T$ or $D > V \cdot S$, and `No` otherwise. Time complexity: $O(1)$ </spoiler> ### [B &ndash; Remove It](https://atcoder.jp/contests/abc191/tasks/abc191_b) <spoiler> Either use a dynamic array (`vector` in C++ / `ArrayList` in Java/Kotlin) to store the values $A_i \neq X$, or construct the output string directly. If using the latter method in Java/Kotlin, one should use the `StringBuilder` class to avoid wasting time copying the string in $O(N^2)$; this is not a problem in C++ as strings are mutable there. Time complexity: $O(N)$ </spoiler> ### [C &ndash; Digital Graffiti](https://atcoder.jp/contests/abc191/tasks/abc191_c) <spoiler> Simulate a "wall-following" algorithm. Specifically, let `.` represent empty space, and `#` represent walls....

Full text and comments »

Codeforces Round #245 — Editorial [problem:430A] ------------------ The problem asks you to output “-1” if there is no solution. A natural question is now: “when there is no solution”? Try to come up with a test like this! After some analysis, you’ll see anyhow we draw the points and the lines, there will always be a solution. By manually solving small cases, you might already have found the pattern. But for now, let’s assume anyhow we draw points and lines, there will always be a solution. Let’s have a fixed set of points. Then, anyhow we draw a line, there should still be a solution. So, we need to find a coloring of points, such as for every line, |number of red points which belong to it – number of blue points which belong to it| <= 1. Suppose anytime you color a point with red you assign it +1 value. Also, anytime you color it with blue you assign it -1 value. Then, for a segment, the drawing is good if S = sum of values assigned to points that belong to segment is between -1 and 1 (in other words |S| ...

Full text and comments »

Contests hack statistics (Number of hacks by round) Just felt like gathering some data about hacks. Parsed around ~400 last contests Probably it would be worth it to also include SFT, but whatever Educational 96 is not finished yet but also whatever Last 100 ------------------ **847** Educational Codeforces Round 96 (Rated for Div. 2) **30** Codeforces Global Round 11 **248** Codeforces Round #674 (Div. 3) **0** 2020 ICPC, COMPFEST 12, Indonesia Multi-Provincial Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred) **97** Bubble Cup 13 &mdash; Finals [Online Mirror, unrated, Div. 2] **86** Bubble Cup 13 &mdash; Finals [Online Mirror, unrated, Div. 1] **20** Codeforces Round #675 (Div. 2) **1** Codeforces Round #672 (Div. 2) **70** Codeforces Round #671 (Div. 2) **58** Educational Codeforces Round 95 (Rated for Div. 2) **3** Codeforces Round #673 (Div. 2) **11** Codeforces Round #673 (Div. 1) **73** Codeforces Round #667 (Div. 3) **121** Grakn Forces 2020 **4** Co...

Full text and comments »

Unknown Language Round #2 <p> Итак, языком этого раунда является Io. Io (первая буква — заглавная i) — скриптовый, чисто объектно-ориентированный язык программирования с динамической типизацией. Язык был разработан Стивом Декортом (Steve Dekorte) в 2002 году. Реализация является кросплатформенной, открытой (лицензия BSD) и рассчитана на лёгкость встраивания в качестве скриптового языка (из Wikipedia). Версия, установленная на Codeforces — Io-2008-01-07 (Win32).</p> <p>Одна из основных особенностей языка — минималистичность синтаксиса. Код знаменитой программы "Hello World!" на этом языке выглядит так:</p> <pre style="background-color: rgb(238, 238, 238);">"Hello World!" println</pre> <p>А вот пример решения задачи "A+B" (числа заданы на разных строках): </p> <pre style="background-color: rgb(238, 238, 238);">a := File standardInput readLine asNumber b := File standardInput readLine asNumber c := a+b c println </pre> <p> Вы можете скачать интерпретатор <a href="http://www.iolanguage.com/...

Full text and comments »

Codeforces Global Rounds 2020: Final Results In 2020, with the support of XTX Markets, 6 rounds of the Codeforces Global Rounds were held. Each round was common for both divisions. All such rounds were rated for all participants. At each such round, 50 brand T-shirts were handed out, and we gave T-shirts to all problem writers! I say a big thank you to XTX Markets (and personally to Yuri Bedny and Alexander Gerko) for supporting Global Rounds. Without your help, we could not host them! I sincerely admire companies like these who come to support and develop the community that some of their employees come from. It will be great if other companies follow the example and also offer their help. We need it! The prizes for the 6-round series in 2020: - In each round, top-100 participants get points according to the [table](https://pastebin.com/QT5sXEaT). - The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest. - The best 20 participants over all series get...

Full text and comments »

Codeforces Global Rounds 2019: Final Results In 2019, with the support of XTX Markets, 6 rounds of the new Codeforces Global Rounds were held. Each round was common for both divisions and had 7–9 problems. The duration of the rounds was 2-3 hours, depending on the number and complexity of the problems. All such rounds were rated for all participants. At each such round, 50 brand T-shirts were handed out, and we gave T-shirts to all authors and problem testers as well. The prizes for the 6-round series in 2019: - In each round, top-100 participants get points according to the [table](https://pastebin.com/QT5sXEaT). - The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest. - The best 20 participants over all series get sweatshirts and place certificates. Final results: [cut]<br/> | Place | Contestant | = | Round 1 | Round 2| Round 3 | Round 4 | Round 5 | Round 6 | | - | - | - | - | - | - | - | - | - | | 1 | [user:tourist,2019-12-17] | <b> 2987 </b> | ...

Full text and comments »

Codeforces Global Rounds 2019: Current Results After Four Rounds In 2019, with the support of XTX Markets, 6 rounds of the new Codeforces Global Rounds will be held. These will be common rounds for both divisions of 7–9 problems each. The duration of the rounds will be 2-3 hours, depending on the number and complexity of the problems. All such rounds will be rated for all participants. <i>At each such round, 50 brand T-shirts will be handed out, and we will be happy to give T-shirts to all authors and problem testers.</i> The prizes for the 6-round series in 2019: - In each round top-100 participants get points according to the [table](https://pastebin.com/QT5sXEaT). - The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest. - The best 20 participants over all series get sweatshirts and place certificates. Current standings after four rounds: | Place | Contestant | = | Round 1 | Round 2| Round 3 | Round 4 | | - | - | - | - | - | - | - | | 1 | [user:tourist,2019-07-21] | 241...

Full text and comments »

Codeforces Global Rounds 2020: Current Results (GR7-GR9) In 2020 (as in 2019), with the support of XTX Markets, 6 rounds of the new Codeforces Global Rounds will be held. These will be common rounds for both divisions of 7–9 problems each. The duration of the rounds will be 2-3 hours, depending on the number and complexity of the problems. All such rounds will be rated for all participants. <i>At each such round, 50 brand T-shirts will be handed out, and we will be happy to give T-shirts to all problem authors and problem testers.</i> The prizes for the 6-round series in 2020: - In each round top-100 participants get points according to the [table](https://pastebin.com/QT5sXEaT). - The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest. - The best 20 participants over all series get sweatshirts and place certificates. Current standings after three rounds (sorted by total points in three rounds): | Place | Contestant | = | GR 7 | GR 8 | GR 9| |--|--|--|--|--|--| ...

Full text and comments »

Codeforces Global Rounds 2020: Current Results (GR7-GR10) In 2020 (as in 2019), with the support of XTX Markets, 6 rounds of the new Codeforces Global Rounds will be held. These will be common rounds for both divisions of 7–9 problems each. The duration of the rounds will be 2-3 hours, depending on the number and complexity of the problems. All such rounds will be rated for all participants. <i>At each such round, 50 brand T-shirts will be handed out, and we will be happy to give T-shirts to all problem authors and problem testers.</i> The prizes for the 6-round series in 2020: - In each round top-100 participants get points according to the [table](https://pastebin.com/QT5sXEaT). - The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest. - The best 20 participants over all series get sweatshirts and place certificates. Current standings after four rounds (sorted by total points in four rounds): | Place | Contestant | = | GR 7 | GR 8 | GR 9 | GR 10| |--|--|--|--|--...

Full text and comments »

HELP! RANKED ~400 IN LAST DIV. 4 ROUND BUT DISQUALIFIED DUE TO CHEATING??? Hello, Yesterday was my first time solving all questions in a round, and I was able to rank among the top ~400 (~90 officially) contestants. When the ratings came out, I was shocked because I found out I was DISQUALIFIED DUE TO CHEATING. I was supposed to get a positive delta but I found that I got a negative delta of 144, and I became a newbie. What's most surprising is that the solution my submission is supposed to coincide with does not by any means "coincide" with my solution. Here's my submission [submission:175959376] and that's the other submission [submission:175924333]. As you can see, there is no "significant coincidence" and I don't like the fact that I literally did all my best in a round but all that effort was worthless because of something I did not do. Please help me by upvoting. I hope this post reaches [user:MikeMirzayanov,2022-10-14]. Update: I got my rating back and a positive delta of 191. Thank you for everyone who helped<3

Full text and comments »

IOI Training contest #4 Hi everybody :D <br> One week ago i've participated in the [APIO2016](http://apio2016.org/) and my score was 61 and it's very bad , i felt like a looser so i stopped the **IOI Training contests** , but now i have pushed the reset button and returned to my normal mood :D <br> so i'm going to invite to participate in the **IOI Training Contest #4** . <br> the problems are from **USACO 2012 November Contest** 2 gold 2 silver as usual . <br> it will be held in [17/May/2016 on 18 MSK](http://www.timeanddate.com/worldclock/fixedtime.html?msg=IOI+training+contest+%234&iso=20160517T18&p1=166&ah=5) . <br> the contest's duration is 5 hours as usual . <br> the contest's URL : [https://www.hackerrank.com/ioi-training-contest-4](https://www.hackerrank.com/ioi-training-contest-4) . <br> i will add the names of the top 3 competitors and the links to the tutorials to the post after the contest . <br> and let's discus here about the problems after the contest :D <br> hope u enjoy and learn :D...

Full text and comments »

A question about memory usage in Python3 I'm trying to solve the python indentation problem in [round 455C](http://mirror.codeforces.com/problemset/problem/909/C). My [submission](http://mirror.codeforces.com/contest/909/submission/33846423) is receiving a memory limit exceeded. Memory limit is: 256 * 1024 * 1024 = 268435456 bytes In my code I am using at most a 5000*5000 matrix to hold the dp values and this will occupy ~ 200000064 bytes I am also using a string to hold the program and it will occupy: 5049 bytes I am using about 6 int variables in my program and then will occupy: 6 * 28 = 168 bytes so in total: 200005281 bytes Or 191 MB. So According to my calculations I am still bellow 200 MB, but in CF I am exceeding 256MB. Is there something that I am missing in the memory computation? Is the python interpreter size counted wi...

Full text and comments »

Strange situation(three different results with different compilers) Hello, Codeforces. I've sent three submissions with different compilers on problem [problem:1553E] from last round and got different results(OK, ML 1, WA 1) [submission:123344376] [submission:123363613] [submission:123363479] Then i've ran valgrind (g++ 11.1.0) and discovered strange "still reachable" memory addresses, somehow connected with ios_base::sync_with_stdio. Then I realised, that fast IO was in solve function, which is called in main $T$ times for each test case. Then I moved it to main and got OK in all compilers. <spoiler summary="valgrind output on sample"> ~~~~~ ==36581== ==36581== HEAP SUMMARY: ==36581== in use at exit: 122,880 bytes in 6 blocks ==36581== total heap usage: 120 allocs, 114 frees, 197,964 bytes allocated ==36581== ==36581== 8,192 bytes in 1 blocks are still reachable in loss record 1 of 6 ==36581== at 0x484021F: operator new[](unsigned long) (vg_replace_malloc.c:579) ==36581== by 0x4982194: _M_allocate_internal_...

Full text and comments »

Blog collection <p>________________________________________________________________________________________<br><br></p><h3><b>Puzzle</b></h3><ul><li><a href="http://mirror.codeforces.com/blog/entry/66">Red and Black hair</a>, </li><li><a href="http://mirror.codeforces.com/blog/entry/112">The 12 chairs and diamonds</a></li><li><a href="http://mirror.codeforces.com/blog/entry/228">Monty Hall Problem</a></li></ul><br><br><h3>Useful <br></h3><ul><li><a href="http://mirror.codeforces.com/blog/entry/70">Petr Mitrichev, 3 days in Sao Paulo Training Camp 2010</a></li><li><a href="http://mirror.codeforces.com/blog/entry/512">Useful links</a></li><li><a href="http://mirror.codeforces.com/blog/entry/529">Problem Set Analysis Of CodeForces</a></li><li><a href="http://mirror.codeforces.com/blog/entry/546">Discussions Of CodeForces Round</a></li><li><a href="http://mirror.codeforces.com/blog/entry/1492">ALL CodeForces rounds Tutorial</a></li><li><a href="http://mirror.codeforces.com/blog/entry/1534">Online Judge Locator</a></li><li><a href="http://mirror.codeforces.com/blog/entry/170...

Full text and comments »

Mail.Ru Cup 2018 — Results of R1+R2+R3 Here are merged results of [contest:1054], [contest:1055] and [contest:1056] according to the GP100 scores (see the announcement for the details https://mirror.codeforces.com/blog/entry/62355). Best two contests give the summary score of a participant. This table is unofficial yet. But anyway... congratulations to the winnerzzzz! | Place | Contestant | = | Round 1 | Round 2 | Round 3| | - | - | - | - | - |-| | 1 | [user:mnbvmar,2018-11-25] | 1497 | 1000 | 497 | 29 | | 2 | [user:V--o_o--V,2018-11-25] | 1281 | 575 | 575 | 706 | | 3 | [user:Radewoosh,2018-11-25] | 1265 | &mdash; | 265 | 1000 | | 4 | [user:aid,2018-11-25] | 1204 | 204 | 1000 | 142 | | 5 | [user:LHiC,2018-11-25] | 1203 | 497 | 706 | 226 | | 6 | [user:Um_nik,2018-11-25] | 997 | 706 | 291 | 235 | | 7 | [user:ksun48,2018-11-25] | 788 | 291 | &mdash; | 497 | | 8 | [user:SpyCheese,2018-11-25] | 742 | 371 | 371 | 265 | | 9 | [user:RAVEman,2018-11-25] | 619 | 19 | 176 | 443 | | 10 | [user:scott_wu,2018-11-25] | 614...

Full text and comments »

Codeforces Round #191 -Tutorial simpler solution to hungry sequence Here's simpler solution to codeforces round 191(div 2) ,question hungry sequence- https://mirror.codeforces.com/contest/327/problem/B Suppose we are given the number N. We can observe that for any N ,number divisible by N is always greater than or equal to 2*N, so we select numbers N+0,N+1,N+2,.......N+N-1 .So, Here we N satisfying conditions of hungry sequence.

Full text and comments »

[Tutorial] DP on Edges *This blog post is a submission for the [Codeforces Month of Blog Posts Pt. III](https://mirror.codeforces.com/blog/entry/149422) challenge. Thank you [user:cadmiumky,2026-02-12] for the initiative!* ## Introduction Problem <spoiler summary="ICPC North America Championship 2025, Problem B - Circle of Leaf"> Link: <https://qoj.ac/contest/2041/problem/11357> Given a rooted tree with $n$ nodes, construct a undirected graph as follows: - For each edge $(u, v)$ in the tree, add an edge between $u$ and $v$. - For each leaf node $u$ in the tree, add an edge between $u$ and the root. Please calculate the number of spanning trees of the resulting graph, modulo $998\,244\,353$. Note that the resulting graph may contain multiple edges between the same pair of nodes. Constraints: - $n \le 200\,000$ </spoiler> Before tackling the problem, let's first try some simple examples. The notation we use will also be introduced in the examples, so please try to understand them ...

Full text and comments »

CSES Graph Algorithms solution Hello Codeforces, this is my first blog and here I have given my solution of the complete CSES Graph Algorithms section. [This](https://github.com/SamudraMitra/cses) is the github repo where I have pushed all the cpp files: Counting Rooms ------------------ <spoiler summary="Thinking"> used simple bfs in a grid </spoiler> <spoiler summary="Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; ll dx[] = {1, 0, -1, 0}; ll dy[] = {0, 1, 0, -1}; bool inrange(ll x, ll y, ll n, ll m) { if (((0 <= x) && (x < n)) && ((0 <= y) && (y < m))) return true; return false; } int main() { ll n, m; cin >> n >> m; vector<string> v(n); vector<vector<ll>> vis(n, vector<ll>(m)); for (auto &i : v) { cin >> i; } ll cnt = 0; queue<pair<ll, ll>> q; for (ll i = 0; i < n; i++) { for (ll j = 0; j < m; j++) { if (v[i][j] == '#') co...

Full text and comments »