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

Наверное, этот пост в первую очередь для меня, чтобы в будущем пересматривать это видео и показывать его друзьям и знакомым при беседе :)

https://youtu.be/Nn5wsdlJp2E

Today I wasn't able to solve the problem D — Small Multiple.
For the whole contest I thought that it is some kind of DP problem, but then I looked at the editorial and it turned out to be a graph problem O_o.

I started looking at the code of the people who solved it and I found out that they are implementing the same idea (more or less). Particularly, I like this solution.

• Is it some kind of a standard problem/idea?
• Does anyone know where I can read about it more abstractly?
• Does anyone know some similar problems that require the same approach?

Here I'll keep the list of problems to train this idea:
1. D — Small Multiple
2. 0-K Multiple
3. INUMBER — Interesting number
4. Sums

We have a tree with n (2 ≤ n ≤ 1000) nodes and we need to find k (1 ≤ k ≤ 100 and k ≤ n - 1) vertices such that the path going through all of these vertices has the maximum length.

Note:

• The path should start at vertex 1 and finish also at vertex 1.
• The algorithm has to return just the length of the maximum path (the path itself is not needed).
• The weight for an edge has following restrictions: 0 ≤ w ≤ 100000.

Let's say we have the following tree with n = 5 vertices:

We need to find k = 3 vertices which will give us the longest path.

For this tree the maximal path is the following:
1 ⟶ 5 ⟶ 2 ⟶ 4 ⟶ 1

It has the total length of 13 + 18 + 10 + 5 = 46.
So, for that particular tree we have to print 46 as our result.

I came up with a following greedy/dp-like solution. First we solve the problem for k = 1 and we remember this solution in a linked list 1 ⟶ v ⟶ 1. After that we try to solve the problem for k = 2 by trying all of the remaining n - 2 vertices and insert it in the current path: 1 ⟶ u ⟶ v ⟶ 1 and 1 ⟶ v ⟶ u ⟶ 1. After going through all of the vertices we choose the one which gave us the best result. Then we proceed to solve k = 3.

The problem is that it looks like this solution is not correct, because it fails the tests for this problem. I cannot prove that my solution is correct and I cannot disprove it. All I managed to do is to generate millions of different random trees and in all of these cases my clever solution matched bruteforce solution.

For now all my effort is directed towards generating a counter example in which my method will fail, but if it is correct I'd be glad to see the reasoning why is it correct.

There are n boxes. Boxes contain marbles.
Box number 1 contains 1 marble.
Box number 2 contains 2 marbles.
...
Box number n contains n marbles.

We have to choose exactly b boxes out of n original boxes, so that we would have exactly t marbles in total.

For example, if we have a set of boxes B = {1, 2, 3, 4, 5} and we have to choose b = 4 boxes to get the total target value t = 13, then we should output 1 3 4 5.

But if we have the same set of boxes B = {1, 2, 3, 4, 5} and we have to choose b = 3 boxes with the same total value of t = 13, then we have to print Impossible.

I have a simple bruteforce solution, which is working, but for too long. And I have a dynamic programming solution, which is not correct:

long long dp[10000][100];

for (int v = 1; v <= n; v++) dp[v][1] = 1ll << v;

for (int boxes = 2; boxes <= b; boxes++)
  for (int cur = 1; cur <= t; cur++)
    for (int v = 1; v <= n; v++)
      if (cur - v >= 1)
      {
        long long flag = dp[cur - v][boxes - 1] & (1ll << v);
        long long possible = dp[cur - v][boxes - 1];
        if (!flag && possible)
          dp[cur][boxes] = dp[cur - v][boxes - 1] | (1ll << v);
      }

My dp solution is not correct, because it remembers only one configuration. For example, to get target value t = 5, we can choose (1, 4) or we can choose (2, 3). My code will remember only one of those 2 choices.

