Help needed in MIN MAX STRING

dhruv788 · August 13, 2020, 7:21pm

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.
It is showing SIGSEGV . Please Help . Your help will be really appreciated.
Link to My solution
https://www.codechef.com/viewsolution/36699572

jatin_sin · August 13, 2020, 7:30pm

i think you are accessing element out of bounds.

dhruv788 · August 13, 2020, 7:31pm

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

jatin_sin · August 13, 2020, 7:39pm

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

dhruv788 · August 13, 2020, 7:43pm

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

jatin_sin · August 13, 2020, 7:47pm

yes my bad i didn’t see that.

jatin_sin · August 13, 2020, 7:52pm

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

ssjgz · August 13, 2020, 7:56pm

[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

dhruv788 · August 13, 2020, 7:59pm

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

ssjgz · August 13, 2020, 8:01pm

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

jatin_sin · August 13, 2020, 8:03pm

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

dhruv788 · August 13, 2020, 8:04pm

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

dhruv788 · August 13, 2020, 8:05pm

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

dhruv788 · August 13, 2020, 8:10pm

Link is updated , help is required,please help😅

swapnilrustagi · August 13, 2020, 8:31pm

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.

dhruv788 · August 13, 2020, 9:05pm

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

dhruv788 · August 13, 2020, 9:07pm

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

ssjgz · August 13, 2020, 9:14pm

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)

dhruv788 · August 13, 2020, 9:18pm

ssjgz:

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> >;
    }

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

ssjgz · August 13, 2020, 9:27pm

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