Codeforces Round #764 (Div. 3) Hello! [contest:1624] will start at [contest_time:1624]. You will be offered 7-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of **open hacks**. You will be given **7-8 problems** and **2 hours and 15 minutes** to solve them. One of the problems in this round is **interactive**. Don't forget to read the [guide on interactive problems](https://codeforces.com/blog/entry/45307). Note that the **penalty** for the wrong submission in this round is **10 minutes**. [Remember](https://codeforces.com/blog/entry/59228) that only the trusted participants of the third division will be included in the official s...

Full text and comments »

Seemingly hard problems trivialized by a single simple observation Here I've enumerated some of my favorite problems. The solutions appear trivial in retrospect &mdash; but the 1 line observation is quite hard to come up with. You have to think really outside of the box for these! I think such problems are quite cool and hard to come by, so please add a comment if you have any other problems of this type that you've seen! They are arranged from easiest to hardest (in my opinion). 1) For $N<10^6$, what's the Nth palindromic number in base 10 with an even number of digits? (The first is 11, then 22, 33, 44, 55, 66, 77, 88, 99, 1001). Key observation: <spoiler summary="Spoiler"> Just concatenate N with itself backwards. </spoiler> Source: https://codeforces.com/contest/688/problem/B 2) A classic: $N < 10^6$ Ants are on a line of length $10^{15}$ at some positions $p_i$. Each has a starting position and direction left or right. They walk at a rate of 1 unit per second, and if 2 collide, both immediately turn around and walk the other...

Full text and comments »

So many "Fake" newbies in the contest The codeforces round #765 is over, among the top 10 rated users, 5 are newbies, 2 are specialist. Ranking are as below.  If you click on these newbie users, like the 3rd place @Alan_boyfriend, you can see the user previously take part in round 764 and rank 1st. The 8th place, @Asaoix, participated in round 763 and get 6th. And so on.... These newbies, I called, are **fake newbies.** Because they are not newbie level, they are far more than that. Some of the newbie users are even red level, they have low rating only because they are new users and only take a few contest, and the rating cannot accurately measure their level. Besides, you will not get your performance rating in the contest, if you get rank 1, your new rating will not be rank 1 rating, you new rank will based on your previous rating and this contest performance. If you have 1400 ratin...

Full text and comments »

Topcoder SRM 764 and Editorials Hey All! **UPD**: Editorials https://www.topcoder.com/blog/single-round-match-764-editorials/ **Topcoder SRM 764** is scheduled to start at [12:00 UTC -4, August 10, 2019](https://www.timeanddate.com/worldclock/fixedtime.html?msg=SRM+764&iso=20190810T12&p1=98). **Please Note**: This SRM will have a common problem set for both Div I and Div II. The difficulty level will be overall a bit easier than usual. 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 765 &mdash; August 23**](https://calendar.google.com/event?action=TEMPLATE&tmeid=MmNtNTRvcDJ1MXZyODdidWRiMmRjZm80M28gYXBwaXJpby5jb21fYmhnYTNtdXNpdGF0ODVtaGRybmc5MDM1amdAZw&tmsrc=appirio.com_bhga3musitat85mhdrng9035jg%40group.calendar.google.com) **Some Important Links** | ...

Full text and comments »

Codeforces Round #764 (Div. 3) Editorial [problem:1624A] Idea: [user:MikeMirzayanov,2022-01-12] <spoiler summary="Tutorial"> [tutorial:1624A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; #define forn(i, n) for (int i = 0; i < int(n); i++) void solve() { int n; cin >> n; int a[n]; for (int i = 0; i < n; ++i) { cin >> a[i]; } int MIN = INT_MAX; int MAX = INT_MIN; for (int i = 0; i < n; ++i) { MIN = min(MIN, a[i]); MAX = max(MAX, a[i]); } cout << MAX - MIN << '\n'; } int main() { int tests; cin >> tests; forn(tt, tests) { solve(); } } ~~~~~ </spoiler> [problem:1624B] Idea: [user:SixtyWithoutExam,2022-01-12] <spoiler summary="Tutorial"> [tutorial:1624B] </spoiler> <spoiler summary="Solution"> ~~~~~ #include<bits/stdc++.h> using namespace std; void solveTest() { int a, b, c; cin >> a >> b >> c; ...

Full text and comments »

