### Sammarize's blog

By Sammarize, history, 16 months ago, ,

Подскажите, пожалуйста, возможно ли сейчас создать тренировку, в которой некоторые задачи будут из полигона, а некоторые — с CodeForces? И если да, то как?

•
• +5
•

By Sammarize, 3 years ago, translation, ,

In this post I want to describe in short how to write a formulas on Codeforces. In fact it is short introduction to the markup language used on Codeforces.

## Three important rules.

Foremost rule: formula me place in dollars (\$), as well as in parentheses.

Another important rule: if you want to apply some operation to some group of symbols it is necessary to form the block using the curly braces. For instance, 2^x+y = 2x + y, but 2^{x+y} = 2x + y.

Third rule — for perfectionists. For traffic economy Codeforces print simple formulas by usually text. Sometimes it is not very pretty: C_{x_i+y_i-2}^{x_i-1} = Cxi + yi - 2xi - 1. Is this case you can add command \relax at the beginning of the formula. Then the formula is guaranteed to be beautiful: \relax C_{x_i+y_i-2}^{x_i-1} = .

## Arithmetic operations.

Addition and subtraction can be written ordinary symbols + and -. Multiplication is usually indicated by a null character (xy is the produst of numbers x and y) or by symbol (\cdot). If it is necessary to multiply two complex expressions (), or are important both factors, not just the value of the product (in expressions of type field ), use the symbol  × , which may be obtained by the command \times.

The division is somewhat more complicated. Usually in mathematics division is not written in one line, but the desire is not to write the fraction of the blue, too, is understandable. In this case, you can always write a : or / (x:y, x/y).

If you want to write all the same fraction, it has two similar commands: \frac and\dfrac. After any of these commands have to write a block of the numerator and block of the denominator, for example: (\frac{1}{4}). Using \frac small fractions are obtained, which is suitable mainly for the simple fractions. If you want to write a serious big fraction you'll need \dfrac: (\dfrac{x+y}{x^2+y^2}). If the numerator and denominator of a single-character, it can not be enclosed in brackets, for example: (\frac14x), but only if the numerator is not a letter.

## The upper and lower indices.

If you want to write a lower index, you will help symbol _ and upper index (basically it is the exponent), the symbol^: (xi + yi)2 ((x_i + y_i) ^ 2). Same manner as with the fractions in the lower or upper index block can be placed, but if a single-character index, it can not do so.

## Other useful tips and special characters

Text — text (---) — not in the formulas, and in the text. This dash, not hyphen (it is not works without surrounding text)
(\dots) — three dots symbol.
(\infty) — infinity symbol.
→  (\to) — arrow right, in expressions such as xn → 0.
Many well-known mathematical functions can be typed with the '', then they will look like a formula, rather than simply as text ( = \tg, = \ln, = \lim and so on)
If you want to index are top and bottom rather than the top-right and bottom-right, use the command \limits:
= \sum_{k = 0}^nx^k
= \sum\limits_{k = 0}^nx^k.
If the brackets around a large expression small, you can make them suitable size, written before the left bracket command \left, and before right bracket command \right. For instance: = \left( \dfrac{x+y}{x^2+y^2} \right).

Thank you for the attention!

•
• +380
•

By Sammarize, 3 years ago, ,

Эй, что происходит? Почему от Codeforces остался только вклад, VK CUP и посты на главной разбиты по одному на страницу?

Картинка на случай, если это так выглядит только на моём компе, только в моём браузере, только в моём аккаунте, только в моей стране или ещё что-нибудь подобное.

•
• +8
•

By Sammarize, 3 years ago, ,

Наверное, все, кому приходилось писать текст с формулами на Codeforces, знают, что каждую формулу, если это возможно, местный TeX пытается набрать символами, и, только если не получается, вставляет картинку с формулой так, как она бы выглядела в обычном ТеХе. Иногда это выглядит нормально, например, 2·109 (2 \cdot 10^9) или (xi + yi)2 ((x_i+y_i)^2).

Но иногда получается совершенно не то, что вы хотели, например, так:

Cxi + yi - 2xi - 1 (C_{x_i+y_i-2}^{x_i-1}).

В таком случае можно поставить в начале формулы символ \quad. Это, так называемый, "символьный пробел". Он представляет из себя белый квадратик, иными словами, пустой символ, но который при этом не считается пробельным символом. Местный ТеХ по какой-то причине не знает, как этот символ написать и поэтому вставляет формулу в виде картинки в настоящем ТеХовском виде, но символьный пробел игнорируется формулой так же, как и обычный пробел, поэтому на вид формулы это никак не влияет. Получается вот что:

(\quad C_{x_i+y_i-2}^{x_i-1}).

•
• +77
•

By Sammarize, 3 years ago, translation, ,

560A - Currency System in Geraldion

Just check is the 1 in the set.

560B - Gerald is into Art

One can snuggle pictures to each other and to edge of stand.

Let's join regular triangles to three edges of hexagon (to 1st, 3rd and 5th edges).

One can check if lexicographically smallest string wich is equals to first string in statement the same as second.

Let's paint bottom-right cell to black color. Then let's calculate number of ways to came to each black cell avoiding previous black cells via dp.

559D - Randomizer

Let's remember Pick's theorem and let's consider all potencial sides of polygon separately. Do we really need to consider them all?

559E - Gerald and Path

Lightened part of path is union of disjoint segments. Hence if we know what segments of path each continious subsequence of spotlights can lighten then we can solve the problem with simple (for such problem munber) dp.

How one can to dicover this information?

When we starts with some spotlight and will add spotlights one-by-one, we can't store all information about it process because we have union of disjoint segments of each step. Union of disjoint segments have too much parameters to store all possible unions. But if we interested of possibility of segment, it is important to know only leftmost and rightmost points of union and leftmoost unlightened point beween them.

•
• +178
•

By Sammarize, 3 years ago, translation, ,

Good day for all!

I invite you to participiate in the Codeforces round 313, which is prepeared by me and tunyash. Each of us is prepared four rounds then it is our fifth of ninth round to your notice. I figured out almost all problems (except D div.1), wrote the statements and analysis of all the problems, and tunyash has developed all problems.

Gerald is not coordinator yet and you probobly missed him. In this round you will meet him again and help him in his ordinary life problems.

I want to thank Zlobober, our translator Maria Belova (Delinur) and MikeMirzayanov and all Codeforces team for this platform.

