### 11920 - 0 s, 1 s and ? Marks

Posted:

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

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=54&t=51484

Page **1** of **2**

Posted: **Sun Feb 06, 2011 9:12 pm**

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

Posted: **Mon Feb 07, 2011 12:03 pm**

It is hard to tell whats wrong, as I have solved it using greedy strategy based on some observations, however, try these inputs
Output should be
Let us know if these work for you or not...

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?
```

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
```

Posted: **Tue Feb 08, 2011 11:35 am**

Dude...

Can u please post some more critical input outputs...

it will be immensely helpful..

Can u please post some more critical input outputs...

it will be immensely helpful..

Posted: **Tue Feb 08, 2011 3:23 pm**

My critical input was this:
Output:

Code: Select all

```
1
00??0?11
```

Code: Select all

`Case 1: 2`

Posted: **Tue Feb 08, 2011 8:47 pm**

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.

Posted: **Wed Feb 09, 2011 7:27 am**

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

Posted: **Wed Feb 09, 2011 9:47 am**

just got ac....

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

input:
output:

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

input:

Code: Select all

```
1
1?00?1
0?11?0
```

Code: Select all

```
Case 1: 2
Case 2: 2
```

Posted: **Thu Feb 10, 2011 11:28 am**

Can u plz give me some hints on how 2 solve this problem using GREEDY method?Hi ,receme

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

Posted: **Thu Feb 10, 2011 6:51 pm**

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

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.

Posted: **Thu Feb 10, 2011 8:01 pm**

Actually there is no critical input, here are some more:
Output:
Not sure will it help or not :p

Code: Select all

```
8
0?0?0?0?0?0?0??
000?111
??01
???????0??????
?????????1?????????????
000??111
0?1?0
000111????111000
```

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
```

Posted: **Thu Feb 10, 2011 10:00 pm**

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

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

Posted: **Wed Feb 16, 2011 9:21 am**

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

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

Posted: **Wed Feb 16, 2011 10:13 am**

finally got AC with my previous mention method

my method is

hope I am help to you all....

Happy coding~

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~
```

Happy coding~

Posted: **Fri Feb 20, 2015 8:53 pm**

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.

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.

Posted: **Mon Feb 23, 2015 11:36 pm**

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.

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.