tunyash's blog

By tunyash, history, 21 month(s) ago, In English,

I'd like to invite everybody to participate in HourRank 12 on HackerRank. It'll start tomorrow at 19:30 PM MSK.

It's my first HourRank but I've prepared problems for HackerRank several times. I also used to prepare problems for Codeforces long time ago.

There will be three problems and one hour to solve them. Contest will be rated and top-10 contestants on the leaderboard will receive amazing HackerRank T-shirts!

I'd like to thank wanbo for testing the problems, it's always a pleasure to work with him. I hope you will enjoy the problems and some of you will solve everything.

Scoring will be: 20-40-80. Editorials will be published right after the contest.

Good luck!

Read more »

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

By tunyash, 5 years ago, In English,

That's a part of final editorial. I'm sorry for delay. Please, report me about mistakes and unclear moments in solutions and in my english.

A div2

Task was to find the least digit, that is not contained in the given number and compare with given k.

B div2

Good sequence may contain only zeroes or contain some positive number. In the second case such a sequence is not longer than sequence {0, 1, 1, 2, 3, 5, 8, ..., x, y} where y > 109 and x ≤ 109. That's possible to find it using dummy algorithm. In the first case you may use binary search of two pointers.

A div1

Let's notice that sum in the rectangle (x1, y1, x2, y2) is sum(x1, x2)·sum(y1, y2). Where sum(l, r) = sl + sl + 1 + ... + sr. Then, we have to calc sum(l, r) for every pair (l, r) and count how many segments give us sum x for any possible x (0 ≤ x ≤ 9·|s|). In the end we should enumerate sum on segemnt [x1, x2] and find . There is corner case a = 0.

B div1

We may assume that John may exchange any subset of his items x to any other subset y, such as s(x) + d ≥ s(y) (it does not matter if x intersects y). We can find all possible sums in subset of elements of the given set of items using standard dp (knapsack problem). John should always exchange all his current set of items to another, because if he had exchanged some subset of x (current set) z to y, we can say that he had exchanged x to . So, we have to find shortest sequence of sets a, such as s(ai + 1) - d ≥ s(ai) for any possible i and a0 = {}. This subtask could be solved using following greedy algorithm. ai, i > 0 is maximal correct sum such as ai ≤ ai - 1 + d. Consider optimal answer c and our answer a. Let k is the first position where ak ≠ ck obiviously ak > ck (because ak selected as maximal as possible). Then consider q such as qi = ci for i ≠ k and qk = ak. q is either optimal. Applying similar operations we will obtain a. So, a is optimal.

C div1

We expected many unproved, but tested solutions. I think that careful prove of my solution with pen and paper is very difficult. So I will use some statistic-based facts.

  1. Consider the set of divisors of number k. One can check that it's beautiful set.
  2. If factorisation of k has the form where αi ≥ 3 and pi is distinct primes, set of divisors of k which is less than is also beautiful.
  3. How to prove item 2? Consider set A of pairs of divisors of k (ai, bi) such as ai·bi = k and ai < bi. Obiviously (if k is not complete square) any divisor will be contained only in one pair. It's easy too see that . Consider some element of factorisation of k pα such as and it is not true that . Let f(x) is maximal number s such as . f(ai) + f(bi) = α. For every q such as numbers q, q·p, ..., q·pα will be divisors of k. That implies that where d is number of divisors of . So in pairs both numbers are divisible by p. So set {a0, ..., a|A|} is beautiful.
  4. But there are some pairs with f(ai) = α. is equivalent approval.
  5. It's always possible to find such k as number of it's divisors is bigger than w where w is number of elements in required set. You may write following dp to find it.
  6. dp[i][j] is minimal k which is constructed of first i primes ans has j divisors.
  7. About 10 primes is enough to cover all k.
  8. Now we can construct beautiful sets with more than k elements.
  9. Using item 4 we will understand that constructed answer is very beautiful (about 60% of elements divisible by every possible p) and we can always delete extra elements.

Last items is not strict, but one can check it with his computer.

D div1

  1. Consider random element ar of a. With probabillity where g is ghd of a.
  2. Let xi = gcd(ai, ar). There are no more than d distinct xi where d is number of divisors of ar.
  3. We can find number of ai such as for every k in O(d2). (D is set of divisors of ar)
  4. Repeat item 1 x times we will get correct solution with probabillity 1 - 2 - x.

