Codeforces Round #660 (Div. 2) Hello, Codeforces! We ([user:Denisov,2020-07-27], [user:Karavaev1101,2020-07-27], [user:perekopskiy,2020-07-27]) are glad to introduce to you [contest:1388], which will happen on [contest_time:1388]. **The round will be rated for the participants with rating lower than 2100**, although higher rated users are more than welcome to take part out of competition. Huge thanks to those who helped make this round possible: - [user:adedalic,2020-07-27] for amazing coordinating and reviewing the round, as well as helping with many different things. - [user:Karavaev1101,2020-07-27], [user:perekopskiy,2020-07-27] for creating problems and preparation. - [user:dorijanlendvaj,2020-07-27], [user:Tlatoani,2020-07-27], [user:BOGDAN_,2020-07-27], [user:gachiBASS,2020-07-27], [user:pikmike,2020-07-27], [user:antontrygubO_o,2020-07-27], [user:Osama_Alkhodairy,2020-07-27], [user:growup974,2020-07-27], [user:errorgorn,2020-07-27], [user:ilyasiv,2020-07-27], [user:Tathagat_shah,2020-07-28], [user:...

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 »

Why no floating point precision errors? I solved a problem recently using floating point arithmetic. I suspect the solution should not work for some test case because of floating point precision errors, but cannot find a case where it would fail. Moreover, the solution gets "Accepted" verdict. Link to the submission (Codeforces Round #660 E): [submission:89366718] The submission is an implementation of the Convex Hull Trick approach mentioned in the [editorial](https://mirror.codeforces.com/blog/entry/80828) of the problem. If you look through the code, you will find that I have maintained forbidden ranges of cotangents of an angle and then iterate over the critical angles (i.e. extremeties of some range of forbidden angles, which are not forbidden themselves). I suspect that `float(xr[j] - xl[i]) / (y[i] - y[j])` should return unequal values for some mathematically equal fractions (like $5/3$ and $15/9$) because of precision errors. In such case, let's say there are two ranges $\[a, b\]$ and $\[c, d\]$ with $b = c$ ...

Full text and comments »

SRM 660 d1hard (hi, I'm a beginner) Hi, It's my first blogpost on codeforces. I was preparing problems for today srm and now want to tell about hardest problem from problemset. This is a short editorial for srm 660 div1hard problem. You probably should not read it if you dont know the problem yet and want to train to solve hard problems by yourself :) Here is a [link](http://community.topcoder.com/stat?c=problem_statement&pm=13696) for the statement. First you can see that morphing operation is reversible(if you can transform array a to array b, then you can also transform b to a by the same operation). So if you imagine that arrays are vertices of some graph where two arrays is connected if it's possible to transform one from another, the minimal number of vertices needed so any can be reached is just a number of connected components in this graph. Now I say that this problem about counting non-isomorphic directed graphs with outgoing degree 1 and ingoing at most k. You can see why :) First lets con...

Full text and comments »

Cheaters found in CF Round #660 , #658 and #657 I found these two cheaters in Yesterday's contest ([ Codeforces Round #660 (Div. 2) ](https://mirror.codeforces.com/contest/1388)). They are from from the **same institute** (Jaypee Institute of Information Technology, Noida). They have been doing this in all almost **every past contests** they both participated. CF authorities should atleast **disqualify them from Round #657** , as they have gained positive deltas from that round unlike other rounds where they have dropped. User 1: _**Agraj Garg**_ [agrajgarg](https://mirror.codeforces.com/profile/agrajgarg) User 2: _**Vatsal Agarwal**_ [Warhead38](https://mirror.codeforces.com/profile/Warhead38) Submissions(For CF Round #660): A: [88462008](http://mirror.codeforces.com/contest/1388/submission/88462008) by Agraj and [88463088](http://mirror.codeforces.com/contest/1388/submission/88463088) by Vatsal (Apparently Vatsal has also submitted two absurd solutions to fool the authorities ) B: [88479313](http://mirror.codeforces.com/conte...

Full text and comments »

Codeforces Round #215 & #216 Statistics Statistics of the rounds (official participants)<br/> [contest:367]<br/> [contest:368]<br/> [contest:369] [cut]:<br/> <pre> <code> --------------------------------------------------------------------------------------------- | Codeforces Round #215 (Div. 1) | --------------------------------------------------------------------------------------------- | | First | Sent | Pretest | Hacked | Systest | Accepted | Attempts | Success | Severity | | | | | failed | | failed | | | % | | --------------------------------------------------------------------------------------------- | A | 00:05 | 639 | 42 | 0 | 2 | 595 | 1170 | 50.9 | 1.83 | | B | 00:08 | 567 | 87 | 35 | 163 | 282 | 1366 | 20.6 | 2.20 | | C | 00:13 | 413 | 73 | 61 | 23 | 256 | 770 | 33.2 | 1.59 | | D | 0...

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 »

Codeforces Beta Round #71 Editorial <p></p><div><span class="Apple-style-span" style="font-family: verdana,arial,sans-serif; font-size: 19px; font-weight: bold; line-height: 20px;">Statistics</span><br></div><div><div><table width="550" align="center" border="1" cellpadding="3" cellspacing="0"><tbody><tr align="center"><td bgcolor="#ffeeff">Problem</td><td bgcolor="#ffbbbb">#Submission</td><td bgcolor="#ffffbb">#Passed Pretest</td><td bgcolor="#bbffbb">#Passed Finaltest</td><td bgcolor="#ffeeff">Average Score</td></tr><tr align="center"><td>A</td><td>858</td><td>767</td><td>660</td><td>433.36</td></tr><tr align="center"><td>B</td><td>749</td><td>655</td><td>600</td><td>813.28</td></tr><tr align="center"><td>C</td><td>467</td><td>352</td><td>229</td><td>1093.07</td></tr><tr align="center"><td>D</td><td>28</td><td>14</td><td>4</td><td>1315.00</td></tr><tr align="center"><td>E</td><td>2</td><td>2</td><td>1</td><td>1620.00<br></td></tr></tbody></table></div><br></div><div><br></div><div><span class="Apple-style-span" style="...

Full text and comments »

Stream week 2 I've got plans for at least 2 streams this week Today I will stream Educational Round 92 [15 minutes after it ends](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Egor%27s+stream+ep.+00&iso=20200729T1850&p1=168&ah=1&am=30) Tomorrow I'll stream Codeforces Round #660 [same time](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Egor%27s+stream+ep.+00&iso=20200730T1850&p1=168&ah=1&am=30) Join me on my [twitch channel](https://twitch.tv/egorcp). I would try to explain my thoughts during the contest and will answer questions from chat. You can ask any questions, not necessarily ones about these contests. UPD: stream started UPD2: stream ended, [here's VOD](https://youtu.be/TAebE-ZmQAU) UPD3: unfortunately I have to cancel stream today, hope there will be one next week

Full text and comments »

Educationals Rounds Link (From Starting) I saw on Codeforces on a regular basis, that there are a lot of questions and answers about practicing and practicing more. Although It is my opinion that the Educationals Rounds are best for this, at least for people like me. They learn from it and the problems are very nice and interesting. There are many Educationals Rounds will come and I will also try my best to keep this blog update. Although if you want to generate these links <s>at any time</s> locally you can find the code on my GitHub repo: https://github.com/adshin21/Codeforces-Contest-Selector-By-Div-s So I've collected the links for all the educationals rounds that has happened. <table class = "bordertable" align="center"> <tbody> <tr> <td>Educational Round 1 </td> <td> <a href= " http://mirror.codeforces.com/contest/598" >http://mirror.codeforces.com/contest/598</a></td> <tr> <tr> <td>Educational Round 2 </td> <td> <a href= " http://mirror.codeforces.com/contest/600" >http://mirror.codeforces.com/contest/600</a></td> <tr> <tr> ...

Full text and comments »

Tracking Codeforces Educational Rounds - Educational Codeforces Round 1 (http://mirror.codeforces.com/contest/598) - Educational Codeforces Round 2 (http://mirror.codeforces.com/contest/600) - Educational Codeforces Round 3 (http://mirror.codeforces.com/contest/609) - Educational Codeforces Round 4 (http://mirror.codeforces.com/contest/612) - Educational Codeforces Round 5 (http://mirror.codeforces.com/contest/616) - Educational Codeforces Round 6 (http://mirror.codeforces.com/contest/620) - Educational Codeforces Round 7 (http://mirror.codeforces.com/contest/622) - Educational Codeforces Round 8 (http://mirror.codeforces.com/contest/628) - Educational Codeforces Round 9 (http://mirror.codeforces.com/contest/632) - Educational Codeforces Round 10 (http://mirror.codeforces.com/contest/652) - Educational Codeforces Round 11 (http://mirror.codeforces.com/contest/660) - Educational Codeforces Round 12 (http://mirror.codeforces.com/contest/665) - Educational Codeforces Round 13 (https://mirror.codeforces.com/contest/678) - Educational Codeforces Round 14 (https://mirror.codeforces.com/contest/691) - Educational...

Full text and comments »

All DIV 3 contests links for practice Hello friends I am sharing the link of all div 3 links for practice. -------------------------------------------------------------------- <br><br> Div3 1: https://mirror.codeforces.com/contest/977<br> Div3 2: https://mirror.codeforces.com/contest/978<br> Div3 3: https://mirror.codeforces.com/contest/988<br> Div3 4: https://mirror.codeforces.com/contest/999<br> Div3 5: https://mirror.codeforces.com/contest/1003<br> Div3 6: https://mirror.codeforces.com/contest/1005<br> Div3 7: https://mirror.codeforces.com/contest/1006<br> Div3 8: https://mirror.codeforces.com/contest/1015<br> Div3 9: https://mirror.codeforces.com/contest/1029<br> Div3 10: https://mirror.codeforces.com/contest/1066<br> Div3 11: https://mirror.codeforces.com/contest/1077<br> Div3 12: https://mirror.codeforces.com/contest/1092<br> Div3 13: https://mirror.codeforces.com/contest/1095<br> Div3 14: https://mirror.codeforces.com/contest/1102<br> Div3 15: https://mirror.codeforces.com/contest/1108<br> Div3 16: https://mirror.codeforces.com/contest/1118<br> Div3 17: https://mirror.codeforces.com/contest/113...

Full text and comments »

Topcoder Single Round Match 660 Всем привет! Завтра в [14:00 MSK](http://www.timeanddate.com/worldclock/fixedtime.html?msg=SRM+660&iso=20150604T1100&ah=2&am=0) состоится очередной [Topcoder SRM 660](http://community.topcoder.com/tc?module=MatchDetails&rd=16463). Предлагаю обсудить задачи после контеста!

Full text and comments »

Same solution gave TLE during system testing but passed during practice. This is in regard with Codeforces Round #660-Div 2 Problem B. I submitted a solution to this problem in O(n) time complexity. It passed all the pretests but gave TLE in system testing but later during practice the same code was accepted. Solution submitted during contest: https://mirror.codeforces.com/contest/1388/submission/88486803 gave TLE. Solution submitted for practice: https://mirror.codeforces.com/contest/1388/submission/88530257 passed all the test cases. Can anyone explain me why it happened? Thanks in advance!

Full text and comments »

UNEXPECTED TLE !! is it ME ?? or is it PYTHON?? or is it CODEFORCES?? Recently I gave Codeforces round #660 (Div 2) ============================================= , where i solved problem B in O(n) time complexity After doing the problem in O(n) I still get TLE !!! and its not only me I get to know many other also faced this problem **EVEN C++ O(n) SUBMISSION GOT TLE !!!!!** My submission : [http://mirror.codeforces.com/contest/1388/submission/88472454](http://mirror.codeforces.com/contest/1388/submission/88472454) A C++ Submission :[ https://mirror.codeforces.com/contest/1388/submission/88470034](codeforces.com/contest/1388/submission/88470034)

Full text and comments »

Lexicographically Minimal String Rotation -------------------- -------------------- -------------------- -------------------- -------------------- # <strong> <center style="color:red;"> Table of content </center> </strong> | Teleporter | Description | | :---------------------------------------------- | :----------------------------------------------------------- | | [I. The Problem](#problem) | Describe about the problem | | [II. Bruteforce Approach](#brute) | Simple way to do the problem | | [III. Hashing Approach](#hash) | Reduce circular substring comparing complexity | | [IV. Sqrt Decomposition](#sqrt) | Divide into parts, solve each part then solve the whole part | | [V. KMP Approach](#kmp) | Magical Linear Booth-KMP Algorithm ...

Full text and comments »

Codeforces !! Yesterday, after so many days I have started doing round 660 div 2. I was able to submit answers for 2 questions which cleared all the pretests. Now comes the magic, I got a TLE on the second one and when I resubmitted exactly the same code, it got Accepted. Now, can someone explain what magic has actually happened and how can I claim the rating I was wrongly awarded ?

Full text and comments »

https://mirror.codeforces.com/contest/1388/problem/D of Codeforces Round #660 (Div. 2) using python I tried to solve question using topological sort from the reference https://mirror.codeforces.com/contest/1388/submission/88532119 .It passed till test 7 but gave runtime error on test 8 with exit code 1, Here's my code https://ideone.com/MK0Ra6 , please help me correct it. Thanks in advance ☺️

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://mirror.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 »