You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 20 Apr '15, 00:56

mogers's gravatar image

5★mogers
639416
accept rate: 25%

edited 11 Feb '16, 18:04

admin's gravatar image

0★admin ♦♦
14.9k347484503


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

link

answered 20 Apr '15, 07:58

achaitanyasai's gravatar image

5★achaitanyasai
2.2k61746
accept rate: 10%

edited 20 Apr '15, 07:59

The link to the solutions are not working.

link

answered 22 May '15, 06:23

aadil_ahmad's gravatar image

4★aadil_ahmad
186
accept rate: 0%

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

link

answered 22 May '15, 10:51

omkalam007's gravatar image

0★omkalam007
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Tags:

×10,459
×727
×338
×62
×2
×1

Asked: 20 Apr '15, 00:56

Seen: 1,399 times

Last updated: 11 Feb '16, 18:04