Page 1 of 2

11920 - 0 s, 1 s and ? Marks

Posted: Sun Feb 06, 2011 9:12 pm
by receme
Anyone can give some critical test case??? I got continuous WA...plz help.... :(

Re: 11920

Posted: Mon Feb 07, 2011 12:03 pm
by zobayer
It is hard to tell whats wrong, as I have solved it using greedy strategy based on some observations, however, try these inputs

Code: Select all

12
11?????000
1??
1??1
1???00
1?0?1?00
11?0?1?00
????0101????
011?010???
???
000111
00000000000000
11?00?0??0?1?1??1?
Output should be

Code: Select all

Case 1: 3
Case 2: 1
Case 3: 2
Case 4: 2
Case 5: 2
Case 6: 3
Case 7: 1
Case 8: 2
Case 9: 1
Case 10: 3
Case 11: 14
Case 12: 3
Let us know if these work for you or not...

Re: 11920

Posted: Tue Feb 08, 2011 11:35 am
by Shinigami
Dude...
Can u please post some more critical input outputs...
it will be immensely helpful..

Re: 11920

Posted: Tue Feb 08, 2011 3:23 pm
by lgarcia
My critical input was this:

Code: Select all

1
00??0?11
Output:

Code: Select all

Case 1: 2

Re: 11920

Posted: Tue Feb 08, 2011 8:47 pm
by receme
I have tried all the test cases and got correct answer. but still WA. Althougth my code is not follow greedy stategy, but I cannot find my mistake. I need some more test cases.

Re: 11920

Posted: Wed Feb 09, 2011 7:27 am
by receme
I tried a lot. but all I got is WA. Should I consider blank line for input??? Plz...give some more inputs.

Re: 11920

Posted: Wed Feb 09, 2011 9:47 am
by receme
just got ac.... :)

My code was giving WA for these test case....
input:

Code: Select all

1
1?00?1
0?11?0
output:

Code: Select all

Case 1: 2
Case 2: 2

Re: 11920

Posted: Thu Feb 10, 2011 11:28 am
by suneast
Hi ,receme
Can u plz give me some hints on how 2 solve this problem using GREEDY method? :)

I can't figure out how to reduce the time complex using dynamic programming, in fact, I got TLE using DP :(

Maybe I have missed some important condition...

thx so much for you help :wink:

Re: 11920

Posted: Thu Feb 10, 2011 6:51 pm
by zobayer
@suneast
It is possible to solve it using dp, but you need to optimize it to O(n). One of our teams solved this using dp in real contest.

Re: 11920

Posted: Thu Feb 10, 2011 8:01 pm
by zobayer
Actually there is no critical input, here are some more:

Code: Select all

8
0?0?0?0?0?0?0??
000?111
??01
???????0??????
?????????1?????????????
000??111
0?1?0
000111????111000
Output:

Code: Select all

Case 1: 1
Case 2: 4
Case 3: 1
Case 4: 1
Case 5: 1
Case 6: 3
Case 7: 2
Case 8: 3
Not sure will it help or not :p

Re: 11920

Posted: Thu Feb 10, 2011 10:00 pm
by receme
@ suneast: I did not solve this problem using greedy method. Actually I have't learn this method yet. Need to study a lot.... :(

I solved this problem using simple brute force considering some test cases.

Re: 11920

Posted: Wed Feb 16, 2011 9:21 am
by suneast
hi, all

after struggle for this problem a few days, I still keep getting WA... :-?

my method is quite simple

b-search the answer and greedy

merge '?' with the previous sequence, util I can't merge them , I try to merge '?' with the successive sequence.

any special test case?

I have try what ever I can... :oops:

any help will do, thx in advance :)

Re: 11920

Posted: Wed Feb 16, 2011 10:13 am
by suneast
finally got AC with my previous mention method :D

my method is

Code: Select all

 * b-search and greedy
 *
 * if the digits before && after "?" is different, we can change the sequence to
 * *0?1*     -> *0?1*      still don't know
 * *0??1*    -> *0101*     ans>=1
 * *0???1*   -> *01001*    ans>=2
 * *0????1*  -> *010101*   ans>=1
 * ....
 * else if they are the same, "0" is consider here, the same to "1"
 * *0?0*     -> *010*      ans>=1
 * *0??0*    -> *0110*     ans>=2
 * *0???0*   -> *01010*    ans>=1
 * *0????0*  -> *010110*   ans>=2
 * ...
 * but how to solve the "0?1" sequence ?
 * my method is b-search and greedy...
 * if I can merge '?' with previous sequence, I will greedy merge them
 * else I have to merge '?' with successive sequence...
 *
 * now, the answer is obvious after some observe...
 *
 * just code it and got AC...
 *
 * happy coding~
hope I am help to you all....

Happy coding~ :D

Re: 11920 - 0 s, 1 s and ? Marks

Posted: Fri Feb 20, 2015 8:53 pm
by brianfry713
I got AC in 0.105 seconds using backtracking with pruning.

I first calculate the optimum max group based on the existing 0's and 1's.

If the first char is a ? I try both 0 and 1.

Then in my recursive function I keep track of the string position, max group size, and current group size.
If you've already managed to reach the optimum max group size then return.
If the max group size is greater than your best max group size then return
If the position is the end of the string then update the best max group size then return.
If the current char is a ? first try the opposite of the previous char, then try the opposite of the next char if it is different.

Re: 11920 - 0 s, 1 s and ? Marks

Posted: Mon Feb 23, 2015 11:36 pm
by brianfry713
To further explain my first step of "I first calculate the optimum max group based on the existing 0's and 1's."

The sample input:
011?010??? - optimum max group size is 2 - the second and third characters 11.
??? - optimum max group size is 1 - It will never be less than 1.
000111 - optimum max group size is 3 - the first, second and third characters 000.
00000000000000 - optimum max group size is 14 - the entire string.

Shadek, why does max_group equal three in your code for the first sample input, and why are you incrementing it if there is a question mark? It doesn't appear you are following my algorithm.