WILLITST [Will it ever stop WA]

[alex0113_sof]

Link

#include<iostream>
using namespace std;
int cbin(long long v[],long long n,long long x)//BINARY SEARCH
{
	long long i=0,j=n-1,m;
	while(i<=j)
	{
		m=(i+j)/2;
		if(v[m]==x)
			return 1;
		else if(v[m]<x)
			i=m+1;
		else j=m-1;
	}
	return 0;
}
void insert(long long v[],long long &n,long long x)//INSERTION SORT
{
	long long i;
	for(i=n;i>0&&v[i-1]>x;i--)
		v[i]=v[i-1];
	v[i]=x; 
	n++;
}
int main()
{
	long long x,v[10000],n=1;
	cin>>x;
	v[0]=x;
	while(x>1)
	{
		if(x%2==0)
			x/=2;
		else
			x=3*x+3;
		if(cbin(v,n,x))
		{
				cout<<"NIE";
				break;
		}
		else
		{
			insert(v,n,x);
		}
	}
	if(x<=1)
		cout<<"TAK";
	return 0;
}
	

Gives me wa ..simple algorithm ...i store every number in an array and if it gest repeated it means infinite loop...if gets under or equal to 1 not

[leppyr64]

Are you certain that 10000 is enough?

[alex0113_sof]

the server allows maximum 1000000 or so but still wa...should i make a chained list or something?

[leppyr64]

x shoul never be less than 1. Use assert to verify that.

[alex0113_sof]

x shoul never be less than 1. Use assert to verify that.

didnt understand that sorry...if x is <1 at input it doesn't enter the loop and it outputs TAK because the sequence is already finished
and otherwise it can't get negative

[leppyr64]

#include<iostream>
#include<cassert>
using namespace std;
int cbin(long long v[],long long n,long long x)//BINARY SEARCH
{
   long long i=0,j=n-1,m;
   while(i<=j)
   {
      m=(i+j)/2;
      if(v[m]==x)
         return 1;
      else if(v[m]<x)
         i=m+1;
      else j=m-1;
   }
   return 0;
}
void insert(long long v[],long long &n,long long x)//INSERTION SORT
{
   long long i;
   for(i=n;i>0&&v[i-1]>x;i--)
      v[i]=v[i-1];
   v[i]=x; 
   n++;
}
int main()
{
   long long x,v[10000],n=1;
   cin>>x;
   v[0]=x;
   while(x>1)
   {
      if(x%2==0)
         x/=2;
      else
         x=3*x+3;
      assert(x>0);
      if(cbin(v,n,x))
      {
            cout<<"NIE";
            break;
      }
      else
      {
         insert(v,n,x);
      }
   }
   if(x<=1)
      cout<<"TAK";
   return 0;
}

[alex0113_sof]

    #include<iostream>
    using namespace std;
    int cbin(long long v[],long long n,long long x)//BINARY SEARCH
    {
       long long i=0,j=n-1,m;
       while(i<=j)
       {
          m=(i+j)/2;
          if(v[m]==x)
             return 1;
          else if(v[m]<x)
             i=m+1;
          else j=m-1;
       }
       return 0;
    }
    void insert(long long v[],long long &n,long long x)//INSERTION SORT
    {
       long long i;
       for(i=n;i>0&&v[i-1]>x;i--)
          v[i]=v[i-1];
       v[i]=x;
       n++;
    }
    int main()
    {
       long long x,v[10000],n=1;
       cin>>x;
       v[0]=x;
       while(x>1)
       {
          if(x%2==0)
             x/=2;
          else
             x=3*x+3;
         if(x<=1)
       	  break;
          if(cbin(v,n,x))
          {
                cout<<"NIE";
                break;
          }
          else
          {
             insert(v,n,x);
          }
       }
       if(x<=1)
          cout<<"TAK";
       return 0;
    }

yea i tried it and it gave me sigabrt(meaning assertion failed) but whyyy...how can x become less than 0 after dividing or multiplying a positive number ....up there it tried to correct it ...still wa

[alex0113_sof]

ty for help....don't know why it gave me wa but i completely changed my approach and got ac :d

[leppyr64]

X was exceeding the datatype size. When it overflows it becomes negative.

[imsinha_sof]

Hi,

I think the number of the form of 2^x are the only ones which will terminate.. Is my logic correct?

[leppyr64]

How exhaustively have you proved that assumption?

[imsinha_sof]

Let T(n) represent the count of numbers which occur before n is eventually reduced to <=1.

T(n)= 0 if n is 1 or 0
1+ T(n/2) if n is even
1+ T(3*(n+1)) if n is odd

So, if value of T(n) can be calculated , then the program will terminate otherwise not.

I begin with the case where n is odd.

Lets start with smallest possible odd number n =3; the course of solution will be as follows => T(3)->T(12)->T(6)->T(3)
We can see that this is an infinite loop

Similarly , we can observe with n=5
T(5)->T(18)->T(9)->T(30)->T(15)->T(48)->T(24)->T(12)->T(6)->T(3)
Again the infinite loop

Similarly I observed for n=7 too..

However, I do not have any mathematical proof which confirms this, But there is counter example to contradict this.

I know this problem could be done through cycle detection too. But will it not be more time consuming solution specially considering the fact that n is of the order of 10^14.?

Does any one has a counter example where the number is not of the form 2^x and still the program is terminating. Of course n is should not be 0.

[leppyr64]

You have an assumption, formulate a proof.

Of course n is should not be 0.

Why not?