# Help needed in MIN MAX STRING

I tried the Min Max string using Hashing . I first calculated the hash value of all the Initial string. Then I created a map . Then I compared the hash value of the last character of each string with every other string and if it didn’t matched with anyone inserted it in the map. Then I went to the queries , if query is of 1st type, I took the value of the hash of the last character of the given string and computed its hash after ammending it with given letter.Then I erased the string from the map which is used to create the new string as old string would be a proper prefix of new one. Then I compared the hash value of new string with every other string present in the map whose size is greater than new string.

If query is of 2nd or 3rd type I simple printed the first and last value.
https://www.codechef.com/viewsolution/36699572

i think you are accessing element out of bounds.

I too think so , but I am not able to know when or in which case

are you sure about v.size() never exceeds 3 * 10^5 in hashi[v.size()]

I think so ,because total no. Of queries are 2 * 10 ^ 5 and N is <10 ^ 4 so actually it should not even exceed 2 * 10^5+10^4

1 Like

yes my bad i didn’t see that.

1 Like

i think experts need to take over this problem.
@ssjgz help him if you can.

2 Likes
``````[simon@simon-laptop][20:54:46]
[~/devel/hackerrank/otherpeoples]>g++ -std=c++14 dhruv788-MINMXSTR.cpp -O3 -g3 -Wall -Wextra -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
dhruv788-MINMXSTR.cpp: In function ‘std::__debug::vector<long long int> hashed(std::__cxx11::string&, int)’:
dhruv788-MINMXSTR.cpp:25:34: warning: unused parameter ‘l’ [-Wunused-parameter]
vector<lli> hashed(string &s,int l)
^
dhruv788-MINMXSTR.cpp: In function ‘int main()’:
dhruv788-MINMXSTR.cpp:83:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if((it->first).size()>r)
~~~~~~~~~~~~~~~~~~^~
[simon@simon-laptop][20:54:58]
[~/devel/hackerrank/otherpeoples]>echo "1
3
abcdef
abc
xyz
6
1 2 d
2
3
1 4 c
2
3 " | ./a.out
dhruv788-MINMXSTR.cpp:22:9: runtime error: index 200001 out of bounds for type 'long long int [200001]'
dhruv788-MINMXSTR.cpp:22:10: runtime error: store to address 0x5592db5dc668 with insufficient space for an object of type 'lli'
0x5592db5dc668: note: pointer points here
0f 16 13 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00
^
1
3
5
3
``````
1 Like

What does it mean? Is it that memory limit is exceeded as we can’t store an array of long long int of size 2*10^5

Precisely what it says: on line 22, you are attempting to access the element at index `200001` in array with only `200001` values (array indexing is `0`-relative, remember!)

No

3 Likes

i knew that some out of bounds access is there but couldn’t figure that out thats why we have people like you

I changed it , but it is still showing the same result , and BTW Thanks

Yeah , @aneee004 @galencolin @humane @everule1 @akshitm16 @carre @swapnil159
Want to seek your help as well

Your `poweri` array is too small. Have at least size 4*10^5, because the maximum size of string can be 2*10^5, and then there are 2*10^5 queries after that.

1 Like

Ok , thanks for the help, but it is still showing the same error.

I have found a random test case on which it fails , but i am not able to understand why it fails more accurately it is not taking the x for the 4th query can someone please explain why. Here is the random testcase I generated.
1
3
abcdefaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
abcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
xyz
6
1 2 d
2
3
1 3 c
2
3

With this solution:

``````[simon@simon-laptop][22:13:32]
[~/devel/hackerrank/otherpeoples]>g++ -std=c++14 dhruv788-MINMXSTR.cpp -O3 -g3 -Wall -Wextra -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
dhruv788-MINMXSTR.cpp: In function ‘std::__debug::vector<long long int> hashed(std::__cxx11::string&, int)’:
dhruv788-MINMXSTR.cpp:25:34: warning: unused parameter ‘l’ [-Wunused-parameter]
vector<lli> hashed(string &s,int l)
^
dhruv788-MINMXSTR.cpp: In function ‘int main()’:
dhruv788-MINMXSTR.cpp:83:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if((it->first).size()>r)
~~~~~~~~~~~~~~~~~~^~
[simon@simon-laptop][22:13:43]
[~/devel/hackerrank/otherpeoples]>echo "1
3
abcdefaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
abcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
xyz
6
1 2 d
2
3
1 3 c
2
3" | ./a.out
4
3
/usr/include/c++/7/debug/vector:417:
Error: attempt to subscript container with out-of-bounds index 3, but
container only holds 0 elements.

Objects involved in the operation:
sequence "this" @ 0x0x55721803bf28 {
type = std::__debug::vector<long long, std::allocator<long long> >;
}
Aborted (core dumped)
``````
1 Like

can you explain this one as well and also tell which IDE you use .
you can also explain with the below test case as well as (any one would be sufficient) it too fails on same condition.
1
3
abcdefa
abca
xyz
6
1 2 d
2
3
1 3 c
2
3

I just use gcc on the command-line

You now have a 100% reproducible testcase, and the compiler-flags needed to expose the error in your code; use gdb to debug it

1 Like