Enchom's blog

Balkan Olympiad in Informatics 2014 Problems — Day 1
By Enchom, 10 years ago, In English

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.

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

»
10 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

solution for the 1st problem:

  • Binary search on the minimum diameter. Let's call the current candidate D.
  • Root the tree arbitrarily.
  • For the root node:
  • First, recursively apply this procedure to all children.
  • Then, call the 'cost' of a subtree the weight of the longest path from the current node through that subtree.
  • The diameter of the current node is the sum of the costs of the two most expensive subtrees.
  • While this diameter exceeds D, cut the edge to the most expensive subtree. Count the number of cuts necessary. If this exceeds K, D is invalid. Otherwise, it's valid.

Not sure if that will pass the largest test case. It's the same as this problem, but with larger constraints.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, that seems so simple now.. I feel kinda stupid.

    And since there are subtasks with N<=110,000 and N<=260,000, I suppose this solution would ge 55. Wondering what the 100 pts solution is.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Don't feel bad! It was also a TopCoder problem solved by only 20% of D1 competitors. I failed it during contest :(

      You might able to shave off a factor of by not keeping all the subtrees ordered by size, since you only need the 2 greatest unless you make a cut... that might just make it O(n2), though.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I told Hristo Venev that solution and he proposed pretty much what sparik mentioned below. All, except at most one, children that are deeper than D/2 must be removed, so remove all except one — this step is linear, then do one more linear step to check if the highest two produce sum larger than D. If they do remove the last one too.

        Still, it's BOI, we had 5 hours unlike topcoder, so I feel kinda stupid :D

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I think we should cut the edges either to all of the subtrees with cost >=D/2 or leave only the cheapest one.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Probably I just haven't understood something, but there are different ways to arrange cut edges in a subtree to get diameter not exceeding D, however those with higher the deepest vertex are better for your greedy solution.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I had the same idea, but why is it N(logN)^2 ?

    If you procedure is ClogC, where C is the number of children of the current node, is it not just NlogN ?

    Edit: wow sorry I completely forgot about the binary search, my bad.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But you have an additional log factor because of the binary search.

      → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

is there any official site that we could see the scores

→ Reply