### MikeMirzayanov's blog

By MikeMirzayanov, 3 days ago, ,

Hello, Codeforces!

Yesterday slappy advised me to stop writing problems. I will not listen to his advice and will not stop coming up with new problems. Moreover, the idea of problem 1118C - Palindromic Matrix is mine, and I do not consider it bad or unsuccessful.

IMHO, this is a good example of a problem, where an sloppy (almost slappy) implementation leads to a casework, duplication of code and a lot of formulas. On the other hand, a well-turned implementation is devoid of all these drawbacks and easy to write. It seems to me that such feedback about the problem is something of a Dunning-Kruger effect.

In general, this is an important skill of the developer to write such code, which solves the problem reliably, concisely and is not dirty. And if your code smells bad, then instead of the shaming the authors, I urge you to think "can I write a solution to this problem better?". Good way is to read solutions of other participants. You can choose short implementations from experienced participants. If you focus on learning, rather than just participating for fun, this should be the rule: read solutions of other participants (better experienced, choosing short codes or extremely efficient) and learn. The fact that you got “Accepted” does not mean that you have nothing to learn with this problem.

Here is the explanation of my solution which was written in ~10 minutes. Please, read the problem 1118C - Palindromic Matrix if you don’t know the statement. This problem is just a generalization of string palindrome constructing problem on 2D.

In general case there are 3 types of elements of a matrix (I didn’t spend to much time on drawing, the image is not perfect):

Each element in the blue area has 4 equal copies (itself and 3 additional symmetric cells). Each element in the yellow area has 2 equal copies (itself and 1 additional symmetric cell). And the single central cell (the green area) has only the single copy (itself). The yellow and green areas are absent in case of even n.

It means that you can fill the matrix with a greedy approach. At first process the blue area: for each cell take any value with number of occurrences at least 4 and fill the cell and its copies. After it process the yellow area (if any): for each cell take any value with number of occurrences at least 2 and fill the cell and its copy. Finally, process the green area (if any): take any value with number of occurrences at least 1 and fill the cell and its copy.

Easy to see that each time you can take a value with the greatest number of occurrences, so I used priority_queue<pair<int,int>> to maintain values ordered by number of occurrences. The first item in a pair is a number of occurrences, the second item in a pair is value itself. To construct such priority_queue q just use simple code like this:

map<int,int> cnts;
forn(i, n * n) {
int val;
cin >> val;
cnts[val]++;
}
for (auto [key, value]: cnts)
q.push({value, key});


To implement the rest of code, use simple function to reflect a position to the symmetric (in 1D):

int rev(int i) {
return n - i - 1;
}


Now the main part of the code is: iterate over blue, yellow, green areas and put values in the matrix (consider all symmetric copies in together):

int m = n / 2;
forn(i, m) // blue area
forn(j, m)
put({{i, j}, {i, rev(j)}, {rev(i), j}, {rev(i), rev(j)}});
if (n % 2 != 0) {
forn(i, m) { // yellow area
put({{i, m}, {rev(i), m}});
put({{m, i}, {m, rev(i)}});
}
put({{m, m}}); // green area
}


The function put takes a sequence of symmetric positions and put same values on them:

void put(vector<pair<int,int>> pos) {
auto t(q.top());
q.pop();
if (t.first < pos.size()) // can’t do it?
no();
for (auto [i, j]: pos)
a[i][j] = t.second;
t.first -= pos.size();
q.push(t);
}


So the complete code is very simple and contains only two if statements (almost no casework!).

Complete Code

•
• +315
•

By MikeMirzayanov, 3 weeks ago, translation, ,

Hi Codeforces!

February 2019 is already on the calendar, which means that I was late with the report for 2018. Better late than never! Let's remember last year.

In 2018, _kun_, 300iq and arsijo joined the team of coordinators. The work of the coordinators is headed (and is the coordinator of the coordinators) KAN. I really hope that a more measured schedule of preparing rounds by a large team of coordinators will give a better insight into the contests. The main innovations in the platform are implemented by me and the developers kuviman, fcspartakm, MaximShipko. Great work on the organization of events and prizes mailing was done by gKseni.

Special thanks to the writers of the problems and testers. It is your content that charges the community with life and unites all of us. Thank you for the problems!

And now let's summarize the 2018th year.

#### Partner Events

We are pleased to hold programming competitions with companies or for companies. I'm sure this is a great way to support the community of young programmers and hire talented candidates. Here is a list of our main partners this year:

• Telegram and personally Pavel Durov is supporting Codeforces activities for many years, every regular round is held with their help, thank you!
• VK, VK Cup — team competition for young Russian-speaking programmers with a series of elimination rounds and finals in St. Petersburg
• Mail.Ru, Mail.Ru Cup — open individual programming competition, consists of several stages, Technocup — open competition for schoolchildren
• Harbour.Space University — a series of educational rounds, the selection of summer school Tech Scouts
• Lyft — a two-level competition with the Final at Lyft headquarters (California) and the mirror contest for worldwide participants
• Avito, Avito Code Challenge and Avito Cool Challenge — open partnership rounds targeting a wide international audience
• Microsoft, Microsoft Q # Coding Contest — unusual quantum computing competition
• AIM Tech — open partnership round targeting a wide international audience
• Huawei — research competition (marathon) with elements of machine learning
• IQ Option — private round as a corporate training

•
• +871
•

By MikeMirzayanov, 3 weeks ago, ,

Hello!

It is always satisfying and important for me when former contest participants offer their help to the community and support the development of programming competitions. And now I am in a hurry to share the news that thanks to the support of XTX Markets and the personal participation of Yuri Bedny and Alexander Gerko, we are launching a new line of Codeforces Global Rounds. Hooray!

