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

We have all the possible 3-grams of lower case letters (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

• If we try to merge aaa with bbb we have to append bbb to the end of aaa, because they don't overlap:
  merge(aaa, bbb) = aaabbb

• If we merge aaa with aab we can create a smaller string:
  merge(aaa, aab) = aaab

In the best case, if we manage to always do a second kind of merge, we will be extending the resulting string by 1 character. There are 17576 triplets, so there can be at most 17575 single character extensions. This will result in 17575 + 3 = 17578 characters string.

In the worst case, we will append all of the 3-grams to each other, thus creating a 17576 * 3 = 52728 characters string.

How to combine all of them to get the total string of the minimum length?

Picture to attract people :)

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.