fcspartakm's blog

By fcspartakm, 2 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, 2 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, 2 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, 2 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, 2 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, 5 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, 7 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, 10 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, 11 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, 12 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, 14 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, 14 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, 14 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, 14 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, 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  
  • +28
  • Vote: I do not like it  

By fcspartakm, history, 17 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, 17 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, 19 months 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, 19 months 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, 21 month(s) 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, 22 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 k - i > 0 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, 22 months 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  

By fcspartakm, history, 23 months ago, In Russian,

649A - Любимые числа Поликарпа

Для решения данной задачи нужно воспользоваться фактом, что степени двойки быстро растут, и максимальная степень двойки, на которую может делится число, не превосходящее 109, равна 29. Поэтому нужно просто проитерироваться по заданным числам, найти максимальную степень двойки, на которую делится текущее число и обновить ответ этой максимальной степенью.

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

649B - Этажи

Для решения данной задачи нужно было аккуратно реализовать то, что написано в условии. Основная сложность заключалась в определении номера подъезда и номера этажа по номеру квартиры. Это можно было сделать следующим образом: если в доме n подъездов, в каждом подъезде по m этажей, а на каждом этаже по k квартир, то квартира с номером a находится в подъезде номер (a - 1) / (m * k) и на этаже номер ((a - 1)%(m * k)) / k, причем эти номера 0-индексированы, что удобно для дальнейших вычислений. После определения номеров подъездов и этажей, нужно было рассмотреть два случая — когда номера подъездов Эдварда и Наташи равны (тогда нужно было выбрать, что оптимальнее — доехать на лифте или подняться/спуститься по лестнице), и когда эти номера различны (тут нужно было не забыть, что дом круглый, и выбрать нужное направление).

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

649C - Печать условий

Сначала отсортируем заданные размеры комплектов задач в неубывающем порядке. Затем нужно начать перебирать комплекты задач, начиная с наименьшего. Если мы не можем напечатать текущий комплект, то никакой следующий комплект мы гарантированно не сможем напечатать, поэтому нужно вывести ответ и закончить алгоритм. В противном случае нужно напечатать текущий комплект, увеличить ответ на единицу и перейти к следующему комплекту. Каждый комплект оптимально печатать следующим образом. Пусть x — это оставшееся количество двусторонних листов, y — это оставшееся количество односторонних листов, а a — это количество страниц в текущем комплекте задач. Если x = 0 и y = 0, то напечатать текущий комплект мы точно не сможем. Если a нечетно и y > 0, напечатаем одну страницу на одностороннем листе и уменьшим a и y на единицу, иначе если a нечетно и x > 0, напечатаем одну страницу на двустороннем листе (который больше использовать не будем) и уменьшим a и x на единицу. Теперь a это всегда четное число. Поэтому выгодно сначала по максимуму использовать для печати двусторонние листы, а если их не хватает — односторонние. Если и односторонних листов не хватает, то текущий комплект распечатать мы не сможем.

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

649D - Дефрагментация памяти

Для решения данной задачи нужно сформировать массив, который будет равен памяти компьютера после дефрагментации. Для этого, например, можно запомнить про каждый процесс (в порядке слева направо) количество ячеек, которые он занимает. Верно следующее утверждение — пока дефрагментация не закончена, всегда будет две такие ячейки с номерами pos1 и pos2 в памяти компьютера, что ячейка pos1 пуста, а ячейка pos2 занята процессом, который по окончании дефрагментации должен находится в ячейке номер pos1. Таким образом, ответ на задачу, это количество таких ячеек в памяти, которые должны быть заняты каким-то процессом после окончания дефрагментации, причем до начала дефрагментации эти ячейки либо пусты, либо в них записаны другие процессы (отличные от тех, которые должны быть записаны после дефрагментации).

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

649E - Автобус

Изначально отсортируем всех путешественников по их начальным позициям в неубывающем порядке, а при равенстве позиций — отсортируем по дистанциям, которые путешественникам нужно преодолеть, также в неубывающем порядке. Затем необходимо бинарным поиском подобрать минимальное количество мест в автобусе, которых будет достаточно для перевозки a путешественников.

Целевая функция бинарного поиска должна работать следующим образом. Пусть mid — количество мест в автобусе. Тогда найдем cnt — максимальное количество путешественников, которых мы сможем подвезти на таком автобусе. Это можно сделать с помощью set-a, в котором мы будем хранить позиции выходов путешественников, которые зашли в автобус, и их индексы.