The task becomes even more complicated when we are given the following constraints:
1 ≤ n ≤ 10¹⁸
1 ≤ t ≤ 10⁶
1 ≤ b ≤ n

Мы порождаем все триплеты используя алфавит из 26 английских букв (A = {a, b, c, ..., z}):
A³ = A × A × A = 
{
  (a, a, a), 
  (a, a, b), 
  (a, a, c), 
    ..., 
  (a, a, z), 
  (b, a, a), 
    ..., 
  (z, z, y), 
  (z, z, z), 
}

|A³| = 26³ = 17576

• Если мы попытаемся слить триплеты aaa и bbb, то нам придётся прикрепить bbb к концу строки aaa, так как они не перекрываются:
  merge(aaa, bbb) = aaabbb

• Но если мы сливаем строку aaa со строкой aab, то мы получим результат меньшей длины:
  merge(aaa, aab) = aaab

В лучшем случае, если нам получится всегда делать слияния второго типа, то для каждого триплета (кроме первого) мы будем просто удлинять результирующую строку на 1 символ. Всего у нас есть 17576 триплетов, так что мы добавим к результирующей строке 17575 символов. В результате этих добавлений финальная строка, содержащая все возможные триплеты, будет иметь длину 17575 + 3 = 17578.

В худшем случае мы всегда будем делать операцию слияния первого типа, что приведёт к результирующей строке длины 17576 * 3 = 52728.

Лучший результат находится где-то в интервале [17578, 52728].

Как же нам скомбинировать все триплеты, чтобы получить строку минимальной длины?

Картинка для привлечения внимания.

Finally, I've solved 100 problems on Timus Online Judge!
It took me almost 5 years :)

Next goal is to reach 200 problems.
Hope it won't take me that long this time ;)

There was recently a problem called Sanatorium. It is relatevely easy and a lot of people solved it. I don't know why, but with some problems I experience difficulties which a normal human should not ever encounter :)

I have a picture in mind which I want to share with you and I'd like to see how would you transform it into the code. Please, do not use your own interpretations (though I'd be glad to see them) of the problem. Do not use your own representations. Just use the following picture:

Each figure is a possible situation(state) for Vanya. We can enumerate all of the skewed rectangles with a pair of numbers (m, n). m — number of missed meals in day 0, n — number of skipped meals in day 5. The first rectangle is (0, 0), because we don't miss meals in the day 0 and we don't miss meals in day 5. Now the problem that I have is fitting (b, d, s) inside of these skewed rectangles. For example, if we are given (b = 6, d = 5, s = 5), we cannot use skewed rectangle (1, 0) (which located to the right of the very first rectangle), because it has x-1=5 breakfasts instead of required b = 6 meals in the morning. As I see it, the input (b = 6, d = 5, s = 5) splits all the possibilities (there are 9 of them) into 2 non-overlapping sets:
PossibleSet = {(0, 0), (0, 1), (0, 2)}
ImpossibleSet = {(1, 0), (2, 0), (1, 1), (2, 1), (1, 2), (2, 2)}

And we can check now the number of missed meals inside the PossibleSet: PossibleSet = {(6 - 6 + 6 - 5 + 6 - 5 = 2), (6 - 6 + 6 - 5 + 5 - 5 = 1), (6 - 6 + 5 - 5 + 5 - 5 = 0)}

So we can get the minimum number of missed meals 0 = min(2, 1, 0).

My brain refuses to produce the code out of these very thoughts.

Please, note that this is not the usual ask for help of how to solve the problem. This isn't merely about solving the problem. This one is about thinking process and it's correction.
I'd be glad to see the transformation steps (as detailed as possible). How does this picture smoothly translates into code (not just the final solution — there are plenty of those already). Maybe it will help me bridge some psycological gap that I currently have in my brain.

Кто-нибудь знает задачи такого же формата, как и задачи на codeforces или topcoder, которые включают в себя численное интегрирование или дифференцирование?

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