11205 - The broken pedometer

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

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

11205 - The broken pedometer

Post by mmonish » Sun May 20, 2007 4:11 pm

I am getting WA in this problem.
Can anyone give me some critical test case.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sun May 20, 2007 5:34 pm

Now i got AC. But my program takes 1.633 sec.
I checked all possible configaration.
Anyone please tell me how can i improve the time.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun May 20, 2007 5:47 pm

You can use bitwise operations to solve it. My brute force code(with bitwise calculations) took 0.312 seconds.
Ami ekhono shopno dekhi...
HomePage

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Mon May 21, 2007 4:05 am

sorry, I don't understand what this problem means.
In this case, LEDs 5 and 6 can be suppressed without losing information, so the solution is 5.
What does this mean??I looked this problem twice but still can't understand it :(

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Mon May 21, 2007 4:37 am

In this prob u have to find minimum number of active led's necessary to identify each symbol's means no repetive pattern.

In the first sample used 7 led's to represent a symbol. But if we turn off led 5 && 6 then it is still have no repetive pattern. So we need 5 active led's && thus the minimum.

Hope it helps.

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Mon May 21, 2007 5:55 am

Thank you for your quick reply.
I finally understand this problem!!

Now I am thinking how to solve it...

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Mon May 21, 2007 11:14 am

Can anyone give some critical test cases?

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Mon May 21, 2007 3:32 pm

try this case

Code: Select all

5
2
2
1 0
1 1
4
5
1 1 1 1
0 1 1 0
1 0 0 1
1 1 0 0
0 0 0 1
1
2
1
0
1
1
0
4
4
1 1 0 0
0 0 1 0
1 0 0 0
0 1 0 0
output

Code: Select all

1
3
1
1
2
[/code]
Last edited by mmonish on Tue May 22, 2007 10:31 am, edited 1 time in total.

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Mon May 21, 2007 3:59 pm

thank you for your test cases!

I really misunderstood the problem :(
Last edited by sjn on Tue May 22, 2007 9:30 am, edited 1 time in total.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Mon May 21, 2007 4:33 pm

yes.
That's the exact reason.

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

Post by sjn » Tue May 22, 2007 9:36 am

mmonish wrote:yes.
That's the exact reason.
Thank you for your post, I should read the problem and your previous post carefully next time :oops:
Last edited by sjn on Tue May 22, 2007 12:30 pm, edited 1 time in total.

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Tue May 22, 2007 10:32 am

Sily mistake in my typing. The result should be 1.

now i edit my post. Thanks for ur reply.

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

asd

Post by darkos32 » Wed May 23, 2007 4:42 pm

i've tried all test cases,but i still got WA...can anyone give me another critical testcases ?


thanks..

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Wed May 23, 2007 6:21 pm

is it a valid input

Code: Select all

1
2
2
11
11

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Wed May 23, 2007 6:57 pm

I think there is no cases like that.

Try this cases
Input

Code: Select all

3
3
1
1 0 1
5
2
1 1 1 1 1
1 1 1 1 0
3
8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Output

Code: Select all

1
1
3

Post Reply

Return to “Volume 112 (11200-11299)”