Sunflowers
I drew spiral sunflowers (think i*a mod n for various i) this morning thinking of a problem that led me to formulate the following:
Given a partition of integers [0,n-1] into 2 lists A and B, check if for each i in A, for all j for which i+j mod n is in B, we have that i-j mod n is in A.
A subquadratic algorithm will be a start.
Given a partition of integers [0,n-1] into 2 lists A and B, check if for each i in A, for all j for which i+j mod n is in B, we have that i-j mod n is in A.
A subquadratic algorithm will be a start.
posted by metoo at 11:16 AM
2 Comments:
I interpret your condition as saying "BAB" is a forbidden arithmetic subsequence, where the first and last B may be the same item. Then I think B must be either the empty set, or a translate of {0, d, 2d, ...}, where d is an odd divisor of n.
For example if n=18, the only possible B sets are them empty set, the 9 translates of {0, 9}, the 3 translates of {0, 3, 6, 9, 12, 15}, and the whole set.
That should be linear time testable.
What a great site, how do you build such a cool site, its excellent.
»
Post a Comment
<< Home