tag:blogger.com,1999:blog-786333285568106173.post5521298146335213657..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: IOI: Another Hard ProblemMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-786333285568106173.post-63177509451749355412010-08-27T15:43:39.026-04:002010-08-27T15:43:39.026-04:00> Radu (do you want to disclose your > last ...> Radu (do you want to disclose your > last name?)<br />Heh, I assumed that logging in with my google account would be enough, guess not.<br /><br />-Radu BerindeRadu Berindehttps://www.blogger.com/profile/10064030310188011998noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-68920351318358864252010-08-24T16:38:04.855-04:002010-08-24T16:38:04.855-04:00By binary search idea + Radu idea, you obtain O(nm...By binary search idea + Radu idea, you obtain O(nm lglg n). First you do binary search O(lglg n) rounds and you find out that the answer is in some range of nm/lg n values. Then you sort those in linear time and you apply Radu idea.<br /><br />Binary search is possible because it requires finding median that takes linear time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-16275841179662421342010-08-24T16:31:50.744-04:002010-08-24T16:31:50.744-04:00Thanks!
Unfortunately, I realize now that ideas l...Thanks!<br /><br />Unfortunately, I realize now that ideas like this can't be made to work for large numbers.. this algorithm tries to do too much in that not only it finds the best segment, but it finds the sequence of segments with decreasing ("best so far") median as you go from left to right (as well as all their medians as well).<br /><br />Such an algorithm can be used to sort a set S of K numbers, with an input of size 3K+1:<br />K+1 very large numbers, the set S of K numbers, and K very small numbers.<br /><br />With W=2K+1, for position 2K+i, the <br />best segment so far is [i+1, 2K+i] and its median is the ith largest element in S.Radu Berindehttps://www.blogger.com/profile/10064030310188011998noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-1145257592821703022010-08-24T16:20:22.014-04:002010-08-24T16:20:22.014-04:00Ok, it is actually O(n + k log U), where U is the ...Ok, it is actually O(n + k log U), where U is the biggest number in our array.ilyarazhttps://www.blogger.com/profile/05104799447222642052noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-85353886613448456912010-08-24T16:19:07.618-04:002010-08-24T16:19:07.618-04:00Deterministic solution for 1-d with running time O...Deterministic solution for 1-d with running time O(n + k log n), where k is an index of minimum median in a sorted array (we do not assume that numbers are small).<br /><br />Let us do binary search on the answer. But now we will do each iteration slightly more efficient.<br />Suppose we want to check if answer is less than x. We will keep track of a list of numbers that are smaller than x. And we can perform the check in time proportional to the length of this list (sweeping two pointers). That gives us O(n + k log n).ilyarazhttps://www.blogger.com/profile/05104799447222642052noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-51327763422340520982010-08-24T16:05:22.641-04:002010-08-24T16:05:22.641-04:00Very nice. That certainly solves the problem as I ...Very nice. That certainly solves the problem as I stated it originally.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-3279887240636118192010-08-24T11:05:40.916-04:002010-08-24T11:05:40.916-04:00To be more clear.
Start on line i = H.
Maintain ...To be more clear.<br /><br />Start on line i = H.<br /><br />Maintain A[j] = # of unmarked values in cells (i-H+1,j) to (i,j).<br /><br />When marking off a value (x, y), if it i-H+1 <= x <= i, decrement A[y]; if it is also in the current square, decrement the value for the current HxW rectangle.<br /><br />We advance left to right as in the 1-d case. When we reach the right end and we have to move to the next line (i <- i+1), we just update A[j] <- A[j] - is_unmarked(i-H,j) + is_unmarked(i,j); this is O(M). Then we have read the first H values of A to get the value for the left-most rectangle, and then we can continue moving to the right when necessary.<br /><br />So O(1) per column advance and O(M+H) per line advance.<br /><br />Can't think of a way to avoid the sorting step right now, but an observation is that what we really need is not necessarily the entire sorted array, but a way to find all yet-unmarked values bigger than the current median.Radu Berindehttps://www.blogger.com/profile/10064030310188011998noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-61144592634842307062010-08-24T09:42:30.221-04:002010-08-24T09:42:30.221-04:00I realized that my solution above works in 2d too,...I realized that my solution above works in 2d too, just keep counts for the current line (no of unmarked values in the H cells above), and updare in O(M) when we need to go to the next line. Does this make sense?Radu Berindehttps://www.blogger.com/profile/10064030310188011998noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-78874796493049701842010-08-24T09:33:44.763-04:002010-08-24T09:33:44.763-04:00Radu, nice solution. I had two ways of doing O(n) ...Radu, nice solution. I had two ways of doing O(n) in 1-d, but yours is different (and I think simpler than mine).<br /><br />One feature of these discussions is that you can have fun going into side topics. (I understand that poly-math projects go into several subtopics regularly.)<br /><br />So: Let's assume the numbers are large, i.e. you don't know how to sort them in linear time. Solve the 1-d problem in O(n) time.<br /><br />ilyaraz proposed a randomized algorithm earlier. Randomization is kosher for this discussion. <br /><br />But note that I can solve the problem deterministically in linear time, even when the numbers are large. So, you can try to come up with any solution (the simplest may be randomized), and later ask for a deterministic one if the first you discovered happened to be randomized.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-10491537405950813892010-08-24T09:23:25.153-04:002010-08-24T09:23:25.153-04:00The blog entry says that the numbers are a permuta...The blog entry says that the numbers are a permutation from 1 to MN.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-46874801198859981112010-08-24T09:22:29.170-04:002010-08-24T09:22:29.170-04:00@Radu, @Mihai: ca we assume the numbers are small?...@Radu, @Mihai: ca we assume the numbers are small? this makes the problem much easier.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-63727511676119112242010-08-24T09:02:40.268-04:002010-08-24T09:02:40.268-04:00Non-randomized O(N) solution for 1-d case (uses th...Non-randomized O(N) solution for 1-d case (uses the fact that the numbers are small):<br /><br />1. Sort the values in decreasing order (using countsort).<br /><br />2. In decreasing order, mark each value as "out". Stop when there is no segment of length W with at least W/2 values not yet marked "out" (i.e. all segments have at least half of the elements marked out). The last value marked "out" before we stopped is the median.<br /><br />How to achieve this in O(N): simply keep track of the leftmost segment of width W with at least W/2 values not yet marked out (and keep track of the # of values not marked out). Whenever we mark out a value, we just check if it is in this segment or not. When the # of unmarked values in the segment falls under W/2, we advance the segment to the right one step at a time, until we find the next suitable segment (if we don't, we're done, and the last segment we kept track of is the one we're looking for). Advancing one step is trivial in O(1), and we only advance at most O(N) times throughout. <br /><br />I think this can be easily adapted for Cosmin's special case as well (we just maintain per-line counts).Radu Berindehttps://www.blogger.com/profile/10064030310188011998noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-36384312167803734942010-08-23T23:27:06.490-04:002010-08-23T23:27:06.490-04:00I do _not_ know yet. :)I do _not_ know yet. :)ilyarazhttps://www.blogger.com/profile/05104799447222642052noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-3054214123151220792010-08-23T22:22:04.250-04:002010-08-23T22:22:04.250-04:00Note that when W=N, this is a generalization of 1d...Note that when W=N, this is a generalization of 1d. How do you get O(n) in 1d?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-23782530800425602112010-08-23T21:54:16.554-04:002010-08-23T21:54:16.554-04:00Care to elaborate?Care to elaborate?ilyarazhttps://www.blogger.com/profile/05104799447222642052noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-17981512250085886722010-08-23T20:34:33.263-04:002010-08-23T20:34:33.263-04:00Another interesting special case is when W = N. I ...Another interesting special case is when W = N. I can do that in O(NM).Cosminhttp://infoarena.ro/blognoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-47357554174998228072010-08-23T13:15:45.966-04:002010-08-23T13:15:45.966-04:00This comment has been removed by the author.ilyarazhttps://www.blogger.com/profile/05104799447222642052noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-26029510071549992162010-08-23T13:15:37.760-04:002010-08-23T13:15:37.760-04:00Another algorithm for 1-d that achieves O(n log n)...Another algorithm for 1-d that achieves O(n log n) time (whp, though).<br /><br />x := n + 1;<br />l := list of all subsegments of length w;<br />while (1) {<br />if there is no element in l whose median is lower than x -- break; (we perferom this check in O(n) time)<br />pick element from l at random;<br />x := its median;<br />}ilyarazhttps://www.blogger.com/profile/05104799447222642052noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-26817163112660329102010-08-23T02:48:20.030-04:002010-08-23T02:48:20.030-04:00One interesting special case is 1-d.One interesting special case is 1-d.ilyarazhttps://www.blogger.com/profile/05104799447222642052noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-18446120257576730342010-08-23T01:01:02.245-04:002010-08-23T01:01:02.245-04:00Let's do binary search on the answer. Suppose ...Let's do binary search on the answer. Suppose we want to check if the answer is less than x. To this aim we calculate in O(nm) time for every subrectangle number of entries that are smaller than x.<br /><br />It is O(nm log nm) time, though.ilyarazhttps://www.blogger.com/profile/05104799447222642052noreply@blogger.com