11920 - 0 s, 1 s and ? Marks

[receme]

Anyone can give some critical test case??? I got continuous WA...plz help....

[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...

[Shinigami]

Dude...
Can u please post some more critical input outputs...
it will be immensely helpful..

[lgarcia]

My critical input was this:

Code: Select all

1
00??0?11

Output:

Code: Select all

Case 1: 2

[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.

[receme]

I tried a lot. but all I got is WA. Should I consider blank line for input??? Plz...give some more inputs.

[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

[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

[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.

[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

[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.

[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...

any help will do, thx in advance

[suneast]

finally got AC with my previous mention method

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~

[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.

[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.