×

# AGENTS - Editorial

Author: Konstantsin Sokol
Tester: Gedi Zheng
Editorialist: Miguel Oliveira

Hard.

# PREREQUISITES:

Math, Linear Algebra.

# PROBLEM

Given 2 polynomials Q and T, find a polynomial P such that $P(x) = Q(x) + \int_0^1 T(x \cdot s) P(s) ds$ holds for every real $x$.

# EXPLANATION

We are given polynomials Q and T, and the formula $P(x) = Q(x) + \int_0^1 T(x \cdot s) P(s) ds$.

$Q(x) = \sum\limits_{k=0}^n q_k x^k$ and $T(x \cdot s) = \sum\limits_{k=0}^m t_k \cdot x^k \cdot s^k$

Thus, $P(x) = Q(x) + \int_0^1 T(x \cdot s) P(s) ds = \sum\limits_{k=0}^n q_k x^k + \int_0^1 (\sum\limits_{k=0}^m t_k \cdot x^k \cdot s^k) P(s) ds$

$P(x) = \sum\limits_{k=0}^n q_k * x^k + \sum\limits_{k=0}^m t_k \cdot x^k * (\int_0^1 s^k P(s) ds)$

Notice that $\int_0^1 s^k P(s) ds$ is a constant for each $x$. Let's call this $c_x$. Then, $P(x) = \sum\limits_{k=0}^n q_k x^k + \sum\limits_{k=0}^m t_k x^k \cdot c_x$

Now we are interested in finding all $c_1, c_2, ..., c_m$.

$c_i = \int_0^1 s^i P(s) ds = \int_0^1 s^i (\sum\limits_{k=0}^n q_k s^k + \sum\limits_{k=0}^m t_k s^k \cdot c_x) ds$

$c_i = \sum\limits_{k=0}^n q_k \cdot \int_0^1 s^{k+i} ds + \sum\limits_{k=0}^m c_k \cdot t_k \int_0^1 s^{k+i} ds$, note that $\int_0^1 s^{k+i} ds = \frac{1}{k+i+1}$

Then we have $c_i = \sum\limits_{k=0}^n q_k \cdot \frac{1}{k+i+1} + \sum\limits_{k=0}^m c_k \cdot \frac{t_k}{k+i+1}$

Thus, we have $m$ equations and $m$ variables. We can build a system of equations and use the gaussian elimination method to solve the system and calculate the coefficients.

Time Complexity

Building the system of equations will take O(N) time and the gauss elimination O(M^3), thus giving O(N + M^3) total time.

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

5★mogers
649516
accept rate: 25%

19.0k348495531

 1 Hello I think solving this problem in python is quite easy : I have figured out the general equation as shown above And I know that there is a module available to solve system of linear equations. And so I directly used that, Here is my solution : http://www.codechef.com/viewsolution/6799925 answered 20 Apr '15, 07:58 2.2k●6●17●47 accept rate: 10%
 0 The link to the solutions are not working. answered 22 May '15, 06:23 28●6 accept rate: 0%
 0 Yeah...the links to the solution files are not working. answered 22 May '15, 10:51 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,366
×1,206
×727
×62
×9
×2

question asked: 20 Apr '15, 00:56

question was seen: 1,634 times

last updated: 11 Feb '16, 18:04