There is the way to solve this problem O(n·plog + d·2plog) for iteration where plog is the maximal number of distinct primes in factorisation of ar.

E div1

  1. Let's find number of rectangles whick consist k ones and intersect in cartesian coordinate system.
  2. It's possible to do it in n2·k. We need to find closest k ones on the top and on the bottom of the and enumareate all segments [l, r] such as 1 ≤ l ≤ r ≤ n and find closest k ones on the top and on the bottom of the segments merging results for rows.
  3. If we have k closest ones on the top and on the bottom of the segment we will find number of rectangles consists k ones and cross on [l, r] in O(k).
  4. Then we should find number of rectangles, which don't cross . Let's rotate table by 90 degrees, solve similar problem for two halfs of the table and so on.
  5. for square-shaped tables.

At the picture 1 two closest ones on the top (black cells) lying on the 4'th and 2'nd horizontals. Closest ones on the bottom lying on the 5'th and 7'th. Then if k = 2 there are zero correct rectangles with two "ones" on the tom. There are four rectangles which consist one "one" on the top and one "one" on the bottom. You can see how segment grows up at the pictures 2, 3 and 4. Every time you should merge closest k ones of the added row with closest k ones of the current segment.

Read more »

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

By tunyash, 5 years ago, translation, In English,

Hi all! This round is prepared by me, caustique, Fata1ist, KAN, malcolm. I thank Gerald, who has organised our work and helped us with tricky situations, MikeMirzayanov for the system of organasing contest delinur for the translation.

I hope that all problems will be OK and everyone will find intersesting problem for him/her.

Winners:

div1:

  1. lovelymoon
  2. niyaznigmatul
  3. cerealguy
  4. ainu7
  5. cgy4ever

div2:

  1. Sern
  2. netman
  3. kybconnor_4

I apologise for the mistakes in statements. I will be more careful in the next time.

Read more »

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

By tunyash, 5 years ago, In Russian,

У меня возник вопрос. Требуется найти наибольшее по мощности множество и не существует i ≠ j таких, что .

Предположительно нужно взять все множества, где элементов. Но доказать это у меня не получилось. Где можно почитать об этом?

Read more »

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

By tunyash, 5 years ago, In Russian,

Коровники (задача с российских летних сборов 2007 года)

Дано дерево из n <= 50000 вершин. Нужно зафиксировать k <= n вершин так, чтобы минимизировать максимальное расстояние от вершины дерева до ближайшей фиксированной. Нужно восстановить ответ.

Я придумал что-то похожее на решение для этой задачи, но, увы, у меня не получается это довести: Сначала сделаем бинпоиск по ответу. Теперь dp[i][j][k] — минимальное количество коровников, необходимое для того, чтобы в поддереве вершины i (рассмотрены только первые k сыновей вершины i) все непокрытые вершины были на расстоянии не более j от корня, либо, если j < 0, была фиксированная вершина такая, что d — maxd = j (d — расстояние до этой фиксированной вершины, maxd — текущий ответ). Тогда переход — это добавление новой ветки. Его можно просто делать за O(maxd) для одного состояния. Но я предположу, что умею делать этот переход за O(1).

Можно посчитать другую динамику dp2[i][j][k] — минимальная функция предыдущей динамики, такая, что нам понадобилось j коровников. (i и k не меняют роли). Тогда, можно заметить, что k * ans <= 2*n и считать динамику, которая считается быстрее. Тогда мы получим асимптотику O(n sqrt(n) log(n)).

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

Есть ли в этой задаче что-то проще и с меньшим количеством случаев?

Read more »

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

By tunyash, 5 years ago, In Russian,

Сегодня на контест мы дали задачку про обратный рюкзак.

Мы, кроме того, умеем почти так же решать обычный рюкзак с бесконечными предметами, если решить его для отрезка [1..m], то есть получить многочлен с коэффициентами 1 там, где можно получить такую сумму и 0 — там где нельзя. К этому многочлену нужно на отрезкок [m+1..2m] добавить единицы в те позиции, где есть предметы. Потом полученный многочлен возвести в квадрат. Тогда мы решили задачу за . Мне интересно, это боян?

