Codeforces Round #766 (Div. 2) omg hi Codeforces! [user:ScarletS,2022-01-12], [user:flamestorm,2022-01-12], [user:fishy15,2022-01-13], [user:saarang,2022-01-12], <a class="rated-user user-orange" href="/profile/lookcook" title="Did no work and cried for name to be here">lookcook</a> and I are glad to invite you to our Codeforces round, [contest:1627], which will be held on [contest_time:1627]. **This round will be rated for participants with rating lower than 2100**. We would like to thank: - [user:Monogon,2022-01-12] senpai for excellent coordination of the contest. - [user:MikeMirzayanov,2022-01-12], for creating the amazing Codeforces and Polygon platforms! - [user:KAN,2022-01-15], for Russian translations! - [user:dorijanlendvaj,2022-01-12], [user:errorgorn,2022-01-12], [user:PurpleCrayon,2022-01-12], [user:generic_placeholder_name,2022-01-12], [user:blue,2022-01-12], [user:polarity-,2022-01-12], [user:atharv,2022-01-12], [user:epicxtroll,2022-01-12], [user:dbsic211,2022-01-12], [user:StArChAn...

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.com/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.com/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 »

Codeforces Round #766 (Div. 2) Editorial Thank you for participating in our contest! We hope you enjoyed it. [problem:1627A] <spoiler summary="Hint 1"> When is the answer $-1$? When is the answer $0$? When is the answer $1$? </spoiler> <spoiler summary="Hint 2"> Can you do all remaining cases in $2$ steps? </spoiler> <spoiler summary="Solution"> [tutorial:1627A] </spoiler> <spoiler summary="Implementation (C++)"> [submission:142882991] </spoiler> <spoiler summary="Implementation (Java)"> [submission:142882684] </spoiler> <spoiler summary="Implementation (Python)"> [submission:142882963] </spoiler> <spoiler summary="Video Editorial"> https://www.youtube.com/watch?v=j_oe8DA4hhM </spoiler> [problem:1627B] <spoiler summary="Hint"> If the classroom was one-dimensional, i.e. $n = 1$, where would the best place for Tina to sit be? </spoiler> <spoiler summary="Hint Solution"> The best place for Tina to sit a grid where $n = 1$ would be either $(1, 1)$, or $(1, m)$. </spoiler> <spo...

Full text and comments »

Как решать задачи на ДП: Обычный подход Привет! В прошлом посте я ввёл два вида динамического программирования: _обычное_ и _с симуляцией процесса_. В нём я рассказал, как решать задачи на ДП, используя симуляцию процесса, пожалуйста, прочитайте, если пропустили, чтобы понимать разницу. Сейчас же я хочу поговорить о хитростях, которые помогают мне при решении задач на ДП обычным подходом. Тогда как в симуляции процесса нам требовалось изобрести некий процесс, который бы строил нам необходимые объекты, **в обычном подходе мы будем работать с объектами напрямую**. Каждое состояние ДП _(т. е., набор значений по каждому параметру)_ будет соответствовать некому классу желаемых объектов, а соответствующее значение в таблице ДП будет содержать информацию об этом классе, _что в действительности эквивалентно формулировке через подзадачи, описанной в предыдущем посте_. В этом посте я сосредоточусь на том, как придумывать переходы в ДП с обычным подходом, если вы уже определились с параметрами. Общий план такой: 1. Сформулируй...

Full text and comments »

