5

There are N problems numbered 1..N which you need to complete. You've arranged the problems in increasing difficulty order, and the ith problem has estimated difficulty level i. You have also assigned a rating vi to each problem. Problems with similar vi values are similar in nature. On each day, you will choose a subset of the problems and solve them. You've decided that each subsequent problem solved on the day should be tougher than the previous problem you solved on that day. Also, to not make it boring, consecutive problems you solve should differ in their vi rating by at least K. What is the least number of days in which you can solve all problems?

Input: The first line contains the number of test cases T. T test cases follow. Each case contains an integer N and K on the first line, followed by integers v1,...,vn on the second line.

Output: Output T lines, one for each test case, containing the minimum number of days in which all problems can be solved.

Constraints:
1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000

Sample Input:
2
3 2
5 4 7
5 1
5 3 4 5 6

Sample Output:
2
1

This is one of the challenge from interviewstreet.
Below is my approach
Start from 1st question and find out max possible number of question can be solve and remove these questions from the question list.Now again start from first element of the remainning list and do this till now size of the question list is 0. I am getting wrong answer from this method so looking for some algo to solve this challenge.

7
  • 2
    How are you deciding the max number of questions solvable per day?
    – Colin D
    Apr 24, 2012 at 18:35
  • What does thi shave to do with graphs?
    – hugomg
    Apr 24, 2012 at 18:41
  • On what case are you getting an erroneous answer? I really can't see any problem with the algorithm you suggested. Apr 24, 2012 at 18:53
  • @AndersLindahl For below case I am getting 7 days and correct answer is 5 days N= 41 K= 335 Question list = 47 387 431 691 217 983 847 186 493 215 852 815 953 341 242 931 754 865 191 255 631 187 673 763 288 73 698 326 222 390 661 621 777 443 311 993 425 510 530 270 76
    – archit
    Apr 24, 2012 at 19:41
  • Is the second sample input for 5 1 5 3 4 5 6 is solvable in 1 day ? Nov 1, 2013 at 6:22

4 Answers 4

17

Construct a DAG of problems in the following way. Let pi and pj be two different problems. Then we will draw a directed edge from pi to pj if and only if pj can be solved directly after pi on the same day, consecutively. Namely, the following conditions have to be satisfied:

  1. i < j, because you should solve the less difficult problem earlier.
  2. |vi - vj| >= K (the rating requirement).

Now notice that each subset of problems that is chosen to be solved on some day corresponds to the directed path in that DAG. You choose your first problem, and then you follow the edges step by step, each edge in the path corresponds to the pair of problems that have been solved consecutively on the same day. Also, each problem can be solved only once, so any node in our DAG may appear only in exactly one path. And you have to solve all the problems, so these paths should cover all the DAG.

Now we have the following problem: given a DAG of n nodes, find the minimal number of non-crossing directed paths that cover this DAG completely. This is a well-known problem called Path cover. Generally speaking, it is NP-hard. However, our directed graph is acyclic, and for acyclic graphs it can be solved in polynomial time using reduction to the matching problem. Maximal matching problem, in its turn, can be solved using Hopcroft-Karp algorithm, for example. The exact reduction method is easy and can be read, say, on Wikipedia. For each directed edge (u, v) of the original DAG one should add an undirected edge (au, bv) to the bipartite graph, where {ai} and {bi} are two parts of size n.

The number of nodes in each part of the resulting bipartite graph is equal to the number of nodes in the original DAG, n. We know that Hopcroft-Karp algorithm runs in O(n2.5) in the worst case, and 3002.5 ≈ 1 558 845. For 100 tests this algorithm should take under a 1 second in total.

6
  • The min path cover is NP-hard, how come you have a polynomial bound? Apr 24, 2012 at 19:04
  • @n.m. Our graph is acyclic. For the special case of acyclic directed graphs this problem is not NP-hard. I will add this to the answer.
    – Skiminok
    Apr 24, 2012 at 19:07
  • What if the restriction of visiting every vertex "once" is relaxed to "atleast" once? Can then we use Bipartite Matching to know the minimum path cover?
    – divanshu
    Jun 9, 2013 at 23:30
  • *I have edited and updated the broken link. Please have a look
    – gabbar0x
    Nov 11, 2015 at 18:02
  • 1
    @bholagabbar that link has broken pictures. I found a description on Wikipedia.
    – Skiminok
    Nov 11, 2015 at 21:57
2

The algorithm is simple. First, sort the problems by v_i, then, for each problem, find the number of problems in the interval (v_i-K, v_i]. The maximum of those numbers is the result. The second phase can be done in O(n), so the most costly operation is sorting, making the whole algorithm O(n log n). Look here for a demonstration of the work of the algorithm on your data and K=35 in a spreadsheet.

