11234 - Expressions

All about problems in Volume 112. 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
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

11234 - Expressions

Post by Kallol » Sat Jul 07, 2007 7:26 pm

i am getting runtime error signal 11 (SIGSEGV). for this code :
But I cant find why ??

Anybody to help me??

Code: Select all

removed after AC
Last edited by Kallol on Mon Jul 09, 2007 6:25 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Jul 07, 2007 8:12 pm

You don't clean your queue - Q.front and Q.back increase with every test, and access memory beyond array boundaries.

STL's queue is fast enough for this problem, btw.

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Mon Jul 09, 2007 3:48 am

Please remove your code if it can get AC after clean the queue ^_^.
"Life is more beautiful with algorithm"

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Mon Jul 09, 2007 4:47 pm

Thank you very much :) , I did not notice that is not being cleaned. Now I have cleaned it. But unfortunately , this time I am getting WA.

here is the changed code ( just cleaned the queue)

Code: Select all

removed after AC

To mf, thank you very much for your advice , I am at very beginning stage of STL learning. I tried to use a STL queue of the pointers of the objects of my self-defined class 'node' . But when popping , the compiler threw an error that the pop function is returning a void type pointer which cannot be casted to my object's pointer. So, I had to go back to my straight forward queue class.
Last edited by Kallol on Mon Jul 09, 2007 6:24 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Jul 09, 2007 5:08 pm

Now your array 't' doesn't get cleaned between test cases. Try this input to see that in action.

Code: Select all

3
xyPzwIM
abcABdefgCDEF
xyPzwIM
I tried to use a STL queue of the pointers of the objects of my self-defined class 'node' . But when popping , the compiler threw an error that the pop function is returning a void type pointer which cannot be casted to my object's pointer.
Use queue::front() to access the head element of the queue.
There's no member function in STL's queue that both extracts the head and returns it, but you could write one like this:

Code: Select all

template<typename T>
T pop(queue<T> &q) { T x = q.front(); q.pop(); return x; }
Last edited by mf on Mon Jul 09, 2007 9:40 pm, edited 1 time in total.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Mon Jul 09, 2007 6:23 pm

Oh My GOD! What is going on with me !! I made this code during the contest and could not get AC for this 2 silly mistakes !! really frustrating. If some problems are missed which I really cant solve doesnt cause me that much pain , but this type of missing is really embarrassing ! :cry:

Anyway , mf , You are really of great help, Thank you !

and thanks again for STL advice . It sounds cooler now :)
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:

Post by albet_januar » Wed Jul 25, 2007 6:45 pm

Code: Select all

delete

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Time Limited Exceeded (TLE)

Post by jjtse » Fri Dec 14, 2007 10:07 pm

Does anyone know more ways to optimize this code? I already optimized my queue usage. I'm suspecting I can do my string concatenations faster, but I don't know how to do it. Any ideas how I can get this faster?


Here's the code:

Code: Select all


#include <iostream>
#include <string>

//11234.cpp

using namespace std;

int t;
string q[990000];
string ans;
int idx;
int head;

void push(string s){
	q[idx++] = s;
}

string pop(){
	string s = q[head];
	head++;
	return s;
}

bool isEmpty(){
	if (head >= idx)
		return true;
	else
		return false;
}


int numOfOps(string s){
	int cnt = 0;
	int len = s.length();

	for (int i=len -1; i>=0; i--){
		if (s[i] < 95)  {//operator
			cnt ++;
			continue;
		}
		else
			break;
	}

	return cnt;
}


int main(){
	
	string s;
	int len;
	int skip;

	cin >> t;

	for (int i=0; i<t; i++){
		cin >> s;
		idx = 0;
		head = 0;
		push(s);
		ans = "";
		while (!isEmpty()){
			s = pop();
			len = s.length();
			if (s[len-1] < 95){
				ans = s[len-1] + ans;
				skip = numOfOps(s);
				if (skip > 1){
					string right = s.substr(len-2*skip, 2*skip-1);
					string left = s.substr(0, len-2*skip);
					push(left);
					push(right);
				}
				else{
					push(s.substr(0, len-1));
				}
			}
			else{
				for (int j=0; j<len; j++)					
					ans = s[j] + ans;
			}
		}		//end while

		cout << ans << endl;
	}		//end for

}




sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: Time Limited Exceeded (TLE)

Post by sclo » Sat Dec 15, 2007 12:18 pm

jjtse wrote:Does anyone know more ways to optimize this code? I already optimized my queue usage. I'm suspecting I can do my string concatenations faster, but I don't know how to do it. Any ideas how I can get this faster?
You are copying string all the time, your algorithm is slow because of that.

dallen
New poster
Posts: 7
Joined: Mon Apr 22, 2013 1:06 am
Location: Asunción, Paraguay

11234 - Expressions Java Compilation Error

Post by dallen » Sun Apr 28, 2013 12:42 am

I'm trying to upload my solution to problem #11234 but I keep getting CE from the Judge. Anyone experienced in Java willing to help? thanks.

Here's my code.

Code: Select all

//import java.io.File;
//import java.io.FileInputStream;
//import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

class Main {

	private static Stack<Character> stack = new Stack<Character>();