This round will be held in unusual time — 17:00 Moscow Time.

Contest finished! Welcome to editoral:
Short editoral.
Extended editoral.

Div.1 scoring distribution:

500 — 1000 — 1500 — 2250 — 2250

Div.2 scoring distribution:

500 — 1000 — 1500 — 2000 — 2500

I wish you to enjoy solving problems!

Congratulations to winners!

Div. 1:
1. TooSimple
2. qwerty787788
3. Baz93
4. ainu7
5. Endagorion

Div. 2:
1. goons_will_rule
2. lbn187
3. crawling
4. loveannie
5. Jagabee

•
• +330
•

By Sammarize, 3 years ago, translation, ,

560A - Currency System in Geraldion

If there is a banlnot of value 1 then one can to express every sum of money. Otherwise one can't to express 1 and it is minimum unfortunate sum.

560B - Gerald is into Art

It is easy to see that one can snuggle paintings to each other and to edge of board. For instance one can put one of painting right over other. Then height of two paintings equals to sum of two heights and width of two paintings is equals to maximum of two widths. Now we can just iterate orientation of paintings and board.

Let's consider regular triangle with sides of k Let's split it to regular triangles with sides of 1 by lines parallel to the sides. Big triange area k2 times larger then small triangles area and therefore big triangle have splitted by k2 small triangles.

If we join regular triangles to sides a1, a3 and a5 of hexagon we get a triangle sides of a1 + a2 + a3. Then hexagon area is equals to (a1 + a2 + a3)2 - a12 - a32 - a52.

Let us note that "equivalence" described in the statements is actually equivalence relation, it is reflexively, simmetrically and transitive. It is meant that set of all string is splits to equivalence classes. Let's find lexicographic minimal strings what is equivalent to first and to second given string. And then check if its are equals.

It is remain find the lexicographic minimal strings what is equivalent to given. For instance we can do it such a way:

String smallest(String s) {
if (s.length() % 2 == 1) return s;
String s1 = smallest(s.substring(0, s.length()/2));
String s2 = smallest(s.substring(s.length()/2), s.length());
if (s1 < s2) return s1 + s2;
else return s2 + s1;
}


Every recursive call time works is O(n) (where n is length of strings) and string splitten by two twice smaller strings. Therefore time of work this function is , where n is length of strings.

Let's denote black cells ad A0, A1, ..., Ak - 1 . First of all, we have to sort black cells in increasing order of (row, column). If cell x available from cell y, x stands after y in this order. Let Ak = (h, w). Now we have to find number of paths from (1, 1) to Ak avoiding A0, ..., Ak - 1.

Let Di is number of paths from (1, 1) to Ai avoiding A0, ..., Ai - 1. It's easy to see that Dk is answer for the problem. Number of all paths from (1, 1) to (xi, yi) is . We should subtract from that value all paths containing at least one of previous black cells. We should enumerate first black cell on the path. It could be one of previous cell that is not below or righter than Ai. For each such cell Aj we have to subtract number of paths from (1, 1) to Aj avoiding black cells multiplied by number of all paths from Aj to Ai.

We have to calculate factorials of numbers from 1 to 2·105 and inverse elements of them modulo 109 + 7 for calculating binomial coefficients.

559D - Randomizer

We can use Pick's theorem for calculate integer points number in every polygon. Integer points number on the segment between points (0, 0) and (a, b) one can calculate over GCD(a, b).

Integer points number in some choosen polynom is integer points number in basic polynom minus integer points number in segmnent of basic polynom separated by every segment of choosen polynom.

Let consider every potencial segment of polygon. We can calculate integer points number in his segment and probability that we will meet it in choosen polygon.

Probability of segment AiAi + k is . Let use note that we can calculate only segments with k < 60 because of other segmnet propapility is too small.

559E - Gerald and Path

Lighted part of walking trail is union of ligted intervals. Let's sort spotlights in increasing order of ai. Consider some lighted interval (a, b). It's lighted by spotlights with numbers {l, l + 1, ..., r} for some l and r ("substring" of spotlights). Let x0, ..., xk is all possible boundaries of lighted intervals (numbers ai - li, ai и ai + li).

Imagine, that we know possible lighted intervals of all substrings of spotlights. Let left[l][r][j] is least possible i such that set of spotlights with numbers {l, l + 1, ..., r} lighting [xi, xj].

With left we can calculate value best[R][i] maximum possible length of walking trail that could be lighted using first L spotlights in such way that xi is rightmost lighted point. It's easy to do in O(n4) because .

Now all we have to do is calculate left. Consider some substring of spotlights [l, r]. Let all spotlights in the substring oriented in some way lighting some set of points. We could consider most left (i) and most right (j) lighted points, and left bound of first lighted interval (t). If set of lighted points is interval t = j. Consider how all the values change when we add spotlight r + 1 and choose its orientation. We have new lighted interval [a, b] which is equal to [ai - li, ai] or [ai, ai + li]. Now most left lighted point is min(a, xi), most right is max(b, xj). Right bound of leftmost lighted interval does not changes if a > t or becomes equal to b, if a ≤ t.

Not for each L we can calculate dp[r][j][y] least possible i that it's possible to orient spotlights from [L, r] in such way that xi is most left lighted point xj is most right one and right bound of leftmost lighted interval is xt. Thet it's easy to calculate left[L][][]. That part is done in O(n4) too.

•
• +97
•

By Sammarize, 3 years ago, ,

По-моему, давно пора бы ввести в обиход сленговые названия для задач определённого типа. Например:

Задача-паззл: задача, решение которой состоит из большого числа маленьких простых частей, которые замучаешься писать.
Задача-бигмак: задача, к который ты не знаешь, как подступиться, с какой стороны на неё не посмотри.
Задача-бильярдный шар: задача, авторское решение которой работает на миллисекунду быстрее, чем TL.
Задача-реферат: задача, в которой надо скопировать код с e-maxx'а и немного его подправить.
Задача-пицца: задача, ключевая формула для решения которой написана прямо в условии.
Задача-шифровка: задача, самое трудное в решении которой — понять условие.

Ещё какие-нибудь?

•
• -47
•

By Sammarize, history, 3 years ago, ,

На днях случился отборочный раунд RCC. Волею судеб мне пришлось писать его в рейсовом автобусе и я решил поделиться с вами своим опытом.

Обычно я не пишу контесты по дороге, в кафешках, в шуме, с мобильника и прочих подобных условиях, но это был отборочный раунд RCC, так что я решил попробовать.

