AGENTS - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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:

Setter’s solution
Tester’s solution

1 Like

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

1 Like

The link to the solutions are not working.

Yeah…the links to the solution files are not working.