Graph Theory Playlist Hello everyone, After concluding my DP playlist on YouTube where I discussed my solutions to 18 intermediate level DP problems (rated 1600 to 2000), I just started a Graph Theory Problem Solving playlist where I plan to post my solutions to intermediate level graph theory problems every 2nd day during the month of June 2021. [DP Playlist] (https://www.youtube.com/playlist?list=PLzVLIdIx9dQxwAN5mMkzdvK2B4rV8879j) [Graph Theory Playlist] (https://www.youtube.com/playlist?list=PLzVLIdIx9dQwzso2IwXCQq3aEicK02iKF) [Tutorial on DFS on Tree] (https://www.youtube.com/watch?v=0vNXkdPserI) The problem list is as under: 1) **Kefa and Park (Round 321 Div 2 C Rated 1500)** &mdash; DFS on a Tree [Problem Link] (https://codeforces.com/contest/580/problem/C) [Video Editorial Link] (https://www.youtube.com/watch?v=hXv0KBoFDBY) 2) **Graph Without Long Directed Paths (Round 550 Div 3 F Rated 1700)** &mdash; Bipartite Graphs; 2-Coloring [Problem Link] (https://codeforces.com/...

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 »

DP Tutorial and Problem List Today I've listed some DP tutorials and problems. Actually, I made it for my personal practice. But I think It may Help others too. Update: I write stuff [Here](https://duoblogger.github.io) in Bengali. I probably have one or two basic DP tutorials too. If you understand Bengali, it may help. **Note: If you have some other tutorial links and nice problems, mention them. I'll add them here. It'll help me too.** ## Dynamic programming: * [Topcoder Tutorial](https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/) * [Dynamic Programming,from novice to advanced](https://www.cnblogs.com/drizzlecrj/archive/2007/10/26/939159.html) * [Learn DP and other tricks](https://www.codechef.com/certification/data-structures-and-algorithms/prepare#foundation) * [Non-trivial DP tricks](https://codeforces.com/blog/entry/47764) * [Everything about Dynamic Programming](https://codeforces.com/blog/entry/43256) * [Digit DP 1](https://...

Full text and comments »

Topcoder SRM 766 Hey All! **Topcoder SRM 766** is scheduled to start at [21:00 UTC -4, Sept 10, 2019](https://www.timeanddate.com/worldclock/fixedtime.html?msg=SRM+766&iso=20190910T21&p1=98). Problem Writer:[misof](http://www.topcoder.com/members/misof) Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins. Good luck to everyone! **[Topcoder Java Applet](http://www.topcoder.com/contest/arena/ContestAppletProd7.2.jnlp)** | [**Next SRM 767 &mdash; Sept 18**](https://calendar.google.com/event?action=TEMPLATE&tmeid=NGpkZ2Jrb3BtNXBhaTdvMWxwOWNzdjZoZ2ogYXBwaXJpby5jb21fYmhnYTNtdXNpdGF0ODVtaGRybmc5MDM1amdAZw&tmsrc=appirio.com_bhga3musitat85mhdrng9035jg%40group.calendar.google.com) **Some Important Links** | | | |---------------------------------------------------------...

Full text and comments »

Topcoder SRM 765 - Begins in 3 hours Hey All! **Topcoder SRM 765** is scheduled to start at [11:00 UTC -4, August 23, 2019](https://www.timeanddate.com/worldclock/fixedtime.html?msg=SRM+765&iso=20190823T11&p1=98). Problem Writer: [misof](http://www.topcoder.com/members/misof) Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins. Good luck to everyone! **[Topcoder Java Applet](http://www.topcoder.com/contest/arena/ContestAppletProd7.2.jnlp)** | [**Next SRM 766 &mdash; Sept 10**](https://calendar.google.com/event?action=TEMPLATE&tmeid=MjI0cnNjODZmZDBiNDduN2RiNm1wMjczNGYgYXBwaXJpby5jb21fYmhnYTNtdXNpdGF0ODVtaGRybmc5MDM1amdAZw&tmsrc=appirio.com_bhga3musitat85mhdrng9035jg%40group.calendar.google.com) **Some Important Links** | | | |------------------------------------------------------...

Full text and comments »

Hello again :) Cheater/Glitcher Report #2 Hello CF, if you read my first post, you know me ;) . Lets see who "cheated". I was looking [standings](http://codeforces.com/contest/766/standings) of Codeforces Round #396 (Div. 2), then I saw interesting one, someone unrated solved just last problem. S/he solved problem in 1:19, so s/he had time to solve at least problem A. I guess that it's someone's fake account to check s/his solution. See our fake account's submission [here](http://codeforces.com/contest/766/submission/24507351). Good, he managed to solve problem E. Lets see who cheated, I saw him on comments many times, he is [user:Whistle,2017-02-13]! YES! You can see him on standings [here](http://codeforces.com/contest/766/standings/participant/11047244#p11047244). Lets look their submissions, [this](http://codeforces.com/contest/766/submission/24507816) is [user:Whistle,2017-02-13]'s submission, and [this](http://codeforces.com/contest/766/submission/24507351) is fake accounts. Same solution, but place of func...

Full text and comments »

DP Stream (Week 2) Hi CodeForces! Last week I made the dp video for [my class](https://codeforces.com/blog/entry/63884) public as a test, and it seemed really useful so I have decided to make all the videos public. The second class was also on dp because dp is a very important concept and it shows up very often. Here were the problems: [Problem 1](https://codeforces.com/group/hK6hgc8x94/contest/222255/problem/J) [Problem 2](https://codeforces.com/group/hK6hgc8x94/contest/222255/problem/D) [Problem 3](http://www.usaco.org/index.php?page=viewproblem2&cpid=766) [Problem 4](https://codeforces.com/group/hK6hgc8x94/contest/222255/problem/K) [Here](https://www.youtube.com/watch?v=EK5S1j6YCfM) is the stream with the discussion on how to come up with the solutions. (It starts at about 25 seconds)

Full text and comments »

Topics Problems Good Day to you! While a lot of us, when he begins to start competitive programming he found difficult to found problems on some topics in the beginning to practice of it, and same thing for a lot of ICPC Communites that they have started. These are some topic not advanced and videos, problems and articles on them. <br> <spoiler summary="Prefix Sum & Frequency Array"> [Wonderful Coloring](https://codeforces.com/contest/1551/problem/B1) [Do Not Be Distracted](https://codeforces.com/contest/1520/problem/A) [Letter](https://codeforces.com/problemset/problem/43/B) [Pangram](https://codeforces.com/problemset/problem/520/A) [Andryusha and Socks](https://codeforces.com/contest/782/problem/A) [Count Numbers](https://codeforces.com/group/c3FDl9EUi9/contest/262795/problem/A) [Count Characters](https://codeforces.com/group/c3FDl9EUi9/contest/262795/problem/B) [Range Sum Query](https://codeforces.com/group/c3FDl9EUi9/contest/262795/problem/E) [Count a's](https...

Full text and comments »

Every problem I ever made As you may [have seen](https://codeforces.com/contests/writer/flamestorm), I've written a lot of problems. In this post, I want to go over each of my problems and describe my thought process for how I created each problem. I got this idea from [user:antontrygubO_o,2023-01-21], but I was also inspired by [user:McDic,2023-01-21]'s editorials that included a "behind story" for each problem. Anyway, I thought it would be fun to give you all a glimpse into my thought process: where my ideas came from, the obstacles I encountered along the way, and any random tidbits that give a bit more pizzazz to the problems. I think it's important to remember that problem-writing is a creative endeavor, so I hope you'll enjoy reading about the making of my problems as much as I enjoyed creating them. And who knows, maybe you'll even be inspired to write some problems of your own. Also, spoilers for a lot of problems. Obviously. <table> <thead> <tr> <th>ID</th> <th>Problem</th> ...

Full text and comments »

Country statistics Hi guys! I have prepared for you some statistics on how countries are performing against each other in Codeforces which I hope you will find interesting! ## Top 5 countries with the most users with certain rank:  ## Top 5 countries with highest percentage of their users in a certain rank: (Here I don't count countries that have less than 10 Codeforces users)  #### Newbie:  #### Pupil:  #### Specialist:  #### Expert:  #### Candidate Master:  #### Master: ![ ](/pre...

Full text and comments »

Simple training for beginners (practice) Hello everyone! I have set up a training for beginners, The training focuses on solving various problems on Codeforces. Training that contains: 100 Problems (<span style = "font-weight: bold;">A</span>) and 100 Problems (<span style = "font-weight: bold;">B</span>). and 50 Problems (<span style = "font-weight: bold;">C</span>). Tags of problems in the training: <spoiler summary="Spoiler"> <ul> <li>math.</li> <li>strings.</li> <li>number theory.</li> <li>binary search.</li> <li>bitmasks.</li> <li>data structures.</li> <li>games.</li> <li>brute force.</li> <li>greedy.</li> <li>geometry.</li> <li>two pointers.</li> <li>constructive algorithms.</li> <li>implementation.</li> <li>combinatorics.</li> </ul> </spoiler> Problems Difficulty: from <span style = "font-weight: bold;">800</span> to <span style = "font-weight: bold;">1500</span>. Problems links: <spoiler summary="100 Problems A"> <ol> <li><a href = "https://codeforces.com/problem...

Full text and comments »

Problems that I authored so far Hi everyone! I have been inspired [by](https://codeforces.com/blog/entry/108940) [recent](https://codeforces.com/blog/entry/108595) [events](https://codeforces.com/blog/entry/113093) to write this blog post. This list is not comprehensive, but mostly because I do not keep detailed logs of problems I have written. There are a few things you will notice after reading through these problems. In no particular order: 1. Most of these problems are not "high-quality" &mdash; they would never see the light of day on a CF round for example. This is mostly due to my lack of skill in generating "high-quality" problems. You'll see that a lot of my problems are generated from observing real-life events and then constructing problems out of those scenarios. There are many ideas that have been proposed and thrown into the void because they were worse. I think there are a couple problems in this list that are actually good problems, but most of them I am not particularly proud of. 2. The diffic...

Full text and comments »

Help needs in a DP.. I can't solve [this](http://informatics.mccme.ru/mod/statements/view3.php?id=766&chapterid=1791#1) problem for a long time. Can you help me? Thank you!

Full text and comments »

Codeforces Global Rounds 2021: Current Results (GR13-GR17) In 2021 (as in 2019 and 2020), with the support of XTX Markets, 6 rounds of the new Codeforces Global Rounds are held: common rounds for both divisions of 7–9 problems each. The duration of the rounds is 2-3 hours, depending on the number and complexity of the problems. All such rounds are rated for all participants. <i>At each such round, 50 brand T-shirts are handed out, and we are happy to give T-shirts to all problem authors.</i> The prizes for the 6-round series in 2021: - 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 five rounds he placed the highest. - The best 20 participants over all series get sweatshirts and place certificates. Current standings after five rounds (sorted by total points in four best placed rounds): | Place | Contestant | = | GR 13 | GR 14 | GR 15 | GR 16 | GR 17| | - | - | - | - | - | - | - | - | | ...

Full text and comments »

Any tips to deal with UVA input ? UVA input format is very frustrating to deal with, or that what I see. For example this [UVA 825 problem](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=766) Anyone can help how to deal with this type of input format and other formats like not giving the number of testcases, the input ends by a newline and other things like those ? :)

Full text and comments »

First Ever Users to Reach Some Rating Milestones Revised: ratings below 1500 and greatest rises Several days ago I published a [table](https://codeforces.com/blog/entry/104320) with first people to reach certain ratings. It featured only ratings above 1500, and [user:adamant,2022-07-09] advised to do the same, but on achieving ratings below 1500. I found it quite interesting, and, after several days of collecting data about participations of 447911 Codeforces users, I finally made this table. [cut] For several reasons I firstly put another table. This is the table of greatest rating rises in the history of Codeforces. The reasons are: 1. I have collected so much data from Codeforces that it would be blasphemy not to use it in as many ways as possible. 2. These tables might intersect a lot: it's easier to get a terrific rise in ratings if you are low-rated. (Many people abuse this and deliberately get very low-rated to make a great jump.) 3. Someone recently posted a table with greatest rating rises and falls. I wasn't able to find this table to check whether it was...

Full text and comments »