11261 - Bishops

[ani_mitr86]

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

[jah]

Well I used an O(n) algorithm which iterates over diagonals rather than square by square.

[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

[sclo]

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.

[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 ?

[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

[sunny]

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]

Yes, that's the idea.
I didn't want to say too much since that would give the problem away.

[shakil]

Why WA. Please help.
please give some sample input and output.

Code: Select all

CUT AFTER AC

[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.

[shakil]

Can anyone give a sample input and output that fail my code(previous post).Thanks in advance.

[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..

[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

[shakil]

Thanks sapnil,mmonish & Piklu_sust. SUST's solvers are very helpful and genious.