A Recap of My First Year in CodeForces Hello all on Codeforces! ------------------ It’s been just over a full year since I created my Codeforces account. Since then a lot has happened on my Codeforces journey so far. With everything that’s happened I want to look back at how I got to my current point, share what I learned in the process, recap some of my best moments, and laugh at whatever I was thinking on a few of these contests, because a lot happened. The only issue is that there’s no way I’m going to detail all **60** contests I took part in 2022. Instead I’ve chosen to “award” the 9 most memorable contests, wheter it be because I did exceedingly well or self destructed in almost hilarious fashion. A few notes before I begin: No full solutions for any problems are shown in this post but there are code snippets and discussions that are spoilers for these problems. I apologize in advance. ### First Contest &mdash; [Hello 2022](https://codeforces.com/contest/1621) This was the first contest held in 2022, ...

Full text and comments »

To admins (cheater report) Hello everyone, I want to report 2 cheaters today. 2 days ago there was CF Round #395 Div2. I participated in contest also, problems were really good. Let's look [standings](http://codeforces.com/contest/764/standings). Hmm, good, 3 people solved all problems, 2 of them are Chinese. [user:ljh2000,2017-02-04] and [user:MashiroSky,2017-02-04]. Ok, I looked their profiles, saw that they are living in same place, studying in same school. Hmm, it doesn't like coincidence. Then I looked their solutions. Solutions for problem A: [user:ljh2000,2017-02-04]'s [solution](http://codeforces.com/contest/764/submission/24367006), and [user:MashiroSky,2017-02-04]'s [solution](http://codeforces.com/contest/764/submission/24365605). Looks similar, but it's easy problem, most peoples solutions looks same. Solutions for problem B: [user:ljh2000,2017-02-04]'s [solution](http://codeforces.com/contest/764/submission/24369314), [user:MashiroSky,2017-02-04]'s [solution](http://codeforces.com/contest...

Full text and comments »

Codeforces Beta Round #36 (Разбор задачи B) Авторское решение задачи строит фрактал при помощи рекурсивной функции. Пусть a - квадратная матрица размера $n^k \times n^k$ для записи результата. Напишем функцию fractal(x, y, k), которая заполняет квадратную часть матрицы с левым верхним углом (x, y) и длиной стороны $n^k$, рисуя в ней фрактал с глубиной $k$. В случае если k = 0 выводим точку. В противном случае требуется разбить имеющуюся часть матрицы на $n^2$ квадратов размера $n^{k-1} \times n^{k-1}$ и заполнить их в соответствии с шаблоном. Если соответствующий символ в шаблоне ''*'', то нужно весь квадрат заполнить символами ''*'', иначе запустить fractal(x1, y1, k-1), где (x1, y1) - координаты левого верхнего угла нового квадрата.<div><br></div><div>Более простое в реализации решение предлагает&nbsp;<span class="Apple-style-span" style="border-collapse: collapse; font-family: verdana, arial, sans-serif; font-size: 12px; "><a href="http://codeforces.com/profile/kdalex" title="Лейтенант kdalex" class="rated-user user-blue" styl...

Full text and comments »

