Polichka's blog

Codeforces Round #108 (Div. 2)
By Polichka, 3 months ago, translation, In English

Good day!

We have got over two weeks of our new term. And we are glad to see you on our regular rating Codeforces round for Div.2 participants. And all who wants can take part in this competition.

This round has been prepared by a team of three people: Gerald, NALP and Polichka. We are grateful for their help in preparation and translation to Artem Rakhov(RAD), Mike Mirzayanov (MikeMirzayanov) and Maria Belova(Delinur).

Today Peter entangled in the tables:-( And you can help him! It’s rather easy!

Score distribution: 500-1000-1500-2500-2500

Easy solutions and high rating to all!

UPD:

Thanks all for participation!

You can read the tutorial on this link: Tutorial.

Read more »

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

Codeforces Round #106 (Div. 2)
By Polichka, 3 months ago, translation, In English

Hello everybody!

Today Codeforces Round # 106 for Div2 participants will be. And all who wants can take part in this competition. You will have the opportunity to break from parents with Peter, to learn some interesting facts about the Martians and to solve, of course, interesting problems for you as we hope.

This round has been prepared by a team of three people: Gerald, NALP и Polichka. We express our gratitude for their help to Artem Rakhov (RAD), Mike Mirzayanov (MikeMirzayanov) and Maria Belova (Delinur) .

Score distribution: 500-1000-1500-2500-2500.

Good luck and high rating to all!

Read more »

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

Codeforces Round #103 (Div. 2) Разбор Задач.
By Polichka, 4 months ago, translation, In English
Problem A

It's clear that the leftmost soldier with the maximum height should be the first and the rightmost soldier with the minimum height should be the last. Thus we will minimize the number of  swaps. And the answer is number of leftmost soldier with the maximum height - 1 + n - number of rightmost soldier with the minimum height. And if the leftmost soldier with the maximum height is more right then the rightmost soldier with the minimum height we should subtract one from the answer.

Problem B

Let's try to check all integer points of the table perimeter and add to the answer such of them that don't cover by circles of radiators. Let xa < xb and ya < yb, and if it's not true then swap xa and xb, ya and yb. So generals sit in the next integer points: (xa, y), (xb, y), (x, ya), (x, yb), where  xa ≤ x ≤ xb и ya ≤ y ≤ yb. We should be attentive when we count the generals who sits in points: (xa, ya), (xa, yb), (xb, ya), (xb, yb),  that don't count them twice.

Problem C

Let's count number of each letter in the second string and save it, for example, in array a[1..26]. For the first strings' prefix of length n, where n is the length of second string, (it's the first substring) we count number of each letter in array b[1..26]. We don't count characters ``\texttt{?}''. If there are b[i] ≤ a[i] for all i, then it's good substring. Then go to the second substring: subtract from the array b the first character:  b[s[1] - 'a' + 1] –  and add n + 1 character: b[s[n + 1] - 'a' + 1] +  + . If some of these characters is ``\texttt{?}'' then we shouldn't do for it the subtraction or addition. Then repeat the showed check and go to the next substring. Let's repeat this procedure for all substrings of length n.

Problem D

d[i] --- the minimum distance from vertex s to vertex i, that counted by algorithm of Dijkstra. "et's count the number of points on each edge of the graph that are on the distance l form the vertex s (and l --- the minimum distance from these points to s).

For edge (u, v):

if d[u] < l and l - d[u] < w(u, v) and w(u, v) - (l - d[u]) + d[v] > l then add to the answer the point on this edge, the distance of which to the vertex u is l - d[u];

if d[v] < l and l - d[v] < w(u, v) and w(u, v) - (l - d[v]) + d[u] > l then add to the answer the point on this edge, the distance of which to the vertex v is l - d[v];

if d[v] < l and d[u] < l and d[u] + d[v] + w(u, v) = 2 * l then add to the answer the point on this edge, the distance of which to the vertex v is l - d[v] and to the vertex u is l - d[u].

And if d[i] = l, then let's add to the answer this point.

Problem E

It's clear that the nearest squares of the secondary diagonal to some sportsman form the "segment" of the squares of the secondary diagonal. Let's write these segments for each sportsman.

Let's consider sportsmen so that we should compare to each sportsman excactly one square of the secondary diagonal from his "segment" and to each square of the secondary diagonal no more then one sportsman. It's clear that sportsmen can reach theirs squares without occupying the same square simultaneously with another sportsman. We should maximize the number of choosen sportsmen. And solution of this reformulated problem is greedy.

Read more »

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

Codeforces Beta Round #28 (Разбор задач A и B)
By Polichka, 20 months ago, In Russian

А. Задача Бендера.

 

Будем говорить, что мы крепим j-ый прут к i-ому гвоздю, если мы крепим j-ый прут местом сгиба к i -ому гвоздю.

 

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

Если задача имеет решение, то нам надо выбрать к каким по четности гвоздям мы будем крепить прутья, а также поднабор из n / 2 прутьев, который и будет считаться ответом.

Если мы крепим j-ый прут к i-ому гвоздю, то len[j] = dist(i, i - 1) + dist(i, i + 1), где len[j] - длина j-ого прута, а dist(i, k) - расстояние между гвоздями с номерами i и k.

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

 

B. pSort.

 

Понятно, что мы можем поменять содержимое ячеек i и j, если |i - j| = di или |i - j| = dj.

Переформулируем задачу: дана перестановка, нам надо ее отсортировать, используя заданные правила обменов, описанные выше.

Построим граф, вершинами в котором являются ячейки массива, а ребро существует между вершинами i и j, если возможен обмен между ними. Граф получаем неориентированный. То есть, если из вершины i в полученном графе достижима вершина j, то возможна такая серия обменов, что содержимое ячейки i поменяется с содержимым ячейки j.

Перестановку возможно отсортировать, если для всех i верно, что из вершины i достижима вершина p[i], где p - исходная перестановка.

 

Read more »

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

Codeforces Beta Round #28 (Codeforces format)
By Polichka, 20 months ago, translation, In English

Attention-Attention!!!

Today Saratov SU #1 (Gerald, Polichka, Fefer) team invites all of you to take part in Codeforces Beta Round #28. 

We began studing sport-programming in school. But when we entered the Saratov State University we took it seriously and made our way from SU #7 to Saratov SU #1. Now our first-grade ambition is to justify this number.

We are going to offer you 5 interesting problems. You will be helping some good people to deal with their problems, will be solving some administrative tasks, will be playing some interesting games and also will be saving the World.

Thanks to everyone for their help in preparing this round. 

Successful hacks and fast accepteds!
With best regards, Saratov SU #1.

UPD: Ratings have been updated.

UPD:

Read more »

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