Hello. Some time ago I encountered a problem:

You are given DAG (directed acyclic graph) of tasks and an array that describes how much time each task takes to be executed. Graph describes dependencies between tasks. If there is an edge from a to b, it means that in order to start executing task a, task b has to finish execution. Now the question is: given some task c and k processors, what is the earliest time c can finish execution?

This problem is easy when we have only 1 processor or infinite amount of processors, but when we restrict ourselves to k processors the question becomes harder. I think I have some idea about this problem, but in order to make sure I'd like to code the solution. Does anyone know online judge that has this problem?

Hello everyone. Here is problem I recently encountered on 'Algorithm and data structures' course exam. The problem statement is:

You are given a sequence a1,a2,...,an, and a number b. Your task is to find algorithm which counts all pairs (l,r) such that median of sequence a(l),a(l+1),..,a(r) is bigger than b.

My solution on exam was O(n^2logn) which used order statistics tree. Other solutions were

• O(n^2) — used sorting to check median of pair in constant time

• O(nlogn) — related to counting inverses in permutation.

And surprisingly someone came up with O(n) solution. So here is my question, can anyone tell me about this solution to the problem? I'm quite curious how this can be done in linear time.

Hello everyone,

I'm struggling for a quite long time with certain problem (like 4 real attempts to solve it). Here is problem statement:

You are given a city which is represented by graph which is a tree (of course road intersections are nodes and roads are edges). Your task is to light every road in the city, you can do this by building street lights on road intersections. When there is street light on road intersection every road which comes out of it is lighted. Now your task is to find the minimum amount of street lights to light entire city and find amount of ways you can do this.

Input:

First line of input is n (n <= 100.000) — the number of road intersections in city. The next n-1 lines contain two integers a,b which mean that there is bidirectional road between intersections numbered a and b.

Output

First integer of output is optimal amount of street lights, and the second integer is the amount of optimal placements of streets lights in the city modulo 10007.

Examples:

Input:

4

1 2

2 3

3 4

Output: 2 3

Input:

5

1 2

2 3

3 4

4 5

Output:

2 1

Input:

6

1 2

2 3

1 4

4 5

1 6

Output:

3 5

Finding optimal number of street lights is quite simple, just two-color the tree and take the less often color. However finding amount of optimal street light placements is really hard for me. I was trying to root the tree at some node, and then find recurrence relation between node and its children so i can use dynamic programming. I believe in order to solve this problem one has to use at least two functions, h(v) — which is answer to the problem when there is street light in node v (where v is root of subtree), and l(v) when there is no street light at node (v), i tried to use some other functions like opt(v) — which represents optimal amount of street lights at subtree rooted at node v, but i just couldn't come up with recurrence relation.

Does anyone have any idea on how to solve this problem ?