tag:blogger.com,1999:blog-786333285568106173.post8330284880042919868..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: More on Problem 2Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-786333285568106173.post-91464912665741347962009-08-06T22:01:28.226-04:002009-08-06T22:01:28.226-04:00Mihai #4.
Hrushikesh, it's good you verified ...Mihai #4.<br /><br />Hrushikesh, it's good you verified the O~(n^2 k). Weird algorithm, indeed.<br /><br />What makes you optimistic about getting O(n lg n) for any constant k? I do not see it. Even if you get O(2^k * nlg n), I would find this quite interesting.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-78908944581391250532009-08-06T19:02:57.848-04:002009-08-06T19:02:57.848-04:00#2 Hrushikesh
"#3 CarpathianBlackMetal":...#2 Hrushikesh<br />"#3 CarpathianBlackMetal": You are indeed right, k=2 is linear, and k=3 is O(n log n). Probably we can get it down to O(n log n) for any k.<br /><br />"Mihai #4": Wow, that does work.<br />Putting it down it here for sake of completeness:<br /><br />State is T[i][h][k] denoting the maximum j such that all points between i and j with height >= h can be covered using at most k rectangles.<br /><br />Answer to the instance is yes if T[0][0][K] = (n - 1)<br /><br />Observe that T[i][h+1][k+1] >= max(T[i][h][k+1],T[i][h+1][k]).<br /><br />So, in the manner similar to O(n^3) solution to original problem, the configuration for T[i][h+1][k+1] covers the point (x[t],h) or not. If yes, T[i][h+1][k] = T[i][h][k]. Otherwise find the smallest number of rectangles required to points in [i,t-1] with height >= h+1, let this number be l, which can take only constantly many values. We have that T[i][h+1][l] >= (t - 1), and then, T[i][h+1][k] = T[t+1][h+1][k-l].<br /><br />Handle T[i][0][k] differently, similar to the O(n^3) solution for original problem.<br /><br />We get a O(n^2 klogk) solution.Hrushikeshhttps://www.blogger.com/profile/11306350705226598133noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-12240365938537689402009-08-06T07:47:06.220-04:002009-08-06T07:47:06.220-04:00Mihai #4.
In retrospect, my suggestion in Mihai #...Mihai #4.<br /><br />In retrospect, my suggestion in Mihai #2 for how to get O(n^2 * K) does not work. <br /><br />I now have a different suggestion, which seems more plausible: let T(i,k,x) be the maximum j such that you can cover all points between i and j, and above k, using at most x rectangles.<br /><br />Does this work for getting O(n^2 * K)?Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-26566381730772347122009-08-06T07:44:37.935-04:002009-08-06T07:44:37.935-04:00Mihai #3.
Mihai, I think there is a well-foundedn...Mihai #3.<br /><br /><i>Mihai, I think there is a well-foundedness problem... You say that you draw a rectangle from x(i) to x(j) and then compute the rest with T(i,j,new height), but this value has not yet been computed.</i><br /><br />No, I was careful about that. Note condition 3 in Observation 2. It says that you only need to consider this rectangle if it covers both i and j. This means that once you kick out the points covered by the rectangle, the minimum (by x coordinate) is strictly larger than i, and the maximum strictly smaller than j.<br /><br />You can look at T(this minimum, this maximum, new height)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-90699248961917282382009-08-05T23:21:14.216-04:002009-08-05T23:21:14.216-04:00#4 CarpathianBlackMetal
Mihai, I think there is a...#4 CarpathianBlackMetal<br /><br />Mihai, I think there is a well-foundedness problem with your description of how to compute T(i,j,0).<br /><br />You say that you draw a rectangle from x(i) to x(j) and then compute the rest with T(i,j,new height), but this value has not yet been computed.<br /><br />I am missing something?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-26058251230114651612009-08-05T14:58:25.359-04:002009-08-05T14:58:25.359-04:00This is Mihai, comment #2.
Just to clarify, are y...This is Mihai, comment #2.<br /><br /><i>Just to clarify, are you assuming that all x's and all y's are different?</i><br /><br />Indeed, I can assume this by arbitrary tie breaking. <br /><br /><i>To compute T(i,j,0), you suggest to "proceed exactly as above"</i><br /><br />Here is the procedure that I was referring to (copy-paste from the post, slightly adapted):<br /><br />First, we draw a rectangle from x[i] to x[j] of maximal height. I get the optimum for covering the remaining points from T(i,j,new height).<br /><br />The other option is that there is no rectangle spanning x[i] to x[j]. Thus, there must be a break point m, such that T(i,j,0) = T(i,m,0) + T(m+1,j,0). Iterate to find the optimal such m. <br /><br /><br /><i>A good first step is to lower again memory usage from n^3 to n^2 while preserving the time complexity </i><br /><br />I agree. Let us first try to achieve this goal. I do not yet have a clear idea of how to attack it.<br /><br />Now, about Hrushikesh #1: I conjecture that my O(n^3) algorithm can actually be turned into O(n^2*K), if you can cover everything by K rectangles.<br /><br />For each pair (i,j), I now hold the optimum for every height k. How about hold, for every X, the lowest height you can solve by using ≤ X rectangles? In other words, T(i,j,k) decreases from X to 0 as k increases. Can I just hold the points where T(i,j,k) strictly increases?<br /><br />If this attack works, it would give an O(n^2) solution for the entire family of Decide_k.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-75184888861041325602009-08-05T09:58:43.654-04:002009-08-05T09:58:43.654-04:00#3 CarpathianBlackMetal
My second comment was wro...#3 CarpathianBlackMetal<br /><br />My second comment was wrong. You would need to find many break points k1, k1', k2, k'2, etc which I don't know how to do in linear time which sucks.<br /><br />@Hrushikesh<br /><br />You can do Decide_2 in linear time even if the points are not sorted. You simply enumerate the two possible "shapes" (either there is a bottom rectangle or a horizontal separator) and you can decide any one of them in linear time.<br /><br />Same trick with the enumeration of "shapes" works for Decide_3, but I think in this case you need the points to be sorted.<br /><br />For Decide_4, it seems to be trickier, but I wouldn't be surprised to see a linear time algorithm for constant number of rectangles.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-64318779714447372702009-08-05T02:18:36.011-04:002009-08-05T02:18:36.011-04:00#1 Hrushikesh (or is it #3?)
Should we also try t...#1 Hrushikesh (or is it #3?)<br /><br />Should we also try to prove lower bounds while we are at it?<br /><br />Here is one obvious way in which one might proceed:<br />Consider the related family of problems {DECIDE_k} for each natural number k. The input to DECIDE_k is the same as input for your problem, but the algorithm has to only decide whether the answer is <= k or > k.<br /><br />Now, DECIDE_1 can be done in linear time. <br /><br />DECIDE_2 can be done in time O(n log n), the time taken for sorting. Can it be done faster or can one prove a matching lower bound?<br /><br />What are the best lower and upper bounds for DECIDE_3?<br /><br />Can we prove quadratic/super-quadratic lower bounds for any DECIDE_k?Hrushikeshhttps://www.blogger.com/profile/11306350705226598133noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-47370053972731660032009-08-04T14:52:14.949-04:002009-08-04T14:52:14.949-04:00#2 CarpathianBlackMetal
For simplification I cons...#2 CarpathianBlackMetal<br /><br />For simplification I consider in the following that points have distinct coordinates.<br /><br />A good first step is to lower again memory usage from n^3 to n^2 while preserving the time complexity :D<br /><br />Therefore, we can compute T'(i,j) = T(i,j,0) directly as follows:<br /><br />You fill in T'(i,j) by increasing j-i.<br /><br />Assume you are trying to compute T'(i,j). There are two options:<br /><br />a) either there is a split point k<br />such that T'(i,j) = T'(i,k) + T'(k+1,j)<br /><br />b) or you have to place a rectangle R between i and j. Here's where the tricky part starts. Compute i' to be the first point after i which is outside R and j' the first point before j which is outside R.<br /><br />Now either the next step is to place a rectangle between i' and j', in which case T'(i,j) = T'(i',j') or there is some split directly above R.<br /><br />So we have to find a split "point" k such that T'(i,j) = T'(i,k) + T'(k',j). k' is the first point after k which is not contained in R.<br /><br />The intuitive reason the above works is that T'(i',j') and respectively T'(i,k), T'(k',j) do not have to cover points within R which they wouldn't cover anyway.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-89746804546958097142009-08-04T14:11:57.137-04:002009-08-04T14:11:57.137-04:00#1 CarpathianBlackMetal
Just to clarify, are you ...#1 CarpathianBlackMetal<br /><br />Just to clarify, are you assuming that all x's and all y's are different?<br /><br />To compute T(i,j,0), you suggest to "proceed exactly as above", but the "above" tells us we need to look at T(i,j,new height). I am assuming you could simply use T(i+1,j-1,height), right?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-19777470653027462262009-08-04T09:14:55.846-04:002009-08-04T09:14:55.846-04:00I had an email discussion about the cubic solution...I had an email discussion about the cubic solution, which I'm posting here for the benefit of the readers.<br /><br /><i> I thought about such a solution, but I think it is wrong.</i><br /><br />I am actually rather convinced that it is correct. I coded it up and it passes all the test cases used during CEOI, which should be good empirical validation.<br /><br /><br /><i> In your solution you define subproblem (i,j,k) of covering points m such that x_i ≤ x_m ≤ x_j and y_m ≥ H[k] where H stores the sorted y's.</i><br /><br />Correct.<br /><br /><br /><i> But you start the recurrence with (i,j,0) which is strange because those are the subcases that cover most points.</i><br /><br />I agree that it's counter-intuitive. That's why I like the algorithm :)<br /><br /><br /><i> In particular, is it trivial to test if the cost of (i,j,k+1) is equal to the cost of (i,j,k)?</i><br /><br />Yes. I know that T(i,j,k+1) ≤ T(i,j,k), because any solution covering the point for (i,j,k) also covers all points for (i,j,k+1).<br /><br />What I have to detect is the case when T(i,j,k+1) is strictly smaller<br />by 1. If it is, it means I have a new solution for (i,j,k+1) which was invalid for (i,j,k) -- otherwise, I would've used it there. How could this new solution be invalid then, but valid now? Only if it does not cover the point at height H[k]! So this new solution, if it exists, is precisely T(i,P-1,k+1) + T(P+1, j, k+1).<br /><br />To compute T(i,j,k), I keep the minimum of the two options: T(i,j,k) and T(i,P-1,k+1) + T(P+1, j, k+1).<br /><br /><br /><i> And the subproblem (0,n-1,0) is THE problem! So I do not see how to progress from smaller k to higher -- and why should I?</i><br /><br />You need to know (i,j,k) for k ≥ 1, because you are using that in the base case when drawing new rectangles. If I want to draw a rectangle from x_i to x_j, I need to know T(i+1, j-1, k) for the appropriate k (which is nonzero).<br /><br />Hope this clears things up.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.com