UPD: это все бред, недостаточно просто возводить в квадрат =(

UPD: но достаточно два раз возвести в квадрат!

Read more »

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

By tunyash, 5 years ago, translation, In English,

Hi all! This round was prepared by me and KAN. I hope, you will enjoy our problems.

I want to thank PavelKunyavskiy, who tested our problems, readed statements and so on. Moreover, alger95, Skird, moskupols, sand-martin tested round too, I thank them for it.

And of course, I thank Gerald for organising our work, MikeMirzayanov for the great system and Delinur for translation of the statements.

I hope, result will be better than results of our previous round. Good luck!

Pay attention, round will be held at unusual time.

Scoring:

div1: 500-1500-1500-2000-2500

div2 : 500-1500-1500-2500-2500

My congrutulations for leaders.

div1:

  1. al13n
  2. tomek
  3. niyaznigmatul
  4. voover
  5. Egor
  6. Zlobober
  7. White_Bear
  8. seanwupi
  9. wjmsbmr
  10. peter50216

div2:

  1. fotile96
  2. roosaphu
  3. wzc1995
  4. gjh
  5. mynameisverylong

Full english editorial: here

Read more »

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

By tunyash, 6 years ago, In Russian,

Решаю задачу 1745 с тимуса.

Кратко: есть n <= 1000 каких-то скобочных последовательностей суммарной длиной не более 10000. нужно из них составить правильную максимальной длины.

Решаю так:

  • Пусть есть какое-то множество последовательностей, такое, что кол-во левых и правых скобок в них одинаково (суммарно во всех)
  • От каждой последовательности нам нужны две величины: минимальный баланс и суммарный баланс. То есть минимум по (кол-во откр. скобок) — (кол-во закр. скобок) на префиксе и эта же величина для всех строки.
  • Отсортируем строки сначала по знаку суммарного баланса, затем, для тех, у которых знак неотрицательный, по невозрастанию минимального баланса, а для тех, у которых знак суммарного баланса отрицательный, по неубыванию.
  • Будем делать динамику dp[i][j] — макс. длина последовательности, составленной из первых i строк в отсортированном порядке (возможно, не все используются), такой, что ее суммарный баланс равен j. Переходы можно делать вперед, добавляя очередную i+1 ю строку в этом порядке.

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

Буду благодарен за любую помощь!

http://pastebin.com/0C4VYbwJ

Ууупс. Нашел ошибку в решении. Неверно, что строки с отрицательным балансом надо так располагать =(

Просто, для отрицательных нужно считать не (минимальный баланс), а суммарный баланс — минимальный баланс.

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

Да, задача зашла.

Read more »

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

By tunyash, 6 years ago, translation, In English,

It will be finised in few hours. If you don't understand something, ask your questions, please.

233A - Perfect Permutation

Idea: Gerald Implementation: tunyash Editorial: Moskupols

Consider permutation p such that pi = i. Actually p is a sequence of numbers from 1 to n. Obviously ppi = i. Now the only trick is to change the permutation to satisfy the second equation: pi ≠ i. Let's swap every two consequtive elements. More formally, for each k: 2k ≤ n let's swap p2k - 1 and p2k. It's easy to see that the obtained permutation satisfies both equations for every n with the only exception: when n is odd, there is no answer and we should print  - 1.

233B - Non-square Equation

Idea: tunyash Implementation: tunyash, Gerald Editorial: Moskupols

Firstly let's find the interval of possible values of s(x). Hence x2 ≤ n and n ≤ 1018, x ≤ 109. In other words, for every considerable solution x the decimal length of x does not extend 10 digits. So smax ≤ s(9999999999) = 10·9 = 90.

Let's bruteforce the value of s(x) (0 ≤ s(x) ≤ 90). Now we have an ordinary square equation. The deal is to solve it and to check that the current bruteforced value of s(x) is equal to sum of digits of the solution. If the solution exists and the equality holds, we should relax the answer.

It seems that the most error-generating part of this problem is solving the equation.

Knowing arrays is not neccessary to solve these two problems.

232A - Cycles

Idea: tunyash, Moskupols Implementation: tunyash Editorial: tunyash

Let's add edge in order of increasing a and for equal b in order of increasing b (here a and b — the least and the greatest vertices of the edge). If the new edge adds too much 3-cycles, we won't add it. We can count the number of new 3-cycles in O(n) complexity (they all contain the new edge, so it's enough to check all variants of the third vertex). Obviously we will obtain some proper graph, because we can always add a vertex and two edges to make a new triangle. So, there is always an answer. The complexity of this solution is O(n3).

Let's proof that 100 vertices are always enough for the given restrictions on n.

  • For some p after first p iterations we will have a complete graph of p vertices.
  • Now we have exactly C(p, 3) triangles. Consider p such that C(p, 3) ≤ k and C(p, 3) is maximal.
  • For the given restrictions p ≤ 85.
  • From this moment, if we add u from some vertex, we increase the total number of 3-cycles on C(u, 2).
  • So we have to present a small number that is less than C(85, 3) as sum of C(i, 2).
  • The first number we subtruct will differ C(85, 1) on some value not greater than C(85, 1) = 85, because C(n, k) - C(n - 1, k) = C(n - 1, k - 1).
  • The second number we subtruct will differ the number we have on some value not greater than C(14, 1) = 14.
  • and so on.
  • For every k it's enough to use not more that 90 vertices.

232B - Table

Idea: tunyash, Skird Implementation: tunyash Editorial: tunyash

  • Let si number of points in the column i.

  • Two neighboring squares are drawn at this picture, A is the number of point it the left area (it is one column), B is the number of points in the middle area and C is the number of points in the right area (it is one column too). That's why by definition we have:
  • Therefore A = C.
  • That's why
  • Divide all columns by equivalence classes on the basis of . For all a and b from one class sa = sb.
  • cnta is number of columns in class with .
  • There are (Cnk)cnta ways to draw k points in the each of columns in the class a independendently of the other classes.
  • dp[i][j] is number of ways to fill all columns in classes 1, ... i in such way that .
  • cnti take only two values and . Let's calc (Cna)cnti for all a and cnti and use it to calc our dp. We have O(n2·k) complexity.

232C - Doe Graphs

Idea: Gerald,tunyash Implementation: tunyash, Gerald Editorial: tunyash

Let's reduce the problem to the same problem for graphs with less orders. Vertex |D(n - 1)| + 1 is cutpoint (except cases n ≤ 2 but equations below is true for these cases).

Without loss of generality a < b.

Let dist(a, b, n) — length of the shortest path in graph of order n.

The first case is a ≤ |D(n - 1)| and |D(n - 1)| + 1 ≤ b

dist(a, b, n) = min(dist(a, |D(n - 1)|, n - 1), dist(a, 1, n - 1)) + dist(b - |D(n - 1)|, 1, n - 2) + 1

Edges is marked in red, paths is marked in blue. This formula means that we can go from the vertex a by the path 1 to the vertex 1. Then we can go to the |D(n - 1)| + 1 by the edge and go to the vertex b by the path 3. Or we can go to the vertex |D(n - 1)| by the path 2 and then go to the vertex |D(n - 1)| + 1 by the path 2 and then go to the vertex b by the path 3.

The second case is |D(n - 1)| + 1 ≤ a, b.

dist(a, b, n) = dist(a - |D(n - 1)|, b - |D(n - 1)|, n - 2)

That's easy case.

The third case is a, b ≤ |D(n - 1)|

dist(a, b, n) = min(dist(a, b, n - 1), min(dist(1, a, n - 1), dist(|D(n - 1)|, a, n - 1)) + min(dist(1, b, n - 1), dist(|D(n - 1)|, b, n - 1) + 2)

If shortest path contains cutpoint (|D(n - 1)| + 1) we can go to the vertex 1 or |D(n - 1)+1$ form the both of a and b. After that we can go to the cutpoint. Else we should consider path from a to b in D(n - 1).

Let's notice that for all of n will be no more than 4 distinct runnings of dist(i, j, n).

It can be prooved by the considering many cases of our actions.

In authors colution we cashed all dist(1, i, n) and dist(i, |D(n)|, n) for all achieveable i and n.

We have complexity for one query. (it's log because |D(n)| grows like φn).

232D - Fence

Idea: Gerald, tunyash Implementation: Moskupols Editorial: Moskupols

Let d and d' be arrays such that di = hi - hi + 1, d'i =  - di for every 1 ≤ i ≤ (n - 1). With that notation the conditions of matching look somehow like these:

  • the pieces do not intersect, that is, there isn't a single plank, such that it occurs in both pieces of the fence;
  • the pieces are of the same width;
  • for all i i (0 ≤ i ≤ r1 - l1 - 1) the following condition holds: dl1 + i = d'l2 + i (that is true in case when l = r).

The main idea of our solution is stated in the next sentence. For each query l...r the answer is number of pairs (a, b) such that (a > r or b < l), 1 ≤ a ≤ b ≤ n - 1, b - a = r - l and dl...r - 1 exactly matches d'a...b - 1. Let's build a suffix array sa from the concatenation of arrays d and d' with a fictive number between them for separation. Let position of suffix i in sa be posi. For each query all pieces of the fence that satisfy both second and third conditions of matching will be placed in sa on some segment boundleft...boundright such that boundleft ≤ posl ≤ boundright and lcp(boundleft...boundright) ≥ (r - l). So, it's possible to use binary search to find bound's. Depending on complexity of lcp finding algorithm, we could get them in O(logn) or O(log2n) complexity.

But there is still a problem to count the number of suffixes from saboundleft...boundright that satisfy the first condition too. Actually it is equal to count the number of i (boundleft ≤ i ≤ boundright) such that (n + 1 ≤ sai ≤ n + l - (r - l) - 1 or sai ≥ n + r) (in the concatenation d' starts from n + 1). It is a classic problem to count numbers from the given interval in the given subarray. For each query it could be solved in O(logn) complexity.

For instance, we could solve it offline using sweep line method and any data structure that support queries of sum on an interval and increment of an element. Or we could use some 2D/persistent structure.

So, the summary of the algorithm looks like this:

  • build d and d'. Build a suffix array on their concatenation.

For each query:

  • find the interval (boundleft...boundright) with two consecutive binary searches using lcp function.
  • query the count of suffixes from that interval that do not intersect with the given piece of the fence.

The best author's solution complexity is O(nlogn + qlogn), but careful written solutions in O(nlog2n) comply with the lime limit too.

232E - Quick Tortoise

Idea: tunyash Implementation: tunyash, KAN Editorial: tunyash

Let's choose central column of the area and for all cells to the left from column calc masks of achieveable cells in the central column and for all cells to the right from column calc masks of cells of which this is achievable. It's easy dp with bitsets. for the right part of board. ( — logical or, here it's bitwise or for masks) for the left part. dp calcs mask of achieveable points in the central column.

For query x1, y1, x2, y2 (if y1 ≤ mid ≤ y2, where mid is chosen central column) answer is yes if ( is bitwise and) is not empty.

Run this algo for left and right part of board we will get answers for all queries. Complexity is .

Read more »

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

By tunyash, 6 years ago, translation, In English,

Hi all!

Codeforces round #144 is going to be today.

Round is prepared by: KAN, Moskupols, Skird, tunyash. Special thanks to Gerald for coordinating round preparing, many awesome ideas and making statements easy-understandable. Also I thank MikeMirzayanov for enjoyable problem-preparing system, Delinur for statements translation.

I hope, that all will be well and you will enjoy solving problems.

Good luck!

UPD: Score distribution will be announced a few minutes before the start of the contest.

UPD2: score distribution is 500-1000-1500-2000-2500 in both divisions

UPD3:

Congrats to winners.

div1:

  1. tourist
  2. rng_58
  3. Mimino
  4. Dmitry_Egorov, Egor

div2:

  1. Debug22
  2. ryz
  3. dvdreddy
  4. vinodreddy
  5. idivyanshu

UPD: editoral for all problems, except div1.D is ready

Read more »

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

By tunyash, 6 years ago, In Russian,

GSS4.

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

Я придумал решение за ( и я не уверен ли это). Идея тупая: каждое число станет единицей, если взять корень 7 раз. Тогда заведем 7 декартовых деревьев, первое из которых будет хранить текущий массив, второе — корни из его элементов, третье — корни из корней и так далее. при запросе на замену на корень вырежем из каждого нужный отрезок и сделаем циклический сдвиг вырезанных отрезков. Отрезок дерева, который мы вытащили из самого первого дерева зальем единичками (после этого вставим в последнее).

Такое решение дает ТЛ. Интересно, можно ли быстрее и/или проще?

Read more »

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

By tunyash, 6 years ago, translation, In English,

Please, report me about every grammar mistake, you see. Thank you.

Problem <>

Let's notice that 2n ≤ k ≤ 5n. If k < 3n author has to get 2 on some exams. There are 3n - k such exams and that's the answer). If 3n ≤ k author will pass all exams (answer is 0).

Problem <>

Let the pencil move by the line and put crosses through every (n + 1) point. Lets associate every point on the line with point on square perimeter. Namely, point x on the line will be associated with point on square perimeter that we will reach if we move pencil around square to x clockwise. Then lower left corner will be associated with all points 4np for every non-negative integer p. Crosses will be associated with points k(n + 1) for some non-negative k. Nearest point of overlap of two families of points will be in point LCM(n + 1, 4n). Then we will put crosses.

Problem "Cutting Figure"

Translation by moskupols

Main idea: using the fact that the answer cannot be greater than 2, check answer 1.

Let's proof that the answer is not greater than 2. Let area of the figure be greater than 3. Let's examine the leftmost of all topmost squares. There is no neighbors left or up to it. So, number of its neighbors is not more than 2. Thus, if we delete its neighbors, we shall disconnect the figure. If the area is equal to 3, we always can disconnect the figure by deletion of one square. It can be proofed by considering all two primary cases. If the area is not greater than 2, there is no way to disconnect the figure.

The algorithm: Check answer 1. We can simply brute-force the square to delete, and for each instance start dfs from any existing square. If during the dfs we visited not all of the remaining squares, we have found the square to delete. The answer is 1 if our bruteforce succeeded, and 2 otherwise.

That was necessary to consider the case when there is no answer.

The complexity of the described algorithm is O(n4). That was possible to search for articulation points and solve the problem in complexity O(n2), but in my opinion that required more time and effort.

Problem <>

Translation by moskupols

Main idea: bruteforce in complexity O(Fun) where Fu if fibonacci number at position u.

This problem had complex statements. We have an array a, and we can transform it in two ways. The goal was to maximize the sum of all its elements with given multipliers after exactly u operations.

A simple bruteforce of all combinations of operations with subsequent modeling leads to complexity O(2u * nu), what is not fast enough. That was possible to optimize it by modeling parallel to recursive bruteforce. Now we have complexity O(2un). Actually, the correct solution is not too far from this algorithm.

There is just one conjecture: every two successive xor operations change nothing, and we can move them to any place of the combination. Thus, it will be enough to bruteforce only combinations in which every pair of successive xor operations is at the end.

It could be done using recoursive bruteforce. We must change in previous solution two things. First, we must n't put xor after xor. Besides that, we should update answer if number u - l is even, where l is current level of recoursion (all remaining operations in the end separates to pairs of xors).

Let's calculate complexity of this algo. There are Fi sequences of length i without two consecutive xors. It's easy to proof, you can calculate some dp to see it. That's why, complexity of our algo is O(Fun).

Problem "Hamming distance"

Main idea: reduction to system of linear equations and solving it using Gauss algorithm.

Let's notice that order of columns in answer doesn't matter. That's why there is only one important thing — quantity of every type of column. There is only 24 = 16 different columns.

Let's represent Hamming distance between every pair of strings as sum of quantities of types of columns. It's possible because every column adds to every distance between pairs 0 or 1.

Now we have system of 6 linear equations with 16 variables. It's not good, let's decrease number of variables. First, some columns adds same values to every Hamming distance. For example strings "abbb" and "baaa". For every column q we can replace all letters "a" by letters "b" and all letters "b" by letters "a" and reach column that adds same values to every distance. We reduced number of variables to 8. We also can notice that columns "aaaa" and "bbbb" is useless and reduce number of variables to 7.

This system can be solved using Gauss algorithm. One variable steel be free. Let's fix it. It's value can't be more than maximum of h(si, sj) because column adds positive value to one or more Hamming distance. For every fixed value we should check if all variables take non-negative integer value and choose the best answer.

We can solve system of equations in integers because coefficients of equation is little.

Complexity of this solution if O(max(h(si, sj))). If we solve it in rational numbers complexity will change to .

Problem "Two segments"

Main idea: inverse the permutation and solve simplified problem (see below), consider function "quantity of segments of permutation that form the given segment of natural series".

In order to solve this problem, we suggest solve another: <<we have a permutation pn, we have to calculate the count of segments such that their elements form one or two segments of natural series>>.

If we solve the inverse problem for some permutation qn such that , we shall get the answer for the initial problem and initial permutation pi.

Straight-forward algo: let's bruteforce the segment of permutation and mark its elements in a boolean array. Check that in that array there is not more than two marked segments. This algo has complexity O(n3).

Let's notice that during the changeover from [l, r] to [l, r + 1] the quantity of segments changes in some predictable way. Let s([a, b]) be quantity of segments that form segment [a, b] of permutation. There are three cases (see picture below):

  • If the new element pr + 1 is between two marked elements (that is, both elements with values pr + 1 - 1 and pr + 1 + 1 belong to segment [l, r]), then s([l, r + 1]) = s([l, r]) - 1. The new element will <> the segments near it.
  • If the new element pr + 1 has only one neighbor with value belonging to [l, r], then s([l, r + 1]) = s([l, r]). The new element will lengthen one of existing segments.
  • If there are no marked elements near pr + 1 the new element forms a new segment, s([l, r + 1]) = s([l, r]) + 1.

The new element is red, elements that are marked to this moment are black.

Improved algo: Let's bruteforce position of the left border and for each instance move the right border from left to right. During each move we shall recount the actual quantity of segments forming the current segment of permutation (s([l, r])). Now we have a solution in complexity O(n2). It works fast enough even when n = 20000. Obviously, that is not enough to get AC.

Move on full solution. It is based on previous. Now we can calc s([l, r]) using s([l, r - 1]). Now we should look at way of changing s([l - 1, r]) as compared with s([l, r]). Let's move left border of segment from the right to left and support some data structure with s([l, i]) for every i satisfying l < i ≤ n and current l. This structure should answer queries "count numbers 1 and 2 in structure", that is count segments [l, i] that generates one or two segments in the original permutaton.

Let Δi be s([l - 1, i]) - s([l, i]). Δl will be equal to 1 because one element form one segment in permutation (notice that in final answer we must not consider 1-element segments, that's why we must subtract n from answer in the end of solution).

Δi determined by the number of neighbors of element l - 1 in the segment [l - 1, i]. Neighbors of l - 1 is elements pl - 1 + 1 and pl - 1 - 1 if they're exist.

  • If l - 1 hasn't neighbors in this segment, Δi = 1, because l - 1 froms new 1-element segment.
  • If l - 1 has one neighbor in this segment Δi = 0, because l - 1 join to existing segment of its neighbor.
  • If l - 1 has two neighbors in this segment Δi =  - 1, because l - 1 connect segments of its neighbors.

Number of neighbors in segment [l - 1, i] non-decreasing with increasing i. That's why Δi non-decreasing with increasing i. That means that there are only three segments of equivalence of Δi. We are interested only in neighbors of l - 1 which positions are right than l - 1. Let a is position of first neighbor, b is position of second neighbor, without loss of generality a < b. Then , , . (elements of permutation are numbered from 0). If a and b aren't exist, for all Δi = 1. If only b isn't exist for , for .

Look at example to clear your understanding. (Δi is in top right corners, l = 3, pl = 5)

Using this facts we can code data structure support following operations:

  • Add +1 or -1 on segment
  • Calc number of 1 and 2 in the structure.

Sum of answers of structure in every iteration (for every l) is answer to problem.

Let's notice that all numbers in structure will be positive. That's why elements 1 and 2 will be minimal of pre-minimal in the structure. Using this fact we can code segment tree, supports these operations.

Complexity of this solution is .

We also can code sqrt-decomposition and obtain complexity .

Problem <>

Translation by moskupols

Main idea: baby-step-giant-step.

In this problem we had some Fibonacci number modulo 1013 f, and we had to determine the position of its first occurence in Fibonacci sequence modulo 1013.

  • Let a and b be two different coprime modula — divisors of 1013.
  • Let F be the actual Fibonacci number such that . Then and .
  • Find all occurences of number in Fibonacci sequence modulo a period.
  • Find all occurences of number in Fibonacci sequence modulo b period.
  • Let's fix a pair of such occurences. Let the occurence modulo a be in position i, and the occurence modulo b be in position j.
  • Let t(m) be Fibonacci sequence modulo m period.
  • From the Chinese Remainder Theorem, it follows that t(ab) = LCM(t(a), t(b)) (remember that a and b are coprime).
  • Then from fixed occurences of f in periods of sequences modulo a and b we can recover the position of occurence of f in period of sequence modulo ab. It could be done by solving the following Diophantine equation: i + t(a) * x = j + t(b) * y. We can solve it using a simple bruteforce of one of the roots.
  • If the occurence in sequence modulo ab period ( we have just found it) is u, then every occurence f in Fibonacci sequence modulo 1013 period can be represented as t(ab) * k + u. Then let's bruteforce k and find all occurences in sequence modulo 1013 period. To determine Fibonacci number on position α + t(ab) from known Fibonacci number on position α, we need to multiply the vector (Fα, Fα + 1) and some matrix.
  • Let's choose a = 59 and b = 213. Note that there is no number that occur Fibonacci sequence modulo a or b period more than 8 times. That means that total count of pairs will never be greater than 64. For each occurence we'll bruteforce not more than numbers. That was the author's solution.

Also that was possible to use the fact that for any number the count of its occurences in period of sequence modulo 10p (for any natural p) is not big more efficiently. From occurences in sequence modulo 10i period we could get occurences in sequence modulo 10i + 1 period using the method we use to jump from modulus ab to modulus 1013.

Read more »

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

By tunyash, 6 years ago, translation, In English,

The upcoming contest is brought to you by me. My name is Arthur, I'm a student of Chelyabinsk lyceum 31.

I am glad to thank Gerald for contest preparation management, delinur for translation of statements, MikeMirzayanov for a really excellent system, dolphinigle for test-solving, proof-reading and much valuable advice, moskupols, grey_wind, skird and alger95 for help in problem development.

There is nothing more to say yet. As you can see, contest will be held in two divisions separately. The scoring system will be standard (not dynamic), but scores for tasks may be unusual (see update of this post).

There won't be volume stories. I hope you will like the contest and its problemset and everything will be OK.

UPD: Scores for tasks:

Division 1: 500-1000-2000-2000-2500

Division 2: 500-1000-1500-2000-3000

UPD2:

Congrats to winners =)

Div1:

  1. Petr
  2. tourist
  3. yeputons
  4. peter50216
  5. aram90

Div2:

  1. lucien
  2. tomasz.kociumaka
  3. sjynoi

UPD3 some part of English editoral posted. You will find the remaining part of the editorial later

UPD4 English editoral was completed.

Read more »

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

By tunyash, 6 years ago, translation, In English,

http://www.ioi-jp.org/apio2012/ — asian pacific informatics olympiad. People, who participated in it, let's discuss problems, after the second open contest. You still have a chance to take a part in the second contest by the way.

Read more »

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

By tunyash, 6 years ago, In Russian,

Недавно прочитал, что узнавать, кто выигрывает в ним, в котором разрешено брать камни из не более, чем k кучек (при этом нужно взять хотя бы один камень хотя бы из одной кучки), довольно легко. Оказывается, достаточно просто выписать все двоичные записи величин кучек и просуммировать биты каждого столбика по модулю (k+1). Если в результате везде нули — первый игрок проиграл. К сожалению, моих знаний языка и математики не хватило, чтобы понять доказательство. Был бы благодарен, если бы кто-нибудь растолковал.

Я нашел задачу, где, собственно, просто надо вывести, кто выигрывает и восстановить выигрышный первый ход: ipc.susu.ac.ru

Но, к сожалению, с восстановлением ответа у меня возникли проблемы. Я попробовал перебирать маску битовых столбцов, в которых мы будем увеличивать число поставленных бит. В остальных, соответственно, уменьшать. Далее я жадно беру k кучек и пробую их изменять. Получаю WA, что, конечно, неудивительно, но ничего лучшего я пока не придумал. Возможно, у этой задачи есть какое-нибудь стандартное решение?

Read more »

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