11319 - Stupid Sequence

All about problems in Volume CXIII. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

11319 - Stupid Sequence

I solved the problem using consecutive differences and detecting when the difference becomes constant. The method works correctly for small enough inputs, including the examples given and some sequences I generated. However, with larger numbers the differences are no longer computed correctly, and they appear not to be constant when they actually are. As a result, the program reports that the sequence is smart when it is not.

I guess it is some king of overflow - for bigger numbers the differences appear larger than they are. I am using unsigned long long to accommodate the 64 bit numbers. Ideas how to deal with the possible overflow?

Any help will be greatly appreciated

Here is my code (the problem occurs as early as the first call to finddiffs):

Code: Select all
Last edited by anikolov on Fri Oct 26, 2007 12:08 am, edited 1 time in total.
anikolov
New poster

Posts: 7
Joined: Sun Oct 21, 2007 1:38 am

11319 - Stupid Sequence

Try just examining the 1500th term to determine the a0, a1, ... co-efficients. If x = 1500 and the maximum any co-efficient can be is 1000 then you can determine all the co-efficients by just examining this one term (hint: start with x^6 to determine a6, then substract that part from the equation and proceed to x^5 to determine a5, etc.).

Hope this helps (but not too much of course!),

Paul.
pburkley
New poster

Posts: 1
Joined: Sun Oct 21, 2007 8:43 am

I applied Gaussian-Elimination to the first 7 equations. As the values won't be too big in the first 7 equations, those can be solved without any overflow(even with 32-bit int).

The other equations are used just to check the feasibilty.
sunny
Experienced poster

Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Thank you for your help!

Sunny, I was able to solve using the first 7 equations (I was also considering gaussian at one point). Now I can always solve, but when I check if the other terms are correct, I still get the wrong answer with big numbers, i.e. an overflow. Here is the function I use to check:

Code: Select all
Last edited by anikolov on Fri Oct 26, 2007 12:09 am, edited 1 time in total.
anikolov
New poster

Posts: 7
Joined: Sun Oct 21, 2007 1:38 am

Note that there won't be any f(x) in the input where it crosses unsigned long long.

You can avoid overflow while checking feasibilty like this:

Code: Select all
`(f(x)-a0)/x = a1 + a2*x + a3*x^2 + a4*x^3 + a5*x^4 + a6*x^5`

of course, if (f(x)<a0) || (fx-a0)%x!=0) the sequence is smart sequence.
The right side will never cross the boundary of unsigned long long.
sunny
Experienced poster

Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

What if ai is not integer, e.g. 1/3, how should the output be? 0.33 or 0.333 or 0.3333?
New poster

Posts: 1
Joined: Thu Oct 18, 2007 7:25 am

There was a clarification in the contest that all inputs and outputs are integers.
sunny
Experienced poster

Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

I used Newton Interpolation in the contest but get wrong answer all the time.Now I know that Newton Interpolation can't get the exact value of a1,a2,,,a6 if I just use Integers.
wudanzy
New poster

Posts: 4
Joined: Wed Sep 05, 2007 3:04 pm

Thank you for all your good suggestions. I think I solved the problem..but the judge does not agree, and I am getting frustrated to no end. I generated my own input files with Python, tested the biggest coefficients for which f(1500) fits in 64 bits (a0 = 1000, a1=1000, a2=1000, a3=1000, a4=1000, a5=928, a6=1), and it worked. I changed a number in a random place in a sequence, and it correctly said it's smart. So how is it possible I am getting wrong answer? I do not know..

I will appreciate it if anybody can help

Code: Select all
Last edited by anikolov on Fri Oct 26, 2007 12:10 am, edited 1 time in total.
anikolov
New poster

Posts: 7
Joined: Sun Oct 21, 2007 1:38 am

Check carefullly. Your code prints a trailing space after each line. This should be PE but now the judge has a problem and shows WA.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Thank you!

I removed trailing spaces. And then trailing endlines. And tried all combinations between trailing space/ no trailing space, trailing newline/no trailing newline. No luck so far.

However, I inserted an if statement to go into an infinite loop if a coefficient is above a 1000 - I got TLE. So..maybe I do not approach the problem the right way. However, it works on all kinds of crazy inputs I generate.
anikolov
New poster

Posts: 7
Joined: Sun Oct 21, 2007 1:38 am

Don't remove trailing newlines!! Edit your post and replace it with your new code.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Problem solved - thank you for your help.

I made it so a sequence is determined smart if at least one of the following is true:

1) Any coefficient is not an integer.
2) Any coefficient is >1000.
3) Consecutuve differences do not become constant after 7 iterations, i.e. the sequence is not generated by a polynomial of power <=6.
4) Not all members of the sequence are consistent with the coefficients discovered from the first 7 members.

My problem was my code did not check for 1) and 2). Trailing spaces were not really an issue. I got AC.

Thank you for all your input.
anikolov
New poster

Posts: 7
Joined: Sun Oct 21, 2007 1:38 am

anikolov wrote:Trailing spaces were not really an issue. I got AC.

You got accepted with this line?? And all the trainling spaces after every lines?
Code: Select all
`cout << "This is a smart sequence! \n"; `

Strange....

P.S Don't forget to remove your code.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

I was not exact - the trailing spaces were a problem, but I got presentation error, and not WA.
anikolov
New poster

Posts: 7
Joined: Sun Oct 21, 2007 1:38 am

Next