11988 - Broken Keyboard (a.k.a. Beiju Text)

[lighted]

Each test case is a single line containing at least one and at most 100,000 letters

Increase array limit

Code: Select all

strt[100010]

[sajal2k8]

Getting wrong answer now. Any critical input?

[lighted]

Use search and post in existing thread.

Try the gift I/O, the link is at:
http://uva.onlinejudge.org/index.php?op ... ontest=278

I'm enclosing links to the input / output that brianfry713 mentioned above and that I found very useful during testing / debugging. I'm unable to post the actual input and output here since it's too big.

(Link to) Input:
http://pastebin.com/33Yd2Xz2

(Link to) AC Output:
http://pastebin.com/2gRmgyZB

It will be good if you remove all your codes after getting accepted.

[alecassis]

Deleted after AC

[Shahidul.CSE]

this problem can be easily solved by using c++ list

[brianfry713]

Use a linked list.

[lighted]

I read each line into char s[100001]. Then recursively printed in right order.

[uohzxela]

Hey guys, need your help to optimize my Java solution. I used a linked list (Java standard, doubly linked list) and an iterator for indexing when the HOME key is pressed.

I'm pretty sure the operations following both HOME and END keys are O(1).

Following END key, beijuText.add(c) is O(1) since the list is doubly linked list.

Following HOME key, initially I used beijuText.add(pointer++, c) with pointer initialized to 0. However I found out that this operation will take O(N) time since the list needs to traverse from index 0 prior to adding the new element. Therefore, I initialized an iterator pointing before the first element in the list and any consecutive additions will increase the iterator index, making this operation O(1). Correct me if I'm wrong.

I still got TLE in the end. I suspect this is related to the slowness in I/O.

Any ideas?

Code: Select all

class Main {
	public static void main(String args[]) throws IOException {
		PrintWriter out = new PrintWriter(System.out);
		Scanner sc = new Scanner(System.in);
		boolean isHome = false;
		while(sc.hasNext()) {
			char[] inputChars = sc.nextLine().toCharArray();
			LinkedList<Character> beijuText = new LinkedList<Character>();
			ListIterator<Character> it = beijuText.listIterator();
			for(Character c : inputChars) {
				if (c == '[') {
					isHome = true;
					it = beijuText.listIterator(0);
					continue;
				}
				if (c == ']') {
					isHome = false;
					continue;
				}
				if (!isHome) {
					beijuText.add(c);
				} else {
					it.add(c);
				}
			}
			for (Character c1 : beijuText) {
				out.print(c1);
			}
			out.print("\n");

		}
		out.close();
		sc.close();
	}
}

[lighted]

Try using BufferedReader and BufferedWriter. This link may be useful.
http://apps.topcoder.com/forums/;jsessi ... =3#1751359

[gautamzero]

getting WA...
i tried all kind of input..

Code: Select all

erased

[brianfry713]

For the sample input you're printing an extra blank line at the end.

[gautamzero]

thnx...

[Ranchho]

i am getting Run Time Error...why ?!

Code: Select all

#include <bits/stdc++.h>

using namespace std;

#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
#define FN(s,c) (int)s.find(c)
/*************************************************/
struct node {
	char c;
	node* next;
};
int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	string a;
	while (getline(cin, a)) {
		char c = ']';
		node* head = NULL;
		node* tail = NULL;
		node* temp_head = NULL;
		node* temp_tail = NULL;
		for (int i = 0; i < SZ(a); ++i) {
			if (a[i] == '[') {
				c = '[';
				if (temp_head != NULL) {
					head = temp_head;
					temp_head = NULL;
					temp_tail = NULL;
				}
				continue;
			}
			if (a[i] == ']') {
				c = ']';
				if (temp_head != NULL) {
					head = temp_head;
					temp_head = NULL;
					temp_tail = NULL;
				}
				continue;
			}
			node* temp = new node;
			temp->c = a[i];
			
			// push_back
			if (c == ']') {
				temp->next = NULL;
				if (head == NULL) {
					head = temp;
					tail = temp;
				} else {
					tail->next = temp;
					tail = temp;
				}
			}
		
			//push_front
			else {
				temp->next = head;
				if (temp_head == NULL) {
					temp_head = temp;
					temp_tail = temp;
				} else {
					temp_tail->next = temp;
					temp_tail = temp;
				}

			}
		}
		if (temp_head != NULL) {
			head = temp_head;
		}
	
		//print the line
		node* ptr = head;
		while (ptr != NULL) {
			cout << ptr->c;
			ptr = ptr->next;
		}
		cout << endl;
	}
	return 0;
}