Переберем всех путешественников слева направо (в том порядке, в котором они были отсортированы). Пока в set-е есть путешественники, которые выйдут из автобуса не позднее момента, когда зайдет текущий путешественник, удалим позиции их выходов из set и добавим их индексы в отдельный вектор ans. В противном случае, если самая дальняя позиция выхода путешественника в set-е больше, чем потенциальная позиция выхода текущего путешественника, заменим в set-е самого дальневыходящего путешественника на текущего.

После того, как мы переберем всех путешественников, добавим индексы всех оставшихся в set-е путешественников в ans. Если размер вектора ans меньше a, сдвинем в mid левую границу бинарного поиска, иначе сдвинем в mid правую границу бинарного поиска. После бинарного поиска, запустим еще раз целевую функцию от ответа и выведем индексы путешественников из вектора ans.

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

Read more »

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

By fcspartakm, history, 23 months ago, In Russian,

648A - Наибольший подъем

Для решения данной задачи насчитаем высоту каждой горы и сохраним ее в массиве h[], где h[j] равно высоте j-й горы. Для этого обойдем заданную матрицу, и если элемент, стоящий в строке i и в столбце j (строки и столбцы 0-индексированы), равен звездочке, обновим высоту j-й горы: h[j] = max(h[j], n - i). Осталось просто проитерироваться по столбцам от 0 до m — 2 включительно, и, если текущий столбец равен j, обновить величину максимального подъема или максимального спуска величиной |h[j + 1] - h[j]|.

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

648B - Собери стол

Для решения данной задачи сначала посчитаем длину одной собранной ножки стола и сохраним ее в переменную len (len = sum / n, где sum — это суммарная длина всех частей, а n — количество ножек стола). Сохраним длины всех частей ножек в массив a[] и отсортируем его по возрастанию. Затем переберем части ножек переменной i от 0 до n - 1 включительно и будем выводить в ответ пары вида (a[i], len - a[i]).

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

648C - Путь Робота

Сначала найдем стартовую позицию Робота, сохраним ее и присвоим значение стартовой позиции звездоке. Так как по условию задана ломаная без самопересечений и самокасаний верен следующий алгоритм: если есть соседняя с текущей клетка, в которой стоит звездочка, перейдем в соседнюю клетку, значение которой равно звездочке, и присвоим ее значение точке (при этом выведем букву, соответствующую направлению, в котором мы перешли). При этом соседняя клетка должна быть отлична от той, из которой мы пришли в текущую клетку. Если нет соседней клетки с звездочкой, значит мы обошли всю ломаную и нужно закончить работу программы.

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

648D - Собачки и миски

Если представить каждую миску в виде отрезка [uj - tj, uj + tj], то i-я собачка сможет покушать из j миски, если uj - tj ≤ xi ≤ uj + tj.

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

Легко видеть, что такая жадность приводит к оптимальному ответу:

  • Если самая левая собачка может покушать, то нет смысла ей не кушать, поскольку этим мы убираем одну миску и ухудшим ответ на единицу;
  • Рассмотрим те миски из которых может покушать самая левая собачка. Все эти миски будут доступны и остальным собачкам кроме тех у которых правая граница находится слишком далеко влево. Таким образом, если мы хотим взять какую-либо миску (а мы уже поняли из пункта 1, что это стоит сделать), то выгоднее будет взять миску с самым левым правым концом, так мы не ухудшим выбор для собачек справа.

По этой задаче можно было попробовать написать другие жадности, но многие являются неправильными.

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

Сложность: O(nlogn) или O(n) в зависимости от структуры данных (*set* или queue).

Решения на С++

648E - Собери число

Заметим, что при построении ответа нам в любой момент важен только лишь остаток от деления текущего его префикса на k. Действительно, если текущий префикс ответа имеет остаток от деления на k, равный r, то при приписывании к префиксу числа ai этот остаток станет равный остатку от деления на k числа r·10li + ai (li — количество цифр в записи числа ai).

Тогда, очевидно, нас интересует получать любой остаток от деления такой операцией, используя минимальное количество цифр в записи. Конечно, остаток 0 мы можем получить сразу, используя пустой префикс, поэтому для остатка 0 нас будет интересовать второй по величине ответ.

