I can’t seem to visualise this part
U(A) + U(B) - U(A intersection B)
Which is equal to
U(A) + U(B) - (U(A union B) - U(A) - U(B))
Isn’t U(A intersection B) supposed to be = to U(A) + U(B) - U(A union B)
I can’t seem to visualise this part
U(A) + U(B) - U(A intersection B)
Which is equal to
U(A) + U(B) - (U(A union B) - U(A) - U(B))
Isn’t U(A intersection B) supposed to be = to U(A) + U(B) - U(A union B)
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();
});
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
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”
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.
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
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.
thank you sir… accepted…
my nlogn passed
oops there was a silly mistake, got AC learnt a lot from this question