Number of partitions on a circle

Правка en2, от cuom1999, 2020-11-18 23:13:27

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 sub-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-linear 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский cuom1999 2020-11-19 07:22:24 17 Change to sub quadratic
en2 Английский 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 Английский cuom1999 2020-11-18 06:51:48 911 Initial revision (published)