fcspartakm's blog

By fcspartakm, history, 8 days ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +46
  • Vote: I do not like it  

By fcspartakm, 2 weeks ago, translation, In English,

Hello, Codeforces.

In this post we want to talk about the Codeforces and Polygon improvements, which were implemented recently.

Blogs (Codeforces)

Previously, Codeforces blog posts can either be published together with the translation, or both versions can be hidden in drafts. Now a blog post can be published or hidden in drafts separately from its translation. In case there is a published post, and its translation is hidden in drafts, or in the opposite case, you will see a corresponding warning about that. Also the logic of the Recent Actions was completely revised.

Talks (Codeforces)

Also added a new functional in the Talks. For some users, it was inconvenient if a talk with one person contains a lot of messages. The page Dialogues has been implemented. It contains all the dialogs, sorted by the time of the last message. For each dialog, only one row with the last message is shown. When you click the message the talk with this person will open. When you open talk with the person, all messages sent to you by the corresponding person automatically become read. The old-style talks page is also fully preserved.

Read more »

 
 
 
 
  • Vote: I like it  
  • +239
  • Vote: I do not like it  

By fcspartakm, history, 7 weeks ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • -21
  • Vote: I do not like it  

By fcspartakm, 4 months ago, translation, In English,

Hello!

In this post I will talk about recent innovation in Codeforces.

It is noticed that many coaches used the opportunity to change the start of the training/rename it for personal purposes (to host group trainings). This leads to confusion and inconvenience for other members of the community.

To keep everything in order, we changed the rules for editing gym contests. Now a coach can change the name/start time/description of a gym if it is not public or the last update was made not later than a week ago. A week after editing a gym, it becomes the history of Codeforces and coaches lose an opportunity to make edits in it.

You cat ask "how do you give a training in a group, specifying the start time?" Now there is such a way!

To allow more convenient re-use of past trainings, as well as regular contests, it was possible to copy past training and regular competitions into a mashup. This can be done by clicking on the corresponding button in the right sidebar or directly in the form of mashup creation.

In the copied mashup all the submissions of participants of parent contest, the statements of the problems and other information are inherited. Thus, it is a convenient way to start a training in a group at a specific time (now participants will participate in an ordinary way, and not make a synchronous virtual start), giving it its own name.

Wish you successful trainings!

Read more »

 
 
 
 
  • Vote: I like it  
  • +195
  • Vote: I do not like it  

By fcspartakm, history, 4 months ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +54
  • Vote: I do not like it  

By fcspartakm, 4 months ago, translation, In English,

Hello again, Codeforces!

I'd like to invite you to Codeforces Round #452 (Div. 2). It'll be held on Sunday, December 17 at 09:35 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

The round is rated.

This round is held on the tasks of the second day of the municipal stage All-Russian Olympiad of Informatics 2017/2018 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU. A convincing request to the participants of the municipal stage in Saratov to do not participate in this contest.

Great thanks to Nikolay Kalinin (KAN) and Grigory Reznikov (gritukan) for helping me preparing the contest, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Alexey Ripinen (Perforator) for writing solutions.

You will be given six problems and two hours to solve them. The scoring distribution will be published soon. Good luck everyone!

UPD The scoring distribution 500-1000-1500-1750-2250-2500

UPD: The system testing is starting now, but upsolving, virtual participation and viewing solutions and tests will be disabled till the end of the olympiad in Saratov (around 2-3 hours from now). Hope for your understanding. Editorial will be posted after the olympiad as well.

UPD Congratulations to the winners!

  1. Spyt

  2. nouniv

  3. Fop_zzZ

  4. szakubki

  5. KhuyenKhichPreVOI

UPD Editorial

Read more »

 
 
 
 
  • Vote: I like it  
  • +159
  • Vote: I do not like it  

By fcspartakm, history, 4 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +51
  • Vote: I do not like it  

By fcspartakm, history, 4 months ago, translation, In English,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #451 (Div. 2). It'll be held on Saturday, December 16 at 14:35 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

