11261 - Bishops

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11261 - Bishops

Post by ani_mitr86 » Wed Sep 05, 2007 3:10 pm

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

Post by jah » Wed Sep 05, 2007 3:18 pm

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

Post by ani_mitr86 » Wed Sep 05, 2007 3:33 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Sep 05, 2007 8:11 pm

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.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

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

Post by ani_mitr86 » Fri Sep 07, 2007 3:13 pm

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

Post by sunny » Fri Sep 07, 2007 5:36 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Sep 07, 2007 7:45 pm

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
Location: CUET , bangladesh
Contact:

Post by shakil » Wed Sep 12, 2007 2:37 pm

Why WA. Please help.
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

Post by Piklu_sust » Wed Sep 12, 2007 4:36 pm

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
Location: CUET , bangladesh
Contact:

Post by shakil » Mon Sep 17, 2007 3:38 pm

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

Post by mmonish » Mon Sep 17, 2007 5:00 pm

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

Post by sapnil » Mon Sep 17, 2007 6:38 pm

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
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Post by shakil » Mon Sep 17, 2007 8:18 pm

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

Post Reply

Return to “Volume 112 (11200-11299)”