vangoor_bharath May be authors should add following testcase:
4 6 123412 561212 123634 781288 2 2 12 34Because my code fails for this but for all the available testcases it passes.
lvsz_ [deleted]
sansui u r right this testcase needs to be added.
wild_fire [deleted]
chakshup49 This test case works perfectly fine for me but test case# 3 fails.
aslam likewise
xxswisherxx331 Lol. Bra. You must check if they're in a column.
DaniloPeres My code failed in your example :)
Good observation #vangoor_bharath
CattleOfRa I was able to get full marks on this exercise from this simple test case. If I may add my own recommendation then I would suggest you take the 12 and 34 and add it to the row below.
4 6
123412
561212
123612
781234
2 2
12
34
Sorry don't know how to add a code block here.
bhgupta Hi @CattleOfRa The code should say yes or no for this test case?
CattleOfRa It should say yes. Last column and last row
Mehulnatu we have to compare 2D pattern not 1D i believe
hamaldonado Thank you! My code failed with your proposed test case. Once I fixed it, I was able to pass test case #5 :)
ATMaher This proposed test case also helped me pass #5. Thank you very much!
bildsoe_thomas [deleted]
jightuse @CattleOfRa thanks! It was the case I missed. Really good testcase.
muthuridennis Your test case got me through all the other test cases apart from testcase #5 which fails due to a timeout.
rohangupta_cs please refer to this and let me know where i can improve further
Coisox lol... thank you! this case give clue to my case 5
balajilitsv it should return "YES", right!! Balaji's Submission Check it please
MichaelChan I agree.It seems like there aren't any test cases checking for column offsets.Edit: I realized this test case should return "YES" (See the end of 2nd and 3rd row).
However, it seems like this test case needs to be added:
1 3 3 123 456 789 2 2 45 89
This should fail since the 45 in row 2 and 89 in row 3 is not aligned properly.
divi344 my code works for this case and also 2 other test cases mentioned above in this thread, but for test case-5, it shows "ABORTED". Any clue ?
candi3114 Does your algorithm pass test 6?If not review it with respect to the above example by @MichaelChan and test offline. If you pass this offline then you will pass test 5 & 6 on submission.
Gunjan4542 Sorry but my code is not passing testcase5 but it passes all the other test case.
Mandeep31 You might be accessing a memory location which is out of range.
candi3114 Very good and helpful point.
sabbispeak my code fails too for that example
clarke_gong Thanks to your case I found a flaw in my code which only failed me at test case 5! I was struggling on case 5!
thethirduniverse I agree, this helped me spot an error in my logic.
H1996 this works fine but fails case#5
ivan_onushkin Looks like something wrong with #5. Because when I run my code locally I have same correct answer
YES YES NO YES NO
T_NSI yes something is wrong with test case 5 because the last two cases are having the same input but it requires different outputs what is the matter with this case i dont please suggest me how to solve this problem
soumyabanerjee19 4 6 123412 561212 123634 781288 2 2 12 34
run your program for this input
ashokamit YES
i dont have problem for your input.
Program is getting Terminated due to timeout for input#5 its taking more than 3s .
Lasani i can't understand why its getting aborted.It must not be going in an infinite loop then what else may be the problem
ashokamit after going through all comments i found the string dimesnion is 1000*1000 and i have used simple brute force. thats why its taking so much time.
According to editorial, we have to use regex for pattern searching then only it will complete in estimated time.Lasani i have started coding just a month ago. what is this regex?
junjiezhang Agree with u. I view the #5 input and find it should output YES.
Marathon I had a similar experience. My code passed all test cases. But, it failed on the following input:
1
5 15
111111111111111
111111111111111
111111011111111
111111111111111
111111111111111
3 5
11111
11111
11110
H1996 If the answer is yes mine passed the above test case
Marathon My bug was the result of a dumb mistake, unlikely to have been made by others. So, I wonder if this is actually a useful discussion?
I could, on purpose, create bugs in code that pass the HackerRank test cases, but fail examples I create to try against the bugs.
If there are bugs that exist but are not caught by HackerRank's test cases, is that a shortcoming of those sets of test cases? Do we expect HackerRank to create new test cases everytime someone reports a test case that caused a program to fail when they ran it, but was not detected by HackerRank? If Yes, some could start a new hobby of creating bugs that HackerRank's test cases don't catch, and expecting HackerRank to spend time creating more test cases.
manty It's not a dumb mistake I would say. It's a very good corner scenario. For those who are still in fix as to what to do for this test case, note that you have to find the overlapping matches and for that you have to perform a 'lookahead' in your regex. e.g . In Python it as shown below:
str1 = '111111111111111'
str2 = '11111' -> This is variable
pattern = '(?=' + str2 + ')'
print([m.start() for m in re.finditer(str2, str1)])
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
meenuravi89 shouldn't the 'str2' in the print statement be replaced by 'pattern' as:
print([m.start() for m in re.finditer(pattern, str1)])
to get the correct output?
thomas154 yep mine too working for this
jcogs The test case for this shows me that I had a runtime error but when I used this as sample input to test on my own it works without a problem...what gives?
giuraso I was able to find a mistake in my code using a modified version of your test:
1
5 15
111111111111111
111111111111111
111111111111111
111111111111111
111111111111110
3 5
11111
11111
11110
Thank you!
P_DOX Try to go from last index to first index i.e from g[r][c] to g[1][1].
I too had faced the same problem.
KAAL_ZATHURA chill hain
deepakv158 Hi Bharath,
Did you specify the number of test cases T in the first line ? Maybe you missed adding that.
bdchambers79 Thanks, this helped me see the problem with test case #5.
Actually, I downloaded the test case so I could check it out, but with a 1000x1000 matrix it was too large.
Your sample demonstrated the edge case (hehehe) much more clearly!
123_cj good observation. code needs to be perfectly fine to pass this testcase. p.s my code passed your testcase.
123_cj good observation. code needs to be perfectly fine to pass this testcase. p.s my code passed your testcase.
thomas154 mine passed all test cases as well your's too
htplvynk missing number of test cases at the beginning ? 1 <--------------------- 4 6 123412 561212 123634 781288 2 2 12 34
thenanox this totally needs to be added.
One mate resolve this reading lines as string, and doing indexOf from pattern lines and checking indexOf of each line are equals than previous indexOf. Tests cases went all fine for him and obtained maximum score, but this test failed for him.
My solution checks matrix positions and this case works fine and tests too.
mingkaic using builtin substring find methods is not the problem. it's the implemention that really matters.
you can still use an optimized find method (c++/python) or indexOf (java/js) to check if the substring exists. just make sure to keep looking for additional substrings if a substring's already found in that given line.
I'd imagine this would extend to real life matrix problems, since real data tend to be clustered.
Ricroid Same here, my script use indexOf too and fail several times, later I realized that the problem was in
input_stdin_array = input_stdin.split("\n");adding this Regex in the split method /\r?\n/ will solve it.
My script with indexOf:
for(G_i = 0; G_i < R; G_i++){ max_index = G[0].length - P[0].length; for(k = 0; k <= max_index; k++){ match = 0; index = G[G_i].indexOf(P[0], k); if(index === -1 || G_i + r > R) continue ;
match++;
for(P_i=1; P_i index2 = G[G_i + P_i].indexOf(P[P_i], k); if(index2 !== index) break; match++;
} if(match === r) break; } if(match === r) break; } if(match === r) console.log("YES"); else console.log("NO");
ddeepika_297 thnx for the test case!! got full points after my pgm passed this test case.
enigman This is getting an YES for my code, though my code is failing for test case # 5 :(
hamaldonado This test case works for me. However test case #5 fails :(
shinzo working perfectly!!!
abhiank hey, thankx for that testcase.. my code was working for all cases apart #5, and since that test case was huge (1000x1000 grids), I couldnt figure out where the code was failing.. ur testcase helped me figure out the logic error.. thankx
Lasani my code also aborts for test case 5 my code is written in c.how to decrease the complexity? Help
cfelipe My code was not working in Test Case #5, but after using your suggestion as a custom test I was able to debbug my algotithm.
Fortunately it was a simple mistake, I was not checking the last rows/columns of the original grid.
fdiaz1321 This is what happened to me too! Thanks for sharing! If you didn't, I'd still be working on case 5 lol
DexterT [deleted]DexterT Author's test case #5 got me.
vangoor_bharath's proposed test case helped me debug a silly off-by-one error.
tanwar4 it works fine for me but other test case fails in set.
sashaFierce [deleted]finbel It works in mine. Though it took a while before I figured out that your input doesn't have a test-case number ^^
nobe0716 Thanks for this testcase
I wonder why this edge case is not preceded before the scalability test
iiiiii This is very helpful, thanks! but should add "1" in the beginning to specify number of test cases:
1 4 6 123412 561212 123634 781288 2 2 12 34soumyabanerjee19 thanks
manish637 My code works fine for all test cases and this one too
#include<iostream> using namespace std; int main() { int T,i; cin>>T; for(i=1;i<=T;i++) { int R,C,r,c,flag=0,final=0; cin>>R>>C; char G[R][C]; for(int j=0;j<R;j++) for(int k=0;k<C;k++) cin>>G[j][k]; cin>>r>>c; char P[r][c]; for(int j=0;j<r;j++) for(int k=0;k<c;k++) cin>>P[j][k]; for(int j=0;j<R;j++) for(int k=0;k<C;k++) { if(G[j][k]==P[0][0]) { int flag=1; if(C-k>=c) for(int pr=0;pr<r;pr++) { if(flag==0) break; for(int pc=0;pc<c;pc++) { if(G[j+pr][k+pc]==P[pr][pc]){ if(pr==r-1&&pc==c-1) final=1; flag=1; } else{ flag=0; break; } } } } } if(final) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }kanishkajoshi 3 3 3 1 2 3 4 5 6 7 8 9 2 2 5 7 8 9 u should try this....
r1singh answer for this testcase should be NO. coz the pattern that we hv to search is 5 7 8 9 and there is no such pattern.
kanishkajoshi bt ur code is giving YES for this try it once.. :(
r1singh i m getting NO for ur testcase try it again :)
manish637 can you explain me your input.
manish637 yes you are correct. Small modification to be made in 31st line.instead of starting pr=1 make it pr=0. I modified my code.
coolrohan123 Will you please explain me why you have taken char G[R][C] instead of int G[R][C], what is the difference?
sinfulexp In this particular exercise, there is no difference. A char has an ascii value of 1 character and an int will store its value. They both do the job here because the numbers are 0 to 9. If the value exceeds 10, then I think int will be the proper method.
coolrohan123 I tried this using int in place of char. But guess what it's wrong, I don't get it. There should not be any difference using int in place of char, but it won't work.Totally confused. Will you please clear my doubt.
sinfulexp Indeed, it should not be different in this case. It is valid to compare int to int and char to char. They both will tell you whether the value between both 2D arrays is the same or not.
coolrohan123 Why it is not working in this case?
sinfulexp I don't know what you may be doing wrong as I don't know how to view your code.
Lasani Because if u use a 2d integer array u have to give a space after each integer entered in a row. Whereas the test case requires u to input all nos in a row one after another without space which can be achieved only by taking an array of strings. Hope this helps
coolrohan123 Thanks for the help, but I still have doubt and it is: I did checked on my local compiler that if I store the matrix using a 2d integer array, it stores fine. I don't have to give any spaces. I checked it by printing the matrix stored, and the output is ok. So how the two are different? I hope you get my question.
sinfulexp Ahh, I see what lasani is saying. The test case give a number input of 9823, not separated by spaces. Unless you break it into 4 int, you'll have a single int of 9823 and that's wrong. however, if you have 9 8 2 3 as seperate integer within the array and still have problem. Then we'll have to look at your code.
In this case, reading it as a string allow us to get each char by accessing the string's index; thus, giving us 4 chars.
coolrohan123 Thanks, now I got it.
manish637 [deleted]
dhiraj_srivasta2 can you explain me please bro which logic you applied
SamarthAltair I'm sorry to say it but this is not a good code. You have used 4 nested for loop making the complexity n^4
ase429 Perhaps in the last three years he has learned how to code for better time complexity :)
anokbakn My code passes your test case, but my time complexity is probably not good.
sfink06 I was afraid of this, my though was that the program would see the first 12 that appeas on the second row, check for the pattern, and go on to the next row. I had to accumulate the indexes where the first line of the pattern appeared and check them all.
AlgorithmKing Similar to test case 15 for which my code fails... maybe I need to maintain a list or vector of pairs which will have the column nos. of the starting and ending indices of each row of the test grid found as present in the main grid. And so if the pattern really exists, then every pair of the list must be the same. Thus, check imposed... Right?
noobCoder11 why 2 2 for grid? shouldn't it be 1 2?
r1singh solution for all the testcase including urs..
for(int k=0;k<=R-r;k++) { end=c; start=0; while(end<=C){ if(G[k].substring(start,end).equals(P[0])){ for(int i=1;i<r;i++) { if(G[k+i].substring(start,end).equals(P[i])) count++; if(count==r-1)result=true; } } count=0; end++; start++; } } if(result) System.out.println("YES"); else System.out.println("NO"); }Dash_25 Thanx Buddy.........
rajeev11430 Awesome
avisrivastava [deleted]axel4u Nice idea. Thanks. It can be faster with standard search function like String.indexOf( String, int ), and some "break"s, when continuing loop is senseless:
String result = "NO"; out: for( int k = 0 ; k < R - r + 1 ; k++ ) { int start = 0; do { start = G[k].indexOf( P[0], start ); if( start > -1 ) { int count = 1; for( int i = 1 ; i < r ; i++ ) { if( G[k + i]. substring( start, start + c ).equals( P[i] ) ) count++; else break; } if( count == r ) { result = "YES"; break out; } start++; } } while( start > -1 ); } System.out.println( result );vonstuckrad Note that substring is inefficient for comparisons.
vonstuckrad Of course this will work, but you should note that using substring is very inefficient. It creates a copy of the string before comparing. Better to use charAt(index) and break out of the loop as soon as a comparison fails.
sinfulexp This case fails because it is missing the input for "test case #". It should have a 1 on top. 1 4 6 123412 561212 123634 781288 2 2 12 34
sagarchoudhary96 my code also fails for this testcase
sagarchoudhary96 my code is giving correct ans for this testcase but failing in test case 5
swatsag Did you add numeric number 1 at the top of this test case to denote 1 test case..?
thebatman1 my code passes for this but fails for test case #5
sagarchoudhary96 same here
Spraynard_K Lol you are so mean for having that testcase added! :3 It took me another half hour to try and get my code to work!
Australianfrog Mine passed your test!
RajaCEGian Success and Thanks for the test case . I thought it needed sophisticated string matching but it worked without TLE despite using 4 for loops
language:c++11
Amudala My code Passed all the tests cases including the above test case.
In case if it helps:
https://www.hackerrank.com/challenges/the-grid-search/submissions/code/21023645
redb17 This input is already included in one of the test cases.
bnegrao My code works for all test cases, including yours.
private static boolean search(int[][] grid, int[][] pattern) { int hGrid = grid.length; int wGrid = grid[0].length; int hPat = pattern.length; int wPat = pattern[0].length; int wG = 0; boolean patternCompletelyFound = false; while (wG + wPat <= wGrid && patternCompletelyFound == false) { boolean matching = false; int hp = 0; for (int hG = 0; hG < hGrid; hG++) { if (!matching && hGrid - hG < hPat) { break; } if (hPat == hp) { break; } if (match(grid[hG], pattern[hp], wG) || match(grid[hG], pattern[0], wG) ) { hp++; matching = true; } else { matching = false; hp = 0; } } if (matching == true && hPat == hp) { patternCompletelyFound = true; } wG++; } return patternCompletelyFound; } private static boolean match( int[] gridLine, int[] patLine, int wG) { boolean matched = true; for (int i = 0; i<patLine.length; i++) { //System.out.println("grid: " + gridLine[i + wG] + " pat: " + patLine[i]); if (patLine[i] != gridLine[i + wG]) { matched = false; break; } } return matched; }
ashish53v My code passed this test...
arnabmondal public class Solution {
public static boolean calculate(int [][]A,int [][]a,int R,int C,int r,int c,int j,int k){ if(j+r<=R&&k+c<=C){ boolean flag = true; for(int i1=0;i1<r;i1++){ for(int i2=0;i2<c;i2++){ if(A[j+i1][k+i2]!=a[i1][i2]){ flag=false; break; } } if(!flag) break; } return flag; } else return false; } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); int t = in.nextInt(); boolean flag = false; for(int i=0;i<t;i++){ int R = in.nextInt(); int C = in.nextInt(); int [][]A = new int[R][C]; String line; for(int j=0;j<R;j++){ line = in.next(); for(int k=0;k<C;k++) A[j][k]=Character.getNumericValue(line.charAt(k)); } int r = in.nextInt(); int c = in.nextInt(); int [][]a = new int[r][c]; for(int j=0;j<r;j++){ line = in.next(); for(int k=0;k<c;k++) a[j][k]=Character.getNumericValue(line.charAt(k)); } for(int j=0;j<R;j++){ for(int k=0;k<C;k++){ if(A[j][k]==a[0][0]) if(calculate(A,a,R,C,r,c,j,k)){ flag = true; break; } } if(flag){ break; } } if(flag) System.out.println("YES"); else System.out.println("NO"); } }}
//Works with your example
akshaykhedkar my code worked perfectly for this test case... but failed for some given test cases.
tenzin392 [deleted]tenzin392 At first I thought I also must had some logical error in my code that passed all the test cases running this manual test case.
Then I realised this test case is missing the 'T' value of 1 in the input -.- I feel like I got trolled
SanjayPradeep the code works perfectly fine for me ... here is my code
import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { int t,x,y,x1,y1; Scanner in = new Scanner(System.in); String s; t=Integer.parseInt(in.nextLine()); for(int i=0;i<t;i++){ s = in.nextLine(); String s1[] = s.split("\\s"); x1=Integer.parseInt(s1[0]); y1=Integer.parseInt(s1[1]); int a[][] = new int[x1][y1]; for(int j=0;j<x1;j++){ s = in.nextLine(); String s3[] = s.split(""); for(int k=0;k<y1;k++){ a[j][k]=Integer.parseInt(s3[k]); // System.out.println("j is " + j +" and k is " + k + " and val is " +a[j][k]); } } s = in.nextLine(); //System.out.println(s); String s2[] = s.split("\\s"); x=Integer.parseInt(s2[0]); y=Integer.parseInt(s2[1]); int b[][] = new int[x][y]; for(int j=0;j<x;j++){ s = in.nextLine(); String s4[] = s.split(""); for(int k=0;k<y;k++){ b[j][k]=Integer.parseInt(s4[k]); } } int r,c=0,count=y,dup=0,dup1=0,er1=0,er2=0,br=0,crt=0,j1=0,k1=0; for(int j=0;j<x1;j++){ for(int k=c;k<y1;k++){ // System.out.print("here j is "+j+" and k is "+k + "and y1 is "+ y1); //System.out.println(a[j][k]+" and " + b[j1][k1]); if(a[j][k]==b[j1][k1]){ //System.out.print("here j1 is "+j1+" and k1 is "+k1 + "and y1 is "+ y1); if(dup1==0) { c=k; er1=j; er2=k; dup1++; } k1++; if(k1>y) { j1++; k1=0; } dup++; //dup1++; } else{ if(dup1!=0){ j=er1; k=er2; // System.out.println("Location Changed "); } dup1=0; dup=0; c=0; crt=0; j1=k1=0; } if(dup==count){ //System.out.println("here"); crt++; if(crt==x){ br=1; break; } dup=0; //dup1=0; j1++; k1=0; break; } } if(br==1) break; } if(br==1) System.out.println("YES"); else System.out.println("NO"); } } }
tat_lim Java 8 Solution (with Regex)
static String gridSearch(String[] G, String[] P) { int n = G[0].length() - P[0].length() + 1; String delimiter = " "; String pad = String.format(".{%s}", n); String grid = String.format("%s%s", String.join(delimiter, G), String.join("", Collections.nCopies(n, delimiter))); String regex = String.format(".*%s%s.*", String.join(pad, P), pad); return grid.matches(regex)? "YES" : "NO"; }
AashSparx Thanks a lot for this corner case. Cleared all the test cases :)
rajeevpodar My code working fine with above testcase too.
varunkamani19 My code Passed this TC. :)
int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int t; cin>>t; while(t--){ int r1,c1,r2,c2,flag=0; cin>>r1>>c1; vector<string> s(r1); for(int i=0;i<r1;i++) cin>>s[i]; cin>>r2>>c2; vector<string> p(r2); for(int i=0;i<r2;i++) cin>>p[i]; for(int i=0;i<=r1-r2;i++){ for(int j=0;j<=c1-c2;j++){ flag=0; if(s[i][j]==p[0][0] && s[i].substr(j,c2)==p[0]){ int d=i+1,k=1; for(;k<r2;k++){ if(s[d++].substr(j,c2)!=p[k]){ break; } } if(k==r2){ flag=1; break; } } } if(flag==1){ break; } } if(flag==1){ cout<<"YES\n"; }else{ cout<<"NO\n"; } } return 0; }
anshumanc007 no need to add.If u write a perfect code,it will not fail any test case
indrasenareddyg My code works for this test case too, I think they have added it as test case 7 :)
mohammedjasam filRow = R - r + 1 filCol = C - c + 1 for i in range(filRow): for j in range(filCol): daffuq = [] for x in range(r): daffuq.append(G[i + x][j : j + c]) if daffuq == P: return "YES" return "NO"
TLE at TC 5, any suggestions?
freya_jeong Hey I had my second try, which was the same as yours above. It failed test case #5. Then I figured that test case #5 includes G of dimension 1000*1000, in which case you have too many "daffuq"'s to compare with P. That exceeds the time complexity required.
slash331erock my code passed your test case but shows abord called for only test case no 5 .please help me with what is reason for abord called
ase429 I don't think the authors need to add any test cases. Part of the challenge is identifying edge cases that your code may fail at. If the authors provide you every test case, what is the point?
JedJulliard it works for me, after i inserted an extra first line "1"
as described in the probelm: the first line contains an integer t , the number of test cases.
tykelley If you are checking by rows (columns), you need to make sure that you keep checking after you match the first row (column) but not the rest. Otherwise, you'll miss any case like this.
RD_Square my code worked for this!!!
ramtiwari my code passed this one.
balajilitsv it should return "YES", right!! Balaji's Submission Check it please. It gives the required answer
shivam08rungta When you are checking the horizontal length also check vertical length
beacuse in last row 12 is present but below that matrix ends so test case fails
vivek_singhal_c1 u saved me!!!
josef_klotzner i am sure, if you put 1 as first line (number of test cases) it will pass
JuniorStudent i thought its about the internal code, my function has been called yet, might be caused by invalid input test case
satyacenation the test case you mentioned is working for me fine. OUTPUT : YES
bantic Some of the test cases have CR+LF (i.e. "\r\n") line endings, and the JavaScript boilerplate solution does not properly strip these off; it assumes all lines end with "\n" only. That means some of the grids and patterns for the test cases will be arrays like grid=["123\r","456\r","789\r"] and pattern = ["12\r","45\r"]. The boilerplate needs to update its processing of stdin to split on "\n" and then strip "\r" from each line as well.
bantic This was causing me to tear my hair out because my program failed some of the test cases when I submitted it, but when I looked at that input and copy/pasted it into the "custom test case" textarea the newlines were as expected (only "\n"), so my program always passed the test cases when I ran them one-by-one but always failed when I submitted it.
hokennethk bantic,
I think I'm running into the same issue here. I've downloaded (or bought) some of the test cases I've failed, but they pass when I run them manually.
Can you provide any guidance to how to do this? How can I strip "\r" in JavaScript?bantic @hokennethk sure. In the boilerplate code that splits on "\n", use map to remove the "\r" from all the lines, too. It is in the process.stdin.on('end' event handler. Add ".map(line => line.replace(/\r/g,''))" after the "input_stdin.split('\n')" part.
Michael_Hobbs Just use .trim() on the inputs they are dirty with white spaces.
marvel32x2 A mod needs to see this... so much frustration and spending hackos to check test cases manually that all worked anyway.
witz517 I've had the same issue with other problems too, I think the hole platform is broken.. It will be nice if we get notifications about HR system stability, that will surely saves us from some frustration !
abaron This really should get fixed! Thanks a lot
fcostarodrigo I am using my own boilerplate now.
I am also removing empty lines just in case.
process.stdin.setEncoding('utf8'); var input = ""; process.stdin.on("data", function (chunk) { input = input + chunk; }); process.stdin.on("end", function () { var lines = input.replace(/\r/g, "").split("\n").filter(function (line) { return line.trim(); }); // Code here. });
jkilbride GAH!! No wonder. Thanks for this! Just added the code to strip the CRs out and now I pass all the tests. To fix it, I updated the split() statement in the boilerplate to use a RegEx:
input_stdin_array = input_stdin.split(/\r?\n/);
Guess I'll have to add that from now on...
aethe Thank you so much!
antonbabkin Thanks, man! Same struggle, seeing correct results on copy/pasted failed test cases.
EDIT: If anybody else finds this annoying, might be helpful to submit a ticket to Support - see link at the bottom of the page. I just did that, hopefully life will get better for us JavaScripters. :)
kallanreed If you use the dimensions of the string that are passed in instead of walking to the end of the string, you shouldn't have this problem.
ameykpatel SIMPLE C++ CODE. PASSES ALL TCs .
int found=0; { for(int i=0;i<=R-r;i++) { for(int j=0;j<=C-c;j++) { int p=0,k=i; while(s[k].substr(j,c)==a[p].substr(0,c)) { if(k-i+1==r) { found=1; break; } k++,p++; } } } (found)? cout<<"YES\n" : cout<<"NO\n"; }
shanki haha...nice code
meethinsu414 pls explain why you have used this: if(k-i+1==r).????
leejh3224 It just simply says that the height (size of the row) is exactly same as the pattern to be matched.
neeli_adi When you break, the code will come out of the while loop and continue in the inner for loop.
You probably need additional breaks in the outter loops to come out completely and return YES.
JsFoxy Here is my solution in Javascript using RegEx. I pass all test cases and times range from 0.06s up to 0.15s
function main() { var t = parseInt(readLine()); for(var a0 = 0; a0 < t; a0++){ var R_temp = readLine().split(' '); var R = parseInt(R_temp[0]); var C = parseInt(R_temp[1]); var G = []; for(var G_i = 0; G_i < R; G_i++){ G[G_i] = readLine(); } var r_temp = readLine().split(' '); var r = parseInt(r_temp[0]); var c = parseInt(r_temp[1]); var P = []; for(var P_i = 0; P_i < r; P_i++){ P[P_i] = readLine(); } // -------------- Code below this point ----------- var patt_len = P.length; var offset = (G[0].length - P[0].length)+1; var pattern = ''; var regex; var result; var i; var str = ''; // Simply concatenate grid using . as separaor // make sure u use some kind of separator or // it won't work, you can use anything but // numbers here as separator str = G.join('.'); // Here I build RegEx pattern for(i = 0; i < patt_len; i++) { if(i !== (patt_len - 1)){ pattern += '(' + P[i] + ').{' + offset + '}'; } else { pattern += '(' + P[i] + ')'; } } // And in end we run it on our strig // and see if we have match or not regex = new RegExp(pattern); result = str.match(regex); console.log(result !== null ? 'YES' : 'NO'); } }
So idea was to get grid array in one string, and then use pattern array to build RegEx expression and run it on string. So for example let's let's take one of default inputs:
10 10 7283455864 6731158619 8988242643 3830589324 2229505813 5633845374 6473530293 7053106601 0834282956 4607924137 3 4 9505 3845 3530
After we concatenate our grid will look like:
// note that u can use any simbol to concatenate string // just make sure it's not a number :) 7283455864.6731158619.8988242643.3830589324.2229505813.5633845374.6473530293.7053106601.0834282956.4607924137
And our pattern will look like this:
//note that "." in this regex it's not actual dot we used // to concatenate string. The {7} part we got by calculating // how much apart our patten needs to be in a string, we simply // use our (grid length - pattern length) + 1, we need this +1 // to count in our concatenate simbol, in my case dot. /(9505).{7}(3845).{7}(3530)/g
Schuetzl My submission only fails test case #5 but the file is too long to test for where I'm going wrong. (Can't even test one of the cases because the text exceeds to allowed limits of the custom input in the editor). Any suggestions?
Marathon [deleted]Kaitek Same problem. Wrong answer on #5 after 1.5s. My code checks for alignment and passes all custom cases posted in the discussions. Admins please increase the size limit for custom input.
Marathon Why not test on your machine? If you do, there are at least 3 things you can do: 1) You can paste to stdin source; 2) Redirect stdin so your program gets data from a file; or 3) Write your program so it can get input from either stdin or from a file.
In case you are not familiar with redirection, in general, redirection uses " < " in a command line:
foo < bar.txt
This tells the program "foo" to use "bar.txt" for stdin.
ddeepika_297 use test case provided by @vangoor_bharath.It helped me pass test case #5
amazinghacker I tried his input. It gives "YES" which is correct. still case 5 doen't satify?
2016ucp1381 You must be getting timeout ! When you found match , break both of the loops not only one.
glinden7834 I am getting WA on cases 9,11,13, and 15. My program is returning YES in all those cases. I have tried taking out the trailing linefeed, but that didn't help. What, precisely, should the format of a single line result be? All the multiple line ones don't seem to care.
erisalke I have the same problem with 6, 11 and 13. My code have only two lines which write the stdout console.log("YES") and console.log("NO") so what blank lines may be there?
glinden7834 Just "YES\n".
samindaw In that case its hard to say. Any chance of looking at your code?
glinden7834 I tried pasting it in here, but it got horribly mangled. Is there a normal way to pass code around? I don't know where all the buttons are yet.
erisalke You may use pastebin.com or similar tool and just paste the link here.
glinden7834 Here is the link to my code: http://pastebin.com/KWSE9EXx
Very handy.
glinden7834 OK, I just ran test case 9 in the "custom input" section and came up with a single "YES" followed by a newline. This fails to pass, though it found the pattern. Test case 7 also has one pattern, to which my program replies exactly the same, but it passes. What in the ever-lovin' blue-eyed world is going on here!?
bantic Same exact thing is happening to me. 9, 11, 13, 15 all fail. If I download the input and output and run them individually my program gives the correct answer for each one. Very confusing/frustrating...
willythewhale Same. It's quite bothersome when you have the correct algorithm, and correct output, but the checker fails to recognize that.
murphybytes Yep, same for me. Super frustrating. If I download the input and run it, it passes, but the same test fails when I submit my code.
glinden7834 Here is the link to my code: http://pastebin.com/KWSE9EXx
I posted this earlier, but it was a little dislocated.
glinden7834 Thank you for responding. I take it you aren't a Haskell programmer, but thanks anyway. In case you missed it, the code is at http://pastebin.com/KWSE9EXx
dwivedi_pranav3 I too facing the same problem. Test cases 9,11 13 and 15 are getting failed despite the correct output.
adancito The editorial's solution sounds like it has a worst-case time complexity O(R * C * r * c). I think the problemsetter should include a mathemathical proof that this naive solution will pass in every scenario, or find such test cases that will break this approach. I implemented a solution in O(R * C + r * c) time and space, using Aho-Corasick and KMP.
harshraj22aug please share your code , it would be helpful for the beginners.
horwath_leszek More or less quite ugly implemented aho corasic + kmp for this case looks like this: mind that I assumed all words in pattern are the same length and ommited some unnecessary code for implementing subpatterns in aho. Also the time complexity is O(R*C*DELTA + r*c*DELTA) where DELTA is size of dictionary (possible next letters) so in this case [0-9]
private static class Node { public Map<Character, Node> nextNode; public Node failure; int terminal; public Node() { nextNode = new HashMap<>(); for(char c = '0'; c <= '9'; ++c) { nextNode.put(c, null); } failure = null; terminal = -1; } public Node addWord(String word, int index) { Node q = this; for(int i = 0; i < word.length(); ++i) { char x = word.charAt(i); q.nextNode.putIfAbsent(x, new Node()); q = q.nextNode.get(x); } if(q.terminal == -1) { q.terminal = index; } return this; } public List<Node> computeBFS() { ArrayList<Node> result = new ArrayList(); Queue<Node> queue = new LinkedList<>(); this.nextNode.entrySet().forEach(entry -> { if(entry.getValue() != null) { queue.add(entry.getValue()); } }); while(!queue.isEmpty()) { Node q = queue.remove(); result.add(q); q.nextNode.entrySet().forEach(entry -> { if(entry.getValue() != null) { queue.add(entry.getValue()); } }); } return result; } public void createFailureFallback() { List<Node> bfsOrder = computeBFS(); this.failure = this; for(char c = '0'; c <= '9'; ++c) { if(this.nextNode.get(c) != null) { this.nextNode.get(c).failure = this; } } for(char c = '0'; c <= '9'; ++c) { this.nextNode.putIfAbsent(c, this); } bfsOrder.forEach( node -> { for(char c = '0'; c <= '9'; ++c) { Node x = node.nextNode.get(c); if(x == null) { node.nextNode.put(c, node.failure.nextNode.get(c)); } else { x.failure = node.failure.nextNode.get(c); } } } ); } } static int [] computeKMPLookup(int [] pattern) { int [] lookup = new int[pattern.length]; lookup[0] = -1; int k = -1; for(int q = 1; q < pattern.length; ++q) { while(k > -1 && pattern[k+1] != pattern[q]) { k = lookup[k]; } if(pattern[k+1] == pattern[q]) { ++k; } lookup[q] = k; } return lookup; } static String gridSearch(String[] G, String[] P) { Node head = new Node(); for(int i = 0; i < P.length; ++i) { head.addWord(P[i], i); } head.createFailureFallback(); //match array will have information about which row from pattern matches at which point in searched string int [][]match = new int[G.length][]; for(int i = 0; i < match.length; ++i) { match[i] = new int[G[i].length()]; Node q = head; for(int j = 0; j < G[i].length(); ++j) { q = q.nextNode.get(G[i].charAt(j)); match[i][j] = q.terminal; if(q.terminal != -1) { if(q.failure!= null) { q = q.failure; } } } } //we need to find pattern that we will search in columns of amtch arrays, it might be that some of rows of pattern are repeated int [] pattern = new int[P.length]; for(int i = 0; i < P.length; ++i) { Node q = head; for(int j = 0; j < P[i].length(); ++j) { q = q.nextNode.get(P[i].charAt(j)); if(q.terminal != -1) { pattern[i] = q.terminal; q = q.failure; } } } //compute KMP lookup array int[] lookup = computeKMPLookup(pattern); //now we jsut use KMP to search for the pattern for(int column = 0; column < match[0].length; ++column) { int q = -1; for(int i = 0; i < match.length; ++i) { while(q > -1 && pattern[q+1] != match[i][column]) { q = lookup[q]; } if(pattern[q+1] == match[i][column]) { ++q; } if(q == pattern.length - 1) { return "YES"; } } } return "NO"; }
thethepiyush13 Hows this code in terms of complexity ?
public static void main(String[] args) { Scanner scan = new Scanner(System.in); int steps = Integer.parseInt(scan.nextLine()); while(steps >0){ int sr = scan.nextInt(); int sc = scan.nextInt(); boolean found = false; scan.nextLine(); int[][] m1 = new int[sr][sc]; for(int i=0;i<sr;i++){ String row = scan.nextLine(); for(int j=0;j<sc;j++){ m1[i][j] = (int)(row.charAt(j) ); } } int fr = scan.nextInt(); int fc = scan.nextInt(); scan.nextLine(); int[][] m2 = new int[fr][fc]; for(int i=0;i<fr;i++){ String row = scan.nextLine(); for(int j=0;j<fc;j++){ m2[i][j] = (int)(row.charAt(j) ); } } /* System.out.println(Arrays.deepToString(m1)); System.out.println(Arrays.deepToString(m2)); */ outLoop: for(int i=0;i<sr;i++){ for(int j=0;j<sc;j++){ if(m1[i][j]==m2[0][0]){ if(isMatrix(m1,m2,fr,fc,i,j) ){ found = true; break outLoop; } else{ found = false; } } } } String r = (found==true)?"YES":"NO"; System.out.println(r); steps--; } } public static boolean isMatrix(int[][] m1, int[][] m2, int fr, int fc, int i, int j){ boolean found = true; for(int a=0;a<fr;a++){ for(int b=0;b<fc;b++){ try{ if(m2[a][b]!=m1[i+a][j+b]){ return false; } } catch(Exception e){ return false; } } } return true; }
iGbanam that's 4 nested loops...
thethepiyush13 Right, but It does pass all the tests and I think the editor`s solution too is using 4 nested loops. What approach do you suggest for this problem ?
mukeshpandey2628 Hi, I used Pattern Matching for this its complexity is very good but only 5th test case giving wrong answer all others are fine. This is my code :-
import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int R = in.nextInt(); int C = in.nextInt(); String G[] = new String[R]; for(int G_i=0; G_i < R; G_i++){ G[G_i] = in.next(); } int r = in.nextInt(); int c = in.nextInt(); String P[] = new String[r]; for(int P_i=0; P_i < r; P_i++){ P[P_i] = in.next(); } StringBuilder sb = new StringBuilder(); StringBuilder sb1 = new StringBuilder(); StringBuilder sb2 = new StringBuilder(); for(int i=0;i<R;i++){ sb.append(G[i]); } for(int i=0;i< C-c ;i++){ sb1.append("."); } sb2.append(".*"); for(int i=0;i< r ;i++){ sb2.append(P[i]); if(i< r-1){ sb2.append(sb1.toString()); } } sb2.append(".*"); if(sb.toString().matches(sb2.toString())){ System.out.println("YES"); } else{ System.out.println("NO"); } } }}
harsha_ramak8882 Similar logic, except using indexOf(str, int) function.
boolean found = false; int k = -1; int l = -1; outerLoop: for(int i=0; i < R; ) { l = k; k = G[i].indexOf(P[0], l+1); //System.out.println("lk is " + l+k); if ( k != -1) { for(int j = 1; j < r; j++) { String local = G[i+j].substring(k, k+c); //System.out.println("local for j = " + j + " is " + local); if (!local.equals(P[j])) { found = false; continue outerLoop; } else { //System.out.println("found match in iteration " + i + j); found = true; if (j == r-1) break outerLoop; continue; } } } i++; } System.out.println(found ? "YES" : "NO");tat_lim [deleted]
param11 Hey Can You explain your logic here!!!Coz I have a different method
tat_lim Java 8 Solution (with Regex)
static String gridSearch(String[] G, String[] P) { int n = G[0].length() - P[0].length() + 1; String delimiter = " "; String pad = String.format(".{%s}", n); String grid = String.format("%s%s", String.join(delimiter, G), String.join("", Collections.nCopies(n, delimiter))); String regex = String.format(".*%s%s.*", String.join(pad, P), pad); return grid.matches(regex)? "YES" : "NO"; }
Sharanayya One small improvement....sr to sr-fc and sc to sc-fc for(int i=0;i
Kuriocity Java
static String gridSearch(String[] g, String[] p) { for(int i=0;i<=(g.length-p.length);i++) { for(int j=0;j<=(g[0].length()-p[0].length());j++) { int a=i; int c=0; if(g[i].substring(j,j+p[0].length()).equals(p[0])) { c++; for(int k=1;k<p.length;k++) { i++; if(g[i].substring(j,j+p[0].length()).equals(p[k]))c++; else break; } if(c==p.length)return "YES"; } i=a; } } return "NO"; }
Sort 478 Discussions, By:
Please Login in order to post a comment