Um_nik's blog

By Um_nik, history, 2 weeks ago, In English,

cgy4ever, when will the round be? clist.by says that it will be tomorrow in 19:00 (MSK), but three days ago it was 18:00 (MSK) and I also cannot find anything related on TopCoder itself. For example, there is no such competition in Web Arena calendar.

Read more »

Tags tco
 
 
 
 
  • Vote: I like it  
  • +47
  • Vote: I do not like it  

By Um_nik, history, 4 months ago, In Russian,

Я получил футболку с надписью "CODEFORCES THREADS 2017", но я не помню такого контеста.
С другой стороны, за Good bye 2016 обещали футболки.

Возможно, я не знаю какого-то перевода слова thread.

Так или иначе, MikeMirzayanov (или gKseni), можете рассказать, что это за футболка?)

Read more »

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

By Um_nik, history, 8 months ago, In English,

Suppose we want to solve a problem by doing binary search on answer. Then the answer will be checked against jury's answer by absolute or relative error (one of them should be smaller then ε). For simplicity we will assume that our answer is always greater than 1 and smaller than B. Because of that, we will always use relative error rather than absolute.

Suppose we have made n iterations of our binary search — what information do we have now? I state that we know that real answer is lying in some segment [xi, xi + 1], where 1 = x0 < x1 < ... < xi < ... < x2n = B. And what is great — we can choose all xi except for x0 and x2n.

Now, for simplicity, we will also assume that we will answer xi + 1 for segment [xi, xi + 1] and the real answer was xi — it is the worst case for us. It is obvious that we will not do that in real life, any other answer would be better, but you will get the idea.

So, what is our relative error? It is . Worst case for us is when relative error is maximal. It is logical to make them equal — exactly what we do by binary search with absolute errors. . We can assume that so . Now we have , but , so . How large should be n to get error less than ε? . Much smaller than .

How to write such binary search? We want to choose m in such a way that or simply .

Now I want to deal with some assumptions I made.

How to choose answer in the end? Again, (it is basically the same as dividing the segment in binary search).

What to do if the answer can be smaller than 1? Try 1; if answer is smaller than 1~--- use standard binary search (because absolute error smaller than relative); is answer is bigger than 1~--- use the binary search above.

P.S. I have never heard about this idea and come up with this while solving 744D - Коровоконг рисует круги. I'm sorry if it is known for everyone except for me.

Read more »

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

By Um_nik, history, 9 months ago, translation, In English,

If you are registered on Timus, then you should have been received e-mail with invitation to this contest. The contest will be on 19 November in 11 Moscow time.

It was a junior championship but it was 'a little' harder than it was intended. As I remember, Merkurev solved all the problems with only 15 minutes to go, so I think that this contest may be interesting for participants with different levels, up to the strongest ACM teams.

The duration is 5 hours, standard ACM rules. It is a team (up to 3 participants) contest but you are welcome to partcipate individually too.

The authors of the problemset are Um_nik, Umqra, kb., Tinsane and dieglaube.

Read more »

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

By Um_nik, history, 10 months ago, In English,

Hello!

October Clash on HackerEarth has started and you have 23 more hours to go.

I am the author of this problemset and niyaznigmatul is a tester. I want to thank Umqra who helped me a lot with preparation.

I hope you find the problems interesting and wish you good luck!

Read more »

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

By Um_nik, history, 11 months ago, In English,

Q1: I'm a newbie. What should I do to become great coder?
A1: Stop doing competetive programming Solve problems.

Q2: I'm doing CP for two months and I'm still not red green. What should I do?
A2: You are lazy and impatient Solve more problems.

Q3: You became a red in less than two years, it is unbelievable!
A3: No, it isn't. You can do it too if you will solve fucking problems.

Q4: You became a red blah-blah-blah such a huge fan blah-blah. Oh, and what should I do to become as great as you?
A4: ... right. You already know the answer. Solve problems. I hate you.

Q5: I'm not good at DP [or something]. What can you suggest?
A5. Maybe you should try to stop asking stupid questions and solve some problems on DP? Or read some blogs and editorials.

