TASTR - Editorial

Can someone help me with the stdin and stdout for node.js. My code is as follows

process.stdin.resume();

process.stdin.setEncoding(‘utf8’);

process.stdin.on(‘data’, function (chunk) {
var lines = chunk.toString().split(’\n’);

var stringDiff = function(a,b){
	var aSet = getAllSubstring(a);
	var bSet = getAllSubstring(b);
	var nSet = difference(aSet, bSet);
	nSet = nSet.concat(difference(bSet, aSet));
	
	return nSet.length;
}

var difference = function(a,b){
	var nSet = [];
	for(var i in a){
		var found = false;
		for(x in b){
			if(a[i] === b[x]){
				found = true;
				break;
			}
		}
		
		if(!found){ nSet.push(a[i])};
	}
	return nSet;
}

var getAllSubstring = function(s){
	var aSet = [];
	var i = 1;
	var j = 0;
	while(i<=s.length&&j<s.length){
		var next = s.substring(j,i);
		if(aSet.indexOf(next)<0){
			aSet.push(next);
		}
		
		
		if(i===s.length){
			j++;
			i = j+1;
		}else{
			i++;
		}
	}
	return aSet;
}

var diff = stringDiff(lines[0], lines[1]);
process.stdout.write(diff+'\n');
process.exit();

});

@anton sir would you please tell me where is my code failing here’s my code :frowning:

@anton_lunyov : sir please help me every time i get a run time error(SIGSEGV)…

http://www.codechef.com/viewsolution/1966634

hello,
could you just tell me weather my code’s output is correct or not, irrespective of time exceed error…

why doesnt work?

module Main where
 
import Data.List
import System.Exit
 
 
al1 xs = nub . concat . map (drop 1 . inits) . tails $ xs
 
cmp xs xz = [ x | x <- ((al1 xs)++(al1 xz)), notElem x (intersect (al1 xs) (al1 xz) )] 
   
 
main = do
    line <- getLine
    line2 <- getLine
    putStr $ show $ length $ cmp line line2
    exitWith ExitSuccess

This is my code in python. it works fine on my system but dont know why it is not working in codechef

http://ww2.codechef.com/viewsolution/2075046

getting run time error NZEC. first submission in codechef. so dont know much abt online compilers. plz help me out sir CodeChef: Practical coding for everyone

Wow… that was a quite a sleek approach… Nice one

This problem really showed our “level” :slight_smile:

1 Like

I did the same thing as the tester . My solutions (during the contest[CodeChef: Practical coding for everyone]) and after the contest with some optimizations (CodeChef: Practical coding for everyone) both TLE … Is this too strict for Java ?
EDIT: I think he has a better Suffix array function.

My O(n*(logn)*(logn)) passes !

Yes @acmonster construct LCP array using hashes in O(N log^2 N) time. We can compare two suffixes in O(log N) time using hashes. So we can sort them in O(N log^2 N) time. And then calculate LCP array in O(N log N) time.

A very good pdf on suffix arrays for contest can be found here (http://www.stanford.edu/class/cs97si/suffix-array.pdf)

Another source is MAXimal :: algo :: Суффиксный массив but make sure you open it in Chrome.

1 Like

stanford link is not working!!!

In the stanford link ‘)’ is part of the hyperlink pasted here . Remove that and paste the link in your browser and you will able to access the pdf .
Or use this link : http://www.stanford.edu/class/cs97si/suffix-array.pdf

1 Like

Try large test where both strings have equal characters.
The first test in the system has the form
string(99990,‘x’)
string(99969,‘x’)
and the answer obviously is 21,
while your answer is 25769803797.

3 Likes

thank you sir…:slight_smile: accepted…

my nlogn passed

oops there was a silly mistake, got AC :slight_smile: learnt a lot from this question

works fine here runs but (time exceed)
import List
Import System