WA in spoj WILLITST (WILL IT EVER STOP)

Can anyone please tell me what is causing this WA.
the problem is: http://www.spoj.com/problems/WILLITST/
here is my solution.
http://ideone.com/qHy4Td

thank you

Seriously, don’t know what is wrong in your code. And I want someone to point it out.

But, in your program, instead of assigning n with 3*n+3 i.e,

n=(3*n)+3;

and then check n in stack, if you break the loop there and then, check for n=1 and print “TAK” and “NIE” accordingly then it surely shows AC. Here is the


[1].


  [1]: http://ideone.com/hWrxTs

Well,thank you for your response. Using the optimizations you suggested my problem got accepted. However I fail to understand why the code gets accepted without considering this assigning part. (n=(3*n)+3;). Is it not mandatory? It will be really helpful if you could explain this portion.
Thanks again :slight_smile:

You are getting WA because of overflow.

Suppose n is an odd number, say 5. Then, in your code,

while(n>1)
{
    if(n%2==0)
        n=n/2;
    else
        n=(3*n)+3;
    
    ...
}

the else part will get executed. Since n is odd, 3*n + 3 will also be odd. This continues in the loop, as long as n is greater than 1. Since n is always growing (and remains odd), it suddenly will get very large, that it overflows the long datatype. In this case, the number wraps around and becomes a negative number.

Now, when n becomes negative, the while loop terminates. And your program prints "TAK". But in fact, the program given in question will never terminate, as n can keep on growing indefinitely.

So, the reason for WA is overflow!

@tijoforyou i also, consider this posibility. But, first look at that 3*n+3 is actually, 3(n+1) which always produce an even number and n%2 always makes sure it factor outs all even part of it. Then, again it became odd and find that in stack and exit the loop.

I even tested the program for 9999999999999 and it works fine.

@tijoforyou : your statement “Since n is odd, 3*n + 3 will also be odd” is incorrect. If n is odd then this expression will be even.

So the problem is not in the overflow.

But the prog definitely goes into infinite loop and terminates when the integer wraps to negative part as you correctly pointed out.

EDIT : @sobhagya yes, what you say seems to be correct

If you closely look at, 3*n+3 it is actually 3(n+1) which always produce an even output but, it also contains 3 as a factor which is a odd part.

So, now if condition passes and it keeps on dividing it with 2 until the odd part remains. Then again it goes to else part where it became even with 3 as a factor. And the process never terminates. So, as soon as you recieve an odd number you simply break the loop.

3 Likes

@sobhagya : very well explained.

Oh, yeah! MY BAD!

Sorry! For the wrong explanation! Didn’t see it through.

Btw, this explanation helped me get the right answer!! :stuck_out_tongue: :stuck_out_tongue:

@sobhagya : Thank you for the explanation,it was really helpful. What i understand from your explanation is,when n=odd,it gets converted to an even number due to the formula n=3*n+3; and that even number on prolonged division by 2,eventually comes down to the same odd number ‘n’. Simply, Back to square one. (correct me if i am wrong).

So there is a repetition of the numbers. eg: if 3 is the input, then the numbers would go like 3 => 12 => 6 => 3(repetition!). Thus it becomes an infinite loop.

But to prevent the while loop from being an infinite one,i had used this check:


if(stack.contains(n))

(all the new values of n obtained by either n=n/2 or n=3*n+3 are pushed into the stack after each iteration.)

So this check if(stack.contains(n)) is supposed to detect whether there are any cases of repetition and accordingly break out of the while loop.
So how can the loop become an infinite one even after that?
Is there any test case for which the checking condition fails?


Thanks again :slight_smile:

@codegagu Nope, it comes down to 3 at the end.

//