Q6: I can't solve a problem / understand your code. Can you help me?
(Well, it is not a bad question in general. It is a good (if you really want me to explain something not to write the solution instead of you) question. But...)
A6: Sure. Can you provide the link to the problem / code?
(I'm not joking, it is a real story).

Bonus!
Q0: Hello bro/sir.
A0: Stop doing this please.

Read more »

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

By Um_nik, history, 11 months ago, In English,

Access to the specified resource has been forbidden.

Codeforces said 20 minutes ago when I was trying to login. The same was about two weeks ago. In both cases I was unable to login for about 10 minutes.
And I constantly logout. Sometimes I can't read 3-4 blog posts before logout.

There were a post about logouting two or three days ago but I can't find it now because search is not working too.

Read more »

Tags bug
 
 
 
 
  • Vote: I like it  
  • +38
  • Vote: I do not like it  

By Um_nik, history, 20 months ago, In English,

I've noticed during the contest that we can see all the hacks in our room.

Now MikeMirzayanov says that it was a bug and will be fixed soon.

I think it really will be bad if there are tons of hacks. But it is very useful to know which problems can be hacked (I mean which problems was already hacked by someone). Can you add number of successfull and unsuccessfull hacks on each problem to the PROBLEMS page?

Read more »

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

By Um_nik, history, 22 months ago, In Russian,

Допустим, вы проводите соревнование для очень разной по силе аудитории. Например, у нас завтра отбор на ВКОШП.

В каком порядке вы бы стали рассказывать задачи на разборе?

Можно рассказывать в порядке A, B, C ... Правда, если в середине встретится сложная задача, то слабые участники могут забить и перестать слушать.

Логичное решение: давайте отсортируем задачи в порядке предполагаемой сложности (в конце концов, по количеству AC). Но тогда сильные участники не будут слушать сразу, а потом могут забыть "включиться". Или, того хуже, начнут шуметь и мешать остальным слушать.

Что бы вы сделали?

Read more »

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

By Um_nik, history, 22 months ago, translation, In English,

I would like to invite you to participate in Ural Regional School Programming Contest.

It is the Ural's qualifying round for All-Russian School Programming Contest and I think that it can be good opportunity for schoolboys to take part in this contest. It will be interesting for students too, I suppose.

Contest starts at 17 October 11:00 MSK at the same time with the onsite contest.

The problemsetters are Um_nik, Umqra, kb., hx0, Merkurev, KuchumovIlya, MikhailRubinchik (spoiler: it's not about palindromes).

Duration of the contest is 5 hours, ACM ICPC rules. Problem statements will be both in Russian and English. Link to the contest page

Read more »

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

By Um_nik, history, 22 months ago, In Russian,

Пользуетесь ли вы prewritten-кодом на раундах OpenCup?)
Разделю вопрос на два:
1) Если вы используете шаблон, пишите ли вы его каждый раз в начале контеста? (понятно, что это не влияет на результаты почти никак, просто интересно)
2) Пользуетесь ли вы заранее написанными стандартными алгоритмами (поток, венгерка, суфструктуры, что-нибудь ещё)?

Про нас (Ural FU Dandelion): Мы пишем шаблон каждый раз в начале контеста (может, за редкими исключениями), стандартные алгоритмы не копируем.

Ни в коей мере не хочу никого пристыдить или в чём-то обвинить, тем более что использование prewritten-кода разрешено правилами. Всем добра :)

Read more »

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

By Um_nik, history, 2 years ago, In Russian,

Тест:
{1}
{1}
Ответ жюри: 2
Количество перестановок с каким-то свойством больше, чем количество перестановок вообще.
UPD: Они уже заметили.

Read more »

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

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

569A - Music

Suppose we have downloaded S seconds of the song and press the 'play' button. Let's find how many seconds will be downloaded when we will be forced to play the song once more. . Hence x = qS.

Solution: let's multiply S by q while S < T. The answer is the amount of operations.

Complexity —

569B - Inventory

Let's look at the problem from another side: how many numbers can we leave unchanged to get permutation? It is obvious: these numbers must be from 1 to n and they are must be pairwise distinct. This condition is necessary and sufficient.

This problem can be solved with greedy algorithm. If me meet the number we have never met before and this number is between 1 and n, we will leave this number unchanged. To implement this we can use array where we will mark used numbers.

After that we will look over the array again and allocate numbers that weren't used.

Complexity — O(n).

568A - Primes or Palindromes?

