Page 1 of 2

11234 - Expressions

Posted: Sat Jul 07, 2007 7:26 pm
by Kallol
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

Posted: Sat Jul 07, 2007 8:12 pm
by mf
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.

Posted: Mon Jul 09, 2007 3:48 am
by Timo
Please remove your code if it can get AC after clean the queue ^_^.

Posted: Mon Jul 09, 2007 4:47 pm
by Kallol
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.

Posted: Mon Jul 09, 2007 5:08 pm
by mf
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; }

Posted: Mon Jul 09, 2007 6:23 pm
by Kallol
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 :)

Posted: Wed Jul 25, 2007 6:45 pm
by albet_januar

Code: Select all

delete

Time Limited Exceeded (TLE)

Posted: Fri Dec 14, 2007 10:07 pm
by jjtse
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

}




Re: Time Limited Exceeded (TLE)

Posted: Sat Dec 15, 2007 12:18 pm
by sclo
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.

11234 - Expressions Java Compilation Error

Posted: Sun Apr 28, 2013 12:42 am
by dallen
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;
//	}

}


Re: 11234 - Expressions Java Compilation Error

Posted: Fri May 17, 2013 3:52 am
by brianfry713
That is AC code. You can click "My Submissions" to see the reason for a Compile Error.

Re: 11234 - Expressions Java Compilation Error

Posted: Fri May 17, 2013 7:40 pm
by dallen
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.

Re: 11234 - Expressions

Posted: Sat Jun 01, 2013 4:51 pm
by @li_kuet
Who are getting WA try this case

Code: Select all

1
abDcdEBefFghGCA
answer should be

Code: Select all

hgfedcbaGFEDCBA

11234 - Expressions

Posted: Sun Aug 04, 2013 11:56 am
by SIO__Five
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;
}

Re: 11234 - Expressions

Posted: Tue Aug 06, 2013 12:47 am
by brianfry713
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.