tag:blogger.com,1999:blog-786333285568106173.post7482409838640681014..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: International Olympiad, Day 1Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-786333285568106173.post-89535933433830053012011-08-01T05:15:43.245-04:002011-08-01T05:15:43.245-04:00Queries in the first problem can be answered in O(...Queries in the first problem can be answered in O( log N ).<br /><br />After making the cycle graph there are at most two important nodes ( let's call them P and P' ). For each node you can easily calculate the distance from P and P', these being d( P ) and d( P' ) respectively.<br /><br />Now let count( n, k ) equal the number of nodes leading to n in exactly k steps. Our solution becomes count( P, k ) + count( P', k ).<br /><br />We can assume in count( n, k ) that n is a part of a cycle, as it is trivial to calculate if it were not. So let len( n ) be the length of the cycle containing n.<br /><br />Now you can precompute ( for P and P' ) some vectors... Let v[0][x] be the vector of distances from P that give x modulo len( P ), and v[1][x] the same vector for P'.<br /><br />Now let's say we're given a distance k, and that m0 = ( k mod len( P ) ).<br />We're looking for all the nodes whose distances give m0 modulo len( P ), but are also greater than or equal to k.<br /><br />This is easily done by a binary search on the vector v[0][m0]...<br /><br />I coded this during the contest cause I didn't see that the number of queries is equal to 2000 in the largest subtask...<br /><br />I should also mention that a similar complexity can be achieved for queries where P changes too, so the problem had a much bigger potential :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-39196020343359018672011-07-25T23:30:12.586-04:002011-07-25T23:30:12.586-04:00The third problem:
For a given set of k points the...The third problem:<br />For a given set of k points the point that minimises the set of distances to it is at k/2 or k/2 + 1.<br /><br />So you can do a solution that involves 2 moving pointers, where the first pointer i goes through each point and the second pointer is the rightmost point j for which the x[i..j] has a valid cost.<br /><br />BTW I've heard the problem of finding a downwards path in a tree of sum S from a Microsoft interview last year, so at least that subproblem is pretty well known.loser2007https://www.blogger.com/profile/11530937349997805374noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-74617943085038634292011-07-25T22:01:11.023-04:002011-07-25T22:01:11.023-04:00Very nice, Anon!
A small variation on your Solut...Very nice, Anon! <br /><br />A small variation on your Solution #1 gets O(nlg k + m), which is enough for full score in the IOI.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-11877903396680360472011-07-25T19:46:21.190-04:002011-07-25T19:46:21.190-04:00I agree.
Now the first problem. For each directed...I agree.<br /><br />Now the first problem. For each directed edge e compute the next edge in the walk after edge e, Next[0][e].<br /><br />The super simple solution:<br />For each i between 1 and the greatest power of 2 less than or equal to k, compute Next[i][e] = Next[i-1][Next[i-1][e]]. Now it's easy to compute in O(log k) time the kth edge in the walk assuming we start at a edge e. We compute this for the first edge in the walk that starts at every given vertex and verify if the final vertex is the target node. Running time O((n+m) log k).<br /><br />The better solution:<br />Look at the directed graph where vertices are the edges of the initial graph, and edges consist of pairs (Next[0][e], e). Since all "vertices" have in-degree 1, our graph looks like a set of cycles with trees attached to them. <br /><br />Each starting vertex corresponds to a single "vertex" in our new graph since that's the first edge on the walk starting at that vertex. For each possible ending vertex (a directed edge uv in the initial graph, where v is the target node) we want to see which starting vertices can be reached in k-1 steps. Due to the structure of our graph, this can only be done by first covering for a number of times the cycle that this ending vertex is part of (which may consist of 0 edges), and then going straight to the desired starting vertex. This will then require x*length_of_cycle_containing_ending_vertex + length_of_path_from_ending_vertex_to_starting_vertex, for any nonnegative integer x. We can compute the length of the cycle and the distances to all other vertices in O(m) time with a breadth first search.<br /><br />So the problem reduces to solving an equation of the form ax+b=k-1 for every possible starting vertex.<br /><br />But there are several possible ending vertices. Again, looking at the structure, we see that there can be at most a constant number of such vertices per cycle, so the total running time is linear.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-44663868922742185702011-07-25T18:47:47.993-04:002011-07-25T18:47:47.993-04:00Anon, thanks for pointing this out. I still think...Anon, thanks for pointing this out. I still think Anton gets the kudos since the idea is essentially the same.<br /><br />I just wish to point out, as an addendum to what Anton said, that no hashtable is necessary, just counting sort and merging.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-25665826875123875682011-07-25T17:07:04.770-04:002011-07-25T17:07:04.770-04:00I just want to add a minor detail, that is one can...I just want to add a minor detail, that is one can not necessarily partition the tree into two balanced trees by removing an edge (imagine a tree with a vertex of degree n-1 and all other nodes of degree 1). You can do this by removing a vertex, but then you may have consider more than 2 subtrees where your two paths may be coming from.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-44637442023029746582011-07-25T16:41:03.240-04:002011-07-25T16:41:03.240-04:00Eternal glory goes to Anton Anastasov. Congrats! :...Eternal glory goes to Anton Anastasov. Congrats! :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-20548960939283489332011-07-25T16:28:36.206-04:002011-07-25T16:28:36.206-04:00Take some edge e, with endpoints a and b; the desi...Take some edge <i>e</i>, with endpoints <i>a</i> and <i>b</i>; the desired path either passes through that edge (in which case we need one path rooted at <i>a</i> and one rooted at <i>b</i> such that their length is exactly X - len(e) (*)) or doesn't pass through <i>e</i> (in which case we can solve the problem recursively for the 2 trees that are left, when <i>e</i> is removed).<br /><br />(*) This is essentially checking whether there are indices i and j, such that A[i] + B[j] = const, which can be solved in O(N) with hashtable.<br /><br />Choosing such an edge <i>e</i> that separates the the tree into two trees of almost equal sizes leads to O(N log N) divide and conquer solution.Anton Anastasovhttps://www.blogger.com/profile/12161792614984169686noreply@blogger.com