CMPLS - Complete the Sequence!

no tags 

You probably know those quizzes in Sunday magazines: given the sequence 1, 2, 3, 4, 5, what is the next number? Sometimes it is very easy to answer, sometimes it could be pretty hard. Because these "sequence problems" are very popular, ACM wants to implement them into the "Free Time" section of their new WAP portal.

ACM programmers have noticed that some of the quizzes can be solved by describing the sequence by polynomials. For example, the sequence 1, 2, 3, 4, 5 can be easily understood as a trivial polynomial. The next number is 6. But even more complex sequences, like 1, 2, 4, 7, 11, can be described by a polynomial. In this case, 1/2.n2-1/2.n+1 can be used. Note that even if the members of the sequence are integers, polynomial coefficients may be any real numbers.

Polynomial is an expression in the following form:

P(n) = aD.nD+aD-1.nD-1+...+a1.n+a0

If aD <> 0, the number D is called a degree of the polynomial. Note that constant function P(n) = C can be considered as polynomial of degree 0, and the zero function P(n) = 0 is usually defined to have degree -1.


There is a single positive integer T on the first line of input (equal to about 5000). It stands for the number of test cases to follow. Each test case consists of two lines. First line of each test case contains two integer numbers S and C separated by a single space, 1 <= S < 100, 1 <= C < 100, (S+C) <= 100. The first number, S, stands for the length of the given sequence, the second number, C is the amount of numbers you are to find to complete the sequence.

The second line of each test case contains S integer numbers X1, X2, ... XS separated by a space. These numbers form the given sequence. The sequence can always be described by a polynomial P(n) such that for every i, Xi = P(i). Among these polynomials, we can find the polynomial Pmin with the lowest possible degree. This polynomial should be used for completing the sequence.


For every test case, your program must print a single line containing C integer numbers, separated by a space. These numbers are the values completing the sequence according to the polynomial of the lowest possible degree. In other words, you are to print values Pmin(S+1), Pmin(S+2), .... Pmin(S+C).

It is guaranteed that the results Pmin(S+i) will be non-negative and will fit into the standard integer type.


Sample Input:

6 3
1 2 3 4 5 6
8 2
1 2 4 7 11 16 22 29
10 2
1 1 1 1 1 1 1 1 1 2
1 10

Sample Output:

7 8 9
37 46
11 56
3 3 3 3 3 3 3 3 3 3
Warning: large Input/Output data, be careful with certain languages

hide comments
simbha: 2017-09-22 01:21:53

The solution works fine for O(n^2) time complexity! Feeling happy after One go AC!

fluked: 2017-08-20 01:47:12

You copied this off Hackerrank, or someone copied you.

azazello_: 2017-06-28 17:39:41

Tip for beginners such as me:
(1) This is an accessible problem once you understand what algorithm you should work at implementing.
(2) Think about how you would use a Difference Table to find the next element in a sequence (many people below use the term Difference Method, but when I googled that I got information that wasn't related to this problem)
(3) The problem only discusses polynomial sequences (which are solved with the Difference Table)
1 2 4 8 is followed by 15 and not by 16 (2^x is not a polynomial sequence).

I'm not even sure if the whole problem is mathematically correct, but using that table is a nice exercise.

horizon121: 2017-05-25 16:28:57

Just use forward diff table and dont try any GP or other series..they dont fall in this category(gave me WA and then checked it out)

Bo MA: 2017-04-18 07:33:33

Beware the corner case of s=1.
Switching case #2 and case #3 may help uncover subtle issues.

Last edit: 2017-04-18 07:34:43
dangerous321: 2017-04-04 13:05:58

Parikshit how did you got the answer for 3rd case

dangerous321: 2017-04-04 12:31:08

How is the third case possible using difference method

manii_bisht: 2017-03-25 06:48:06

felt nice after making it in one go.

Vladimir Tsibrov: 2017-01-19 09:27:16

@flyingduchman_ now original array, a[n] = a[n-1]+a1[n-2] is expanded.
- why [n-2]? should be a[n] = a[n-1]+a1[n-1]

flyingduchman_: 2016-11-19 19:52:36

Use difference method.
Algo: given array a of size n, on first step make an array a1 of size n-1 by the keeping the difference of two adjacent element of given array a. Like:a1[0] = a[1]-a[0] .....
a1[n-2] = a[n-1]-a[n-2]. Say array a1 as first row of difference table. Keep making rows until all elements in a row are same or there are only one element in a row.
so make a2, a3 .... until all elements become same or have only one element left. Now it's time to stop and expand those rows in a bottom-up manner. Let you made a table of size k = 3, a1(n-1 elements), a2(n-2 elements), a3(n-3 elements).
Now expand the last row of the difference table by "c" elements, with same elments or the remaining one.Here a3 will be expanded with "c" elements. Now you can expand the last element of a2[n-1](new expanded element) = a2[n-2]+a3[n-2](extended by constant difference), here array index starts from 0.
similarly, a1[n-1] = a1[n-2]+a2[n-3]
now original array, a[n] = a[n-1]+a1[n-2] is expanded.
If you repeat the bottom-up procedure "c" times, original array will be expanded by c number of elements. You can use "std vector" in c++

Last edit: 2016-11-19 19:56:49

Added by:adrian
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:ACM Central European Programming Contest, Prague 2000