11319 - Stupid Sequence

[anikolov]

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

[pburkley]

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.

[sunny]

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.

[anikolov]

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

[sunny]

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.

[pladene]

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

[sunny]

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

[wudanzy]

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.

[anikolov]

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

[Jan]

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.

[anikolov]

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.

[Jan]

Don't remove trailing newlines!! Edit your post and replace it with your new code.

[anikolov]

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.

[Jan]

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.

[anikolov]

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