Why does this work

Let's reformulate the problem to the problem of graph coloring. We create graph G as follows: vertices will be the problems and there will be an edge between two problems iff |v_i - v_j| < K.

In such graph, independent sets exactly correspond to sets of problems doable on the same day. (<=) If the set can be done on a day, it is surely an independent set. (=>) If the set doesn't contain two problems not satisfying the K-difference criterion, you can just sort them according to the difficulty and solve them in this order. Both condition will be satisfied this way.

Therefore, it easily follows that colorings of graph G exactly correspond to schedules of the problems on different days, with each color corresponding to one day.

So, we want to find the chromaticity of graph G. This will be easy once we recognize the graph is an interval graph, which is a perfect graph, those have chromaticity equal to cliqueness, and both can be found by a simple algorithm.

Interval graphs are graphs of intervals on the real line, edges are between intervals that intersect. Our graph, as can be easily seen, is an interval graph (for each problem, assign an interval (v_i-K, v_i]. It can be easily seen that the edges of this interval graph are exactly the edges of our graph).

Lemma 1: In an interval graph, there exist a vertex whose neighbors form a clique.

Proof is easy. You just take the interval with the lowest upper bound (or highest lower bound) of all. Any intervals intersecting it have the upper bound higher, therefore, the upper bound of the first interval is contained in the intersection of them all. Therefore, they intersect each other and form a clique. qed

Lemma 2: In a family of graphs closed on induced subgraphs and having the property from lemma 1 (existence of vertex, whose neighbors form a clique), the following algorithm produces minimal coloring:

  1. Find the vertex x, whose neighbors form a clique.
  2. Remove x from the graph, making its subgraph G'.
  3. Color G' recursively
  4. Color x by the least color not found on its neighbors

Proof: In (3), the algorithm produces optimal coloring of the subgraph G' by induction hypothesis + closeness of our family on induced subgraphs. In (4), the algorithm only chooses a new color n if there is a clique of size n-1 on the neighbors of x. That means, with x, there is a clique of size n in G, so its chromaticity must be at least n. Therefore, the color given by the algorithm to a vertex is always <= chromaticity(G), which means the coloring is optimal. (Obviously, the algorithm produces a valid coloring). qed

Corollary: Interval graphs are perfect (perfect <=> chromaticity == cliqueness)

So we just have to find the cliqueness of G. That is easy easy for interval graphs: You just process the segments of the real line not containing interval boundaries and count the number of intervals intersecting there, which is even easier in your case, where the intervals have uniform length. This leads to an algorithm outlined in the beginning of this post.

2
  • "independent sets exactly correspond to sets of problems doable on the same day. (<=) If the set can be done on a day, it is surely an independent set. " - Won't the independent sets correspond to problems that cannot be done on a day ? Since it has all the problems that are not adjacent in the graph ?
    – Kyuubi
    Oct 22, 2013 at 16:18
  • "You just process the segments of the real line not containing interval boundaries and count the number of intervals intersecting there, which is even easier in your case, where the intervals have uniform length." - Can you explain this with a small example ?
    – Kyuubi
    Oct 22, 2013 at 16:32
0

Do we really need to go to path cover? Can't we just follow similar strategy as LIS.

The input is in increasing order of complexity. We just have to maintain a bunch of queues for tasks to be performed each day. Every element in the input will be assigned to a day by comparing the last elements of all queues. Wherever we find a difference of 'k' we append the task to that list.

For ex: 5 3 4 5 6

1) Input -> 5 (Empty lists so start a new one)

5

2) 3 (only list 5 & abs(5-3) is 2 (k) so append 3)

5--> 3

3) 4 (only list with last vi, 3 and abs(3-4) < k, so start a new list)

5--> 3

4

4) 5 again (abs(3-5)=k append)

5-->3-->5

4

5) 6 again (abs(5-6) < k but abs(4-6) = k) append to second list)

5-->3-->5

4-->6

We just need to maintain an array with last elements of each list. Since order of days (when tasks are to be done is not important) we can maintain a sorted list of last tasks therefore, searching a place to insert the new task is just looking for the value abs(vi-k) which can be done via binary search.

Complexity:

The loop runs for N elements. In the worst case , we may end up querying ceil value using binary search (log i) for many input[i].

Therefore, T(n) < O( log N! ) = O(N log N). Analyse to ensure that the upper and lower bounds are also O( N log N ). The complexity is THETA (N log N).

1
  • ok..I'm wrong here..we can't do a ceil because it's not necessary that the values will all be in increasing order. But again, we can solve this via connected component fashion using union-find. Jan 26, 2013 at 18:13
0

The minimum number of days required will be the same as the length of the longest path in the complementary (undirected) graph of G (DAG). This can be solved using Dilworth's theorem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.