wu :: forums « wu :: forums - Find i such that S and (S+i) is maximal » Welcome, Guest. Please Login or Register. May 18th, 2024, 5:56pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: towr, SMQ, Grimbal, william wu, ThudnBlunder, Eigenray, Icarus)    Find i such that S and (S+i) is maximal « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Find i such that S and (S+i) is maximal  (Read 636 times) cuckoo Junior Member     Gender: Posts: 57 Find i such that S and (S+i) is maximal   « on: Oct 21st, 2007, 8:12pm » Quote Modify S is a set of integers. S+i={ x+i | x \in S}. Find an integer such that [ S AND (S+i) ] has maximual number of elements. AND represent set intersection.   Can this problem be solved in less than O(n^2) time? (n=|S|) IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Find i such that S and (S+i) is maximal   « Reply #1 on: Oct 22nd, 2007, 2:25am » Quote Modify You want the maximal intersection? Why not pick i=0?   If you want an i>0, I think you can still do better than O(n2). Maybe use string matching techniques, or something like a convolution (using FFT-like techniques). IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board