Algorithm Sequence Programming Competition

[Member_16120772]

= ((x + a[1]) * (x + a[2]) * (x + a[3]) ... (x + a[k])) / d You do not know the value of d. You do not know the values for a[1] ... a[k]. You only know that each (a[i] ≥ 0) and (d > 0) and you can assume that the product in the numerator is evenly divisible by the integer value d. You can assume that the numerator can be represented by a 32-bit integer. But you know that the formula for n[x] is a polynomial function of degree k and you know the value of k+2 points for this function. Based on this information, you actually have enough information to calculate the next number n[k+3] in the sequence! This is your task. Input The first line will contain a single positive integer by itself that represents the value k. The second line will consist of (k+2) integer values separated from each other by a single space. The values on the second line represent the series n[1] through n[k+2]. The input must be read from standard input. Output The output of program should display a single integer on a line by itself representing the value for n[k+3]. The output must be written to standard output. Sample Input #1 First Line : 1 Second Line : 3 4 5 Output : 6 Sample Input #2 First Line : 2 Second Line : 1 3 6 10 Output : 15 I dont even understand why this problem is solvable when there is an unknown variable(d) and another function in the sequence(a[x]) and how to get the value of n(k+3)

[Lost User]

It's Algebra and Dynamic Programming; converging on a number. (I go blank after x number of words; so it's just a thought).

"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I

[Mircea Neacsu]

as a polynomial with unknown coefficients c[1] to c[k]:

n[x]=x^k + c[1]*x^(k-1)+c[2]*x^(k-2)...+c[k]

We know the values of this polynomial in each of the points 1, 2,...k+1 so we can write the following system of k+1 equations:

1^k + 1^(k-1)*c[1]+...+c[k] = n[1]*d
2^k + 2^(k-1)*c[1]+...+c[k] = n[2]*d
....
k^k + k^(k-1)*c[1]+...+c[k] = n[k]*d
(k+1)^k + (k+1)^(k-1)*c[1]+...+c[k] = n[k+1]*d

Reordering terms, this gives:

-n[1]*d + 1^(k-1)*c[1]+...+c[k] = -1^k
-n[2]*d + 2^(k-1)*c[1]+...+c[k] = -2^k
....
-n[k]*d + k^(k-1)*c[1]+...+c[k] = -k^k
-n[k+1]*d + (k+1)^(k-1)*c[1]+...+c[k] = -(k+1)^k

This is a system of k+1 equations with k+1 unknown that can be solved:

| d |
|c[1]|
|... | = M^-1 * V
|c[k]|

where M is the coefficients matrix:

-n[1] 1^(k-1) ... 1
-n[2] 2^(k-1) ... 1
...
-n[k+1] (k+1)^(k-1)...1

and V is the free terms vector:

-1^k
-2^k
...
-(k+1)^k

After you've calculated the coefficients finding the value of the polynomial is trivial. Here is a numerical example for the case k=2

|-1 1 1 | |-1|
M= |-4 2 1 | V= |-4|
|-6 3 1 | |-9|

= x^2+ 1*x + 0. n[4]/2 = (16+4)/2 = 10 (matching the extra equation given) and n[5]/2 = (25+5)=15 matching the suggested answer.

Mircea

[Member_16120772]

Why can we rewrite the original equation into this? n[x]=x^k + c[1]*x^(k-1)+c[2]*x^(k-2)...+c[k] Where does 'd' goes, Why does x^k until x^(k-k) and why replace a(x) with c(x). Sorry for the inconveniences, I just dont understand.

[Mircea Neacsu]

If you look at the original expression for n(x), you see that each of the values -a[i] is a root of the polynomial (because the term x+a[i] becomes 0). Now, a polynomial with k roots must be a polynomial of degree k, hence we can write it in the form n(x)= x^k + c[1]*x^(k-1) + … c[k]. Moreover, coefficients c[i] are related to roots -a[i] through Vieta's formulas - Wikipedia[^]. Looking at the original assignment, I see that I should have called the polynomial “n1(x)” and say that n(x) = n1(x)/d, or equivalent, n1(x)=n(x)*d. It doesn’t make much difference as we get to the system of equations:

n[1]*d = 1^k + 1^(k-1)*c[1]+… +c[k]
n[2]*d = 2^k + 2^(k-1)*c[2]+… +c[k]
. . .

this is the system of (k+1) equations that needs to be solved to find the values of d, c[1],… c[k]

Mircea

[Lost User]

You've been given "2 answers" in the original "question" (assuming it's not a "trick"); including inputs. You can perform 2 direct substitutions to start "converging" on the answer through insight gained.

"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I

[Justice Marc]

C++ and Java are the best languages for competitive programming. Most competitive programmers participate using C/C++. Java is the second most popular language for competitive programming. C++ and Java are the preferred languages because of STL and Java Libraries in the respective languages.Mexico Pharmacy Online | Mexico Online Pharmacy[^]