tag:blogger.com,1999:blog-786333285568106173.post840339675972362364..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Bijective CombinatoricsMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-786333285568106173.post-71210309446897497902008-07-12T08:15:00.000-04:002008-07-12T08:15:00.000-04:00To make your algorithm O(n), just use a linear str...To make your algorithm O(n), just use a linear structure (queue?) instead of a heap. Store an array D[1..n], where D[i] contains a list of nodes with degree i. You hold a pointer to the minimum nonempty D[i], and just increment it through this array.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-69702585180388334312008-07-12T01:32:00.000-04:002008-07-12T01:32:00.000-04:00I have an O(n log n) solution for tree decoding pr...I have an O(n log n) solution for tree decoding problem. <BR/>1. Read the initial array to find out the degree of each node (no of occurrences + 1). Create a heap with all nodes having degree 1 (leaves) ordered as per their labels.<BR/>2. Now iterate over the array from beginning. At ith step, <BR/> a. create an edge between the heap minimum and the array[i]. Delete the minimum.<BR/> b. Decrement the degree of the node with label array[i]. If this reduces the degree to 1, add it to the heap.<BR/>3. Finally add an edge between two nodes remaining in the heap at the end.<BR/><BR/>Can you outline the O(n) solution?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-446043547568544032008-01-04T01:30:00.000-05:002008-01-04T01:30:00.000-05:00Here's a solution that's easier to visualize:consi...Here's a solution that's easier to visualize:<BR/><BR/>consider an n by n grid, theres 2n choose n paths from bottom left to top right, the encoding of all such paths correspond to all n-subsets of [2n]. For any given path p, decompose it into catalan paths. The encoded integer is #of times p crosses the line y=x. Then each catalan path can be encoded as a balanced parenthesis, you simply concatenate them all into one piece.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-89495158644822003402007-08-03T13:40:00.000-04:002007-08-03T13:40:00.000-04:00@rgrig: Actually, I found the problem quite diffi...@rgrig: Actually, I found the problem quite difficult also. I cannot remember how much it took to solve it. In any case, no need to ruin your life ;)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-88256505286366088932007-08-02T17:39:00.000-04:002007-08-02T17:39:00.000-04:00The Catalan number is for n pairs of parenthesesOo...<I>The Catalan number is for n pairs of parentheses</I><BR/><BR/>Oops, fixed. Thanks!Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-47815274041759892732007-08-02T17:29:00.000-04:002007-08-02T17:29:00.000-04:00The Catalan number is for n pairs of parentheses w...The Catalan number is for <I>n</I> <B>pairs</B> of parentheses which are correctly matched.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-71380643018885820612007-08-02T16:37:00.000-04:002007-08-02T16:37:00.000-04:00I seriously consider stopping reading this blog af...I seriously consider stopping reading this blog after I spent 8h to solve Exercise 2 :) It makes me feel stupid. :)<BR/><BR/>Very brief, decoding is like this: Take the parentheses string and the number k. Identify the kth pair in the string. Swap ( and ) in that pair and in all pairs in which the kth pair is nested. then write ( as 0 and ) as 1. For example if k=2 and the string is (())() then you change to ))((() which means the subset 110001. Encoding is kind of similar.<BR/><BR/>I don't have a proof but I'll stop for today. It's late.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.com