It is known that amount of prime numbers non greater than n is about .

We can also found the amount of palindrome numbers with fixed length k — it is about which is .

Therefore the number of primes asymptotically bigger than the number of palindromic numbers and for every constant A there is an answer. Moreover, for this answer n the next condition hold: . In our case n < 107.

For all numbers smaller than 107 we can check if they are primes (via sieve of Eratosthenes) and/or palindromes (via trivial algorithm or compute reverse number via dynamic approach). Then we can calculate prefix sums (π(n) and rub(n)) and find the answer using linear search.

For A ≤ 42 answer is smaller than 2·106.

Complexity — .

568B - Symmetric and Transitive

Let's find Johnny's mistake. It is all right in his proof except ``If '' part. What if there is no such b for an given a? Then obviously otherwise we'll take b = a.

We can see that our binary relation is some equivalence relation which was expanded by some "empty" elements. For "empty" element a there is no such b that .

Thus we can divide our solution into two parts:

  1. Count the number of equivalence relations on sets of size 0, 1, ..., n - 1

  2. For every size count the number of ways to expand it with some "empty" elements.

We can define equivalence relation using its equivalence classes.

So first part can be solved using dynamic programming: dp[elems][classes] — the numbers of ways to divide first elems elements to classes equivalence classes. When we handle next element we can send it to one of the existing equivalence classes or we can create new class.

Let's solve second part. Consider set of size m. We have found that there are eq[m] ways to build equivalence relation on this set. We have to add n - m "empty" elements to this set. The number of ways to choose their positions is Cnk. We can calculate all the binomial coefficients using Pascal's triangle.

So the answer to the problem is .

Complexity — O(n2)

568C - New Language

Suppose we have fixed letters on some positions, how can we check is there a way to select letters on other positions to build a word from the language? The answer is 2-SAT. Let's see: for every position there is two mutually exclusive options (vowel or consonant) and the rules are consequences. Therefore we can do this check in O(n + m) time.

Let's decrease the length of the prefix which will be the same as in s. Then the next letter must be strictly greater but all the next letters can be any. We can iterate over all greater letters and then check if we can made this word the word from the language (via 2-SAT). Once we have found such possibilty we have found the right prefix of the answer. After that we can increase the length of the fixed prefix in a similar way. This solution works in O(nmΣ ) time. We can divide this by Σ simply try not all the letter but only the smallest possible vowel and the smallest possible consonant.

And you should remember about the case when all the letters are vowel (or all the letters are consonant).

Complexity — O(nm)

568D - Sign Posts

Suppose, that solution exist. In case n ≤ k we can put one signpost on each road. In other case let's choose any k + 1 roads. By the Dirichlet's principle there are at least two roads among selected, which have common signpost. Let's simple iterate over all variants with different two roads. After choosing roads a and b, we will remove all roads, intersecting with a and b in common points and reduce k in our problem. This recursive process solves the problem (if solution exist).

Complexity of this solution — . If implement this solution carefully — you will get AC =)

But in case of TL we can add one improvement to our solution. Note, that if we find point, which belongs to k + 1 or more roads, then we must include this point to out answer. For sufficiently large n (for example, if n > 30k2) this point always exist and we can find it using randomize algorithm. If solution exist, probability that two arbitrary roads are intersects in such a point not less than . Because of it, if we 100 times pick two random roads, then with probability such a point will be found and we can decrease k.

All operations better to do in integers.

Complexity — .

568E - Longest Increasing Subsequence

Let's calculate array c: c[len] — minimal number that can complete increasing subsequence of length len. (This is one of the common solution for LIS problem).

Elements of this array are increasing and we can add new element v to processed part of sequence as follows:

  1. find such index i that c[i] ≤ v and c[i + 1] ≥ v

  2. let c[i + 1] = v

We can process this action in time.

When we handle a gap, we must try to insert all numbers from set b. If we sort elements of b in advance, then we can move with two iterators along arrays b and c and relax all needed values as explained above. This case requires O(n + m) time.

Authors implied solution with O(n) space complexity for answer restoring. We can do this in the following way:

  1. Together with array c we will store array cindex[len] — index of element, which complete optimal increasing subsequence of length len. If this subsequence ends in a gap — we will store  - 1.

  2. Also, we will store for every not gap — length of LIS(lenLIS[pos]), which ends in this position (this is simply calculating while processing array c) and position(prevIndex[pos]) of previous element in this subsequence (if this elements is gap, we store  - 1)

