551 - Nesting a Bunch of Brackets

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

Moderator: Board moderators

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Feb 08, 2004 12:16 pm

Hi Mahmud,

Your output does not seem to be right.

Example:
()*()
this should give a negative result----- but your one doesn't;
the corresponding closing of the first should be the last.
Hope it helps.
:wink:

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

Not Specified

Post by Mahmud776 » Tue Feb 10, 2004 11:40 am

Hi Sohel,
I think the above sample inputs and outputs are not wrong as I got accepted with this inputs and outputs. You said,
()*()
this should give a negative result----- but your one doesn't;
the corresponding closing of the first should be the last.
But, I think, here () is followed by a separate character * and this sequence is followed by another ().As () is a correct sequence so, I think, ()*() should give positive answer. After all I got accepted in this way.

Mahmud

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Fri Mar 05, 2004 4:07 pm

Hi,

I'm getting WA for this problem.

Can someone explain me why these 2 inputs give different outputs.
((**)()a+b)[(a){a+n}](*
((**)()a+b)[(a){a+n}](

And I'm not sure what this statement means?
"If the expression is not properly nested your program should determine the position of the offending bracket, that is the length of the shortest prefix of the expression that can not be extended to a properly nested expression."

Thanx,
angga888

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

don't think so

Post by sohel » Sun Mar 07, 2004 6:59 am

Hi again,
((**)()a+b)[(a){a+n}](*
((**)()a+b)[(a){a+n}](
How do you know these two inputs give two different outputs---
my AC program gives the same output..... very strange.
And I'm not sure what this statement means?
"If the expression is not properly nested your program should determine the position of the offending bracket, that is the length of the shortest prefix of the expression that can not be extended to a properly nested expression."
this is actually the first bracket (from left) that is out of position.

eg. ())[]9()909

it will be impossible for a valid combination to emerge after the third bracket ..).. therefore this particular one is the offending one.

Hope it helps.
:P

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

Not specified

Post by Mahmud776 » Sun Mar 07, 2004 2:10 pm

Hi:
Sohel is correct.

Here, '(*' has to be considered as different characters
as '(*' is not completed and they are the last two characters in
that sequence.
((**)()a+b)[(a){a+n}](*

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sun Mar 07, 2004 2:39 pm

Hi,
How do you know these two inputs give two different outputs---
my AC program gives the same output..... very strange.
I look at the first post in this topic and I've got AC now. :D
Thanks for your reply.

Regards,
angga888

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

Post by Rajib » Sun Jun 20, 2004 4:34 pm

Which one is wrong, Problem description or the sample input ????
Last edited by Rajib on Sun Jun 20, 2004 4:40 pm, edited 1 time in total.

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

Post by Rajib » Sun Jun 20, 2004 4:36 pm

When I get a WA in the problem, then I check out some help for me and I test the sample input given by Mahmud776. I was mad with his sample input because I fail to match with his output. But those are output from his AC code. So I was not confident to say his output was wrong.

But finally understanding the problem properly I get AC and find that his output was wrong. I think Judge Data is not strong enough to test the solution of problem. Though I think the problem was little confusing because it ask for the minimum prefix which can't extended as correct one.

For example:

()()(a+b)(

Output for it: NO 11

But that expration can be extended as correct one like; ()()(a+b)()
So output should be 'YES' rather 'NO 11' :oops:

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

551

Post by Emilio » Sun Oct 17, 2004 8:38 pm

Hi:
Can anyone help me?
I only need the outputs for this inputs, or others inputs/outputs with some special cases.
Thanks!

Input:

(*adf(y)(*
(*adf(y)(
(a*)
)()
*)()
ads()asdf
(***)
(**
({{]}]
(**){*{]}]
<><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)><
<sgf(sfg[sfg{sfg(*sfgsdfg*)dhj}]dfh)>(*
[**
((((())
(*(*(*(**)*)
(**********(
(*a++(*)
(*a{+}*)
(*)
(**)
((**))
((()))
{}{}{}{}{}{}{}{}{
{{{}[()((**))][][]}}
(())))
(***)
{*(())(()*)*}
{adfadf[adfadf(adfa(*adfadf*)adfaf)(*afdsf*)]adfadf}
(AADFASDFADSF)

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Thu Oct 21, 2004 7:53 am

No 9
No 9
No 3
No 1
No 1
Yes
Yes
No 3
No 4
No 6
No 4
Yes
No 37
No 37
No 4
No 8
No 7
No 12
No 6
Yes
No 2
Yes
Yes
Yes
No 18
Yes
No 5
Yes
No 10
Yes
Yes
if u can think of it .. u can do it in software.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Fri Oct 22, 2004 6:54 am

Thanks very much jagadish!
I got AC to the first! :D
I only had a small mistake!
Thanks!

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Fri Apr 08, 2005 4:28 am

Dear Mahmud776,
one of the sample cases you have posted here is wrong. for the input

Code: Select all

((**)()a+b)[(a){a+n}](
you said the output is

Code: Select all

NO 20
which is wrong. my AC code gives output

Code: Select all

NO 21
I guess this is a silly typo. Again, for the case

Code: Select all

((**)()a+b)[(a){a+n}](*
I considered the last '(*' as one symbol and that is what one is supposed to for all the cases in this problem.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon May 30, 2005 3:38 pm

Apparently the output logic of this problem is quite arguable.

I tend to agree with Rajib's theory that for
cases like

Code: Select all

()()(a+b)(
the output should be

Code: Select all

YES
because strings of this kind can be extended so that they
represents a valid bracketing ( a valid expression ).
I mean they have no prefix for which no extension is possible.
Anyway. Apparently there's some mess about this problem.

But I doubt the Judge's tests follow this
logic ( Rajib's theory ).

I found another thread where there's sufficient I/O.

http://online-judge.uva.es/board/viewtopic.php?t=6724

jagadish has posted some output there which
is quite close to mine although it differs in some cases.

We differ in the following test cases:
input

Code: Select all

[**
((((())
(*(*(*(**)*)
my output

Code: Select all

NO 2
NO 4
NO 3
his output

Code: Select all

No 4 
No 8 
No 7
It would be nice if someone having ACC program could
verify and say which one of these outputs is correct. I hope
he/she won't come up with a new theory about
how a correct answer should look like :)

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon May 30, 2005 5:31 pm

Can someone explain these outputs

Output

Code: Select all

No 3
No 4 
No 8 
No 7 
for the following

Input

Code: Select all

(**
[**
((((())
(*(*(*(**)*)

My WA program currently prints

Output

Code: Select all

NO 2
NO 2
NO 4
NO 3
for that sample input.

Could someone explain if/why my output is wrong
and if/why the first output ( from jagadish ) is OK ?

These are the only test cases in which my Output differs
from jagadish's Output for his sample Input ( see above ).

I have made also a post in
http://online-judge.uva.es/board/viewtopic.php?t=4897
but that thread is even more confusing. The theory of Rajib
seems reasonable to me but when I follow it the Judge still
gives me WA. Although I would say this interpretation is the
most correct one ( logically ).
Thanks in advance.

Any help is welcome.

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Mon May 30, 2005 8:43 pm

My output is same as Jagadish.

Post Reply

Return to “Volume 5 (500-599)”