## 11532 - Simple Adjacency Maximization

Moderator: Board moderators

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### 11532 - Simple Adjacency Maximization

I try to solve this problem
But i get WA.......
can any one help me????????

Code: Select all

``````CUT after acc..........................
``````
Last edited by saiful_sust on Sat Jan 10, 2009 11:50 am, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11532 - Simple Adjacency Maximization

Try some test cases..

Code: Select all

``````6
0 1
1 0
5 1
1 5
7 2
2 7``````

My output is..

Code: Select all

``````0
1
47
1
367
5``````

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11532 - Simple Adjacency Maximization

Thanks helloneo
now i can solve it........

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### Re: 11532 - Simple Adjacency Maximization

I think this problem can be solved by using DP, but i can't find the recursive relationship...
could someone give me a hint?
electron

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11532 - Simple Adjacency Maximization

f74956227 wrote:I think this problem can be solved by using DP, but i can't find the recursive relationship...
could someone give me a hint?
I didn't solve this problem with DP.. Just try to find a pattern..
If there are enough '0's, the best representation would be like this..

...000000101101101101

If there are not enough '0's, you have to insert '0' in smarter way..

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### Re: 11532 - Simple Adjacency Maximization

I got AC!!! It is just a simple simulation problem Thank!
electron

aliahmed
New poster
Posts: 24
Joined: Fri Oct 24, 2008 8:37 pm
Contact:

### Re: 11532 - Simple Adjacency Maximization

ACC
It was wrong for 3 1
Last edited by aliahmed on Mon Apr 27, 2009 9:31 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11532 - Simple Adjacency Maximization

I think you might get a precision error here..
aliahmed wrote:

Code: Select all

``			sum+=pow(2,q);``
Do not use floating point operation

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11532 - Simple Adjacency Maximization

The number of 1s adjacent to one or more 0 in the binary representation is maximized.
What does this mean ? Why isn't 0101011 (43) better than 0101101 (45) in case of 4 3 .

Also i don't understand in case 3 2 , why is it 1101 (13) instead of 10101(21) ?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11532 - Simple Adjacency Maximization

43 -> 0101011 has three '1's which are adjacent to '0'
45 -> 0101101 has four '1's which are adjacent to '0'
So, 45 is better than 43

For input
3 2

1101 and 10101 both have three '1's adjacent to '0'
But, problem statements say that
Find the smallest integer N ..
So, the answer would be 13 (1101)