WHY TLE ? I have written the code to solve [this](http://codeforces.com/contest/764/problem/C) problem, but it gives TLE. I think the complexity of my soln. is O(n). My approach is as follows: `Let dp[from][to] = 1 if all nodes in the subtree of "to" (including "to") are of the same color when we perform dfs from node "from" and "to" is the child of node "from".` `dp[from][to] = 0, otherwise.` `To calculate dp[from][to] we use dfs. Let node "to" have k children, then let's compute dp[to][child] for all children of "to".` `Then dp[from][to] = 1 if and only if dp[to][child]==1 for all children of "to" and the color[child]==color[to] for all children of "to".` `Otherwise, dp[from][to]=0;` Now, to compute the final answer, Let's iterate over all "from" nodes, and for each "to" such that "to" is adjacent to "from", if dp[from][to]==1, then final answer="YES", and node="from". If no such "from" is found then answer="NO"; `But this looks like O(n^2) solution. But, if w...

Full text and comments »

Intuition Behind Codeforces Round #764 (Div. 3) Hello codeforces! Too often, I find editorials with only the solutions to the problems, without any explanation as to how one is to derive them. Whilst I appreciate that there are infinite intuitions and derivations leading to any solution, I thought it would be good if I shared my own intuition, so hopefully people can learn and apply similar ideas and techniques for future problems! I've made a video editorial explaining my intuition at https://youtu.be/3X-1PBLepwY for anyone who is interested, as well as my 35th place commentated screencast at https://youtu.be/q_RPqdRjmuM ! If there is enough demand, I'll also write my intuition in this blog. Wish you all good luck in the future!

Full text and comments »

[Java] What's wrong on my code Hi. I've submitted [Problem C](http://codeforces.com/contest/764/problem/C)[ Round #395 (Div. 2)](http://codeforces.com/contest/764). Why when I change these line ~~~~~ u=nodeColor.get(i); v=nodeColor.get(a.get(i).get(j)); if (u!=v) ~~~~~ [>>Full code](http://codeforces.com/contest/764/submission/24436228) become ~~~~~ if ((Integer)nodeColor.get(i)!=(Integer)nodeColor.get(a.get(i).get(j))) ~~~~~ [>>Full code](http://codeforces.com/contest/764/submission/24436281) it get wrong answer? Thanks!

Full text and comments »

Problems that I authored so far Hi everyone! Today I saw a discussion in AC Discord server about how many problems some people made for different competitions. It was sparkled by [this](https://codeforces.com/blog/entry/108595) CF entry. I haven't keep track of this before, so it made me curious to go through everything that I made and publish in a comprehensive list. I'm doing it mostly out of curiosity, but maybe it might be interesting for someone else too :) [cut]<br> | # | Date | Problem | Contest | Comment | |-|-|-|-| | 1 | Jan 2016 | [Sasha and Swaps](https://www.hackerrank.com/contests/infinitum14/challenges/sasha-and-swaps/problem) | Ad Infinitum 14 | Find a $T$-th root of a given permutation, while minimizing the number of swaps in which the root may be decomposed. | | 2 | Aug 2015 | [Sasha and swag strings](https://acm.timus.ru/problem.aspx?space=1&num=1799) | Ptz Summer 2015. MIPT Contest | Compute the total number of distinct substrings on all edges of a given string's suffix tree. | | 3 | ...

Full text and comments »

764C — Timofey and a tree Getting TLE Hello codeforces community , i am getting TLE . My logic is : First i store those edges node to set<int> those which color are different , then i put a simple dfs on each of the node stored in set<int> which will be exact for root i break the loop and print it . If i aint found a node , print no . Now I understand for which case i got TLE . If i can stop calling dfs again and again , i can reduce TLE . But can find the logic . - [MY CODE](http://codeforces.com/contest/764/submission/24403582) - [problem](http://codeforces.com/contest/764/problem/C)

Full text and comments »

Codeforces Popularity Ranking Hello Codeforces! There has been several blogs similar to this. I know about [TOP 15 most popular users on codeforces](http://codeforces.com/blog/entry/49122) and [Who is the most popular?](http://codeforces.com/blog/entry/21041). But as none of these are updated, I thought this might be helpful. I have just calculated the most popular handles in Codeforces. I only considered those handles which have at least one rated contest. Begging my pardon to them who hasn't participated in any rated round. And here, the popularity depends simply on the number of people you are friend of. The complete standings can be found [here](https://docs.google.com/spreadsheets/d/1ADlF-bd6pBYCap75yzf-pUnVwI9f9YmPkiYNW3lD-xo/edit?usp=sharing)(This may took a while to load at the bottom). Anyway here is Top 200 handles. | Rank | Handle | Follower | |---|---|---| 1. | [user:tourist,2018-08-22] | 14082 | 2. | [user:Petr,2018-08-22] | 6430 | 3. | [user:OO0OOO00O0OOO0O00OOO0OO,2018-08-22] | 420...

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 »

Задача на динамическое программирование Всем привет! Помогите решить задачу. Есть територия n*m(матрица). Есть размер дома a*b. На некоторых клетках територии ростут деревья, поэтому на них нельзя строить деревья. Нужно посчитать количество способов построить дом. [Ссылка](http://www.e-olimp.com/ua/problems/764)

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 »

Teams going to Gwalior/Pune Regionals **UPDATE:** I've uploaded the code that I used to generate this on Github, in case someone needs to generate something similar: [Codeforces Team Rating Calculator](https://github.com/abdullah768/Codeforces-Team-Rating-Calculator) The regional round has ended and here's the final Ranklist: https://www.codechef.com/public/rankings/ACM18GWR Inspired by the list of teams going to Kharagpur regionals, I decided to make one for Gwalior/Pune regionals. The list contains all the teams from the official Gwalior website. If you know the usernames of members of any of the teams. Please update the excel file: ### [HERE] (https://docs.google.com/spreadsheets/d/1jRvwzQzp1DOcazgI7jXBB8uY3u7Ze_eQ77Xa75_Q810/edit?usp=sharing) Team rating calculation has been done according to the official Codeforces team rating calculation formula. The table will be updated with details from the excel file every 6 hours or so. Last Updated: 10 pm, 12th December IST | No. | AIR | Team Name ...

Full text and comments »

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

Full text and comments »