673 - Parentheses Balance

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

Moderator: Board moderators

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

673 Accepted but so long time. but I think my algorithm is..

Post by 20717TZ » Fri May 14, 2004 9:09 am

673 Accepted but so long time. CPU=0:07.137 My God!!!!!
I think my algorithm is so simple and it should execute quickly, but I am wrong.
Why?
help me plzzzzzzz!

[cpp]
#include <stdio.h>
#include <string>
using namespace std;

int fnBalance(string s)
{
int place;

for(int i=0;s.find("[]")!=-1 || s.find("()")!=-1;i++)
{
while((place=s.find("[]"))!=-1)
s.erase(place,2);
while((place=s.find("()"))!=-1)
s.erase(place,2);
}
return s.length()==0?1:0;
}

void main()
{
FILE* fp=fopen("Input.txt","r");
int n; char c; string s;

fscanf(fp,"%d",&n);
c=fgetc(fp);//fgets(cs,MAX,fp);//skip a '\n'
for(int i=0;i<n;i++)
{
s="";//reset
while((c=fgetc(fp))!='\n' && c!=EOF)
s+=c;
printf("%s\n",fnBalance(s)?"Yes":"No");
}
}
[/cpp]
I Believe I Can - leestime.com

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri May 14, 2004 12:30 pm

1. don't use STL - think how it can be done without string
2. don't post code, which is accepted - it's spoiler - anyone can submit it and get Accepted without any work - that's not fair. Please change code to description of used algorithm :-)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

Post by 20717TZ » Mon May 24, 2004 9:05 am

Thank you
I am frustrated with STL
is it OK?
i think time is everything in a contest, STL can supply it to me.
but its efficiency.... I just don't konw....
I Believe I Can - leestime.com

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Use STL sensably

Post by Mohammad Mahmudur Rahman » Sat May 29, 2004 1:09 pm

