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 = 2^x + y, but 2^{x+y} = 2^x + 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} = C_{xi + yi - 2}^x_i - 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^: (x_i + y_i)² ((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.
(\in) and (\ni) — element of the set.
 →  (\to) — arrow right, in expressions such as x_n → 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!

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.

559A - Gerald's Hexagon & 560C - Gerald's Hexagon

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

559B - Equivalent Strings & 560D - Equivalent Strings

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

559C - Gerald and Giant Chess & 560E - Gerald and Giant Chess

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.

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. jqdai0815
2. qwerty787788
3. SirShokoladina
4. ainu7
5. Endagorion

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

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.

559A - Gerald's Hexagon & 560C - Gerald's Hexagon

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 k² times larger then small triangles area and therefore big triangle have splitted by k² small triangles.

If we join regular triangles to sides a₁, a₃ and a₅ of hexagon we get a triangle sides of a₁ + a₂ + a₃. Then hexagon area is equals to (a₁ + a₂ + a₃)² - a₁² - a₃² - a₅².

559B - Equivalent Strings & 560D - Equivalent Strings

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.

559C - Gerald and Giant Chess & 560E - Gerald and Giant Chess

Let's denote black cells ad A₀, A₁, ..., A_k - 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 A_k = (h, w). Now we have to find number of paths from (1, 1) to A_k avoiding A₀, ..., A_k - 1.

Let D_i is number of paths from (1, 1) to A_i avoiding A₀, ..., A_i - 1. It's easy to see that D_k is answer for the problem. Number of all paths from (1, 1) to (x_i, y_i) 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 A_i. For each such cell A_j we have to subtract number of paths from (1, 1) to A_j avoiding black cells multiplied by number of all paths from A_j to A_i.

We have to calculate factorials of numbers from 1 to 2·10⁵ and inverse elements of them modulo 10⁹ + 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 A_iA_i + 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 a_i. 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 x₀, ..., x_k is all possible boundaries of lighted intervals (numbers a_i - l_i, a_i и a_i + l_i).

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 [x_i, x_j].

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 x_i is rightmost lighted point. It's easy to do in O(n⁴) 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 [a_i - l_i, a_i] or [a_i, a_i + l_i]. Now most left lighted point is min(a, x_i), most right is max(b, x_j). 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 x_i is most left lighted point x_j is most right one and right bound of leftmost lighted interval is x_t. Thet it's easy to calculate left[L][][]. That part is done in O(n⁴) too.

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.

(I will glad to see the remarks about translation mistakes)

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 hball1st, 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!

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:
1. KADR
2. RAVEman
3. PavelKunyavskiy
4. Dmitry_Egorov
5. RAD
6. sy2006
7. mmaxio
8. riadwaw
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. jschnei
7. littlepanda
8. langdamao
9. 9mmlitswe
10. Renkai

334A - Candy Bags

In this problem one must divide all natural numbers from 1 to n² 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 n² 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 x₁, x₂ и x₃ as well as y₁, y₂ и y₃. Now lets check if for every pair (x_i, y_j) (except (x₂, y₂)) 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.

334C - Secrets / 333A - Secrets

Actually we are looking for longest sequence of natural number a₁, a₂, ..., a_k, 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 a_i = 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 .

334D - Chips / 333B - Chips

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.

334E - Lucky Tickets / 333C - Lucky Tickets

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 10⁴. 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(a_i1, j1, a_i1, j2, a_i2, j1, a_i2, j2) for all i₁, i₂, j₁, j₂ such that 1 ≤ i₁, i₂ ≤ n, 1 ≤ j₁, j₂ ≤ m, i₁ ≠ i₂, j₁ ≠ j₂. 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 i₁, i₂, j₁, j₂ so that a_i1, j1 = a_i1, j2 = a_i2, j1 = a_i2, j2 = 1.

Lets consider all pair of natural numbers (i₁, i₂) so that there exist nutural number j so that a_i1, j = a_i2, 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 .

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.

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