По счастью, как раз в 13:00 автобус сделал остановку на 40 минут, так что начался контест спокойно. Интернет с мобильника, на удивление, был достаточно стабильным, с этим проблем не было. Ноут лежал на коленях и был менее зафиксирован, чем я к тому привык, но к этому легко удалось удалось адаптироваться — достаточно было не опираться на него руками. Был яркий солнечный день и экран бликовал, тем более, что мне пришлось немного убавить яркость, чтобы зарядки хватило на 3 часа, однако, и к этому удалось довольно легко адаптироваться, скоро я перестал замечать блики. В общем, первые 45 минут прошли довольно успешно, я сдал А и почти дописал В. Вокруг шумели дети, которых мы везли на выезд по по случаю выпускного из 9 класса, но и к этому легко удалось адаптироваться. Можно, конечно, было надеть наушники с музыкой, но этого не потребовалось.

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

В общем, серьёзных препятствий к написанию программ не было. Однако открылась неожиданная проблема. Я тщётно пытался тестировать решение задачи B и думать о решении задач C и D — выяснилось, что из-за дражание сиденья, которое ощущалось во всём теле, совершенно невозможно было погрузиться в размышления о задачах. Через некоторое время мне пришлось выключить ноут.

А насколько вы терпимы к окружающим условиям во время контеста?

•
• +31
•

By Sammarize, history, 3 years ago, ,

А там e-maxx упал. Кто знает, будет ли он работать? Есть какие-то прогнозы?

•
• +30
•

By Sammarize, 3 years ago, translation, ,

Round 1 FHC starts in January, 17, at the 18.00 UTC.

Look this and other information here. The top 500 finishers will advance to Round 2, as well as contestant who gets the same number of points as the 500th contestant.

Round 1 will last 24 hours. This is not virtual contest, when you can choose moment when you start during these 24 hours, but 24-hour contest of full value. It is unusually decision. It is clearly that organizers wants all participants to find the convenient time to solve the problems. I hope the problemset we be completed such a way so how many times does participient can spend to solve the problems, 2 hours or 24, will not have a big impact to his result. Perhaps it is assumed that a certain set of problems will be solved by large number of participants, much more than 500, but very few people will be able to solve something else.

•
• +80
•

By Sammarize, 4 years ago, translation, ,

The mystery of creating rounds unveiled by author of the 4 of them!
The guide for preparing the round without horror-fiction and pastorals!

Thanks for RodionGork, who push me to writing this post and thanks for lucAbalo, who push RodionGork to pushing me to writing this post.

Also, many thanks to RodionGork for the translation of this post to English.

## 1. Inventing problems

It's hard to advise anything on this point. There's no some standard way of creating problems — and if one have existed we'll have only "complicated algorithmic exercises" instead of "problems". People who participated in Russian Code Cup do know well the tasks of that sort.

To cook good and interesting problem there should be some idea! which came to your mind (and later to minds of participants of the contest). Even the simplest problems of A level for the Div2 should have some idea.

So here is the warning: creative way of thinking is trained from the childhood — and since so, not all people are equally good in inventing problems. Alas!

•
• +458
•

By Sammarize, 4 years ago, ,

•
• -26
•

By Sammarize, 4 years ago, ,

Мы все давно уже, с появлением Codeforces, оценивая успешность каждого человека в СП, смотрим на два его рейтинга — здесь и на TopCoder. И часто рейтинги сильно различаются. А почему бы не сотворить объединённый рейтинг? Мысленно объединить аккаунты каждого человека на TC и CF и рассматривать все SRM'ы и CFR'ы равноправно. Формулу подсчёта рейтинга можно взять с топкодера, благо она там открыта.

Самая большая проблема — это объединить аккаунты. Поначалу можно объединить по совпадающим никам, а так же аккаунты всем известных личностей (понятно, что могут случится левые объединения, но их будет крайне мало и общей картины это не испортит). Кроме того, добавить общедоступную табличку, куда все, кто хочет, смогут написать своё соответствие.

