tag:blogger.com,1999:blog-6555947.post111729512527688499..comments2019-11-29T22:41:04.161-07:00Comments on The Geomblog: A Paltry Plethora of Permutation PuzzlesSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-6555947.post-1117553953182532022005-05-31T09:39:00.000-06:002005-05-31T09:39:00.000-06:00Re: Sariel's post. My bad. I revert to parametri...Re: Sariel's post. My bad. I revert to parametric search. Thanks.  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117547755318865332005-05-31T07:55:00.000-06:002005-05-31T07:55:00.000-06:00Anon3:I don't follow your comment on Sariel's post...Anon3:<BR/><BR/>I don't follow your comment on Sariel's post. <BR/>Suppose<BR/>A: 10 9 5 4<BR/>B: 3 2 0 0 <BR/><BR/>Then your alg would pick all of A and none of B (I think). How does this then generate large sums a+b? Note that the optimal solution to this instance is to pick 10,9 from A and 3,2 from B, and generate<BR/>13, 12, 12, 11<BR/><BR/>Graham <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>Graham CormodeAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117475029925517392005-05-30T11:43:00.000-06:002005-05-30T11:43:00.000-06:00Since you linked to it, I have to ask: Was Sariel...Since you linked to it, I have to ask: Was Sariel's post about the google job question a joke? I admit that after reading the question, my first instinct was to resort to parametric search. And I remember thinking, "What kind of sadist asks a question like this for a job-interview question?" Then, after letting it soak in, I figured that a simple merge of the two arrays A and B in sorted order (with a notation added to each element so that we can recognize whether an element is from A or B), followed by a check to see when a "switch" occurs, (e.g., we have a transition from set A to set B) in the merged ordering should do the job. What was Sariel thinking?<BR/><BR/> <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117469762864105292005-05-30T10:16:00.000-06:002005-05-30T10:16:00.000-06:00I will leave the linear reversal algorithm as an "...I will leave the linear reversal algorithm as an "exercise for the<BR/>reader" ... ;-)<BR/><BR/>If you dont notice that trick though, it is a pretty annoying<BR/>little problem <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2005/05/paltry-plethora-of-permutation-puzzles.html#comments" REL="nofollow" TITLE="mathmarc at gmail dot com">Marc</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117464231328864182005-05-30T08:43:00.000-06:002005-05-30T08:43:00.000-06:00Nice comments so far. Anon1. The bit fiddling ope...Nice comments so far. <BR/><BR/>Anon1. The bit fiddling operations are a little hard to read, but it looks like you are using them to do a cyclic shift of 1, then doing this k times over. Overall this has a cost of O(kn) not O(n) as desired. But I think your approach could be modified to run in a single pass. There are solutions with the same cost that don't do any bit operations (just copying/replacing entries) which might be a bit easier to read. These also require a nice little fact about the cyclic permutation being performed. <BR/><BR/>Marc. That's correct. For full credit, you'd need to specify how to do the reversals in linear time (not difficult, but a necessary step). <BR/><BR/>Anon2: Right argument, but I think your arithmetic is a bit off: the values subtracted are {0,1,2,..2n-1} which is a permutation, so summing the differences yields 0 mod 2n-1. Full credit for method, but less than full credit for working. <BR/><BR/>cheers<BR/>Graham <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>Graham CormodeAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117428707326664122005-05-29T22:51:00.000-06:002005-05-29T22:51:00.000-06:00The third one is nice, but has a simple solution: ...The third one is nice, but has a simple solution: in any permutation of {0, ..., 2n-1}, the sum of the elements must always be the same (mod 2n). To possibly yield a permutation, this implies that the sum of the shifts must be 0 mod 2n. But:<BR/>0 + (-1) + (-2) + ... + (-2n+1) = - (2n+1)/2 * 2n <BR/> = - n (2n+1) <BR/>which is non-zero modulo 2n.<BR/><BR/>On the other hand, taking permutations on an odd number of elements we see that the sum of the shifts is:<BR/>0 + (-1) + ... + (-2n+2) = - (n-1)(2n-1)<BR/>which is zero modulo 2n-1. At least in principle, then, it is possible to obtain another permutation when dealing with an odd number of elements.  <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117417697258850672005-05-29T19:48:00.000-06:002005-05-29T19:48:00.000-06:00I was actually asked #2 at an interview. Part A w...I was actually asked #2 at an interview. Part A was reverse the elements in an string. part B) was to perform the reversal as stated above. Luckily, I happened upon the trick for (B). <BR/><BR/><BR/>*********************<BR/><BR/>solution to b:<BR/><BR/>reverse entire string so "abc def" -> "fed cba"<BR/>then reverse each word so "fed cba -> "def abc"<BR/> <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A><A HREF="http://geomblog.blogspot.com/2005/05/paltry-plethora-of-permutation-puzzles.html#comments" REL="nofollow" TITLE="mathmarc at gmail dot com">marc</A>Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-1117394354882871772005-05-29T13:19:00.000-06:002005-05-29T13:19:00.000-06:00Solution for Problem 1. I think that this satisfi...Solution for Problem 1. I think that this satisfies your constraints.<BR/><BR/><BR/>int shifter(valarray int & vec, int k)<BR/>{<BR/> if (vec.size() == 0 || k < 0)<BR/> return -1;<BR/><BR/> if (k % vec.size() == 0)<BR/> return 0;<BR/><BR/> int tmp;<BR/><BR/> for (int s = 0; s < k; s++) {<BR/> tmp = vec[1];<BR/> vec[1] = vec[0];<BR/> for (int index = 2; index < vec.size(); index ++) {<BR/> tmp ^= vec[index];<BR/> vec[index] ^= tmp;<BR/> tmp ^= vec[index];<BR/> }<BR/> vec[0] = tmp;<BR/> }<BR/><BR/> return 0;<BR/>}<BR/> <BR/><BR/><A></A><A></A>Posted by<A><B> </B></A>AnonymousAnonymousnoreply@blogger.com