11920 - 0 s, 1 s and ? Marks

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

11920 - 0 s, 1 s and ? Marks

Post by receme » Sun Feb 06, 2011 9:12 pm

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

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11920

Post by zobayer » 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

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...
You should not always say what you know, but you should always know what you say.

Shinigami
New poster
Posts: 1
Joined: Tue Feb 08, 2011 11:31 am

Re: 11920

Post by Shinigami » Tue Feb 08, 2011 11:35 am

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

lgarcia
New poster
Posts: 16
Joined: Mon Sep 14, 2009 7:49 pm
Location: Venezuela

Re: 11920

Post by lgarcia » Tue Feb 08, 2011 3:23 pm

My critical input was this:

Code: Select all

1
00??0?11
Output:

Code: Select all

Case 1: 2

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

Re: 11920

Post by receme » 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.

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

Re: 11920

Post by receme » 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.

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

Re: 11920

Post by receme » Wed Feb 09, 2011 9:47 am

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
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11920

Post by suneast » Thu Feb 10, 2011 11:28 am

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:

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11920

Post by zobayer » 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.
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11920

Post by zobayer » Thu Feb 10, 2011 8:01 pm

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
You should not always say what you know, but you should always know what you say.

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

Re: 11920

Post by receme » 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.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11920

Post by suneast » 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... :oops:

any help will do, thx in advance :)

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11920

Post by suneast » Wed Feb 16, 2011 10:13 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » 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.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » 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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 119 (11900-11999)”