ndatta's blog

Help needed for UVa 12143 — Stopping Doom's Day
By ndatta, history, 8 years ago, In English

Problem link: https://uva.onlinejudge.org/external/121/p12143.pdf

I got a solution here : http://mypaper.pchome.com.tw/zerojudge/post/1325083499

But I failed to understand how the problem is reduced to gaussian elimination. Can anybody explain please? If there are any other ideas please feel free to share.

Thanks for you help.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Here's my understanding of the solution provided in your link:

A sufficiently 'nice' sum that depends only on N will be a polynomial on N. I don't have a definition of 'nice' or a proof that this sum is 'nice', but several examples should convince you of this — or or .

Furthermore, the degree of the polynomial should be 10. We're multiplying five terms and summing over five variables. Again, take a look at the above examples — the third one should be a degree-three polynomial in N, as we are multiplying one term and summing over two variables.

Unfortunately, we don't know the coefficients of this magical 10th degree polynomial. However, we can find them if we have 10 linear equations in terms of these coefficients. Let P(N) = c10x10 + ... + c1x + c0. Then our desired equations are P(Ni) = c10(Ni)10 + ... + c1Ni + c0 for 10 different Ni, where P(Ni) must be calculated manually or with a slow program.

Finally, we put these equations into an augmented matrix and use Gaussian elimination to solve for the 'variables', which are the 10 coefficients ci. Now we simply evaluate P(N) for each given N.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your explanation. It seems helpful :)

    → Reply