11920  0 s, 1 s and ? Marks
Moderator: Board moderators
11920  0 s, 1 s and ? Marks
Anyone can give some critical test case??? I got continuous WA...plz help....

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 11920
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
You should not always say what you know, but you should always know what you say.
Re: 11920
My critical input was this:
Output:
Code: Select all
1
00??0?11
Code: Select all
Case 1: 2
Re: 11920
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
Re: 11920
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

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 11920
@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.
You should not always say what you know, but you should always know what you say.

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Re: 11920
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
You should not always say what you know, but you should always know what you say.
Re: 11920
hi, all
after struggle for this problem a few days, I still keep getting WA...
my method is quite simple
bsearch 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
bsearch 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
Re: 11920
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
* bsearch 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 bsearch 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~

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11920  0 s, 1 s and ? Marks
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.
Check input and AC output for thousands of problems on uDebug!

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11920  0 s, 1 s and ? Marks
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.
Check input and AC output for thousands of problems on uDebug!