Я бы рад сам всё это сделать, но времени нет =(

•
• +8
•

By Sammarize, 5 years ago, translation, ,

Good day for all!

I invite you to participiate in the round 194. I'm author of it. It is my fourth round, but three previous ones were a long time ago: Codeforces Beta Round #79 (Div. 1 Only), Codeforces Beta Round #94 (Div. 1 Only), Codeforces Round #110 (Div. 1) (I apologize to the div-2 participants that I have mention only div-1 round, but even one link looks bulky).

This time you will help to boy Gerald cope with his problems as in the Codeforces Beta Round #79 (Div. 1 Only). This time his problems are so serious that he became coordinator of contests on the Codeforces, to be able to throw his problems to you.

I want to thank Gerald for he is great as coordinator. When you are work with him you are fill the everythink is under control. Moreover I want to thank Maria Belova for translation problems statements to the English.

This round will be held in unusual time — 12:30 Moscow Time.

Score distribution is standart: 500 — 1000 — 1500 — 2000 — 2500.

Thanks everyone for participation, welcom to editoral.

Congratulations to winners:
Division 1:
2. RAVEman
3. PavelKunyavskiy
4. Dmitry_Egorov
6. sy2006
7. mmaxio
8. AlexDmitriev
9. niyaznigmatul
10. RomaWhite

Separate note two Ukrainian participiants, who only solve all five problems!

Division 2:
1. IMOiguanas
2. savsmail
3. suyash666
4. AntiForest
5. kang205
6. jschneider2013
7. qwe123
8. langdamao
9. 9mmlitswe
10. Renkai

•
• +248
•

By Sammarize, 5 years ago, ,

Недавно я впервые стал красным на топкодере. Конечно, сам по себе этот факт мало кому интересен. Интересно другое: став красным, я стал уникальным (ли?) обладателем всех пяти цветов (в разные моменты времени, конечно):

Жаль, что в Record Book нет пункта "повышение рейтинга в как можно большее количество раз" — я бы наверняка туда попал.

Кто-нибудь видел ещё столь же разноцветных людей на TopCoder'е или на Codeforces'е?

•
• -7
•

By Sammarize, 5 years ago, translation, ,

334A - Candy Bags

In this problem one must divide all natural numbers from 1 to n2 to groups size of n with the same sums.

Lets divide all this numbers to pairs . We can to do it since n is even and therefore n2 is even too. Then we can just make n groups consists of of these pairs.

334B - Eight Point Sets

In this problem you must to do only what's written — you must to define does this set of points sutisfies to decribed conditions.

There are many ways to define it. For instance:

1. Check if there are exactly 3 discinct x's and y's. One can put all x's to set and then get it size to find amount of distinct x's (as well as y's). Then print ugly'' if this amount isn't equals to 3.
2. Finally we have x1, x2 и x3 as well as y1, y2 и y3. Now lets check if for every pair (xi, yj) (except (x2, y2)) such point exist in given set of points.

But I think that to read editoral of this problem is not good idea. It is better to just look at the implementation.

Actually we are looking for longest sequence of natural number a1, a2, ..., ak, so that every number in it sequence is the power of three, sum of all numbers is more then n and if we remove any number sum will be less then n. To be precise we are looking for length of this sequence.

Consider minimal number ai = A in the sequence. All this numbers are divides to A since them all are powers of 3. And then, sum S of all this number is divides to A too. Suppose that n is divide to A too. Then, since S > n, then S - A ≥ n. And then if we remove A from sequence, sum of other number not less then n — contradist with second condition.

Well, we now that n is not divide to none element in sequence. Now lets find minimal k so that , and answer is .

At first lets make two remarks:

1. On every (vertical of horizontal) line we can put only one chip.
2. If there is at least one forbidden cell on the line then we can't put chip on this line.

Follow last remark we will avoid hits chip on forbidden cells. Lets avoid collisions'' of chips.

Lets consider these four line: vertical lines number i and n + 1 - i and horizontal lines with the same numbers. Chips on these lines can collides together, but con't collides to another chip. Therefore we can solve the problem for these four line independently. And finally lets observe that we can put the chip on each of these lines without cillisions as well as on the picture.

So, we can iterate all possible fours and put chip on every possible line. And don't fogot about case of two middle line in case of n is odd.

In this problem we can find the right amount of lucky tickets.

Lets consider amount of different numbers we can get from one four-digit ticket number. It is easy to iterate all this tickets, since it amount only 104. It happened that we can get almost 60 numbers from ticket on the average.

Suppose we can get number x from ticket n. It is clearly that either x - k ≥ 0 or k - x ≥ 0. If k - x ≥ 0 we can write eight-digit ticket number who will have k - x in the first four digits and n in the last four digits. It is clearly that such ticket is k-lucky. This method allows us to get almost 600 000 lucky tickets and it is enough.

333D - Characteristics of Rectangles

In this problem we must to find maximal value of minimum of values on four intersections of two rows and two columns of table.

In another words, we are looking for maximum value of min(ai1, j1, ai1, j2, ai2, j1, ai2, j2) for all i1, i2, j1, j2 such that 1 ≤ i1, i2 ≤ n, 1 ≤ j1, j2 ≤ m, i1 ≠ i2, j1 ≠ j2. Lets us binary search of the answer. For us it we must can define is there two rows and two colums with ones on all four its intersections; in other words, integers i1, i2, j1, j2 so that ai1, j1 = ai1, j2 = ai2, j1 = ai2, j2 = 1.

Lets consider all pair of natural numbers (i1, i2) so that there exist nutural number j so that ai1, j = ai2, j = 1. Existence of two equals such pairs is equals to existence of above four numbers. But it is can be only such pairs. Therefore we can make the array where we will mark pair who were meets. Lets iterate all pairs in any order until we meet repeated pair or pairs are ends. So we have solution of time .

333E - Summer Earnings

In this problem it is need to draw three circle equals together with maximum possible radius with centers in given points. In another words it is need to find triangle wich minimum side is maximal.

Unfortunately solution with bit optimize is not expected for us.

Lets call to memory two simple geometric facts. Firstly, sum of alnges of trianle is equals to . Secondly, minimal angle is opposit to minimal side of triangle.

Since, at leats one side of angles of triangle not less then and this anlge is not least one. And side opposite to it is not least side. Therefore, if in then min(|AB|, |BC|, |CA|) = min(|AB|, |BC|).

And then lets do the follows. Lets iterate apex B and for each B lets find triangle with maximal minimum of sides when B is the apex of triangle and . For it lets sort all other points by the angle relative to B, and for each point A lets find point C most distant to B among such points that . We have to use segment tree for maximum and two pointers or binary searsh to now left and right bound of possible points C during iterating A.

Finally, we have solution of time .

•
• +44
•

By Sammarize, 5 years ago, ,

Мне кажется, что было бы удобно на главной страничке раунда отображать дату раунда. Можно, например, под фразой "Codeforces Round #N" поместить ещё одну строчку, что-нибудь в стиле: "15 апреля 2011 года, начало в 22:00, длительность 2:10".

Иногда это бывает интересно знать, но нет никакого простого способа это выяснить. Сейчас можно только перейти в материалы раунда (если они есть, но они могут быть опубликованы в другой день и уж точно в другое время), либо покопаться в списке "соревнования".

•
• +1
•

By Sammarize, 5 years ago, ,

Итак, давайте поговорим о том, как следует оценивать штрафные попытки по задачам.

Толчком к подобным размышлениям служит следующая мысль. С точки зрения "качества программирования", если можно так выразиться, есть большая разница между задачей, сданной с первой же попытки и задаче, сданной после одной неверной попытки. Тогда как сдана задача с 10 или 11 попытки — существенной разницы нет. Однако же, разница в баллах сейчас одна и та же: 50 баллов (если, конечно, стоимость задачи ещё не опустилась до 30% стоимости задачи). В связи с этим, есть следующее конструктивное предложение: сделать стоимость минусов убывающей.

Например, если задача имеет стоимость 1000, это может выглядеть так:

 номер попытки штраф за минус суммарный штраф 1 100 100 2 79 179 3 62 241 4 50 291 5 39 330 7 25 386 10 12 432 15 3 461 20 1 469 > 20 0 469

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

Таким образом получается, что минусы после 20ого (часто ли вы такое видите?) даются бесплатно. Получение трёх минусов карается четвертью стоимости задачи, пяти — третью стоимости, а сделав двузначное число штрафных попыток, Вы теряете почти половину стоимости задачи.

•
• +16
•

By Sammarize, 6 years ago, ,

## A (Div2) Результат игры

В этой игре можно было просто сделать, то, что просят в условии.А именно, завести счётчик, перебрать все клетки поля, и для каждой клетки найти сумму чисел в клетках, стоящих с ней на одной горизонтали, сумму чисел в клетках, стоящих с ней на одной вертикали, и сравнить эти суммы. Если сумма по вертикали больше, увеличить счётчик на один. После того, как перебраны все клетки, вывести счётчик. Максимальная сумма может быть 2 × 30 × 100 = 6 000, поэтому для её достаточно типа int.

## B (Div2) След

Извиняюсь за кривой

Давайте для начала отсортируем радиусы окружностей по убыванию. Пусть у нас теперь радиус первой окружности — r1, второй окружности — r2, ..., последней окружности — rn, где r1 > r2 > ... > rn. Внешняя область — так, которая снаружи первой окружности — покрашена в синий цвет, значит, область между первой и второй окружностью покрашена в красный. Далее, область между второй и третьей окружностью покрашена в синий цвет, между третьей и четвёртой — в красный, между четвёртой и пятой — в синий, и так далее.

Первая область, закрашенная в красный цвет (область между первой и второй окружностями) — это вся область внутри первой окружности, из которой выкинули внутреннюю область второй окружности. Значит, площадь это области равна π × (r12 - r22). Аналогично, площадь второй красной области (между третьей и четвёртой окружностями) равна π × (r32 - r42). И так далее. Значит, суммарная их площадь равна π × (r12 - r22 + r32 - r42 + r52 - r62 + ...). Значит, чтобы посчитать ответ можно, например, сложить квадраты радиусов окружностей с нечётным номером, вычесть из полученной суммы квадраты радиусов всех окружностей с чётными номерами, и полученную величину умножить на \pi.

Может возникнуть небольшое затруднение с последней окружностью. Если число окружностей нечётно, то последняя область — не кольцо между двумя окружностями, а круг. Но это, на самом деле, ничего не меняет: тогда последняя окружность имеет нечётный номер, и квадрат её радиуса надо тоже прибавить к сумме.

## A (Div1) — C (Div2) Сообщение

Для начала, добавим к строке s с обоих концов по 2000 фиктивному символу — например, <<#>>. Заметим, что это не повлияло на ответ. Действительно, пусть мы взяли подстроку t, частично или полностью состоящую из <<#>>. Тогда все символы <<#>> надо было бы заменить. Но если бы их просто не было, то нужные символы надо было бы добавить.

Рассмотрим оптимальную подстроку t, и последовательность действий, которую надо с ней сделать, чтобы превратить её в строку u. Рассмотрим первое добавление или удаление символа с одного из концов.

Заметим, что это не удаление. Ведь если мы выбрали подстроку t и удалили из неё, к примеру, последний символ, то его не надо было бы и брать, потому что для строки t без последнего символа надо на одно действие меньше, чем для всей строки t.

А теперь заметим, что это и не добавление. Действительно, пусть мы рассмотрели строку t, некоторое время меняли в ней символы на другие, и наконец, добавили один, скажем, в начале. Тогда - Если слева от строки есть символ (то есть, строка там ещё не кончается), то можно было его взять сразу (то есть, рассмотреть не t, а t с ещё одним символом слева). Вместо того, чтобы добавлять символ, можно заменить существующий — это тоже занимает одной действие. - Если слева от строки нету символа (то есть, первый символ t является первым символом строки s), тогда в t есть как минимум 2000 <<#>>. Значит, либо ответ для такой строки как минимум 2000, потому что каждую решётку надо удалить или заменить; либо никаких символов, кроме решёток, в строке t нет, и тогда надо сделать как минимум |u| действий, потому что каждый символ u надо добавить (или сделать из другого символа). Но чтобы получить всего |u| действий, достаточно взять любую подстроку длины |u|.

Таким образом, существует оптимальная подстрока t, из которой получается u без добавлений и удалений. Это ключевой момент решения! Ведь это означает, что длина такой строки равна длине u. Значит, достаточно перебрать подстроки строки s длины |u|. Всего таких подстрок O(|s|), и для каждой подстроки легко за время O(|u|) посчитать необходимое количество изменений — это просто количество символов, которые надо заменить.

Таким образом, получается очень простое в написании решение за время O(|s| × |u|).

## B (Div1) — D (Div2) Подозреваемые

Будем называть людей, которые сказали <<Убийство совершил подозреваемый номер ai>> обвиняющими, а людей, которые сказали <<Подозреваемый номер ai не совершал убийства>> — оправдывающими. Рассмотрим подозреваемого номер k. Предположим, что он совершил убийство и посчитаем, сколько тогда человек сказали правду. Люди, которые сказали правду — это люди, которые обвиняли его, и люди, которые оправдывали не его. Таким образом, их количество — это количество людей, которые обвинили его, плюс количество людей, которые оправдали кого-либо, и минус количество людей, которые оправдали его. Таким образом, нам надо знать - количество людей, которые кого-либо обвиняют (это легко посчитать за O(n)) - для каждого подозреваемого количество людей которые его обвиняют - для каждого подозреваемого количество людей которые его оправдывают Последние две величины легко посчитать за время O(n) для всех подозреваемых. Действительно, пусть i-того человека обвиняют xi людей и оправдывают yi людей. Тогда надо просто для каждого человека номер i, если он оправдывающий, то увеличить yai, а если обвиняет — увеличить xai.

После этих действий можно за O(1) посчитать для каждого подозреваемого число людей, которые говорят правду в том случае, если он преступник, и если это количество равно m, то данный человек может быть преступником. А после того, как мы нашли список возможных преступников, то не составляет труда для каждого человека определить, может ли он говорить правду и может ли он врать.

## С (Div1) — E (Div2) Шифр

Я мог бы привести полное и строгое доказательство этого факта, но оно будет длинным и немного занудным и, думается мне, его вряд ли кто-нибудь будет читать. Лучше я просто опишу две переформулировки задачи, в которых этого утверждение становится более очевидным.

1. Переформулировка первая. Представим себе, что у нас вместо каждого числа — стопка монет, от 0 до 25 штук. Тогда разрешенные действия — это переложить одну монету из какой-то стопки в соседнюю так, чтобы во всех стопках оставалось от 0 до 25 монет.

2. Переформулировка вторая. Рассмотрим последовательность si (i = 0, ..., n), такую, что si равно сумме первых i чисел в слове. Последовательность неубывает и разность между соседними элементами последовательности не превосходит 25. Тогда разрешенная операция — это изменить одно из чисел на один в любую сторону, так, чтобы разность между любыми двумя соседними числами по-прежнему не превосходила 25, и последовательность по-прежнему неубывала.

Таким образом, нам надо посчитать, сколько слов такой же длинны имеют такую же сумму букв. Это легко сделать сразу для всех слов длины не больше 100. Посчитаем с помощью динамики такую величину x[l][s] : количество слов длины l с суммой букв s. - База динамики: l = 0. Есть ровно одно слово (пустое, оно же единственное слово длины 0) с суммой букв 0, и по 0 слов с любой другой суммой букв. - Переход динамики: очень простой. Чтобы узнать, сколько слов длины l имеют сумму s, надо перебрать, какая может быть последняя буква у этого слова: x[l][s] = x[l - 1][s] + x[l - 1][s - 1] + ... + x[l - 1][s - 25]. Конечно, надо не забыть считать эту величину по модулю 109 + 7.

После того, как мы посчитали эту величину для всех 0 ≤ l ≤ 100, 0 ≤ s ≤ 2500 за O(1002 × 25) памяти и O(1002 × 252) времени, надо просто для каждого слова найти его длину сумму букв и вывести ответ (не забыв вычесть 1).

## D (Div1) Улики

### Как придумать формулу

Простите все, кому это непривычно, но поскольку интерпретатор ТеХа на Codeforces в данный момент несколько кривоват, вместо традиционных нижних индексов будут нетрадиционные верхние. Это не степени, о степенях я буду оповещать отдельно.

Говоря математическим языком, в задаче надо посчитать количество способов дополнить граф до связного минимальным количеством ребер. Понятно, что сам граф не имеет значения — важны только компоненты связности. Более того, сами компоненты связности не важны, важны только их размеры.

Итак, пусть у нас есть k компонент связности размера s1, s2, ..., sk.Посмотрим, чем равна искомая величина для маленьких k.

Пусть k = 1. Тогда граф уже связный, есть 1 способ добавить ноль ребер.

Пусть k = 2. Тогда в графе две компоненты связности и надо добавить одно ребро между ними. Существует s1 способ выбрать вершину из первой компоненты, s2 способов — из второй, всего s1s2 способов.

Пусть k = 3. Тогда в графе три компоненты связности, и надо провести два ребра, которые будут соединять различные пары компонент связности. Общее количество способов будет равно s1s2 × s1s3 + s1s2 × s2s3 + s1s3 × s2s3 = s1s2s3 × (s1 + s2 + s3) = s1s2s3 × n.

Участники с самой богатой фантазией могли уже сейчас догадаться до правильной формулы. Но лучше посмотрим на следующее значение k:

Пусть k = 4. Тогда в графе 4 компоненты связности размера s1, s2, s3, s4. Надо провести три ребра. Немного подумав, можно понять, что эти рёбра либо будут соединять одну из компонент связности с остальными тремя, либо первую со второй, вторую — с третьей, а третью — с четвёртой (разумеется, компоненты могут следовать в любом порядке).

Количество способов первого типа: (s1)3 × s2s3s4 + (s2)3 × s1s3s4 + (s3)3 × s1s2s4 + (s4)3 × s1s2s3 = ((s1)2 + (s2)2 + (s3)2 + (s4)2) × (s1s2s3s4).

Количество способов второго типа: есть две компоненты связности, из которых выходит по два ребра. Пусть это первая и вторая. Тогда одно ребро проведено между ними, и ещё одно — из них в другие компоненты связности. Эти два ребра могут быть проведены двумя способами: от первой к третьей, а от второй к четвёртой, или наоборот. Значит, количество таких способов равно 2 × (s1)2 × (s2)2 × s3 × s4 = 2s1s2 × (s1s2s3s4). И Таких слагаемых 6 штук. Просуммировав их всех и прибавив к ним способы первого типа, можно вынести множитель (s1s2s3s4) за скобки, и останется аккурат формула квадрата суммы 4-х слагаемых. Значит, общее количество способов будет равно (s1s2s3s4) × n2.

На этом месте можно было уже легко догадаться до формулы (s1s2... sk) × nk - 2, тем более, что в первом случае получается как раз 1 = (s1) × n - 1.

### Как доказать формулу

Осталось только эту формулу доказать (хотя, конечно, для того, чтобы сдать задачу, доказательства не требовалось =))

Итак, пусть есть некий набор из k - 1 ребра, который дополняет граф до связного. Построим по нему две последовательности чисел: (x^1, x^2, ..., x^{k-2}) и (a^1,a^2,...,a^k). При это каждое x может быть любым числом от 1 до n, а ai может быть любым числом от 1 до si. Легко понять что таких пар последовательностей аккурат столько же, сколько (якобы!) способов дополнить наш граф до связного.

Пара последовательностей же строится следующим образом.

Для начала заметим, что этот набор из k - 1 ребра как бы образует дерево, в вершинах которого — компоненты связности.

1. Рассмотрим минимальную по номеру компоненту связности, из которой выходит только одно дополняющее ребро. Пусть это компонента номер i и ребро соединяет вершину номер t в компоненте номер i и вершину номер b в другой компоненте. Тогда x1 = b, а ai равно (внимание!) номеру вершины t среди вершин компоненты i, то есть, числу от 1 до si.

2. Одна из компонент связности теперь отвалилась от графа. Остальные k - 2 ребер дополняют оставшиеся k - 2 компоненты до связного графа. Повторим ту же процедуру еще k - 1 раз.

3. Осталось одно ребро. Оно соединяет две компоненты связности u и v, которые ещё не упомянуты во второй последовательности. Первая же последовательность заполнена — в ней как раз k - 2 элемента. Осталось во вторую последовательность на места номер u и v записать номера концов оставшегося ребра среди вершин компонент номер u и v соответственно.

Итого, для каждого способа дополнить граф до связного существует такая пара последовательностей. Заметим, что если компонента i была <<висячей>>, то есть, соединялась только с одной другой компонентой, то её вершины не упоминаются в первой последовательности. А если не была висячей — то упоминаются, потому что все рёбра, которые выходят из этой компоненты, надо выкинуть. Каждое ребро, которое мы выкидываем, упирается одним концов в висячую компоненту. И когда было выкинуто первое ребро, выходящее из компоненты i, компонента i не была висячей. Значит, при выкидывании этого ребра в первую последовательность была записана вершина из компоненты i.

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

Значит, в начальный момент, и каждый момент в процессе построения первой последовательности, по оставшемуся куску последовательности можно судить, какие вершины в данный момент висячие.

Итак, пусть у нас есть какой-то, неизвестный способ дополнить граф до связного и мы построили по нему две последовательности (x1, x2, ..., xk - 2) и (a1, a2, ..., ak). Восстановим по ним дополнение графа до связного.

1. Рассмотрим x1. Это число говорит нам, что сначала было выкинуто ребро одним концом в x1, а другим — в наименьшей по номеру висячей компоненте связности. Мы можем её определить, так как знаем текущий список висячих компонент. Пусть это компонента i. Тогда в ai записан номер вершины в компоненте i, которая соединена с x1. Итак, одно ребро восстановили. Выкидываем компоненту номер i.

2. Делаем эту операцию ещё k - 1 раз. Выкинуты k - 2 компоненты и восстановлены k - 2 ребра. Осталось два неиспользованных элемента второй последовательности, которые определяют вершины в двух оставшихся компонентах. Эти вершины и надо соединить k - 1-ым ребром.

Итого, по каждой паре последовательностей восстанавливается дополнение до связного графа, из которого эта пара последовательностей была получена. Значит, количество способов дополнить граф до связного равно количеству пар последовательностей, которое и равно (s1s2... sk) × nk - 2.

## E (Div1) Оладьи миссис Хадсон

Для начала заметим, что легко придумать очень простое решение этой задачи. Можно просто хранить остаток от деления каждой из цен на каждое из 25 простых чисел от 2 до 97. Тогда каждый запрос будет выполняться за O(25 × 10000). И всего решение будет работать за O(25 × 10000 × 30000) = O(7, 5 × 109) взятий по модулю. К сожалению, это не укладывается в ограничение по времени =)