	public static void main(String[] args) /*throws FileNotFoundException*/ {
		//final long startTime = System.currentTimeMillis();
//		System.setIn(new FileInputStream(new File("test.txt")));

		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		
		StringBuilder output = new StringBuilder();

		while (sc.hasNextLine()) {
			String line = sc.nextLine();
			for (char c : line.toCharArray()) {
				stack.push(c);
			}

			Node tree = buildTree();
			output.append(tree.queueExpression() +  "\n");
			stack.clear();
		}
		
		output.deleteCharAt(output.length() - 1);
		System.out.println(output.toString());
		//System.out.println(System.currentTimeMillis() - startTime);
	}

	public static Node buildTree() {
		Character c = stack.pop();
		Node leftSubtree, rightSubtree;

		if (Character.isUpperCase(c)) {
			leftSubtree = buildTree();
			rightSubtree = buildTree();
		} else {
			return new Node(c);
		}

		return new Node(c, leftSubtree, rightSubtree);
	}

}

class Node {
	Character value;
	Node leftChild;
	Node rightChild;

	Node(Character value) {
		this(value, null, null);
	}

	Node(Character value, Node leftChild, Node rightChild) {
		this.value = value;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}

	public String queueExpression() {
		Queue<Node> frontier = new LinkedList<Node>();
		Stack<Character> visited = new Stack<Character>();
		frontier.add(this);

		while (!frontier.isEmpty()) {
			Node current = frontier.remove();
			visited.push(current.value);

			if (current.rightChild != null) {
				frontier.add(current.rightChild);
			}

			if (current.leftChild != null) {
				frontier.add(current.leftChild);
			}
		}

		StringBuilder sb = new StringBuilder();

		while (!visited.isEmpty()) {
			sb.append(visited.pop());
		}

		return sb.toString();
	}

//	@Override
//	public String toString() {
//		String str = "[value:" + value + ", left:" + leftChild.value
//				+ ", right:" + rightChild.value + "]";
//		return str;
//	}

}


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

Re: 11234 - Expressions Java Compilation Error

Post by brianfry713 » Fri May 17, 2013 3:52 am

That is AC code. You can click "My Submissions" to see the reason for a Compile Error.
Check input and AC output for thousands of problems on uDebug!

dallen
New poster
Posts: 7
Joined: Mon Apr 22, 2013 1:06 am
Location: Asunción, Paraguay

Re: 11234 - Expressions Java Compilation Error

Post by dallen » Fri May 17, 2013 7:40 pm

I already solved the problem. I don't know why the judge displayed "compilation error" but later it changed to "runtime error", BTW if you're curious the mistake in the code is not handling empty input the rest is correct and I got accepted when I fixed that. Thanks anyway for responding.

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 11234 - Expressions

Post by @li_kuet » Sat Jun 01, 2013 4:51 pm

Who are getting WA try this case

Code: Select all

1
abDcdEBefFghGCA
answer should be

Code: Select all

hgfedcbaGFEDCBA

SIO__Five
New poster
Posts: 2
Joined: Sun Aug 04, 2013 11:39 am

11234 - Expressions

Post by SIO__Five » Sun Aug 04, 2013 11:56 am

I already solve the problem, but got a "runtime error". Can anybody tell me why? Thanks!

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<stack>
using namespace std;
char str[10010],in[10010];
struct node
{
    char ch;
    node* lchild;
    node* rchild;
};
node* build(int n, char *in, char *str, node* u)
{
    if (n<=0) return NULL;
    int i=0;
    while(*(in+i)!=*str) i++;
    u=(node*) malloc (sizeof(node));
    u->ch=*str;
    u->lchild=build(i,in,str-n+i,u->lchild);
    u->rchild=build(n-i-1,in+i+1,str-1,u->rchild);
    return u;
}
void bfs(node* u)
{
    node* tree[20010];
    int front=0,rear=1,n=0;
    char cx[10010];
    tree[0]=u;
    while(front<rear)
    {
        node* temp=tree[front++];
        cx[n++]=temp->ch;
        if (temp->lchild!=NULL) tree[rear++]=temp->lchild;
        if (temp->rchild!=NULL) tree[rear++]=temp->rchild;
    }
    for (int i=n-1; i>=0; i--)
        cout<<cx[i];
    cout<<endl;
    return;
}
int main ()
{
    int t,len,i;
    cin>>t;
    while(t--)
    {
        memset(str,0,sizeof(str));
        cin>>str;
        stack<string> s;
        len=strlen(str);
        for (i=0; i<len; i++)
        {
            if (str[i]<='Z')
            {
                string t1,t2,temp;
                t1=s.top();
                s.pop();
                t2=s.top();
                s.pop();
                temp+=t1+str[i]+t2;
                s.push(temp);
            }
            else
            {
                string temp;
                temp+=str[i];
                s.push(temp);
            }
        }
        string temp;
        temp=s.top();
        while(!s.empty())
        {
            s.pop();
        }
        int j=0;
        memset(in,0,sizeof(in));
        for (i=temp.length()-1; i>=0; i--)
            in[j++]=temp[i];
        in[j]='\0';
        node* root=build(j,in,str+j-1,root);
        bfs(root);
    }
    return 0;
}

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

Re: 11234 - Expressions

Post by brianfry713 » Tue Aug 06, 2013 12:47 am

You call malloc but never free, maybe you are running out of memory.
You can solve this with only recursion. No queues, stacks, trees, or bfs is needed.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 112 (11200-11299)”