Все описанное выше позволяет нам построить граф на k вершинах (от 0 до k - 1, соответственно остаткам), ребра в котором определяются числами ai: из вершины v в вершину длины li, означающее, что с помощью дописывания li цифр мы можем из префикса с остатком v получить префикс с остатком u. Легко заметить, что некоторые ai в этом графе будут соответствовать одним и тем же ребрам (сейчас их nk) — это числа с одинаковой длиной десятичной записи и остатком от деления на k, поэтому стоит оставить лишь уникальные по такому критерию числа (их будет не больше 10k), и тогда количество ребер не будет превышать 10k2.

Теперь все, что от нас требуется — найти длину кратчайшего непустого пути из вершины 0 в саму себя же в построенном графе. Чтобы избежать столь неприятной цикличности, давайте просто добавим дополнительную вершину k, имеющую те же исходящие ребра, что и вершина 0, считая, что такой остаток может иметь лишь пустой префикс. Теперь задача сводится к нахождению кратчайшего пути из вершины k в вершину 0, которую можно решить алгоритмом Дейкстры за O(k2). Однако, в силу специфичности задачи, решение алгоритмом Форда-Беллмана (с правильными отсечениями, конечно) так же проходит все тесты, хоть в теории и имеет столь большие O(k3).

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

Пример решения алгоритмом Дейкстры

Read more »

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

By fcspartakm, history, 2 years ago, translation, In English,

610A — Pasha and Stick

If the given n is odd the answer is 0, because the perimeter of any rectangle is always even number.

If n is even the number of rectangles which can be construct equals to n / 4. If n is divisible by 4 we will count the square, which are deprecated, because we need to subtract 1 from the answer.

Asymptotic behavior — O(1).

610B — Vika and Squares

At first let's find the minimum in the given array and store it in the variable minimum. It is easy to understand, that we always can paint n * minimum squares. So we need to find such a minimum in the array before which staying the most number of elements, which more than the minimum. In the other words we need to find 2 minimums in the array which are farthest from each other (do not forget about cyclical of the array). If there is only one minumum we need to start paint from the color which stay in the array exactly after the minimum (do not forget about cyclical of the array too). It can be done with help of iterations from the left to the right. We need to store the position of the nearest minimum in the variable and update her and the answer when we meet the element which equals to minimum.

Asymptotic behavior — O(n), where n — the number of different colors.

610С — Harmony Analysis

Let's build the answer recursively. For k = 0 the answer is  - 1 or  + 1. Let we want to build the answer for some k > 0. At first let's build the answer for k - 1. As the answer for k let's take four copies of answer for k - 1 with inverting of values in last one. So we have some fractal with 2 × 2 base: 00, 01. Let's prove the correctness of such building by induction. Consider two vector from the top (down) half: they have zero scalar product in the left half and in the right, so the total scalar product is also equals to zero. Consider a vector from the top half and from the down: their scalar products in the left and the right halfs differs only in sign, so the total scalar product is also zero.

Note the answer is also is a matrix with element i, j equals to \texttt{+} if the number of one bits in number i|j is even.

Complexity O((2k)2).

610D — Vika and Segments

At first let's unite all segments which are in same verticals or horizontals. Now the answer to the problem is the sum of lengths of all segments subtract the number of intersections. Let's count the number of intersections. For this let's use the horizontal scan-line from the top to the bottom (is can be done with help of events — vertical segment is open, vertical segment is close and hadle horizontal segment) and in some data structure store the set of x-coordinates of the open segments. For example we can use Fenwick tree with precompression of the coordinates. Now for current horizontal segment we need to take the number of the opened vertical segmetns with value x in the range x1, x2, where x — vertical where the vertical segment are locating and x1, x2 — the x-coordinates of the current horizontal segment.

Asymptotic behavior: O(nlogn).

610E — Alphabet Permutations

Consider slow solution: for operations of the first type reassign all letters, for operations of the second type let's iterate over the symbols in s from left to right and maintain the pointer to the current position in alphabet permutation. Let's move the pointer cyclically in permutation until finding the current symbol from s. And move it one more time after that. Easy to see that the answer is one plus the number of cyclic movements. Actually the answer is also the number of pairs of adjacent symbols in s that the first one is not righter than the second one in permutation. So the answer depends only on values of cntij —- the number of adjacent symbols i and j.

To make solution faster let's maintain the segment tree with matrix cnt in each node. Also we need to store in vertex the symbol in the left end of segment and in the right end. To merge two vertices in the segment tree we should simply add the values in the left and in the right sons in the tree, and update the value for the right end of the left segment and the left end of the right segment.

Complexity: O(nk2 + mk2logn).

Read more »

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