Первая идея авторского решения: если результаты наших действий класть с мап и доставать оттуда при необходимости, это сильно ускорит работу программы. Но мапить надо с умом! Во-первых, надо класть в мап остатки от произведения цен баночек, подходящих под шаблон, по модулю простых чисел. Во-вторых, все шаблоны, под которые подходят все номера, надо считать идеинтичными, независимо от основания системы исчисления.

Нет смысла приводить здесь нудные вычисления, показывающие, что это действительно дает прирост производительности — гораздо проще написать программу, которая это подсчитает. Получается порядка 3 × 107 чисел, остатки которых надо перемножить, вместо 10 000 × 30 000 = 3 × 108.

Однако всё же 3 × 107 × 25 = 7, 5 × 108 взятий по модулю. Понятно, что это всё равно не уложится в 5 секунд.

Вторая идея авторского решения.

Рассмотрим 4 модуля:

1224469897 = 7 × 17 × 37 × 47 × 61 × 97

1503325967 = 11 × 13 × 41 × 43 × 67 × 89

1336143462 = 2 × 3 × 23 × 31 × 53 × 71 × 83

937397015 = 5 × 19 × 29 × 59 × 73 × 79

Квадрат всех этих 4 чисел влезает в знаковый 64-битный тип данных и их произведение делится на все простые числа до 100. Для каждой из 10 000 цен чисел будем хранить остаток этой цены по каждому из четырех модулей. Легко посчитать остаток произведения и прибавить к нему константу. По четырём остаткам легко определить, какой будет минимальный делитель — перебрать 25 вариантов.

