11532 - Simple Adjacency Maximization

All about problems in Volume 115. 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
saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

11532 - Simple Adjacency Maximization

Post by saiful_sust »

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

Post by helloneo »

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

Post by saiful_sust »

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

Post by f74956227 »

I think this problem can be solved by using DP, but i can't find the recursive relationship... :cry:
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

Post by helloneo »

f74956227 wrote:I think this problem can be solved by using DP, but i can't find the recursive relationship... :cry:
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

Post by f74956227 »

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

aliahmed
New poster
Posts: 24
Joined: Fri Oct 24, 2008 8:37 pm
Location: CUET, Chittagong, Bangladesh
Contact:

Re: 11532 - Simple Adjacency Maximization

Post by aliahmed »

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

Post by helloneo »

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

Code: Select all

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

Remove your code after AC :-)

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

Re: 11532 - Simple Adjacency Maximization

Post by tryit1 »

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

Post by helloneo »

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)

Post Reply

Return to “Volume 115 (11500-11599)”