11261 - Bishops
Moderator: Board moderators
-
- 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?
-
- New poster
- Posts: 20
- Joined: Mon May 28, 2007 4:36 pm
- Location: India
Think about this problem: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.
-
- New poster
- Posts: 20
- Joined: Mon May 28, 2007 4:36 pm
- Location: India
No, here the binary array corresponds to the diagonals whether that diagonal is attaked/not attacked by any bishop.ani_mitr86 wrote: but in this problem there will be a n*n binary array and n*n order precomputing will give TLE
The number of upward/downward diagonals of a n*n chessboard is 2*n-1,
so there won't be n*n binary array.
-
- Learning poster
- Posts: 74
- Joined: Sat Jul 15, 2006 6:28 am
- Location: CUET , bangladesh
- Contact:
Why WA. Please help.
please give some sample input and output.
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
-
- 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:
CORRECT OUTPUT:
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.
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
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 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
ur sol is right. Why u r comparing like this
Do integer comparison & get AC.
Hope this helps..
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));
}
Hope this helps..