PLEASE HELP ME FIND RUNTIME ERROR IN THIS CODE

general
, ,
1

Why does this code:

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    string s;
    cin >> n >> s;

    unordered_set<string> set1;
    for (int i = 0; i < n - 2; i++) {
        string s1 = s.substr(0, i) + s[i + 1] + s[i + 2] + s[i];
        if (i < n - 3) s1 += s.substr(i + 3);
        set1.insert(s1);
    }

    cout << set1.size() << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

for the question: Triangular Swaps Practice Coding Problem - CodeChef

Please help. Thank You.

2

Runtime Error usually (although not always) comes from bad usage of memory. That includes bad allocation, index out of range or… literally no memory left, which is the case.

Your code consumes memory like crazy. Just imagine a 10^5 length string. And you are possibly saving up to 99,998 variations of the same length. If each character is a byte, then 9,999,800,000 bytes would be required (9.31 GB) and you only have 1.5 allowed.

image

Basically that.
Check your submissions and watch how it’s up to 1 GB or more (before the Judge drops the execution).

3

But even if you had enough memory available (using hash for instance), you would probably get Time Limit Exceeded anyway.

subtr() is literally copying char by char with complexity O(n). So it runs the whole string each loop. You code is O(n^2)

Note how on the 1.5 GB you filled, you were at moreless 20% of the total execution, and your submissions were already close to 1 sec.

I added a hashing function to reduce the memory usage to prove my point. It fixes the Runtime Error, but pushes you directly to a TLE:

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    string s;
    cin >> n >> s;

    unordered_set<int> set1;
    for (int i = 0; i < n - 2; i++) {
        string s1 = s.substr(0, i) + s[i + 1] + s[i + 2] + s[i];
        if (i < n - 3) s1 += s.substr(i + 3);
        set1.insert(hash<string>{}(s1));
    }

    cout << set1.size() << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
4

I got the point. Thank you very much.

1 Like