tag:blogger.com,1999:blog-6555947.post6912832700702012..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: A counting gemSuresh Venkatasubramanianhttps://plus.google.com/112165457714968997350noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-6555947.post-27906334964303439352007-08-13T10:24:00.000-06:002007-08-13T10:24:00.000-06:00So I should have clarified: the first comment is i...So I should have clarified: the first comment is indeed the correct solution, and this can be generalized using k counters to get an element of frequency more than n/k.Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-15608456813581879162007-08-13T10:01:00.000-06:002007-08-13T10:01:00.000-06:00Okay, the following algorithm in Python code worke...Okay, the following algorithm in Python code worked for me, it is similar to the first comment but not exactly.<BR/><BR/>An interesting variation on the algorithm is for a given proportion of maxima occurences (not 50+% but say 30+%), can you change the code with the same algorithm and make it work? [If it can be done then would it involve another computing a cnt comparision (instead of 0) to make it work]<BR/><BR/># Pre tags not allowed in Blogger comments, so view source to copy the indented code.<BR/>import random<BR/><BR/>def maxima (rng):<BR/> """Find the element with over 50% population occurence in range."""<BR/> max = rng[0]<BR/> cnt = 0<BR/> for e in rng[1:]:<BR/> print max, e, cnt,<BR/> if e == max: cnt += 1<BR/> else: cnt -= 1<BR/><BR/> if cnt <= 0:<BR/> max = e<BR/> cnt = 0<BR/> print " -> ", max, e, cnt<BR/> if cnt > 0: return max<BR/><BR/>def populate (rng):<BR/> idx = range(len(rng))<BR/> while len(idx) > len (rng)/2 - 1:<BR/> x = random.randint(0,len(idx)-1)<BR/> rng[idx[x]] = random.randint(1,10)<BR/> del idx[x]<BR/> max = random.randint(1,10)<BR/> for x in idx:<BR/> rng[x] = max<BR/><BR/>rng = [None for i in xrange(100)]<BR/>populate (rng)<BR/>print maxima (rng), rngAlokhttp://www.blogger.com/profile/00541962357236077809noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-62939416910469754682007-08-12T06:23:00.000-06:002007-08-12T06:23:00.000-06:00I am curious about your elegant solution. Would yo...I am curious about your elegant solution. Would you be kind enough to post it, if it is different from the first comment?Alokhttp://www.blogger.com/profile/00541962357236077809noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-10869633779242565462007-08-03T05:47:00.000-06:002007-08-03T05:47:00.000-06:00BTW, a generalized version of this trick was also ...BTW, a generalized version of this trick <BR/>was also used in "serious" research. <BR/><BR/>For instance, <BR/><BR/>http://www.cs.berkeley.edu/~christos/iceberg.ps<BR/><BR/><BR/>YakovAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-28529553793295902442007-07-30T17:16:00.000-06:002007-07-30T17:16:00.000-06:00This used to be a classic at informatics olympiads...<I>This used to be a classic at informatics olympiads (I think I first saw it around 5th grade). Oh, the days... :)</I><BR/><BR/>Here is a different version of the problem:<BR/><BR/><A HREF="http://www.oi.edu.pl/php/show.php?ac=e181300&module=show&file=zadania/oi7/lollobr" REL="nofollow">http://www.oi.edu.pl/php/show.php?ac=e181300&module=show&file=zadania/oi7/lollobr</A>krzysztofhttp://www.blogger.com/profile/08079769483555884795noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-48765437597982620132007-07-29T15:04:00.000-06:002007-07-29T15:04:00.000-06:00We can slide a window of 3 the n+1 times repeating...We can slide a window of 3 the n+1 times repeating element will appear twice in atleast one of the 2n-3+1 windows.<BR/><BR/>This will work if all the other elements are distinct.vamsihttp://www.blogger.com/profile/06920946350286969217noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-71804362926827480342007-07-28T15:13:00.000-06:002007-07-28T15:13:00.000-06:00MindHacks just recommended this interview on how t...MindHacks just recommended this interview on how to build a Cognitive Reserve and, who knows, probably solving all these puzzles help us...<BR/><BR/>http://www.sharpbrains.com/blog/2007/07/23/build-your-cognitive-reserve-yaakov-stern/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-63594474137621151372007-07-28T04:06:00.000-06:002007-07-28T04:06:00.000-06:00"Given 2n items, determine whether a majority elem..."Given 2n items, determine whether a majority element (one occuring n+1 times) exists." OK, so it is a yes/no question.<BR/><BR/>Then there is the following piece of information: "you are promised that such an element exists."<BR/><BR/>OK, so I can solve this problem with zero units of storage area, and without inspecting the data at all: I just answer "YES" immediately.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-4161010584048995582007-07-26T17:11:00.000-06:002007-07-26T17:11:00.000-06:00Definition of "unit of workable storage" (whether ...Definition of "unit of workable storage" (whether it can store a value or number 0-n) would have been good... My solution uses one unit of each of those two types.Andrishttp://www.math.uwaterloo.canoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-6567699781272485212007-07-26T15:56:00.000-06:002007-07-26T15:56:00.000-06:00A variation: now the sequence contains both arriva...A variation: now the sequence contains both arrival and departures of items: an arrival means that the count of the item increases by one, a departure means that it decreases by one. Assume (promise) that the net count of an item never dips below zero. <BR/><BR/>a) Again with the promise that a majority item exists, how much space is needed to find it? <BR/>b) Still using two units of working storage, determine whether there exists only a single item with non-zero count, and if so, return the item and its count.<BR/><BR/>GrahamAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-64724139434809423412007-07-26T14:23:00.000-06:002007-07-26T14:23:00.000-06:00This used to be a classic at informatics olympiads...This used to be a classic at informatics olympiads (I think I first saw it around 5th grade). Oh, the days... :)<BR/><BR/>-mipMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-35241997188465991202007-07-26T12:33:00.000-06:002007-07-26T12:33:00.000-06:00Keep a count and store current value.Pass over arr...Keep a count and store current value.<BR/><BR/>Pass over array, if you see the current stored value, inc count. Else decrement. If count reaches 0, replace the stored value with the current value in array.<BR/><BR/>In the end, you will end up with the right value.Anonymousnoreply@blogger.com