Итого, такая оптимизация дает асимптотику O(4 × (3 × 107)) = O(1, 2 × 108).

•
• +25
•

By Sammarize, 6 years ago, translation, ,

Hello!

Welcom to the todays round! Note that this is last possibility to training before VK Cup on Codeforces — don't miss your chance! I hope, everybody will find interesting problems for him, you will not have misunderstanding with statements and there will have a harmony beteen your your solutions and our tests.

I'm an author of todays round. My name is Valeriy Samoylov, a graduated student of SPb SU. I want to thank Artem Rakhov (RAD) and Gerald Agapov (Gerald) for great help in investigation of problems.

And so I want to thank Maria Belova for translation of the statements and Alexanber Kouprin (Alex_KPR) for the statement prereading and the picture =)

Please, pay attantion to unusual problems cost in the first division:

500 — 1000 — 1500 — 2500 — 2500

And without surprise in the second division:

500 — 1000 — 1500 — 2000 — 2500

Good luck for all!

Round is postponed to 30 minutes by technically reasons. Registration is ending in 21:25.

•
• +118
•

By Sammarize, 6 years ago, ,
Уважаемая администрация ресурса!

Есть конструктивное предложение перенести раунд 99 на другой день в связи с тем, что в этот день появился SRM.

•
• -42
•