The round is rated.

This round is held on the tasks of the municipal stage All-Russian Olympiad of Informatics 2017/2018 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU. A convincing request to the participants of the municipal stage in Saratov to do not participate in this contest.

Great thanks to Grigory Reznikov (gritukan) and Nikolay Kalinin (KAN) for helping me preparing the contest, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Alexey Ripinen (Perforator) and Roman Glazov (Arc) for writing solutions.

You will be given six problems and two hours to solve them. The scoring distribution 500-750-1500-1750-2000-2500. Good luck everyone!

UPD Editorial

UPD2 Congratulations to the winners!

  1. Namys

  2. MSeashell

  3. zhouyidong

  4. Hattori_Heiji

  5. meoconn

Read more »

 
 
 
 
  • Vote: I like it  
  • +201
  • Vote: I do not like it  

By fcspartakm, history, 7 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +49
  • Vote: I do not like it  

By fcspartakm, 9 months ago, translation, In English,

Hello, Codeforces!

The latest innovation in Codeforces is introduction Google calendar with information about the upcoming contests. To view calendar you can visit tab "Calendar" in the top menu.

The Codeforces contests are adding in calendar automatically. Also you can add contests from the other programming platforms. Each red user has this option. In addition, we will grant the rights to edit the calendar to employees/enthusiasts of other popular platforms.

In the tab "Add" you can add information about upcoming contest. The form shown below will help you for this.

Please, add to the calendar classic algorithmic contests which duration does not exceed a day. Also the contest must be publicly available, i. e. had English statements and open for a wide range of participants. We ask you to use short names for competitions, as it is presented in the examples, for convenience and uniformity.

Also you can edit or remove information about upcoming events in corresponding tabs.

We hope that the calendar will be useful for you and will help to planning your time and learn about all upcoming programming events.

In our plans to expand the functionality of the calendar. Write about your ideas for improving it in the comments.

Read more »

 
 
 
 
  • Vote: I like it  
  • +646
  • Vote: I do not like it  

By fcspartakm, 12 months ago, translation, In English,

Hello, Codeforces!

It is time to tell about the improvements in Polygon. It is a system for the preparation of programming problems. All Codeforces rounds and many other olympiads prepared in Polygon. Everyone at any time can use this system.

Common

A special fields with examples now displayed on a page with a list of files which used in problem and on checker, interactor and validator pages. It will be very useful for the new users and will help them faster understand the system.

Read more »

 
 
 
 
  • Vote: I like it  
  • +209
  • Vote: I do not like it  

By fcspartakm, history, 13 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +17
  • Vote: I do not like it  

By fcspartakm, history, 13 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +23
  • Vote: I do not like it  

By fcspartakm, history, 16 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +52
  • Vote: I do not like it  

By fcspartakm, history, 16 months ago, translation, In English,

Hello, Codeforces! It's me again=)

I'd like to invite you to Codeforces Round #387 (Div. 2). It'll be held on Monday, December 19 at 05:05 MSK and Div. 1 participants can join out of competition.

This round is held on the tasks of the second day of the municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU.

Great thanks to Nikolay Kalinin (KAN) for helping me preparing the contest, to Tatiana Semenova (Tatiana_S) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Vladimir Petrov (P1kachu), Alexey Ripinen (Perforator), Mikhail Levshunov (Levshunovma), Mikhail Piklyaev (PikMike), Aleksey Slutskiy (ferc), Ivan Androsov (BledDest), Oleg Smirnov (Oleg_Smirnov) and Roman Kireev (RoKi) for writing solutions and editorials.

You will be given six problems and two hours to solve them. The scoring distribution will be announced later. Good luck everyone!

UPD The scoring distribution 500-1000-1500-2000-2000-2500

UPD2 Editorial

UPD3 Congratulations to the winners!

  1. mxh0724

  2. vigoss18

  3. haleyk100198

  4. ouch__casquinha

  5. peijinz

