## 11735 - Corner the Queens

Moderator: Board moderators

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

### 11735 - Corner the Queens

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
Contact:

### Re: 11735 - Corner the Queens

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

### Re: 11735 - Corner the Queens

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

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.