By Sammarize, 7 years ago, translation, ,

Hello everyone!

I am glad to welcome you on Codeforces Beta Round 94. I hope, some more early time of start will not have bad effect on you results =)

I'm author of today problems. I'm a graduated student of SPbSU, Valery Samojlov. This is my second round. I hope, today nobody will be sorry of his participation. I want to say very big thanks to RAD, who rend me very big support with preparation of problems. Also thanks to Maria Belova, who has translate statements to English.

Please, don't be startled of unusually cost of problems:

Div-1: 1000 - 1500 - 1500 - 2000 - 2500

Div-2: 500 - 1000 - 2000 - 2500 - 2500

•
• +160
•

By Sammarize, 7 years ago, ,
Вернусь к уже поднятой теме. Я бы смог написать каждый из последних ~6 раундов, будь он на пару часов позже. Очевидно, что я не один такой, потому что все люди разные. Почему бы не устраивать раунды хоть в немного разное время? Для нормального среднестатистического человека 19:00 - это выйти с работы в 18.00, час на дорогу, ~0 на подготовку. Я понимаю, что целевая аудитория ресурса - студенты. Но так ведь у студентов и так целый вечер свободен (обычно), почему бы не устроить раунд пораньше или попозже?

На самом деле, ясно, почему так происходит. Потому что организаторы контестов предоставляют право выбора даты и времени составителю, а составителю хочется, чтобы на его раунд пришло побольше народу, а для этого надо выбрать mainstream - 19:00.Хочется попросить администрацию ресурса проявить МЕНЬШЕ демократии к составителям и БОЛЬШЕ - к участникам. Всё-таки, ресурс существует для участников.

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

•
• +50
•

By Sammarize, 7 years ago, translation, ,

### 1. Clothes (A Div-2)

In this problem constraints are allow to look throw all triples of clothes. For every triple one can check if all elements of tripe areturn out to match with others, and anong those triples find one whith minimal cost.

