Lucky Number Problem

[SparkXV]

Can somebody give better approach to solve this problem?.I am getting TLE.
https://www.codechef.com/JAN19B/problems/HP18

int bob(long long int r[],int t,int n)
{
              int s=0,c,i;
              for(i=n-1;i>=0;i--)
               {
                    if((r[i]%t)==0)
                    {
                         s=i+1;
                         break;}
               }
               if(s==0)
                  return 0;
	       else
               {
                  for(c=s-1;c<n-1;c++){
         	          r[c]=r[c+1];
                  }
               }
         return (n-1);	                 
 }
int main()
{
	int T;
	cin>>T;
	int a,b,n,i;
	while(T--)
	{
		cin>>n>>a>>b;
		long long int r[n];
		for(i=0;i<n;i++)
		{
			cin>>r[i];
		}
        while(1)
        {
      	  if((n=bob(r,a,n))==0)
      	  {
      		  cout<<"ALICE\n";
      			  break;
      	      
      	  }
		   if((n=bob(r,b,n))==0)
      	   {
      		  cout<<"BOB\n";
      		  break;
      	       
      	   }
		 }
	}
	return 0;
}

[salem c]

Well better indentation would attract more interest in your post.

int bob(long long int r[], int t, int n)
{
  int s = 0, c, i;
  for (i = n - 1; i >= 0; i--) {
    if ((r[i] % t) == 0) {
      s = i + 1;
      break;
    }
  }
  if (s == 0)
    return 0;
  else {
    for (c = s - 1; c < n - 1; c++) {
      r[c] = r[c + 1];
    }
  }
  return (n - 1);
}

int main()
{
  int T;
  cin >> T;
  int a, b, n, i;
  while (T--) {
    cin >> n >> a >> b;
    long long int r[n];
    for (i = 0; i < n; i++) {
      cin >> r[i];
    }
    while (1) {
      if ((n = bob(r, a, n)) == 0) {
        cout << "ALICE\n";
        break;
      }
      if ((n = bob(r, b, n)) == 0) {
        cout << "BOB\n";
        break;
      }
    }
  }
  return 0;
}

> In each turn, the current player must remove a non-zero number of elements from the sequence;
Have you considered whether removing more than one at once always gives the same answer?
What about removing all the multiples on the first attempt?

> long long int r[n];
This isn't valid C++.

$ g++ -pedantic -Wall -Wextra main.cpp
main.cpp:3:14: warning: ISO C++ 1998 does not support ‘long long’ [-Wlong-long]
 int bob(long long int r[], int t, int n)
              ^
main.cpp: In function ‘int main()’:
main.cpp:29:10: warning: ISO C++ 1998 does not support ‘long long’ [-Wlong-long]
     long long int r[n];
          ^
main.cpp:29:22: warning: ISO C++ forbids variable length array ‘r’ [-Wvla]
     long long int r[n];
                      ^

You don't need long long, your input values only go up to 10⁹, which fits in a long anyway.

> r[c] = r[c + 1];
You don't need to shuffle the whole array down one spot.
Just move the last element to the slot to be deleted.
r[s-1] = r[n];

[ne555]

> C++ 1998 does not support ‘long long’
C++11 does

[SparkXV]

@salem c

>For your first approach,Will it not become tedious to shift the array.?

>As u are saying that,just shuffle the last element to the slot to be deleted.
But doing this,i am still getting TLE.

[ne555]

because you start at `n' instead of `s'
in the range [s; n] you know that there is no multiple, but you traverse it every time.

[SparkXV]

@ne555 Can u plz elaborate ur answer?
I am not getting what u are saying.

For ur information,In bob function's 2nd loop i am shifting the array.

[salem c]

Consider this example.

5 3 2
2 4 3 9 6

Basically, it's a race to see who can claim the 6 (being a common multiple of both 2 and 3).

There are two phrases in the challenge which seem interesting.
> both Bob and Alice play optimally.
> the current player must remove a non-zero number of elements from the sequence;

It's not a question of removing the first multiple of 2 or 3 from the sequence, but removing the "best" number from the sequence (in this case 6).

Alice can win if Bob is stupid and chooses 3 first, and she plays smart and picks 6 (leaving 2 4 9).

There is no point in Bob picking 3 or 9 early in the game, because these numbers can never be chosen by Alice. Similarly for Alice, 2 and 4 can be left until late in the game.

The smart numbers to go for are https://en.wikipedia.org/wiki/Coprime_integers

[SparkXV]

Thanks @salem c

[shubhum]

can't we just take all multiples of bob lucky number and remove them ??
in your example provided if there was also 12 can bob remove 3,9,6,12 in single turn

[Browni3141]

shubhum wrote:

can't we just take all multiples of bob lucky number and remove them ??
in your example provided if there was also 12 can bob remove 3,9,6,12 in single turn

Yes you could, but then Bob would lose the next turn because he would be without moves.