11735 - Corner the Queens

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

11735 - Corner the Queens

Post by mak(cse_DU) » Thu Jun 24, 2010 10:12 am

At first I read the link: http://sps.nus.edu.sg/~limchuwe/cgt/cgt1.htm
Then I calculated all losing position.

Then for every test case I need O( 2*log2(690000) ) Iterations.(twice binary search)
But Time limit 1.000 second. Have any constant solution ??

My AC time: 0.112s

some Intput/output:

Code: Select all

10
41 467 6334 6500
169 724 1478 9358
962 464 5705 8145
281 491 9961 827
995 942 4827 5436
391 153 3902 604
292 382 7421 8716
718 895 5447 1726
771 538 1869 9912
667 299 7035 9894
Ac output:

Code: Select all

Board 1: 9493390 / 9494499
Board 2: 2262219 / 2262370
Board 3: 36439079 / 36443408
Board 4: 9680 / 9681
Board 5: 17226611 / 17229335
Board 6: 49600 / 49607
Board 7: 59422803 / 59428550
Board 8: 393463 / 393536
Board 9: 10302064 / 10303125
Board 10: 15277781 / 15279231
Mak
Help me PLZ!!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11735 - Corner the Queens

Post by Jan » Tue Jun 29, 2010 9:29 pm

My idea is same, and it takes .064. I think no constant solutions are available. May be your code is not efficient enough.
Ami ekhono shopno dekhi...
HomePage

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 11735 - Corner the Queens

Post by mak(cse_DU) » Tue Jun 29, 2010 9:47 pm

Thanks Jan vai.
Your's one was 2 times faster than me.
I found that my code calls a binary search function 16 times for each case. :(
Mak
Help me PLZ!!

alsteiner11
New poster
Posts: 1
Joined: Mon Nov 12, 2012 10:25 pm

Re: 11735 - Corner the Queens

Post by alsteiner11 » Mon Nov 12, 2012 10:30 pm

Jan wrote:My idea is same, and it takes .064. I think no constant solutions are available. May be your code is not efficient enough.
I used a constant time solution, so I had AC in 0.024s. It's not complicated too. The hint is that F(n+1)/F(n) approximately phi, for very large fibonacci numbers F(n+1) and F(n). I used F(n) = 5702887.

Post Reply

Return to “Volume 117 (11700-11799)”