Like many of you, I had never heard of XTX Markets before but it is one of the largest quantitative-driven electronic liquidity providers in the world. I understand little about the financial sector, but with their 34,148 cores and 42 petabytes of usable storage in their research cluster, XTX’s rapid growth and strong market share globally speak for themselves.

So, 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. 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 will be very happy for Codeforces to work with the best authors of the problems. I hope that the XTX Markets initiative will allow for interesting and testing rounds that will delight community members! We have the opportunity to pay \$800, double fee, for the preparation of a full set of problems (for some rounds we may collect problems from different authors).

The first Global Round will take place very soon — starting Feb/07/2019 16:35 (Moscow time). I hope you will enjoy the round!

•
• +1206
•

By MikeMirzayanov, 4 weeks ago, ,

Привет, Codeforces!

Закончился первый тур олимпиады. Надеюсь, что скоро участники поделятся своими впечатлениями от задач и результами. В этом году впервые Codeforces участвовал в проведении этой олимпиады — 12 регионов принимали участие на нашей платформе. Есть кто из участвующих? Как впечатления? Кажется, всё работало без сбоев. Очередей не было.

Дорешивать задачи можно в Тренировках по ссылке 2018-2019 Всероссийская олимпиада школьников по информатике, региональный этап, 1 тур.

UPD: Закончен второй тур. По ссылке Тренировках можно дорешивать и задачи 2-го тура: 2018-2019 Всероссийская олимпиада школьников по информатике, региональный этап, 2 тур.

•
• +146
•

By MikeMirzayanov, 4 weeks ago, translation, ,

Hello!

The shortest news on Codeforces. I added support for Microsoft Visual Studio C ++ 2017. The solutions are compiled with the command line cl /std:c++17 /W4 /F268435456 /EHsc /O2 /DONLINE_JUDGE %1.

•
• +79
•

By MikeMirzayanov, 5 weeks ago, ,

Привет!

Совсем скоро состоится региональный этап РОИ. В этом году Codeforces присоединяется к проведению, и некоторые регионы будут писать олимпиаду на базе Codeforces.

Для проведения олимпиады мной были пописаны некоторые элементы функциональности Codeforces и Polygon. Теперь, в Полигоне можно не только устанавливать политики начисления баллов для групп тестов и их зависимости, но и рекомендуемую для тестирующей системы политику отображения информации о тестировании. Как и на Всеросиийских олимпиадах, поддержаны следующие политики:

• NONE — не показывать в отчете информацию о тестировании группы,
• POINTS — показывать только баллы за группу тестов,
• ICPC — показывать вердикт до первого упавшего теста (включительно),
• COMPLETE — показывать все вердикты (в этом случае группа тестируется полностью, даже если оценивается только её полное прохождение).

В тестировании на Codeforces было поддержано прерывание групп тестов и пропуск их тестирования, если это можно сделать в соответствии с политиками групп.

Кроме того, для организаторов регионов был разработан отдельный интерфейс, который сделает проведение олимпиады простым и комфортным.

Приглашаю всех интересующихся присоединиться к открытому пробному туру региональной олимпиады по адресу https://roi19p.contest.codeforces.com. Просто используйте свой аккаунт Codeforces, чтобы зайти на этот подсайт и примите участие в пробном туре. Обратите внимание, что каждое условие содержит описание политик начисления баллов и отображения отчетов. По задачам можно задавать вопросы (тестируем всё!), но я не могу обещать, что смогу ответить на них.

Если что-то работает неправильно, непредсказуемо или неудобно, то пишите комментарий под этот пост.

Спасибо!

•
• +105
•

By MikeMirzayanov, 2 months ago, ,

Congratulations to all the new 2019 year! At this very moment you can make an important wish. Done? I wish it to be fulfilled!

I wish you to become better in the new year, to think better and to meet less often with bugs and mistakes. Let all your solutions be fast, effective and correct!

Later, I will compile statistics for 2018 and publish in the form of an annual report

Now I'd like to remind you most voted posts of 2018. Here is the list of the top 15:

Happy New Year!

•
• +710
•

By MikeMirzayanov, 2 months ago, ,

Do you already have a New Year's mood?

#### Change Handle Feature

Hurry! Only until the 10th of January, you can change your handle (but only once)! Note that it will be possible to roll back the changes or change the handle again only after a year. Be careful what you wish for.

You can change your handle to the new one which wasn't used before by anybody or which was used by you before. The links to a profile page with old handle would automatically redirect to the actual profile.

This year we have an improvement. If you took part in at least 10 rounds you can request handle of an inactive participant. It means that the participant should have a period of activity on Codeforces of at most 90 days, this period should be in 2015 or earlier. The inactive participant can’t have posted comments, messages and so on. It can't take part in more than 2 contests. It will be automatically renamed and informed by email. If you can’t change handle to others, it means that some requirement doesn't meet. Please do not ask me to do something with it. I'm not Santa Claus.

Talking about handles I always reminisce the following story. Once a user wrote me the message: "Please change my handle from I_love_Valya to I_love_Sveta, as I no longer love Valya ..."

#### New Year's Masquerade of Colors and Ranks

Traditional magical tab has appeared in the profile setting. Happy New Year!

•
• +1044
•

By MikeMirzayanov, 3 months ago, ,

Hello,

We have some technical issues for operating with recent problems. If you created a gym/mashup (today or yesterday), it is possible that its submissions are not visible. I'm working on it. Probably, today night it will be a planned maintenance shutdown to fix it.

I think it will not affect Educational Codeforces Round 55 (Rated for Div. 2).

