Runtime Error for no reason

general
, ,
1

Hey, yesterday during the contest, I was trying to solve this particular question called Triangular Swap.
I thought that a brute force solution would work in O(n). But, I dont get why is it giving a runtime error?

Please help

Here is the link to my Submission

2

I’m not sure why the judge is giving out runtime error, but your solution wouldn’t pass either way because you’re using close to O(n²) in memory by saving the entire modified string every time.

I used your approach but hashing the string to an integer pair so saving it in a set wouldn’t be so heavy.

My code: CodeChef: Practical coding for everyone

1 Like
3

I had the same issue trying in both Python and C++ last contest. I hope someone can answer.

4

You were right.
Not only does your solution works, you can say that was why it is giving the runtime error.

I had exactly the same error than OP. I tried in both C++ and Python getting the same Runtime Error. All my submissions used moreless between 1 and 1.5 GB (which is the Memory Limit for the problem).

In Python, I used (getting RTE):

Set = set()
Set.add(unique_string)

But inspired by your solution, I changed it to:

Set = set()
Set.add(hash(unique_string))

Which returns an integer value (like your solution).

And guess what? Memory usage dropped from 1 GB to 18 MB and passed the tests.
So, yes. We can assume the RTE is due the memory usage.

Thank you for your comment. It helped me too! :grin:

1 Like
5

That’s pretty neat, didn’t know it was so easy to hash strings in python lmao

1 Like
6

There’s apparently an equivalent hash function in the C++ standard:
cplusplus.com/reference/functional/hash/

Used like:

size_t hashed_string = std::hash<string>{}("string");

Is it faster than a customized one? Probably, depending on the customization.
But it does not guarantee there won’t be a collision eventually.