### 2. Sum of digits (B Div-2)

Initial number consist of no more then 100000 digits. Therefore after first transform resulting number will be no more then 900000, and then it will constist of no more then 6 digits. Thus after next transform number will be no more then 54 and so it will be two-digit or one-digit. Sum of digits of a two-digit number no more, then 18, and sum of digit of such number no more, then 9.
Thus Gerald can't do nore, then 4 transforms. First transform one can implement one simple pass throw symbols of given string. Following operations take very little time.

### 3. Homework (C Div-2, A Div-1)

Lets count up the number of entries to string of every letter. Let Gerald choose x letter and lose them. Obvious thet if he lose x rarest letters then overall number of losed letter do not increase, and then if he can lose some x lettes, he can lose x rarest ones. Thus it's easy to determine if Gerald can loses x letters. And now to calculate the answer one only need to find the minimal such x, so Gerald can lose x letters.

### 4. Buses (D Div-2, B Div-1)

For every slop from 0 to n lets calculate kx - number of ways come to them. Consider the i-th bus. Number of ways come to stop ti applied i-th bus is uqual to number of way to embus to i-th bus.
One can embus to i-th bus on the stops si, si + 1, ..., ti - 1. Thus number of ways come to stop ti in the i bus is equal to sum ksi + ksi + 1 + ... + kti - 1. Finally, lets note that overall number of way to come to stop ti is the sum of numbers of ways to come to stop ti on every bus.
It's remained two problems. First problem: 0 ≤ n ≤ 109. Therefore all kx not climb in memory limit. But we need to know only non-zero kx. For instance, one can gripe coordinates: create list of all occured stops (and also stops 0 and n), sort this list, delete the repeated stops and replace all numbers of stops they indexes in this list. After this operations all number of stops not exceed 200001, and all kx are climb to the memory.
Second problem: if we will use loop "for" for counting sum ksi + ksi + 1 + ... + kti - 1, asymptotic of time of working will be O(m^2). There is an easy way to solve this problem: one can create and update array sum[], such that sum[i] = k[0] + k[1] + ... + k[i - 1], by another words, sum[0] = 0, sum[i + 1] = sum[i] + k[i].
Then munber of ways to come to stop ti using bus i is equal to sum[ti] - sum[si].
So time complexity is O(m \cdot log(m)), memory complexity is O(m).

### 5. Vectors (E Div-2, C Div-1)

Lets formulate the problem in complex number.
Consider complex numbers a = xA + iyAb = xB + iyB and c = xC + iyC. One can do operation A → A + C and A → iA.
If we apply this transform some times in some order to A, we will get number A· ik + aC + biC - cC - idC for some non-negative integers k, a, b, c, d or, in another words, A· ik + aC + biC for k = 0, 1, 2, 3 and some integers a, b. Since k can be equal only 0, 1, 2 or 3, sufficiently to get to know is one can to represent B - A, B - iA, B + A or B + iA in the form of aC + biC.
Then, how to determine, is one can to represent some complex number D in the such form? One can represent equation D = aC + biC in the form of linear real equation system:
a· xC - b· yC = xD
a· yC + b· xC = yD
To solve this system - is standart tehnical problem.

6. Castle (D Div-1)

Remunerate vertexes in such a way, that start Gerald vertex have got number 0.
Consider that vertex 0 is the root of tree, and lets consider its children. Let Gerald first go to vertex x. Then he must to travel throw hole subtree, otherwise he will not visit all vertex in subtree. Then he come back to 0 and go to some next its child.
Lets try to calculate looked for value for hole tree when we know all subtree values. If we can to do it, we can solve problem using dynamyc programming on the tree.
Lets vertex 0 have n children. Lets i-th subtree have ki offspring (inclusive i-th child of 0).
Let the hole tree consist of N vertexes.
Lets Ti is the doubled sum of lenght all edges in i-th subtree, inclusive edge between 0 and its i-th child. It is the time to travel throw hole i-th subtree, starting in 0 and returning to 0.
Finally, lets ti is answer to problem on i-th subtree. At once we add to this time length of edge between 0 and its i-th child.
Lets Gerald travel throw all subtrees in order 1, 2, ..., n. What is average time of finding the treasure?
Treasure can be in first subtree with probability . Then average time of finding the treasure will be t1.
Treasure can be in second subtree with probability . Then average time of finding the treasure will be T1 + t2.
And so on. Thus, average time of finding the treasure will be

Can we decrease this time? Lets swap i and i + 1 subtrees. Then item ki + 1Ti disappear from sum and appear item kiTi + 1. Sum will chenge to kiTi + 1 - ki + 1Ti. Sum will decrease, if kiTi + 1 - ki + 1Ti < 0, in ather words .
Therefore, one can't decrease average time, if subtrees are sorted by increasing value .
So, we must to sorted trees in this order and traveling from them in this order.

7. Candies and Stones. (E Div-1)

Essence of problem is that there is a board n × m in cell of wich placed numbers. And one must go from cell (0, 0) to cell (n - 1, m - 1), doing moves to one cell up and right (that is, increasing by 1 on of coordinates), maximizing sum o number on the cell in the path.
Gerald's problems is determine m + n - 1 cells of optimal path. Lets start with search one, middle cell. Lets . What cell of board can be k-th in path? It is cell, sum of coordinate of wich is equal to k, thus, it is diagonal of doard. And then we can calculate, what maximum sum Gerald can collect, came to every cell in the diagonal, by dynamic programming in lower triangle. And the same way, we can calculate, what maximum sum Gerald can collect, came to cell (n-1,m-1), starting from every cell in the diagonal. Sumed up this to values, we calculate, what maximum sum Gerald can collect, came to from cell (0, 0) to cell (n - 1, m - 1), travel throw every cell in the diagonal. And now we will find cell (x, y), in wich maximum is reached. It is k-th cell of the path. We used time O((n + m)2) and memory O(n + m).
Then we make recursive call on subproblems. In other word, will find optimal path from cell (0, 0) to cell (x, y) and from cell (x, y) to cell (n, m).
It is evident, this solution take memory O(n+m). Why it tkae time O((n+m)^2)?
Lets n + m is r.
Once we are find middle cell of path of length k. Twice we are find middle cell of path of length . Four times we are find middle cell of path of length . And so on. Therefore, time of program working will be . Thus, this solution take time O((n + m)2).