POLTOPOL - Polynomial f(x) to Polynomial h(x)

no tags 

Given polynomial of degree d, f(x)=c0+c1x+c2x2+c3x3+...+cdxd

For each polynomial f(x) there exists polynomial g(x) such that:

-> f(x)=g(x)-g(x-1) for each integer x

-> g(0)=0

Your task is to calculate polynomial h(x)=g(x)/x

(Note : degree of polynomial h(x) = degree of polynomial f(x))


The first line of input contain an integer T, T is number of test cases (0<T≤104)

Each test case consist of 2 lines:

- First line of the test case contain an integer d, d is degree of polynomial f(x) (0≤d≤18)

- Next line contains d+1 integers c0,c1,...,cd, separated by space, represent the coefficient of polynomial f(x) (-231<c0,c1,...,cd<231 and cd≠0)


For each test case, output the coefficient of polynomial h(x) separated by space. Each coefficient of polynomial h(x) is guaranteed to be an integer.


-1 2
0 2
2 -5 9
23 9 21 104

0 1
1 1
1 2 3
31 41 59 26

Explanation for the first test case :
g(x) that satisfy: g(x)-g(x-1)=f(x)=13 and g(0)=0 is: g(x)=13x
h(x)=g(x)/x so h(x)=13
output : 13
Explanation for the second test case :
g(x) that satisfy: g(x)-g(x-1)=f(x)=-1+2x and g(0)=0 is: g(x)=x2
h(x)=g(x)/x so h(x)=x=0+1x
output : 0 1
Explanation for the third test case :
g(x) that satisfy: g(x)-g(x-1)=f(x)=2x and g(0)=0 is: g(x)=x+x2
h(x)=g(x)/x so h(x)=1+1x
output : 1 1


See also: Another problem added by Tjandra Satria Gunawan

hide comments
Francky: 2014-12-10 07:44:23

That's fine, it's now challenging with Python language.

Welcome to Tjandra as EB. Congratulations. Nice job for your new bot ; you always have good ideas.

(Tjandra Satria Gunawan)(曾毅昆): 2014-12-10 02:54:21

I can't increase the test case because for T=10^4 the file IO size is already ~1.32MB, it's large because for each test case has at most 19 32-bit numbers, so if I increase number of testcase to 10^5 theoritically the file IO will be ~13.2MB. So I decided to just rejudge this problem. This problem isn't challenging for speed anymore since the cluster changed to cube. Sorry for the inconvenience.

(Tjandra Satria Gunawan)(曾毅昆): 2014-11-23 12:11:26

@Francky: Done, I forgot to check "Include All Languages" when I publish this problem long time ago. Thanks for reminding me :-)

--ans--> Thanks, it seems cluster is now cube (and before Pyramid, isn't it ?) ans that solutions hadn't been rejudged yet. Maybe you could set new time limit to 3s... (?) as you want ; before this hypothetical rejudge. Or better, add another input file with more data (increase T to 10^5, but not d_max). What do you think about that?

Ans(Tjandra): I changed time limit to 3s for now. I'll upload more test case and rejudge later (probably next week), now I'm not in my home city.

Last edit: 2014-11-23 13:44:01
Francky: 2014-11-23 12:08:02

@tjandra : please open to all languages, I think at PY3.4 ;-)

(Tjandra Satria Gunawan)(曾毅昆): 2014-11-23 12:08:02

@Francky: As I said before, your new code doesn't handle negative output..
But I still don't know why your assertion is pass (AC), I'm curious too why python assertion fail..
But this is the fact, my output test data contains many negative number..
--ans(Francky)--> OK, so it's a spoj bug or feature on assert, I tried a division by 0 instead and can see the red light. Thanks for your patience with me. I have at last my green light in C, and I'll try the 0.06s !!! (edit, done ;-)

Last edit: 2014-02-28 20:11:25
Francky: 2014-11-23 12:08:02

I still waiting for a counter example if you can. I'm unable to found one between my AC one and my WA one ???? Thanks in advance.

Francky: 2014-11-23 12:08:02

Hi Tjandra, thanks for your reply, but if you take a look at #11069295 AC submission, you will see that I'm still very curious about the reason of my WA.
Ans: Try this: assert ((0<=Q[i]) and (Q[i]<2**31-1))
--ans(Francky)--> Done, I'm still very curious ;-)
Ans: Now you make me curious too :-P Ok, I'll tell you when I know why.

Last edit: 2014-02-16 21:41:34
Francky: 2014-11-23 12:08:02

Hi Tjandra, I've yet an AC in Py2.7, but I can't understand why my new py3 code fail. I've compared over 10^5 polynomials my two near solutions, and they match.
Please test my sub_10998183. Thanks. I'm very curious about that.
Ans: It's simple, you forgot to handle negative output :) I recommend test your code on ideone, because the engine is same with SPOJ.

Last edit: 2014-02-09 22:52:39
sarelfeniel: 2014-11-23 12:08:02

Awesome problem. Experimented with many ways to solve it but am content with top 5.

Shashi Kant Prasad: 2014-11-23 12:08:02

Mine: O(d²)

Added by:Tjandra Satria Gunawan
Time limit:3s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Own Problem