Now we will start recovery the answer with this information.

While we are working with not gaps — it's all right. We can simply restore LIS with prevIndex[pos] array. The main difficulty lies in processing gaps. If value of prevIndex[pos] in current position equal to  - 1 — we know, that before this elements must be one or more gaps. And we can determine which gaps and what values from b we must put in them as follows:

Let suppose that we stand at position r (and prevIndex[r] =  - 1). Now we want to find such position l (which is not gap), that we can fill exactly lenLIS[r] - lenLIS[l] gaps between l with increasing numbers from interval (a[l]..a[r]). Position l we can simply iterates from r - 1 to 0 and with it calculating gaps between l and r. Check the condition described above we can produce via two binary search query to array b.

Few details:

  1. How do we know, that between positions l and r we can fill gaps in such a way, that out answer still the best?
    Let countSkip(l, r) — count gaps on interval (l..r), countBetween(x, y) — count different numbers from set b, lying in the range (x..y).
    Then, positions l and r are good only if lenLIS[r] - lenLIS[l] = min(countSkip(l, r), countBetween(a[l], a[r])). countSkip we can calculate while iterates position l, countBetween(x, y) = max(0, lower_bound(b, y) - upper_bound(b, x)).

  2. What to do, is LIS ends or begins in gaps?
    This case we can solve by simply adding  - ∞ and  + ∞ in begin and end of out array.

Complexity — . Memory — O(n + m).

Read more »

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

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

Hello everyone!

Codeforces Round #315 will take place soon. The authors of this round are students of Ural FU Umqra and Um_nik. This is our second round. First one was in the black days of Codeforces and we hope that this will not happen again after our round :)

We want to thank Codeforces team for great Codeforces and Polygon platforms and Zlobober for helping us prepare this round.

Good luck!

UPD1:
Score distribution.
div2 : 500-1000-1500-2250-2750
div1 : 500-1000-1500-2250-2500
We strongly recommend you to read all the problems. We try our best to prepare different problems and some problems that hard for us can be easy for you.

UPD2:
Editorial

UPD3:
Congratulations to the winners!

div1:
1. KAN
2. Petr
3. enot.1.10
4. tonyjjw
5. HYEA

div2:
1. Amdi
2. loser21
3. Aliquando
4. hqpwca
5. Lone_Wolf_LZ

Thank you for participating.

Read more »

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

By Um_nik, history, 2 years ago, In Russian,

More precisely: How to generate large inputs?

Read more »

Tags tc
 
 
 
 
  • Vote: I like it  
  • -19
  • Vote: I do not like it  

By Um_nik, 2 years ago, In Russian,

А пока все радуются фантастической возможности поучаствовать в Я.Алгоритме, у меня назрел вопрос по VKCup.

В официальной группе ВК была информация о том, что онсайт будет 24-27 июля.
Может быть, я что-то пропустил, но на кф я ничего такого не видел.

"Лучшие 20 команд по результатам отборочных интернет-этапов будут приглашены в финал соревнования, который состоится в июле 2015-го года в Санкт-Петербурге. Компания ВКонтакте покроет расходы на проезд и проживание финалистов, которые будут бороться не только за звание лучших из лучших, но и призовой фонд чемпионата." (c)
С кем связаться по поводу билетов и проживания?

Read more »

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

By Um_nik, 2 years ago, In Russian,

Может, я не прав, но мне кажется, что годик назад сильно-красных было от силы человек 15-20, да и красных было сотни три.

Обычно когда происходит инфляция, с этим что-то делают.

Можно, например, поднять границы до 2300 и 2700 соответсвенно.

Read more »

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

By Um_nik, 2 years ago, In Russian,

There was a tag search in the upper-right part of the page and now there is not.

What has happened?

Read more »

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

By Um_nik, 2 years ago, In Russian,

Пару раз сталкивался с такой ситуацией: добавление комментария в код меняет вердикт проверки.

Сегодня удаление одних комментариев и вставка других меняют вердикт с TL 9 на RTE (access violation) 9.

Год назад комментирование cin >> n; в конце программы меняло вердикт с RTE (access violation) 34 на RTE (access violation) 13.