Read more »

 
 
 
 
  • Vote: I like it  
  • +131
  • Vote: I do not like it  

By fcspartakm, history, 16 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +52
  • Vote: I do not like it  

By fcspartakm, history, 16 months ago, translation, In English,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #386 (Div. 2). It'll be held on Sunday, December 18 at 13:35 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

This round is held on the tasks of the municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU.

Great thanks to Nikolay Kalinin (KAN) for helping me preparing the contest, to Tatiana Semenova (Tatiana_S) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Vladimir Petrov (P1kachu), Alexey Ripinen (Perforator), Mikhail Levshunov (Levshunovma), Mikhail Piklyaev (PikMike), Aleksey Slutskiy (ferc), Ivan Androsov (BledDest), Oleg Smirnov (Oleg_Smirnov) and Roman Kireev (RoKi) for writing solutions and editorials.

It will be a little unusual round — you will be given seven problems and two and half hours to solve them. The scoring distribution will be 500-1000-1500-2000-2500-3000-3000. Good luck everyone!

UPD Editorial

UPD2 Congratulations to the winners!

  1. IHaveShort

  2. tqyaaaaaaaang

  3. UmaThurman

  4. jrMz

  5. FIKS_samurai

Read more »

 
 
 
 
  • Vote: I like it  
  • +179
  • Vote: I do not like it  

By fcspartakm, history, 18 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +28
  • Vote: I do not like it  

By fcspartakm, history, 19 months ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +85
  • Vote: I do not like it  

By fcspartakm, history, 19 months ago, translation, In English,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #375 (Div. 2). It'll be held on Monday, October 3 at 14:35 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. They were prepared by me and Mike Mirzayanov (MikeMirzayanov).

Great thanks to Gleb Evstropov (GlebsHP) for helping me preparing the contest and for the idea of the most tricky problem, which was specially made for this round, to Tatiana Semenova (Tatiana_S) for translating the statements into English and to Nikolay Kalinin (KAN) for writing solutions and very helpful advices.

It will be a little unusual round — you will be given six problems and two and half hours to solve them.

Score distribution 500-1000-1500-2000-2500-3000. Good luck everyone!

UPD Editorial

Read more »

 
 
 
 
  • Vote: I like it  
  • +182
  • Vote: I do not like it  

By fcspartakm, history, 21 month(s) ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Soon...

Read more »

 
 
 
 
  • Vote: I like it  
  • +68
  • Vote: I do not like it  

By fcspartakm, history, 21 month(s) ago, translation, In English,

Hello, Codeforces!

Educational Codeforces Round 15 will take place on 29 July 2016 at 18:00 MSK for the first and the second divisions.

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

We with Mike MikeMirzayanov Mirzayanov decided to prepare this Round, because Edvard Edvard Davtyan is very busy at his new job. Good luck and have fun!

UPD Competition completed! Thank you all! Editorial

Read more »

 
 
 
 
  • Vote: I like it  
  • +157
  • Vote: I do not like it  

By fcspartakm, history, 23 months ago, translation, In English,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #354 (Div. 2). It'll be held on Wednesday, May 25 at 18:05 MSK (Moscow time) and Div. 1 participants can join out of competition. As usual round starts in the unusual time!!!

Me an Grigory Oxxxymiron Akhremenko prepared the tasks for this Round. It is the debut for Grigory as the problemsetter.

Great thanks to Gleb GlebsHP Evstropov for helping us preparing the contest, to Mike MikeMirzayanov Mirzayanov for the great Polygon platform and for Ilya IlyaLos Los and for Artur ikar Svechnikov for writing solutions.

The scoring distribution will be announced later. Good luck everyone!

UPD Score distribution 500-1000-1500-2250-2250

UPD2 Editorial

UPD3 Congratulations to the winners

  1. Thomas66

  2. super_wormy

  3. Valkata.a.k.a.TheHacker

  4. tcchung

  5. Karakotov

UPD4 See you soon!=)

