So Day 1 passed and the problems aren't online. As they were quite tough I decided to put them here and see the community's solutions. I don't have the english papers and I don't have much time to write so I will just describe them shortly and try to include the most useful information.

Problem 1 — Diameter

You are given a weighted tree of N nodes and a number K. You must perform a K-partitioning. That is you must choose K non-empty, non-intersecting subsets of nodes that cover all nodes. Each subset is called a partition. A diameter of a partition is the longest distance between a pair of nodes in the partition. A partition doesn't have to be connected, so distance is defined as the distance in the initial tree. A diameter of partitioning is the longest diameter of all partitions. Your task is to find the minimum possible diameter of K-partitioning.

Constraints:

1<=N<=260,000

1<=K<=N

1<=weight of edges of tree<=1,000

Subtask 1 (10 points) : K=1

Subtask 2 (15 points) : K=2

Subtask 3 (30 points) : N<=110,000

Subtask 4 (45 points) : no additional constraints

Time Limit : 1s

Memory Limit : 256MB

Example

Input:

5 2

1 2 1

1 3 1

2 4 1

2 5 1

Output:

2

Input format is : n,m then n-1 lines "a b c" denoting an edge from a to b with weight c.

My solution

During the competition I couldn't find any polynomial-time complexity solution, so I simply solved the K=1 subtask in which you obviously have to find the diameter of the original tree which is a trivial problem.

P.S. Binary search for the answer possibly?

Problem 2 — Hittites

You are given N codes in the form of strings of lower-case latin letters. You need to calculate the amount of different strings of length K that have at least one of the given codes as a substring. Print the amount modulo 10^9+7.

Constraints:

Subtask 1 (13 points):

1<=K<=5

1<=N<=10

Subtask 2 (19 points):

1<=K<=5,000

1<=N<=26

Length of each code is exactly 1.

Subtask 3 (29 points):

1<=K<=5,000

N=1

Sum of lengths of the N codes is at most 2,000.

Subtask 4 (39 points):

1<=K<=5,000

1<=N<=2,000

Sum of lengths of the N codes is at most 2,000.

Time Limit = 3s

Memory Limit = 256MB

Example

Input:

3 2

aa

dbe

Output:

52

Input format is : n, followed by n lines with one string on each — the codes.

My solution

I managed to solve this problem for full points. Here is my solution. It goes as the Aho-Corrasick algorithm. We build a trie and calculate the failure function on each node. Then for each node and for each letter on it we calculate a "reach" function. That is, where we would end up if we are in this node and this letter is added. Then I mark all nodes that lead to a successful word, that is those nodes in which if we end up — then we had some word as a substring. Finally I do DP-like calculations on K iterations. On each iteration each node that isn't marked for each letter adds its value to the node it reaches according to the "reach" function. In the beginning the root is 1 and all others are 0. Finally I sum the values of all nodes that aren't marked after the k-th iteration and this is the amount of words that don't have any of the listed words as their substring. The answer is then 26^k — (number of words that don't have listed words as their substring).

Solution complexity is : O(26*L*K), where L is the total length of all strings. This manages to pass under 3 seconds.

Problem 3 — Princes

There are three princes A,B and C. The king has N diamonds and wants to distribute them among the princes. The i-th diamond has value of 2^(i-1), so the values of the diamonds are 2^0, 2^1, 2^2...2^(N-1).

In the beginning princes don't have any diamonds and in N steps the king chooses a diamond and a prince and gives the diamond to the prince. Let Aj,Bj and Cj be the corresponding values to the total value of the diamonds the princes have after the j-th iteration. Since A is the eldest and C is the youngest, the inequality Aj>=Bj>=Cj for all 1<=j<=N must hold.

Each process of distributing in which the equality holds for all j is called "fair". Denote number of a diamond by dj and the prince it's given to by pj. The process of distributing is coded by the vector "_p1d1 p2d2 ... pNdN_". Find the K-th fair distribution if they are sorted lexicographically.

When comparing two distributions lexicographically their elements are compared from left to right. An element is a pair of a prince and a diamon. For each element first the princes are compared (A<B<C) and then the numbers (1<2<3..<N).

For example the process "Give diamond 3 to A, give diamond 2 to B, give diamond 4 to A, give diamond 1 to C" is coded by "A3 B2 A4 C1".

Example of comparing is that the vector "A3 A4 A1 B2" is smaller than "A3 B2 A4 C1".

The first vector of length 4 is "A1 A2 A3 A4", the second is "A1 A2 A4 A3" and so on.

Constraints:

Subtask 1 (11 points)

1<=N<=20

1<=K<=10^18

Subtask 2 (17 points)

1<=N<=50

1<=K<=10^200

Subtask 3 (31 points)

1<=N<=100

1<=K<=10^19

Subtask 4 (41 points)

1<=N<=100

1<=K<=10^300

Time Limit = 3s

Memory Limit = 256MB

Example

Input : 3 1

Output : A1 A2 A3

Input : 3 3

Output : A1 A3 B2

Input : 4 9 Output : A1 A4 A2 B3

Input format : n,k

Note: During the competition it turned out the tests were wrong. They were fixed and the competition was extended by 45 minutes. However I have reasons to believe the new tests may not be correct either.

My solution

I implemented a DP and a simple approach I won't explain now due to lack of time, however I managed to get it to pass only for cases in which I could use unsigned long long, that is subtasks 1 and 3, therefore i got 42 points.

So in total I got 152 points which is 6th place. I'd love to hear some solutions about diameter as it is the only task whose solution I have no clue of.