SPOJ ROOTCIPH wrong answer

Question

Here is the SPOJ problem ROOTCIPH.

I have solved it by two ways in C. One approach gives the correct answer and the other is wrong.

We won’t discuss the how to solve the problem. The solution is simple. It is always aa -2b. (Think in term of roots of a cubic equation...) Anyway, the question does not relate to it. This detail I gave so that one can run their solution to the source and analyse more.

Now the question:

In the code below, if instead of 'int', I take long long, my answer is shown correct, otherwise for 'int' it is shown wrong. I have taken %lld in printf, so even if the integer bound exceeds, it should handle.

Wrong code:

int main()
{
    int a, b, c;
    int t;

    scanf("%d", &t);

    while(t--)
    {
        scanf("%d%d%d", &a, &b, &c);
        printf("%lld\n", 1LL*a*a - 2*1LL*b);
    }

    return 0;
}

Right code:

int main()
{
    long long a, b, c;
    int t;

    scanf("%d", &t);

    while(t--)
    {
        scanf("%lld%lld%lld", &a, &b, &c);
        printf("%lld\n", a*a - 2*b);
    }

    return 0;
}

Note that absolute value of a, b, and c will not exceed 10^8.

Why does the first approach give the wrong solution? You can run the solution in the link given and check.

According to C operator precedence table , * have left to right associativity.

Is it possible that there are very large numbers that don't fit in an `int` that do fit into `long`? — Engineer2021, Mar 05 '14 at 13:57
i have used 1LL , so by order of precedence , the resultant answer should always be long long — Number945, Mar 05 '14 at 14:39
The result will be a `long long`; that says nothing about the types of intermediate values (in particular, a*a). — Scott Hunter, Mar 05 '14 at 17:47
What happens if you replace the printf expression in wrong code with (1LL*a)*a-2*(1LL*b)? — Scott Hunter, Mar 05 '14 at 18:03

score 1 · Answer 1 · edited Sep 11 '22 at 01:01

1

As Engineer2021 suggests, using long long's, which can hold bigger numbers than int's, is likely the difference. For example, part of your expression is a*a; even if you multiply that by a 1LL, in effect converting it, the damage may have already been done.

edited Sep 11 '22 at 01:01

Peter Mortensen

30,738
21
105
131

answered Mar 05 '14 at 14:01

Scott Hunter

48,888
12
60
101

But the multiplication by `1LL` happens before the multiplication `a*a`. – interjay Mar 05 '14 at 14:06
Just because you put it first doesn't (necessarily) enforce the order of execution. Compilers are clever beasts... – Scott Hunter Mar 05 '14 at 17:45
It does enforce the order. Compilers have to conform to the standard, which specifies the order. – interjay Mar 05 '14 at 17:57
Unless I'm mis-reading it, this says otherwise: http://en.cppreference.com/w/c/language/eval_order – Scott Hunter Mar 05 '14 at 18:01
Your link says "the expression a + b + c is parsed as (a + b) + c due to left-to-right associativity of operator+". The same is true for multiplication. – interjay Mar 05 '14 at 18:02

score 0 · Answer 2 · edited Sep 11 '22 at 01:02

0

If your answer is not in the interval [-2 147 483 648 ; 2 147 483 647], then it can't fit into an int, which is stored in 32 bits (or 16 if you are on a 16 bits system, so in [-32 768 ; 32 767]).

A long long integer is stored in 64 bits, regardless of your system.

edited Sep 11 '22 at 01:02

Peter Mortensen

30,738
21
105
131

answered Mar 05 '14 at 14:07

Antoine C.

3,730
5
32
56

1

+1 for noting about 16-bit. Note: A long long integer is stored on _at least_ 64 bits. – chux - Reinstate Monica Mar 05 '14 at 18:18
From *[What range of values can integer types store in C++?](https://stackoverflow.com/a/1819236)*: *"The* ***minimum*** *range for this type, if your compiler supports it, is: long long int: -9,223,372,036,854,775,807 to 9,223,372,036,854,775,807. unsigned long long int: 0 to 18,446,744,073,709,551,615."* – Peter Mortensen Sep 11 '22 at 01:08

SPOJ ROOTCIPH wrong answer

2 Answers2