Read more »

 
 
 
 
  • Vote: I like it  
  • +182
  • Vote: I do not like it  

By fcspartakm, history, 23 months ago, translation, In English,

670A - Holidays

There are many ways to solve this problem. Let's talk about one of them. At first we need to write a function, which takes the start day of the year and calculate the number of days off in such year. To make it let's iterate on the days of the year and will check every day — is it day off or no. It is easy to show that if the first day of the year equals to the first day of the week (i.e. this day is Monday) in this year will be minimum possible number of the days off. If the first day of the year equals to the first day off of the week (i.e. this day is Saturday) in this year will be maximum possible number of the days off.

670B - Game of Robots

To solve this problem we need to brute how many identifiers will called robots in the order from left to right. Let's solve this problem in one indexing. Let the current robot will call i identifiers. If

Unable to parse markup [type=CF_TEX]

let's make k = k - i and go to the next robot. Else we need to print a[k], where a is the array with robots identifiers and end our algorithm.

670C - Cinema

We need to use map-ом (let's call it cnt) and calculate how many scientists knows every language (i. e. cnt[i] equals to the number of scientists who know the language number i). Let's use the pair res, where we will store the number of \textit{very pleased} scientists and the number of \textit{almost satisfied} scientists. At first let res = make_pair(0, 0). Now we need to iterate through all movies beginning from the first. Let the current movie has the number i. Then if res < make_pair(cnt[b[i]], cnt[a[i]]) let's make res = make_pair(cnt[b[i]], cnt[c[i]]) and update the answer with the number of current movie.

670D1 - Magic Powder - 1

This problem with small constraints can be solved in the following way. Let's bake cookies one by one until it is possible. For every new cookie let's calculate val — how many grams of the magic powder we need to bake it. For this let's brute all ingredients and for the ingredient number i if a[i] ≤ b[i] let's make b[i] = b[i] - a[i], else let's make b[i] = 0 and val = val + a[i] - b[i]. When we bruted all ingredients if val > k than we can't bake more cookies. Else let's make k = k - val and go to bake new cookie.

670D2 - Magic Powder - 2

Here we will use binary search on the answer. Let's we check the current answer equals to cur. Then the objective function must be realized in the following way. Let's store in the variable cnt how many grams of the magic powder we need to bake cur cookies. Let's iterate through the ingredients and the current ingredient has the number i. Then if a[icur > b[i] let's make cnt = cnt + a[icur - b[i]. If after looking on some ingredient cnt becomes more than k the objective function must return false. If there is no such an ingredient the objective function must return true.

If the objective function returned true we need to move the left end of the binary search to the cur, else we need to move the right end of the binary search to the cur.

670E - Correct Bracket Sequence Editor

Let's solve this problem in the following way. At first with help of stack let's calculate the array pos, where pos[i] equals to the position of the bracket which paired for the bracket in the position i. Then we need to use two arrays left and right. Then left[i] will equals to the position of the closest to the left bracket which did not delete and right[i] will equals to the position of the closest to the right bracket which did not delete. If there are no such brackets we will store -1 in the appropriate position of the array.

Let's the current position of the cursor equals to p. Then if the current operation equals to \texttt{L} let's make p = left[p] and if the current operation equals to \texttt{R} let's make p = right[p]. We need now only to think how process the operation \texttt{D}.

Let lf equals to p and rg equals to pos[p]. If lf > rg let's swap them. Now we know the ends of the substring which we need to delete now. If right[rg] =  =  - 1 we need to move p to the left (p = left[lf]), else we need to move p to the right (p = right[rg]). Now we need to recalculate the links for the ends of the deleted substring. Here we need to check is there any brackets which we did not deleted to the left and to the right from the ends of the deleted substring.

To print the answer we need to find the position of the first bracket which we did not delete and go through all brackets which we did not delete (with help of the array right) and print all such brackets. To find the position of the first bracket which we did not delete we can store in the array all pairs of the ends of substrings which we deleted, then sort this array and find the needed position. Bonus: how we can find this position in the linear time?

670F - Restore a Number

At first let's find the length of the Vasya's number. For make this let's brute it. Let the current length equals to len. Then if len equals to the difference between the length of the given string and the number of digits in len if means that len is a length of the Vasya's number.

Then we need to remove from the given string all digits which appeared in the number len, generate three strings from the remaining digits and choose smaller string from them — this string will be the answer. Let t is a substring which Vasya remembered. Which three strings do we need to generate?

  1. Let's write the string t and after that let's write all remaining digits from the given string in the ascending order. This string can be build only if the string t does not begin with the digit 0.

  2. Let's write at first the smallest digit from the remaining digits which does not equal to 0. If we have no such a digit we can't build such string. Else we need then to write all digits with smaller than the first digit in the t in the ascending order, then write the string t and then write all remaining digits in the ascending order.

  3. Let's write at first the smallest digit from the remaining digits which does not equal to 0. If we have no such a digit we can't build such string. Else we need then to write all digits with smaller than or equal to the first digit in the t in the ascending order, then write the string t and then write all remaining digits in the ascending order.

Also we need to separately consider the case when the Vasya's number equals to zero.

Read more »

 
 
 
 
  • Vote: I like it  
  • +89
  • Vote: I do not like it  

By fcspartakm, history, 2 years ago, In Russian,

Лучше поздно, чем никогда...

644A - Берляндский парламент

Из условия задачи следует, что либо демократов и республиканцев поровну (если n чётно), либо демократов на одного больше (если n нечётно). Так как представители одной и той же партии не должны сидеть на соседних креслах, представим парламентский зал в виде шахматной доски, где левая верхняя клетка будет белой. Затем начнем перебирать ряды клеток сверху вниз, а клетки в каждом ряду слева направо и будем по очереди сажать парламентариев — демократов в белые клетки, а республиканцев в черные.

Таким образом, если n > a·b, ответом будет  - 1. В противном случае рассадка всегда найдется.

Для определения того, какого цвета клетка (и, соответственно, кого нужно в нее посадить), находящаяся в i-й строке и j-м столбце (в случае, если они нумеруются с единицы), можно поступить следующим образом. Если (i + j)mod2 = 0, значит соответствующая клетка должна быть белой, иначе чёрной.

Пример решения

644B - Обработка запросов

Для решения данной задачи очень удобно воспользоваться структурой данных, которая называется очередь.

Очередь — это структура данных со следующим принципом доступа к элементам: «первый пришёл — первый ушёл». Добавление элемента (\textit{push}) возможно лишь в конец очереди, а взять элемент из очереди можно только из её начала (\textit{front}). Удалить элемент можно также только из начала очереди (\textit{pop}).

В данной задаче нужно было перебрать все запросы в хронологическом порядке. Будем хранить в очереди времена окончания обработки запросов. Для текущего запроса, пока в начале очереди находятся запросы, которые закончат обрабатываться не позднее, чем появился текущий запрос, нужно просто удалять их из начала очереди, так как они никак не повлияют на текущий. Если после этих действий размер очереди равен максимальному допустимому числу, ответ для текущего запроса  - 1. В противном случае, нужно добавить время окончания обработки текущего запроса в очередь, вывести это время и продолжить алгоритм.

Пример решения

644C - Псевдонимы серверов

Для решения данной задачи воспользуемся структурами данных map и set. Переберем все имеющиеся адреса страниц, затем получим hostname и path для каждого адреса, и добавим текущий path в множество путей для текущего hostname (для этого будет нужен map, где ключом будет строка hostname, а значением — множество строк path).

Осталось только объединить все hostname, множества путей которых совпадают (это можно сделать с помощью map, где ключом будет множество строк path, а значением — вектор строк hostname), и вывести те группы, размер которых больше единицы.

Пример решения

Read more »

 
 
 
 
  • Vote: I like it  
  • +29
  • Vote: I do not like it