Дело происходит на тимусе, компилятор Visual C++ 2010.

Можете помочь с этим? Что может вызывать такое поведение?

UPD: Второй пример.
http://pastebin.com/41yqH6BF
http://pastebin.com/7PE31Erm
Условие

Read more »

 
 
 
 
  • Vote: I like it  
  • -17
  • Vote: I do not like it  

By Um_nik, 3 years ago, In Russian,

Всем привет.

14.01.2015 около 15:00 МСК (и некоторое время после этого) я не мог залогиниться. Соответствующая кнопочка просто выкидывала на главную страницу так и не залогинненым.

Это у меня локальная проблема или администрации стоит обратить внимание?

Read more »

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

By Um_nik, 3 years ago, In Russian,

У многих команд ACM есть тренера. Тренер может составлять план тренировок, следить за состоянием команды, давать советы по тактике, выявлять ошибки и предлагать пути по их исправлению.

Но откуда тренера берутся? ACMщики могут прийти из школьных олимпиад, их могут привести друзья и т.д. А тренер не может прийти из школьных олимпиад.
Казалось бы, чтобы стать тренером, нужно самому быть звёздным ACMщиком, знать алгоритмы и тонкости тактики. Но мне кажется, что это не главные качества тренера. Зачем тренеру знать все алгоритмы, лучше знать, кто эти алгоритмы хорошо знает и может рассказать. С тактикой сложнее, но опять же, тактика меняется от команды к команде, почему все тактические изыски команд бурной ACM-карьеры тренера подойдут его подопечным?
Видимо, главным качеством тренера должна быть способность увлечь студентов, дать им толчок к самостоятельной работе. Но это качество присуще чисто характеру человека и никак не связано с ACM. Дак почему же мы решили, что тренер должен быть ACMщиком?

В защиту традиции можно предъявить следующий аргумент: "Никто ведь не заставляет ACMщиков идти в тренера. Идут те, кому это интересно, те, у кого есть все эти лидерские/тренерские качества."
Действительно, если ACMщиков много, то среди них может найтись человек, в той или иной степени обладающий этими замечательными способностями, готовый пойти воспитывать молодёжь. А может и не найтись. Проблема.
А если ACM-сообщество небольшое, то даже большая вероятность, что может не найтись.

И что делать?
В такой ситуации кто-то из "заканчивающих карьеру" может сказать: "Ну кто-то же должен это делать, давайте я буду." Это может не очень хорошо закончится, не правда ли?

Read more »

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

By Um_nik, 3 years ago, In Russian,

Постановка задачи:

Имеется n деталей и два станка. Каждая деталь должна сначала пройти обработку на первом станке, затем — на втором. При этом i-ая деталь обрабатывается на первом станке за ai времени, а на втором — за bi времени. Каждый станок в каждый момент времени может работать только с одной деталью.

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

Решение задачи описано на e-maxx.ru

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

Опуская доказательства: в решении предлагается отсортировать пары чисел (ai, bi) следующим компаратором:

Мы определили некоторое бинарное отношение на множестве пар чисел. Внимание, вопрос: почему этим отношением можно пользоваться как компаратором?

Сначала о плюсах: Это отношение действительно транзитивно.

Давайте это докажем (если вы хотите минусов, эту часть можно пропустить).

Дано: min(a1, b2) < min(a2, b1), min(a2, b3) < min(a3, b2).

Доказать: min(a1, b3) < min(a3, b1)

Доказательство: от противного. Предположим min(a1, b3) ≥ min(a3, b1)

Есть два варианта:

1) a1 ≤ b2

Из этого следует a1 < a2, a1 < b1. Из нашего предположения получаем, что

Отсюда min(a1, b3) ≤ b3 < min(a3, b1)

2) a1 > b2

Из этого следует b2 < a2, b2 < b1.

Отсюда min(a1, b3) ≤ b3 < min(a3, b1)

Получили противоречие.

Ч.т.д.

А вот теперь о минусах. Очевидно, это отношение не обладает свойством антисимметричности. Более того: Давайте на множестве пар чисел введем отношение "быть равными" в том смысле, что ни одна из пар не больше другой. . Это отношение транзитивным не является!

