I too figured out the linear time solution for KAVMAT. i also had the simplest algorithm of precalculating and then finding the best upper left vertex for a given lower right vertex such that average in region would be greater than equals to K using binary search. But then i went on with linear time complexity solution using 2 pointers. I didn’t knew nnlog(n) was allowed
coming to water sort i did play that game but in the one i downloaded had aim to separate all colors in just one test tube. Was looking for heuristics to solve the problem but then gave up.
maybe next time
Your str is not bouned on the right by “\0” so after k * it may contain garbage values that’s why.
try putting str[k]=’\0’; after memset(str,’*’,k); and it might work.
partially ac for 30 point but bro i did not understood what to said i know every string get with null char. at last .so putting only after the memset it worked i did not understood
can u please give me example if it getting out bound it run time error.
oh wait it worked but putting str[k]=’\0’ before memset
after memset partially ac i did not understood
check this before memset CodeChef: Practical coding for everyone
after memset CodeChef: Practical coding for everyone
explain it bro. it’s happening becuz of memset
It will be great if you just answer my question. If you think that someone is a cheater then just report that to codechef. I think the will take care of that.
Bro try debugging your code.
in the partial answer u uncommented s[n] = ‘\0’ at line 117
bro i have commented s[n]=‘\0’ but still it partially putting str[k]=‘\0’ after the memset
check CodeChef: Practical coding for everyone
also i did not understood why did it get ac putting before memset
It’s seem like you are new to competitive coding.
here’s why
u basically made an array of st which basically means u reserve some space to be filled by characters
u fill from index 0 to k-1 by ‘*’ and fill the kth index by ‘\0’
so either you do it before memset or after memset the result will be same. kth index will be ‘\0’
Also the question doesn’t require KMP (KMP is used in other places where pattern matching is quite complex).
In the current question you can simply run a loop and figure out the answer. Try Watching some video editorials to see how else you could have solved this problem
bro i got this (i thought null char. already put by complier as i never did before)
but result r not same putting before and after it as u can see your self
but bro tell me this one
result r not same putting before and after it as u can see your self
This:
char str[k];
//for(int i=0; i<k ;i++)
//str.push_back('*');
memset(str,'*',k);
str[k]='\0';
is an out-of-bounds access and hence Undefined Behaviour:
[simon@simon-laptop][21:49:14]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh
Compiling akshay_012-SSCRIPT.cpp
+ g++ -std=c++14 akshay_012-SSCRIPT.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
akshay_012-SSCRIPT.cpp: In function ‘void KMPSearch(char*, char*)’:
akshay_012-SSCRIPT.cpp:16:16: warning: conversion to ‘int’ from ‘size_t {aka long unsigned int}’ may alter its value [-Wconversion]
int M = strlen(pat);
~~~~~~^~~~~
akshay_012-SSCRIPT.cpp:17:16: warning: conversion to ‘int’ from ‘size_t {aka long unsigned int}’ may alter its value [-Wconversion]
int N = strlen(txt);
~~~~~~^~~~~
+ set +x
Successful
[simon@simon-laptop][21:49:20]
[~/devel/hackerrank/otherpeoples]>echo "3
5 2
*a*b*
5 2
*a**b
5 1
abcde" | ./a.out
akshay_012-SSCRIPT.cpp:110:11: runtime error: index 2 out of bounds for type 'char [*]'
NO
YES
NO
can debug this please CodeChef: Practical coding for everyone
by putting str[k]=‘\0’ before memset (it did not give out of bound )
also it get ac why .?
There’s Undefined Behaviour for you 
What’s wrong in my solution in question worthy matrix?
Solution link:- CodeChef: Practical coding for everyone
I have used prefix sum matrix
Then do binary search where square matrix solutions exist…
Can anybody tell me that in worthy matrix problem why three inner for loop solution work I mean in that type of solution time complexity is O(N^3)…