Well, STL provides some important resources & good use of it should be done whenever appropriate. It eases the work (Surely you don't need to re-invent the wheel.) But again, as it is built on the object oriented structure, it's surely a bit slow. So, you really need not use STL components such as a string class which you could have easily done with some backdated though more efficient techniques such as the array based C string. In fact, you must understand which one is more important in a particular stage, efficiency or ease of coding.
You should never take more than you give in the circle of life.

JaviGS
New poster
Posts: 6
Joined: Thu Aug 05, 2004 5:24 pm
Location: Spain

673 - Accidental discovery

Post by JaviGS » Sun Aug 08, 2004 7:55 pm

I recently discovered accidentally that, in every input of the judge, any string that contains the substring "[]" is correct. Am I right? I think that if this is correct the judge should provide more extra input to avoid such lucky incidents as mine.
Regards
Javi

User avatar
tetuya
New poster
Posts: 14
Joined: Thu May 27, 2004 2:31 pm

Why WA? 673 Parentheses Balance

Post by tetuya » Mon Aug 09, 2004 5:54 pm

I got Wrong Answer too.
my program work fine too.
did you find the cause of WA?

[cpp]
#include <iostream>
#include <string>
#include <cstdio>
#include <functional>
#include <algorithm>
using namespace std;
char buff[200];

void func() {
string str;
cin.getline(buff,50);
string::size_type st;
str = buff;
int end;

do {
end = 0;

st = str.find("[]",0);
if(st==string::npos) end++;
else str.erase(str.begin()+st,str.begin()+st+2);

st = str.find("()",0);
if(st==string::npos) end++;
else str.erase(str.begin()+st,str.begin()+st+2);

} while(end < 2);

if(str.length()==0) cout << "Yes" << endl;
else cout << "No" << endl;
}
int main() {

int n;
cin >> n;
cin.getline(buff,50);//ignore \n

while(n--) {
func();
}
}
[/cpp]

User avatar
tetuya
New poster
Posts: 14
Joined: Thu May 27, 2004 2:31 pm

Post by tetuya » Thu Aug 19, 2004 5:29 pm

I used stack and got AC.but, i cant figure out why my first program cant get AC.
thanx :D

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Thu Sep 02, 2004 12:04 am

Hiii htl, the bug in your code is check if the stack its empty after all the push and pops , i just add this in your code and give AC

[c]
Before :
if(error)
printf("No\n");
else
printf("Yes\n");

After :
if(error)
printf("No\n");
else
if(top == 0)

printf("Yes\n");
else
printf("No\n");[/c]
with this change you get AC
Hope it helps :D
Keep posting [/c]

Ivo Sluganovic
New poster
Posts: 12
Joined: Tue Sep 21, 2004 10:08 pm

673->parenthenses ballance WA (plz help!)

Post by Ivo Sluganovic » Thu Oct 28, 2004 11:42 pm

I am frustrated, I tried every possible input, but I still keep on getting WA.
Does anybody have a clue what is wrong with my code?
Is it something with the classes?
Please help!

[c]
I got AC!
[/c]
Last edited by Ivo Sluganovic on Sat Oct 30, 2004 9:03 am, edited 1 time in total.

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

Post by Junayeed » Fri Oct 29, 2004 12:42 am

Try this input

Code: Select all

3 
) 
() 
)( 
Output

Code: Select all

No 
Yes 
No 
Hope this will help.
Junayeed

Ivo Sluganovic
New poster
Posts: 12
Joined: Tue Sep 21, 2004 10:08 pm

Post by Ivo Sluganovic » Fri Oct 29, 2004 4:43 pm

Thanks Junayeed, but it works perfectly for your input.

Could you post more inputs?

Thanks!

Junayeed
New poster
Posts: 50
Joined: Sat Oct 26, 2002 9:02 am
Location: Dhaka, Bangladesh

Post by Junayeed » Fri Oct 29, 2004 6:48 pm

Try this

Input

Code: Select all

([)] 
( 
()( 
[()
Output

Code: Select all

No
No
No
No
And another thing, be ware of string length. It should be at least 128
Junayeed

Ivo Sluganovic
New poster
Posts: 12
Joined: Tue Sep 21, 2004 10:08 pm

Post by Ivo Sluganovic » Sat Oct 30, 2004 9:02 am

I reallized where my mistake was!

In some inputs like "(((])", I would print NO two times!

Thanks anyway!

.pandre.
New poster
Posts: 9
Joined: Mon Nov 08, 2004 10:58 pm
Location: Coimbra, Portugal

673 - can't understand why WA... :(

Post by .pandre. » Wed Nov 10, 2004 11:50 am

Hi
I've seen all post in this forum and tried every input people told albout and got the rigth output, but the judge keeps saying my answer is not correct.
Can anyone help me?

here is my code:

[java]
import java.io.*;

class Main{

public static void main(String args[]){

String s;

//read the number of inputs
int n = Integer.parseInt(ReadLn(25).trim());

//for each input
for(int x=0; x<n; x++) {

//read the string
s = ReadLn(135).trim();

//if the number of elements is odd
if (s.length() % 2 != 0)
System.out.println("No"); //then it's incorrect
else {

//go through all caracters from the string
for(int i=0;i<s.length()-1;i++) {

//if the sequences () or [] exist in the string
if((s.charAt(i)== '(' && s.charAt(i+1) == ')') ||
(s.charAt(i)== '[' && s.charAt(i+1) == ']')){

//remove them
s = s.substring(0,i) + s.substring(i+2);

//and start from the beggining
i=0;
}
}

if(s.equals("") || s.equals("()") || s.equals("[]"))
System.out.println("Yes");
else
System.out.println("No");
}
}
}

static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}
}[/java]

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Wed Nov 10, 2004 4:58 pm

hmmm, everything looks correct to me. Just some comments:
Have you tried the special case of empty lines as input? Maybe you should also exclude the '\r' character in the readline function? And doesn't s.substring(i+2) give an exception when applied at the end of the string s?

Post Reply

Return to “Volume 6 (600-699)”