Hi everyone,↵
↵
today, I am stuck with a problem. I hope you can help me with it. I think this is a very interesting problem and I am not even sure there exists a deterministic solution to it. The problem is as follows:↵
↵
"↵
Given n (n <= 1000, but O(n^3) is also fine) distinct integers, group them into sets of at least 4 elements, and each set is an Arithmetic Sequences. ↵
"↵
↵
Example: ↵
↵
Input: 1250, 3748, 6246, 8744, 2493, 4993, 7493, 9993, 2497, 4996, 7495, 9994, 2498, 4997, 7496, 9995, 2499, 4998, 7497, 9996↵
↵
Output:↵
(1250, 3748, 6246, 8744),↵
(2493, 4993, 7493, 9993),↵
(2497, 4996, 7495, 9994),↵
(2498, 4997, 7496, 9995),↵
(2499, 4998, 7497, 9996)↵
↵
In this test, if you find the longest sequence first, then the rest will not form any valid sequence anymore.↵
↵
↵
(Assumption: For the given input, there always exists at least one solution that satisfies the constraints and no number is left)↵
↵
I have spent hours working on this problem but unfortunately I cannot think of any ideas that will work well in general. What do you think?↵
↵
Thank you.
↵
today, I am stuck with a problem. I hope you can help me with it. I think this is a very interesting problem and I am not even sure there exists a deterministic solution to it. The problem is as follows:↵
↵
"↵
Given n (n <= 1000, but O(n^3) is also fine) distinct integers, group them into sets of at least 4 elements, and each set is an Arithmetic Sequences. ↵
"↵
↵
Example: ↵
↵
Input: 1250, 3748, 6246, 8744, 2493, 4993, 7493, 9993, 2497, 4996, 7495, 9994, 2498, 4997, 7496, 9995, 2499, 4998, 7497, 9996↵
↵
Output:↵
(1250, 3748, 6246, 8744),↵
(2493, 4993, 7493, 9993),↵
(2497, 4996, 7495, 9994),↵
(2498, 4997, 7496, 9995),↵
(2499, 4998, 7497, 9996)↵
↵
In this test, if you find the longest sequence first, then the rest will not form any valid sequence anymore.↵
↵
↵
(Assumption: For the given input, there always exists at least one solution that satisfies the constraints and no number is left)↵
↵
I have spent hours working on this problem but unfortunately I cannot think of any ideas that will work well in general. What do you think?↵
↵
Thank you.