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

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

Moderator: Board moderators

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11988 RE why?

Post by lighted » Fri Sep 19, 2014 12:10 pm

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]
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

sajal2k8
New poster
Posts: 16
Joined: Mon Nov 18, 2013 5:15 pm

Re: 11988 RE why?

Post by sajal2k8 » Fri Sep 19, 2014 12:53 pm

Getting wrong answer now. Any critical input?

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 11988 RE why?

Post by lighted » Fri Sep 19, 2014 1:36 pm

Use search and post in existing thread.
v1n1t wrote:
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. 8)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

alecassis
New poster
Posts: 10
Joined: Sat Sep 20, 2014 6:36 am

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

Post by alecassis » Tue Nov 04, 2014 5:47 am

Deleted after AC :D

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

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

Post by Shahidul.CSE » Tue Dec 02, 2014 7:20 pm

this problem can be easily solved by using c++ list
Last edited by Shahidul.CSE on Mon Sep 07, 2015 9:10 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

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

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

Post by brianfry713 » Wed Dec 03, 2014 1:01 am

Use a linked list.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

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

Post by lighted » Wed Dec 03, 2014 6:34 pm

I read each line into char s[100001]. Then recursively printed in right order. :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

uohzxela
New poster
Posts: 4
Joined: Thu Jan 01, 2015 2:51 pm

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

Post by uohzxela » Fri Jan 02, 2015 12:47 am

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

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

Post by lighted » Sat Jan 03, 2015 12:07 pm

Try using BufferedReader and BufferedWriter. This link may be useful.
http://apps.topcoder.com/forums/;jsessi ... =3#1751359
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

gautamzero
New poster
Posts: 32
Joined: Fri Oct 10, 2014 1:10 pm
Location: Sylhet, Bangladesh

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

Post by gautamzero » Tue Jan 06, 2015 9:57 pm

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

Code: Select all

erased
Last edited by gautamzero on Wed Jan 07, 2015 1:10 pm, edited 1 time in total.
None but a fool is always right..
so don't be upset when u r wrong..

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

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

Post by brianfry713 » Wed Jan 07, 2015 3:16 am

For the sample input you're printing an extra blank line at the end.
Check input and AC output for thousands of problems on uDebug!

gautamzero
New poster
Posts: 32
Joined: Fri Oct 10, 2014 1:10 pm
Location: Sylhet, Bangladesh

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

Post by gautamzero » Wed Jan 07, 2015 1:11 pm

thnx... :D
None but a fool is always right..
so don't be upset when u r wrong..

Ranchho
New poster
Posts: 1
Joined: Wed Sep 30, 2015 9:40 pm

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

Post by Ranchho » Wed May 04, 2016 6:51 am

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;
}

Post Reply

Return to “Volume 119 (11900-11999)”