Lucky Number Problem

Jan 9, 2019 at 1:27pm
Can somebody give better approach to solve this problem?.I am getting TLE.
https://www.codechef.com/JAN19B/problems/HP18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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;
}
Jan 9, 2019 at 4:49pm
Well better indentation would attract more interest in your post.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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++.
1
2
3
4
5
6
7
8
9
10
11
$ 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 109, 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];




Jan 9, 2019 at 5:35pm
> C++ 1998 does not support ‘long long’
C++11 does
Jan 9, 2019 at 7:43pm
@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.
Last edited on Jan 9, 2019 at 7:47pm
Jan 9, 2019 at 10:21pm
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.
Jan 10, 2019 at 3:50am
@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.
Jan 10, 2019 at 5:43am
Consider this example.
1
2
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
Jan 10, 2019 at 5:58am
Thanks @salem c
Jan 11, 2019 at 12:16am
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
Jan 11, 2019 at 2:23am
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.
Topic archived. No new replies allowed.