Page 1 of 1

11261 - Bishops

Posted: Wed Sep 05, 2007 3:10 pm
by ani_mitr86
i did an n^2 order traversal and got TLE. can smbdy help with a better algo?

Posted: Wed Sep 05, 2007 3:18 pm
by jah
Well I used an O(n) algorithm which iterates over diagonals rather than square by square.

Posted: Wed Sep 05, 2007 3:33 pm
by ani_mitr86
but hw do u remove redundancy i.e. the squares which are at the intersection of two diagonals since they will be counted twice

Posted: Wed Sep 05, 2007 8:11 pm
by sclo
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
Think about this problem:
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.

Posted: Fri Sep 07, 2007 1:38 pm
by RC's
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 ?

Posted: Fri Sep 07, 2007 3:13 pm
by ani_mitr86
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

Posted: Fri Sep 07, 2007 5:36 pm
by sunny
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.

Posted: Fri Sep 07, 2007 7:45 pm
by sclo
Yes, that's the idea.
I didn't want to say too much since that would give the problem away.

Posted: Wed Sep 12, 2007 2:37 pm
by shakil
Why WA. Please help.
please give some sample input and output.

Code: Select all

CUT AFTER AC

Posted: Wed Sep 12, 2007 4:36 pm
by Piklu_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.

Posted: Mon Sep 17, 2007 3:38 pm
by shakil
Can anyone give a sample input and output that fail my code(previous post).Thanks in advance.

Posted: Mon Sep 17, 2007 5:00 pm
by mmonish
>>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..

Posted: Mon Sep 17, 2007 6:38 pm
by sapnil
your idea is abslty right:

Change your compare function
like this:

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

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

return(*p-*q);
}

sapnil

Posted: Mon Sep 17, 2007 8:18 pm
by shakil
Thanks sapnil,mmonish & Piklu_sust. SUST's solvers are very helpful and genious.