hey m using a turbo c++ 4.5 compiler...

i submitted d solution but its givin an error...

i can execute d prog on my pc...

can u help me out here....

http://www.codechef.com/wiki/faq

k thaks got it..

Does timelimit error mean my solution has errors? or is it just took long time to provide all the right answers to the test cases?

Is it possible to provide additional test cases to validate my result?

See the FAQ.

what is the meaning of "play optimally"?

It means each player will make the best possible moves, knowing their opponents will make the best possible moves too.

got it....

damn good way to present the problem......

here only when input is 1 ....alice will win else bob will win(always).....i did yhe same thing....why am i getting the wrong answer error?

please help me...........

sorry on input==2....alice will win else bob will win.....my mistake in my last comment.........help me.......

If the input is 6, Alice can win by subtracting 3. Bob will be forced to subtract 1, and Alice will subtract 1 again to win.

Please verify if this is really a level 2 problem or not...because the solution is pretty straight forward and can be proved using induction.

Here is a question for test case N=1. The problem description clearly states that  "In his/her turn, a player can subtract from N any proper divisor (not equal to N) of N. The number thus obtained is the new N". So when N = 1 how can Alice subtract 1 from 1 (1 equal to N)?....as well for N=2 test case if Alice starts then 2-1 = 1  left for Bob to subtract from which he cannot make a move since 1 equals the new N?.....Please clarify me if Iam wrong. Thanks

Alice never subtracts 1 from 1. The first test case is N=1; Alice cannot move therefore Bob wins. The second test case is N=2; Alice subtracts 1 and now Bob cannot move, so Alice wins.

My bad dude...I mistook the first input 2 to be N....where it is just the no of inputs....sorry about that..Thanks.

To admin:

First I was getting TLE error. Then I looked back into the algorithm and wrote something different. Now I am stuck with Runtim Error. Don't know where is the problem. Please help.

http://www.codechef.com/viewsolution/409212

500000005 chars is far too much memory to store on the stack (ie inside a function); but even if you moved it onto the heap (global) it is still too much memory.

@Stephen: Agreed! I think this solution should work good but why TLE? http://www.codechef.com/viewsolution/409182

Time complexity is of the order O(n^2). Is there any other algorithm with improved complexity?

Have you tried testing your code at all? It runs forever on nearly every single input. Even if it were O(N^2), your program should be able to solve a total of 10000 test cases of size 1000000000 - you wouldn't be able to solve 1 test case of size 100000 in one second with O(N^2), let alone that.

@Stephen: Damn!! I again din't read the problem statement carefully! :( :(. Sorry! Whole Code was wrong!

I learnt one thing here- I used to think, time limit is for every individual test case, but as u say its for the entire test suit. Thanks! :)

On my machine, my program shows me total time consumed as 20 ms for 10000 inputs  with each input being  a random number between 1 to 1000000000... After submission, the time is .54 sec.. this is a huge difference? The language is C#..

plz look at my code.

awesome game theory problem :

an odd # is divisible by odd only so a person getting odd number gives opponent even who in turn if gives opponent again odd(by substracting 1 which he always can as he gets even); ultimately the 1 st person always gets odd and reaches 1 at last and loses implying...

person getting odd loses so if Alice gets odd ; Bob should always try to keep him odd by taking 1 otherwise his opponent can take 1 or win himself...............here comes the meaning of optimal.

@Stephen=i am getting time limit extended again and again ...plz help me

http://www.codechef.com/viewsolution/461254

here my code ...tell me the prob ...

i am stuck with run time error..please tell me where is the problem.....

My code is giving correct output,but at the time of submission it shows Wrong Answer.

Please Admin help me to out of my problen..

http://www.codechef.com/submit/complete/49083-6308--4d6ea54e9b5ac

veryyyyyyyyyyyyy easy... loved ths one.. took only 5 minutes of deep thinking.

waw...what an problem....

i coded this very complex and observed on test cases and hahaha it's so simple.

im observing it too, and get the answer, but i still dont really know, why? :)

My program is just working fine in TURBOC, but i m getting TLE here, can any 1 help me.....

Following is the mine soln:

#include<stdio.h>
int main()
{
int i,t,n,flag;
scanf("%d",&t);
while(t--)
{
flag=0;
scanf("%d",&n);
for(i=n/2;i>=1;)
{
if(n%i==0)
{
n-=i;
i=n/2;
flag=!flag;
}
else
i--;
}
if(flag)
printf("ALICEn");
else
printf("BOBn");
}
return 0;
}

#include<stdio.h>
int main(){
int t,n,j,i,flag=0;
scanf("%d", &t);
if((t>=1) && (t<=10000))
{
  for(i=0; i<t; i++)
  {
    scanf("%d", &n);
    if((n<=1000000000) && (n>=1)){
    for(j=n/2;n!=1;)
    {
     if(n%j==0)
     {
      n=n-j;flag=!flag;j=n/2;
     }
     else
      j--;
    }
    if(flag)
    {
      printf("Alicen");
    }
    if(!flag)
    {
      printf("Bobn");
    }flag=0;
  }
  }
}
return 0;
}

my program execute and work fine in my comp. but gives wrong answer there why it is happend.......?

How do you know it works fine on your computer.?

problem in this line   if(n%2 == 0)   .

Hi Admin,

I have submitted the solution with ID 532563. I have checked for some test cases and my code is working fine. But is showing WA in your system. Can you tell me for which test case it is failing or what is the reason it is showing wrong answer

Hi,

Can someone take a look at my code and see which part could be optmized ... I am getting a TLE message.

Thanks

Link to my code:

http://www.codechef.com/viewsolution/537982

@Aparna Nobody can see your link...the solutions to this problem are not public

@vikram - anyone who has solved the problem can see code.

@Aparna - other than the fact that your algorithm is wrong (for example, you assume each player will always subtract the biggest possible factor, which certainly isn't the best strategy), N can be up to 1000000000 - that's a pretty huge number. If N were a prime just under that, you'd have to loop from 1 up to 31000 or so just to find a single move, let alone the entire game or 10000 test cases of that size.

I'm afraid you'll need to start from scratch - make sure your algorithm will run in time before you write any code at all.

hey...

i maked the game programme... but i do not understand that how can take the timer in turbo C++....???

can any one help me...??

Hi stiphen , why my code is giving runtime error ? Is it out of memory issue ? Please let me know ...

/*
 * Yet Another Number Game 
 */
import java.io.BufferedReader;
import java.io.InputStreamReader;
/**
 * @author Saptarshi Chatterjee (sapta9433)
 * @version 1.0 
 * @date May 3,2011.
 */
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine()),maxDiv=1,i;
		long n;
		final StringBuffer ALICE =new StringBuffer("ALICE");
		final StringBuffer BOB =new StringBuffer("BOB");
		for (; t > 0; t--) {
			n = Integer.parseInt(br.readLine());
			//if n is not divisible by 2 we can increment i by 2 to reduce looping.
			for(i=2;i*i<=n;i+=2) {
		        if(n%i==0){
		        	maxDiv =i;
		        	break;
		        }
		    }
			maxDiv = (int)n / maxDiv;
			if (maxDiv == n){
				maxDiv = 1;
			}
			// always give oppnt max pick + min pick (here 1) + 1
			if((n-1)%(maxDiv + 1) == 0){
				System.out.println(BOB);
			}else{
				System.out.println(ALICE);
			}
		}
	}
 
}