Пример: (2, 3) = (1, 1) = (4, 5), но (2, 3) < (4, 5).

Справедливости ради: Можно показать, что если (a1, b1) = (a2, b2) = (a3, b3) и a2! = b2, то (a1, b1) = (a3, b3)

Давайте определим отсортированную последовательность так: Последовательность отсортирована по неубыванию, если для любых , т.е. никогда больший элемент не идет перед меньшим.

Построим ориентированный граф так: Вершины — элементы последовательности, дуга из i в j соответствует pi < pj. Тогда наше определение отсортированной последовательности совпадает с топологической сортировкой этого графа.

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

Но если мы просто передадим наш компаратор в пузырьковую сортировку, то последовательность не будет отсортирована.

Пример: (4, 5), (1, 1), (2, 3)

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

Таким образом, доказательство на e-maxx не верно.

Read more »

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

By Um_nik, 3 years ago, In Russian,

Кто готов поделиться своими красивыми решениями?

Read more »

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

By Um_nik, 4 years ago, In Russian,

Тема такая: У меня завтра ДР, и мы собираемся отпраздновать прекрасным контестом в какой-нибудь уютной кафешечке.
И мы даже готовы писать серьезную тренировку, но все же пытались найти какой-нибудь веселый праздничный контест.
Соответственно, возник такой вопрос: существуют ли они где-нибудь в природе, праздничные контесты?)
Например, контесты с серьезными задачами, но тематическими уральскими графоманскими сказочками предысториями?
Всем заранее спасибо)

Read more »

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

By Um_nik, 4 years ago, In Russian,

Вступление

Задача меня порадовала (часть про [1...k], разумеется), на самом контесте я написал двухмерную динамику 3458123, но ограничения позволяли написать что угодно :)

Слышал я о решении полным перебором за kk + 2. Но после контеста я узнал о волшебной формуле ans = kk - 1

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

А теперь о причине, побудившей меня написать это: лично я понятия не имел (и не имею) о том, что такое Cayley trees. Поэтому хочу постараться подробно описать вывод формулы, не требующий никаких знаний.

Надеюсь, вы найдете у меня ошибку ;)

Динамика

Начнем с попытки прогенерировать первые номера домов.

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

Условно обозначим это 1... (потом станет понятнее, почему обозначение именно такое), соответствующих вариантов у нас k.

Для номера второго дома есть три принципиально различных варианта:

    1. усл.об. — 11..., вариантов — k*1=k
    1. Но тогда мы не сможем попасть к первому дому от второго.
  1. 3 и более. Кол-во вариантов — k*(k-2). усл.об. — 13... Почему именно 3 ? Потому что если не 3, то мы вполне можем поменять местами дома так, чтобы этот стал третьим.

Переходим к третьему дому от первого варианта:

  1. 1 или 2. вариантов — k*2=2k. усл.об. — 111... Вот тут важный момент. Почему 112 не отличается от 111 ? Потому что и так, и так мы сможем дойти от всех домов к первому. Таким образом, '1' в усл.об. характеризует то, что от данного дома мы уже можем добраться до первого, а значит теперь необязательно стремиться в первый дом, можно стремиться в один из них.

... (дальше понятно)

Тогда посчитаем такую двухмерную динамику: в dp[x,y] будем хранить кол-во вариантов таких, что "обработано" уже х домов, причем из первых y из них мы можем попасть в первый. Из попыток генерации вполне понятно, как пересчитывать:

dp[1,1]=k

(j<i) dp[i, j] = dp[i - 1, j]·(k - i)

Ответом, очевидно, будет являться dp[k,k]

Вывод формулы

Путем анализа формул пересчета и божественного рандома заметим

(i>1) dp[i, i] = ki - 1

(1<j<i)

Теперь докажем эти формулы по индукции.

База индукции dp[1,1]=k верна.

(j<=i)

Для доказательства докажем индукцией по х такое равенство:

База индукции х=2, очевидно, верна.

Подставляя в полученное равенство x=i, получаем

dp[i + 1, i + 1] = ki - 1(k - i) + ki - 1i = k(i + 1) - 1

Таким образом, формулы доказаны, а значит dp[k, k] = kk - 1 для всех k>1

Но так уж получилось, что 1 = 1^0, поэтому можно считать ответ всегда равным kk - 1

Read more »

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