Mike.

•
• +160
•

By MikeMirzayanov, 3 months ago, ,

Here are merged results of Mail.Ru Cup 2018 Round 1, Mail.Ru Cup 2018 Round 2 and Mail.Ru Cup 2018 Round 3 according to the GP100 scores (see the announcement for the details https://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 mnbvmar 1497 1000 497 29
2 V--o_o--V 1281 575 575 706
4 aid 1204 204 1000 142
5 LHiC 1203 497 706 226
6 Um_nik 997 706 291 235
7 ksun48 788 291 497
8 SpyCheese 742 371 371 265
9 RAVEman 619 19 176 443
10 scott_wu 614 307 307 307
11 ch_egor 575 575
13 BudAlNik 531 277 254 122
14 lewin 515 443 72
15 al13n 477 186 62 291
16 tourist 443 443
17 isaf27 426 277 149
18 I_love_Tanya_Romanova 422 204 218
19 natsugiri 419 48 371
20 Reyna 405 244 54 161
20 Golovanov399 405 403 2
22 ecnerwala 403 403
22 Endagorion 403 403
24 DeadMedveD 389 145 68 244
25 j_______________________ 384 198 186
25 Kostroma 384 218 46 166
27 Errichto 382 36 346
28 zemen 371 226 32 145
29 kostka 370 45 325
30 uwi 364 153 211 131
31 BigBag 355 198 157
31 dreamoon 355 265 90
33 kmjp 353 70 218 135
34 dotorya 346 346
35 Zhukov_Dmitry 337 235 102
36 OO0OOO00O0OOO0O00OOO0OO 325 325
36 Petr 325 325
38 krijgertje 319 181 138
39 SYury 313 78 235
40 Marcin_smu 309 138 171
41 mjhun 308 110 198
42 KrK 294 102 192
43 socketnaut 286 181 105
44 Benq 277 277
45 mmaxio 270 16 254
46 Nikitosh 261 142 119
47 irkstepanov 258 254 4
48 AndreySergunin 251 166 85
49 qwerty787788 244 244
50 Fedosik 242 135 107
51 sevenkplus 236 226 10
52 gamegame 229 192 37
53 voover 227 56 171
54 Xellos 225 72 153
55 FCB1234 224 43 181
56 MakeRussiaGreatAgain 218 138 80
57 neal 211 211
57 ainta 211 211
59 MrDindows 204 204
60 znirzej 190 122 68
61 progmatic 186 186
62 AeonHQ 182 161 21
63 maroonrk 176 176
63 snuke 176 149 27
63 rudy102 176 176
66 cki86201 171 171
67 Shef 166 166
68 mHuman 163 21 142
69 zeliboba 162 34 128
70 imeimi 161 161
71 KMAASZRAA 160 97 63
72 Alex_2oo8 157 157
72 wxy_z 157 157
74 JiK 154 128 26
75 ilyakor 153 153
76 yashChandnani 152 92 60 45
76 amethyst0 152 135 13 17
78 DmitryGrigorev 151 52 11 99
79 kaldiuo 150 90 60
80 function348 149 149
81 fgcos 148 107 41
82 andrey_efremov 145 145
83 subconscious 143 63 80
84 Merkurev 131 131
84 N1k1_tos1_NA 131 131
86 grumpy_gordon 129 116 13
87 Nurboom 128 128
88 zscoder 127 116 11
89 prof.PVH 126 34 50 76
90 Shayan 125 125
90 majk 125 125
90 rimuruu 125 125
93 Miyukine 122 122
93 WA_TLE 122 122
95 palayutm 121 87 34
96 queria_ser_abella 119 119
97 savkinsd2089 117 107 10
98 sharyava 116 116
99 bbatti93 114 22 92
100 Swistakk 113 113
100 boook 113 113
100 Fdg 113 113
103 rui-de 111 87 24
104 Definitely_Not_Ngkan146 110 110
104 liujunhao 110 110
106 pparys 105 105
108 Quang 104 14 90
109 ivanovmp 102 102
110 rtilikay 99 99
110 Motarack 99 41 58
110 sy_chen 99 99
113 hank55663 97 97
113 MicGor 97 97
115 tlwpdus 94 94
115 mrscherry 94 94
115 Batrr 94 94
119 PoDuReM 87 4 83
119 ll931110 87 87
121 e-pluszak 86 72 14
122 dario2994 85 85
122 cephian 85 85
124 lezdzh 83 83
124 SmsS4 83 83
126 fsouza 82 56 26
127 kimden 80 80
128 ei133333 78 78
130 papa3 76 76
130 Coder 76 76
132 tfg 74 74
132 ablikexe 74 74
132 hloya_ygrt 74 74
135 ushakov.fedor 72 72
136 Mateuszrze 70 70
136 maximumSHOT 70 70
138 waynetuinfor 68 68
139 iitbhu_0 66 66
139 kefaa 66 27 39
139 NurlashKO 66 66
142 nanachi 63 63
143 Ali.Sh 62 62
143 ismagilov.code 62 62
145 AlexDmitriev 60 60
146 nhho 58 58
146 Noam527 58 58
148 131131yhx 56 56
149 qoo2p5 54 54
149 alex9801 54 54
151 Sert 52 52
151 mariand 52 52
155 cuber2460 50 50
156 Damon 48 48
156 archie_fake 48 48
156 mango_lassi 48 48
159 shananton 46 46
160 Wild_Hamster 45 45
160 Holidin 45 2 43
162 nikabb 43 43
163 Farhod_Farmon 41 41
164 walnutwaldo20 39 39
164 Alexandr_TS 39 39
166 qlmupi 37 37
166 wa1tz719 37 37
168 Egor 36 36
168 stilltoosimple 36 36
170 f.bialas 32 32
170 LoneFox 32 32
172 sina_pakseresht 31 31
172 Kaban-5 31 31
172 nigus 31 31
175 kyleliu 29 29
176 mateusz 27 27
177 joomas 26 26
177 NBAH 26 26
179 icecuber 24 24
180 chemthan 22 22
181 kalinov 21 21
182 kr_abhinav 19 19
182 Arterm 19 19
184 Sagiri_Izumi 17 17
184 Lollipop 17 17
186 sava-cska 16 16
186 jinzhihan 16 16
188 Weeeee 14 14
189 sqrtdecompton 13 13
190 test616.cpp 11 11
191 shoemakerjo 10 10
192 tamionv 8 8
192 bazsi700 8 8
192 guille 8 8
195 spiderg 7 7
195 ErdemKirez 7 7
195 albertg 7 7
198 muratt 5 5
198 AlexLuchianov 5 5
198 glebushka98 5 5
198 teleport 5 5
202 mitterr1999 2 2
203 k__mas 1 1
203 erop.sergeev 1 1
203 _LeMur_ 1 1

•
• +69
•

By MikeMirzayanov, 3 months ago, ,

Hello.

As I wrote into a comment, last round we are faced a strong DDOS-attack which ruined the competition. I don't know who did it, I also don't know reasons to do it. I'm very upset about the situation and ready to make effort to be prepared for such issues.

I spend a lot of time to be ready for such incidents.

Here are steps you need to do to be ready for unexpected failures:

• Be sure that you know the password of your Codeforces account. If you don't remember it, just use the password recovery feature. Please, do it right now.
• I've implemented a minimalistic website for replacing the main site in case of emergencies. Now you can only read problems, view you submissions (without any details), submit codes. Probably, later I'll add some more features, but anyway the minimalistic version will have only vital features to take part in a contest. I've deployed it in several places, you can visit any of them by the links: http://m1.codeforces.com, http://m2.codeforces.com, http://m3.codeforces.com. If any of them is unavailable, just use another. Do not use them if the main website is alive.

•
• +3011
•

By MikeMirzayanov, 3 months ago, ,

Hi, Codeforces!

I am glad to announce and invite you to the second launch of my course on algorithms and data structures.

On 7-25 of January, 2019, I will be giving the course "Advanced Algorithms and Data Structures" at Harbour.Space University (Barcelona, Spain). It will be in English, and is not limited to Harbour.Space students — anyone is welcome! Who wants to join?

This course isn't just for Harbour.Space students, it is also open to Codeforces participants, who will be offered a special price, 1000 EUR. The cost does not include travel or accommodation.

Register for the Course →

The curriculum will include a breakdown of algorithms and data structures, a lot of practical exercises, and emphasis not only on the correctness, but also the beauty and structure of the code. My goal is to make classes that are useful and interesting for both those who want to understand the fundamental CS, and for those interested in programming competitions. And of course, we will have the opportunity to meet and talk. I look forward to share stories about the history of Codeforces and future development plans.

The course will consist of three weeks of intensive training, 5 days in each week, 3 hours per day. The program includes daily lectures and practical exercises. It will not be boring for sure!

Here is the expected course outline:

Week Day Topics
1 1 Heap data structure, heap properties and operations. HeapSort. Priority queue. Other heap applications. Mergeable heaps: binomial heap, pairing heap, randomised meldable heap.
1 2 Fenwick tree. Description and motivation. Implementation of Fenwick tree. Generalisation for higher dimensions. Skip list data structure. Implementation details. Indexable skiplist.
1 3 Segment trees. Top-down implementation. Bottom-up implementation. Segment trees applications. Persistent data structures. Persistent stack, persistent array. Persistent Fenwick and segment trees.
1 4 Cartesian trees, treap data structure. Merge and split operations. Treap implementation in detail. Treap applications.
1 5 Treaps with implicit keys. Ropes. Segment reverse operation. Examples of problems.
2 6 Introduction to strings. String searching (matching) problem. Pattern pre processings. Z-function, prefix-function. Their applications. Knuth–Morris–Pratt algorithm. Matching finite state machine.
2 7 Multiple pattern matching. Trie data structure. Aho-Corasick algorithm. Implementation details. Dynamic programming on a trie.
2 8 String hashing. Rabin-Karp algorithm. Fast substrings comparison with hashes. Suffix array. LCP array. Efficient construction algorithm. Applications.
2 9 Suffix tree. Ukkonen's algorithm. Suffix tree construction from LCP array. Suffix tree applications.
2 10 Suffix automaton. Size bounds. Linear Algorithm. Using suffix automata as an index for approximate string searches.
3 11 Introduction to automata theory. Formal languages. Context-free languages. Formal grammars. Context-free grammars. NFA, DFA, convert NFA to DFA. Build automaton by regular expression.
3 12 LL(1) parser. Arithmetic expressions parsing. Shunting-yard algorithm. Simplified Pascal language parsing and interpretation.
3 13 Algorithms for traversing a graph. DFS. Properties. DFS search tree. Edges classification. Linear bridge-finding algorithm. Linear articulation points finding algorithm. Strongly connected components. Tarjan's strongly connected components algorithm.
3 14 Tree problems. Bottom-up approach. LCA problem. LCA algorithms.
3 15 Bipartite graphs. König’s criterion. Problems: maximum matching, minimum edge cover, maximum independent vertex set, minimum vertex cover. Connection of the problems. Berge's lemma. Kuhn algorithm. Kuhn algorithm properties. Minimal vertex cover by maximum matching. Cover DAG by minimal number of paths.

Harbor.Space University is located in Barcelona (Spain). For users of Codeforces, Harbour.Space is known for active participation in the life of the community of sports programming (partnership with Codeforces in the framework of Educational Rounds). The main activity of the university is teaching (there are bachelor's and master's programs) in the following areas:

• Maths as a Second Language
• Computer Science
• Data Science
• Cyber Security
• Interaction Design
• Digital Marketing
• High Tech Entrepreneurship
• FinTech
• BioTech
• Aerospace Engineering
• SuperCities UrbanTech

Register for my upcoming course via this link.

•
• +36
•

By MikeMirzayanov, 3 months ago, ,

Here are merged results of Mail.Ru Cup 2018 Round 1 and Mail.Ru Cup 2018 Round 2 according to the GP100 scores (see the announcement for the details https://codeforces.com/blog/entry/62355).

Place Contestant = Round 1 Round 2
1 mnbvmar 1497 1000 497
2 aid 1204 204 1000
3 LHiC 1203 497 706
4 V--o_o--V 1150 575 575
5 Um_nik 997 706 291
6 SpyCheese 742 371 371
7 scott_wu 614 307 307
8 BudAlNik 531 277 254
9 tourist 443 443
9 lewin 443 443
11 Golovanov399 403 403
11 Endagorion 403 403
13 j_______________________ 384 198 186
14 Errichto 382 36 346
15 uwi 364 153 211
16 dreamoon 355 265 90
17 dotorya 346 346
18 OO0OOO00O0OOO0O00OOO0OO 325 325
18 Petr 325 325
20 SYury 313 78 235
21 Reyna 298 244 54
22 ksun48 291 291
23 kmjp 288 70 218
24 isaf27 277 277
26 Kostroma 264 218 46
27 zemen 258 226 32
28 irkstepanov 254 254
29 al13n 248 186 62
30 qwerty787788 244 244
31 Zhukov_Dmitry 235 235
32 gamegame 229 192 37
33 voover 227 56 171
34 sevenkplus 226 226
35 Xellos 225 72 153
36 MakeRussiaGreatAgain 218 138 80
38 ainta 211 211
39 I_love_Tanya_Romanova 204 204
40 BigBag 198 198
41 RAVEman 195 19 176
43 socketnaut 181 181
43 krijgertje 181 181
45 maroonrk 176 176
46 cki86201 171 171
47 AndreySergunin 166 166
47 Shef 166 166
49 mHuman 163 21 142
50 imeimi 161 161
50 AeonHQ 161 161
52 Alex_2oo8 157 157
52 wxy_z 157 157
54 JiK 154 128 26
55 yashChandnani 152 92 60
56 snuke 149 149
56 function348 149 149
58 amethyst0 148 135 13
59 andrey_efremov 145 145
60 Nikitosh 142 142
61 Marcin_smu 138 138
62 Fedosik 135 135
63 Merkurev 131 131
63 N1k1_tos1_NA 131 131
65 Nurboom 128 128
66 majk 125 125
66 rimuruu 125 125
68 Miyukine 122 122
68 znirzej 122 122
68 WA_TLE 122 122
71 queria_ser_abella 119 119
72 savkinsd2089 117 107 10
73 zscoder 116 116
73 grumpy_gordon 116 116
75 bbatti93 114 22 92
76 Fdg 113 113
76 boook 113 113
78 liujunhao 110 110
78 mjhun 110 110
80 fgcos 107 107
81 pparys 105 105
83 KrK 102 102
83 ivanovmp 102 102
85 sy_chen 99 99
85 rtilikay 99 99
87 KMAASZRAA 97 97
87 hank55663 97 97
89 Batrr 94 94
89 tlwpdus 94 94
91 kaldiuo 90 90
92 rui-de 87 87
92 palayutm 87 87
94 dario2994 85 85
94 cephian 85 85
96 prof.PVH 84 34 50
97 lezdzh 83 83
97 SmsS4 83 83
99 kimden 80 80
101 papa3 76 76
101 Coder 76 76
103 hloya_ygrt 74 74
103 ablikexe 74 74
105 ushakov.fedor 72 72
105 e-pluszak 72 72
107 maximumSHOT 70 70
108 iitbhu_0 66 66
108 kefaa 66 27 39
108 NurlashKO 66 66
111 subconscious 63 63
111 nanachi 63 63
111 DmitryGrigorev 63 52 11
114 ismagilov.code 62 62
115 AlexDmitriev 60 60
116 Noam527 58 58
116 nhho 58 58
118 fsouza 56 56
119 alex9801 54 54
120 Sert 52 52
120 mariand 52 52
122 natsugiri 48 48
122 mango_lassi 48 48
122 archie_fake 48 48
125 Wild_Hamster 45 45
125 kostka 45 45
127 FCB1234 43 43
127 nikabb 43 43
129 Motarack 41 41
129 Farhod_Farmon 41 41
131 Alexandr_TS 39 39
132 wa1tz719 37 37
133 Egor 36 36
134 zeliboba 34 34
135 f.bialas 32 32
136 sina_pakseresht 31 31
136 nigus 31 31
138 kyleliu 29 29
140 mateusz 27 27
141 joomas 26 26
141 NBAH 26 26
143 icecuber 24 24
144 chemthan 22 22
145 kalinov 21 21
146 kr_abhinav 19 19
147 Lollipop 17 17
147 Sagiri_Izumi 17 17
149 mmaxio 16 16
149 sava-cska 16 16
151 Weeeee 14 14
151 Quang 14 14
153 sqrtdecompton 13 13
154 test616.cpp 11 11
155 shoemakerjo 10 10
156 tamionv 8 8
156 guille 8 8
158 spiderg 7 7
158 ErdemKirez 7 7
160 glebushka98 5 5
160 AlexLuchianov 5 5
160 teleport 5 5
163 PoDuReM 4 4
164 Holidin 2 2
164 mitterr1999 2 2
166 erop.sergeev 1 1
166 _LeMur_ 1 1

•
• +96
•

By MikeMirzayanov, 4 months ago, translation, ,

Hi Codeforces.

I am glad to share a small but useful update of Polygon, which was fully developed by me in the walls of ITMO. Now preparing problems with unusual I/O will become a little easier.

Now in the new problems you will get examples in the statements without any transformations by LaTeX/HTML. If earlier you had difficulties with the correct formatting of empty lines or the fact that a double hyphen is replaced with a dash, now there are no such difficulties. The enhancement works for both PDF and HTML statements.

For example, to have such I/O examples just add such a test and use the appropriate output from the model solution.

Note that the feature to overwrite the examples is stayed working (custom content of input or output data for statements). It seems that there are almost no reasons to use it for an input now (apparently, only for interactive problems).

Previously created problems use the old approach, so this innovation should not break existing problems.

How do you like the feature?

•
• +230
•

By MikeMirzayanov, 4 months ago, translation, ,

Hi Codeforces!

Meet a small innovation on Codeforces — difficulties of problems (and at the same time a new widget filtering problems in the archive). For all the problems of the archive, I’ve calculated the difficulties in the scale of the rating of participants. Approximately this means that if the rating of the problem is equal to yours, then on a typical round you would solve the problem with a probability of 0.5. And, in general, if your rating is ri, and the problem rating is rj, then the problem during the round can be solved approximately with probability:

For example, if the rating of a problem is less than yours by 200, then the expected probability of solving the problem is 0.75. With a difference of 400 rating points, the probability increases to 0.9.

For convenient search of problems in the archive, you can now use a special widget:

With it, you can find not only problems that have all the chosen tags, but also which have at least one tag from the list.

A difficulty of a problem is also displayed when choosing problems in a mashup.

I hope that now you will be able to do more effective practice, and the process of making new mashups for trainings will become easier.

UPD 2: (API update) Optional field rating has been added to the object Problem in API.

•
• +3188
•

By MikeMirzayanov, 4 months ago, translation, ,

Hello!

ACM-ICPC Southern Subregional Contest (NEERC/Northern Eurasia) 2018 has ended on October 16. There were 72 teams onsite in Saratov, most of them were invited because of their result on the qualification stage.

In this contest I play a role of Cheif Judge and the jury teams consists of ex-participants of ICPC from Saratov and jury members from other cities. Many thanks to all of them! I hope you will like the problems!

I invite ACM-ICPC teams and individual participants of Codeforces competitions to take part! Sure, the contest will be unrated.

MikeMirzayanov

•
• +221
•

By MikeMirzayanov, 4 months ago, translation, ,

Hi Codeforces!

For you, perhaps it was yet another Codeforces round. But not for me. Codeforces Round #515 (Div. 3) is the first round tested on new judging servers at ITMO University. And this is not just an update of location. Ta-dam! Now your solutions will be judged on the new Intel i3-8100 processors. And this is not all news. The number of judging servers has increased, which means fewer queues during rounds!

I am pleased to announce that now I live in St. Petersburg, I work at ITMO, and Codeforces is gradually moving from the walls of dear to me Saratov University to ITMO University. The decision to move was not easy for me. My plan is that, based on ITMO, I can focus more on Codeforces development and work on the platform. The number of world champions per square meter is simply overwhelming, and working with a large team of such enthusiasts (and professionals!) of sports programming, like me, is extremely inspiring. I always liked St. Petersburg and the atmosphere of ITMO. Intuition did not let me down. I feel surrounded by people close to me in spirit (and I’m not only talking about a work). I am sure there are many interesting common projects ahead!

I do not say goodbye to Saratov. This is my hometown, full of people dear to me. I came to my first programming training at SSU exactly 20 years ago. Antonina Fedorova, thank you very much. Natalya Andreeve, I would like to say a personal thank you now. You have opened for me an interesting world of programming competitions. We were happy together when we first advanced to the ICPC Finals, and later when we became champions of Russia and the World. We made countless competitions and helped many Saratov students find themselves in programming. I fervently support the future of the Programming Competitions Training Center at SSU and future generations of Saratov contest participants. And now, I am in Saratov and still the head of the jury of the ICPC Subregional Contest, and even an SSU employee. I hope that we will make a good and interesting contest.

I will try to make a complete relocation of the Codeforces infrastructure to ITMO without downtimes. A good Internet connection between SSU and ITMO is encouraging. All the planned work will adapt to the schedule of the rounds, and now it pleases more than ever (I send my greetings to the coordinators!).

Currently, all Codeforces and Polygon solutions are being judged on new servers based on Intel i3-8100 processors. Fortunately, the performance of a single core is not very different from the one that the old generation of judging servers had. Thus, the time limits in all problems remain the same.

Such news. I am waiting for you on Codeforces Round #516 (by Moscow Team Olympiad).

•
• +1331
•

By MikeMirzayanov, 4 months ago, ,

My friends from Harbour.Space and Remy Robotics asked to publish the news. I am excited and glad to do it, because for our community this is a true exclusive offer. In short, they offer to study robotics in Barcelona, paying for your studies and even with a scholarship! It's so cool!

Here is a direct speech from Harbour.Space.

=

Hi Codeforces!

We are excited to announce our new Master’s in Robotics programme scholarship, which will be paired alongside an internship with our partner Remy Robotics! The programme will begin on January 7th, 2019, at our university in Barcelona, Spain.

Harbour.Space’s Robotics programme is the bridge between a personal interest in the world of Robotics, Artificial Intelligence, and a top-level professional future in one of the most exciting and fastest growing fields of technology. Students who enter the programme will either graduate as Control Engineers (theoretical specialists who ensure that robots interact with the environment in safe and effective manner), or CV Engineers (industrial manufacturers of robots, based more on practical experience).

Students will learn the Design and Control for Dexterous Manipulation; Kinematics, Dynamics and Control; Advanced Manipulation Algorithms robots use to physically interact with their world; Dynamic Optimisation for behavioral control; Integrated Intelligence in Robotics: Vision, Language, and Planning which builds upon the cognitive development; Mechanics of Manipulation focusing on using intelligent development of kinematic constraint, gravity, and friction; Manipulation, Estimation, and Control allowing for robots to locomote and navigate the world; Reinforcement learning in Robotics.

SCHOLARSHIP VALUE: €34,900

Apply →

The scholarship includes:

• Complete coverage of the University tuition fee (€22,900)

• Living allowance (€1,000 per month during 1 year)

• Internship at Remy Robotics (20h per week during 1 year)

REQUIRED EDUCATION:

Bachelor's or Master's Degree in Robotics or Computer, Electrical, Mechanical Engineering or related disciplines.

QUALIFICATIONS AND SKILLS:

• Hands-on robotic programming
• Ideally experience within the automotive manufacturing sector
• Knowledge understanding of robot control interface with ancillary equipment
• Use of robot simulation packages
• Deep experience with all things robotic, from infrastructure-free autonomy to ROS, computer vision, and machine learning
• Experience working with robot parts and components, developing robotics devices
• Ability to concurrently manage multiple diverse and often complex issues and / or projects at the nexus of software, sensors, and hardware

To be selected for this programme, you will need to go through the following steps:

1. Fill out the given form by the link: https://codeforces.com/userForm/89f420923cb55373
2. Attend a series of online tests and interviews with our admissions office and partners
3. Pack your bags for Barcelona!

•
• +36
•

By MikeMirzayanov, history, 5 months ago, ,

Mail.Ru Group совместно с МФТИ, МГТУ им. Н. Э. Баумана и Codeforces в четвертый раз запускает «Технокубок» — олимпиаду по программированию для школьников. В прошлом учебном году олимпиада вошла в перечень олимпиад школьников, повысив свой уровень до второго — круг учебных заведений, дающих льготы победителям и призерам, значительно расширился. Лучшие участники получат ценные призы от компании Apple.

Сразиться за звание самого талантливого молодого программиста приглашаются учащиеся средних образовательных учреждений 8-11 классов.

Победители и призеры олимпиады будут определены по результатам очного этапа, который будет проведен 3 марта 2019 года на базе МФТИ, МГТУ им. Н.Э.Баумана, а также на других региональных площадках по всей России, о которых будет сообщено позднее.

•
• +30
•

By MikeMirzayanov, 6 months ago, ,

Problem idea: MikeMirzayanov, PikMike; prepared by: Vovuh.

Problem idea: MikeMirzayanov, prepared by: MikeMirzayanov.

Problem idea: MikeMirzayanov, prepared by: PikMike.

Problem idea: Vovuh, MikeMirzayanov; prepared by: PikMike.

Problem idea: Errichto, prepared by: Errichto.

Problem idea: lewin, prepared by: lewin.

Problem idea: Endagorion, prepared by: Endagorion.

•
• +62
•

By MikeMirzayanov, 6 months ago, ,

Hello, friends!

I want to discuss separately the negative feedback on the round 505.

I understand, that many participants are disappointed by solutions, which failed on system tests. In fact, the pretests in problems B, D and E turned out to be weak. The problem C also didn’t gone too smoothly, but I don’t see nothing critical.

Surely, this was a flaw in a work of author and coordinator. Unfortunately, such situations sometimes arise and it is difficult to avoid them at all. For these problems, the number of pretests and their type was not looking too weak.

Problem B: 9 pretests, there are small and large answers, two tests with answer -1, there are pretests with n = 1 and n = 2, there are four pretests with n = 150000.

Problem D: 14 pretests, among them manual tests and four different generators, few pretests with n = 700, majority of answers is ‘Yes’, but there are ‘No’ as well. In my opinion, too little pretests with ‘No’.

Problem E: 14 pretests. Yes, this problem on VK cup finals contained 10 pretests and caused many systests fails for participants. I have added 4 more tests to pretests from tests, which caused system tests fails for onsite participants. I was very surprised to see, that there were still so many fails after systests.

Summing up, the pretests turned out to be incomplete, but it is hard to say, that it was obvious defect by author or coordinator. Probably it is a combined effect from the problem specifics and the lack of experience of _kun_ as a coordinator.

I haven’t examined all the problems thoroughly, but still round seemed interesting to me. There were no serious fails with statements, bugs in tests and solutions. The system was also working smoothly, without large queue.

Thanks, MikeMirzayanov

•
• +330
•

By MikeMirzayanov, 6 months ago, translation, ,

Hello!

I am happy to sum up the results of the draw of prizes in two rounds. Congratulations to the top-10 with the win of a plush Peach!

Total Place Handle Place in 504 Place in 505 Total Score (GP-30)
1 Benq 3 4 110
2 fjzzq2002 2 8 107
3-4 Swistakk 1 100
3-4 ko_osaga 1 100
5 Egor 4 9 79
6 CongLingDanPaiShang3k5 2 75
7-8 Kostroma 3 60
7-8 ksun48 6 13 60
9-10 AwD 5 45
9-10 natsugiri 5 45
11-12 gepardo 11 15 40
11-12 xumingkuan 6 40
13-14 RomaWhite 7 36
13-14 mcfx 7 36
15 DarkestLight 8 32
16 matthew99 9 29
17-18 kriii 10 26
17-18 yosupo 10 26
19 scott_wu 11 24
20 XYX_The_Wanderer 18 21 23
21-22 Marcin_smu 12 22
21-22 majk 12 22
23-24 samjia2000 13 20
23-24 yjq_naiive 16 26 20
25-26 neal 14 18
25-26 yutaka1999 14 18
28 pavel.savchenkov 16 15
29-30 Batman 17 14
29-30 fateice 17 14
31-32 000000 27 22 13
31-32 kmjp 18 13
33-34 AndreySergunin 19 12
33-34 Arturgo 19 12
35-36 eds467 20 11
35-36 mareksom 20 11
37 grumpy_gordon 21 10
38 gisp_zjz 22 9
39-40 __Rolton__ 23 8
39-40 mitterr1999 23 8
41-42 ditoly 24 7
41-42 krismaz 24 7
43-44 jvjhfhg 25 6
43-44 yanQval 25 6
45 M.Mahdi 26 5
46 yfzcsc 27 4
47-48 DEGwer 28 3
47-48 wzporz 28 3
49-50 Alex_2oo8 29 2
49-50 WangZhikun 29 2
51-52 Ilya_MSU 30 1
52-52 MrDindows 30 1

•
• +41
•

By MikeMirzayanov, 7 months ago, translation, ,

Hello, Codeforces.

This is a short blog to introduce you recent updates in Testlib and Polygon.

# Testlib

### Generate a Permutation

Now, you can easily generate a permutation with codes like this:

Code Result
vector<int> p = rnd.perm(n); Generates 0-indexed permutation of size n
vector<int> p = rnd.perm(n, 1); Generates 1-indexed permutation of size n

### Function println

Now, you can easily print space-separated lines in a generator. A println uses cout, thus prefer faster method if you print huge data.

Some examples:

Code Result
println(5); Print 5 and line break
println(1, 2, 3); Print 1 2 3 (three space separated integers) and line break
println("one", "more", 5.5); Print one more 5.5 (three space separated items) and line break
vector<int> a; ...; println(a); Print vector a (separate elements with spaces) and line break
vector<int> a; ...; println(a.begin(), a.end()); Exactly the same as above
string b[5]; ...; println(b, b + 5); Print array b (separate elements with spaces) and line break

Here is the example of a generator to print a permutation:

#include "testlib.h"

using namespace std;

int main(int argc, char* argv[]) {
registerGen(argc, argv, 1);

int n = atoi(argv[1]);
println(n);
println(rnd.perm(n, 1));
}


### Function readInts and similar

int n = inf.readInt(1, 200000, "n");


# Polygon

### Example Problems

I've introduced three example problems. Each Polygon user has READ-access to them. Please, use them as examples how to write a problem in Polygon. They are:

• example-a-plus-b: simple A+B problem
• example-almost-upper-bound: simple problem to illustrate non-standard checker (always consider to use readAnswer function like in the example), generators and stress tests
• example-interactive-binary-search: simple interactive problem on a binary search

### Other Small Fixes

• Allow to upload files (for example, images) as a contest property/file to use them in the statements.ftl. File names should start with 'statements-'.
• API has been improved to support general description, general tutorial, tags, test groups and points.
• Show problem ID on the summary box (on the righmost top block).
• Replace UTF-8 typographic characters to their ASCII equivalent (for example, replace em dash — with ---).
• Caching issue has been fixed. Previously, it could show RJ on tests even if the reason has been fixed.

Thanks to fcspartakm for implementing most features in Polygon.

•
• +308
•

By MikeMirzayanov, 7 months ago, translation, ,

Hello, Codeforces!

As many of you I'm not really satisfied how the round 497 has ran. KAN is not working on Codeforces this month, he is out of the city. It was a first round coordinated by arsijo. I liked his enthusiasm and work he did. But it happened, it wasn't an example of a well-prepared round.

The main issues are as follows:

• The problem statement in the problem A wasn't clear enough (actually, it didn't contain any mistakes, just wasn't easy to understand).
• The improper example to illustrate the problem B (no mistake here, but it has confused some users).
• I really didn't like the statement of the problem D2D/D1B. I agree it wasn't good. Again it didn't contain any mistakes, but it was hard to understand it quickly. Also I did the incorrect announcement (but it was fixed quickly).
• The incorrect behavior of the interactor in the problem D2E/D1C (Time Limit Exceeded/Idleness Limit Exceeded on too many queries instead of Wrong Answer).
• The huge gap in the difficulty between the D2C and the D2D.

Right now, I'm really do not sure, should the round be a rated or not. What is your opinion about it? The current idea of the writers and the coordinator to make it unrated for whose, who got incorrect verdict on D2E/D1C.

Anyway, I'd like to say “thanks” to the problem writers, testers and the coordinator arsijo. They really tried to make a good round. I hope to see more rounds from Skyglow and coordinated by arsijo. I'm sure they made proper conclusions from the round.

Thanks, MikeMirzayanov

UPD: Thank you for sharing your opinion. The round is rated.

•
• +270
•

By MikeMirzayanov, 8 months ago, translation, ,
Code in C++ for details
Code in C++ for details
Code in C++ for details
Code in C++ for details
Code in C++ for details