Number of partitions on a circle
Difference between en2 and en3, changed 17 character(s)
We usually see problems like: Given an array $a_1, a_2, ..., a_n$. How many ways to partition the array into continuous groups in which each group satisfies a condition (e.g sum not exceeding a number, ...)? This kind of problem is usually done in linear or sublog-linear time with dynamic programming and prefix sum. ↵

What about changing the statement to a circular array? Formally, given a circular array $a_1, a_2, ..., a_n$. How many ways to partition the circle into continuous groups in which each group satisfies a condition? Two ways are different if there are two indices belonging to the same group in one way, but different groups in the other way. ↵

How to solve this problem in sub-
linearquadratic time in general? I find even the simplest conditions like the below are quite hard.↵

a) Each group has sum $\leq M$, with a given $M$.↵

b) Each group has $gcd > 1$.↵

...↵

Solution for problem a or b are appreciated.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English cuom1999 2020-11-19 07:22:24 17 Change to sub quadratic
en2 English cuom1999 2020-11-18 23:13:27 48 Tiny change: '1$.\n\n...' -> '1$.\n\n...\n\nSolution for problem a or b are appreciated.'
en1 English cuom1999 2020-11-18 06:51:48 911 Initial revision (published)