## 11261 - Bishops

Moderator: Board moderators

ani_mitr86
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

### 11261 - Bishops

i did an n^2 order traversal and got TLE. can smbdy help with a better algo?

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am
Well I used an O(n) algorithm which iterates over diagonals rather than square by square.

ani_mitr86
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India
but hw do u remove redundancy i.e. the squares which are at the intersection of two diagonals since they will be counted twice

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
ani_mitr86 wrote:but hw do u remove redundancy i.e. the squares which are at the intersection of two diagonals since they will be counted twice
Suppose you have an boolean array of size n:
You want to find out how many 1's are between i and j inclusive.
How do you solve it in O(1) time with O(n) precomputing.

Really, it degenerates into this problem.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
I still don't understand what you mean...
To compute how many 1's between i and j inclusive in O(1) time I think DP can be used.
Can I traverse the bishops diagonally with looping without getting TLE ?

ani_mitr86
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India
i hv already done that and since looping through diagonals but got TLE

i know hw to find no. of 1s in btweem i and j index of binary array with O(1) and O(n) precomputing.

but in this problem there will be a n*n binary array and n*n order precomputing will give TLE

i really don't know what to do

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
ani_mitr86 wrote: but in this problem there will be a n*n binary array and n*n order precomputing will give TLE
No, here the binary array corresponds to the diagonals whether that diagonal is attaked/not attacked by any bishop.

The number of upward/downward diagonals of a n*n chessboard is 2*n-1,
so there won't be n*n binary array.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
Yes, that's the idea.
I didn't want to say too much since that would give the problem away.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:
please give some sample input and output.

Code: Select all

``CUT AFTER AC``
Last edited by shakil on Mon Sep 17, 2007 8:22 pm, edited 1 time in total.
SHAKIL

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST
Here some random input and output. These may be helpful for u.

INPUT:

Code: Select all

``````11

760 10
65 123
32 654
132 458
325 187
256 325
25 63
7 9
3 6
65 45
12 99

10000 30
1 10000
2 6
5 3
4 98
9 8
365 4589
321 6548
356 10000
789 987
487 789
452 326
12 99
99 65
99 45
54 89
89 89
569 100
100 6547
6589 1000
3254 9872
456 9874
4000 5000
5400 1589
5100 1578
9000 10000
9999 1111
2222 3333
4578 9856
1 1
10000 10000

4 4
1 4
2 2
3 4
3 2

4 4
1 1
2 2
3 3
4 4

4 4
1 2
2 2
3 2
4 2

4 4
1 4
2 4
3 4
4 4

4 4
1 1
2 1
3 1
4 1

40000 1
1 1

40000 1
20000 20000

40000 4
20000 40000
30000 20000
10000 30000
40000 20000

40000 40
10000 30
1 10000
2 6
5 3
4 98
9 8
365 4589
321 6548
356 10000
789 987
487 789
452 326
12 99
99 65
99 45
54 89
89 89
569 100
100 6547
6589 1000
3254 9872
456 9874
4000 5000
5400 1589
5100 1578
9000 10000
9999 1111
2222 3333
4578 9856
20 10000
10000 10000
23658 39999
10000 5555
12345 12567
32564 9876
1 2
1 1
40000 4000
1325 20
4 40000
``````
CORRECT OUTPUT:

Code: Select all

``````Case #1: 568522
Case #2: 99702154
Case #3: 2
Case #4: 8
Case #5: 0
Case #6: 2
Case #7: 2
Case #8: 1599960000
Case #9: 1599920002
Case #10: 1599840008
Case #11: 1598384887
``````
I have edited my post.
I suggest you should recode because if there is any silly mistake in very very long code you cannot trace out. My ACC code is less than 45 lines.
Last edited by Piklu_sust on Wed Sep 12, 2007 8:42 pm, edited 1 time in total.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:
Can anyone give a sample input and output that fail my code(previous post).Thanks in advance.
SHAKIL

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
>>shakil
ur sol is right. Why u r comparing like this

Code: Select all

``````int ss(const void *a,const void *b)
{
return (strcmp((char *)a,(char *)b));
}``````
Do integer comparison & get AC.

Hope this helps..

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

like this:

int ss(const void *a,const void *b)
{
long *p,*q;

p=(long *)a;
q=(long *)b;

return(*p-*q);
}

sapnil

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am