Calculate sum of a substring

Question

I try to solve some old Codeforces questions. The problem is;

Petya once wrote a sad love song and shared it to Vasya. The song is a string consisting of lowercase English letters. Vasya made up q questions about this song. Each question is about a subsegment of the song starting from the l-th letter to the r-th letter. Vasya considers a substring made up from characters on this segment and repeats each letter in the subsegment k times, where k is the index of the corresponding letter in the alphabet. For example, if the question is about the substring "abbcb", then Vasya repeats letter 'a' once, each of the letters 'b' twice, letter 'c" three times, so that the resulting string is "abbbbcccbb", its length is 10. Vasya is interested about the length of the resulting string.

Help Petya find the length of each string obtained by Vasya.

Input The first line contains two integers n and q (1≤n≤100000, 1≤q≤100000) — the length of the song and the number of questions.

The second line contains one string s — the song, consisting of n lowercase letters of English letters.

Vasya's questions are contained in the next q lines. Each line contains two integers l and r (1≤l≤r≤n) — the bounds of the question.

Output Print q lines: for each question print the length of the string obtained by Vasya.

Example input:

7 3
abacaba
1 3
2 5
1 7

Corresponding output:

4
7
11

I used C++ to solve with dynamic programming and it works, but I am getting timeouts. Therefore, I need suggestions to decrease execution time.

My code:

#include<bits/stdc++.h>

using namespace std;
#define PII pair<int,int>


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    map<char, int> alph;
    string latin = "abcdefghijklmnopqrstuvwxyz";
    for(int x = 0; x < (int)latin.length(); x++)
        alph[latin[x]] = x + 1;
    
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> results;
    map<string, int> memo;
    
    for(int k = 0; k < q; k++){
        int l,r, length;
        length = 0;
        cin >> l >> r;
        
        if(memo.find(s.substr(l-1, r - l + 1)) == memo.end()){
            for(int b= l-1; b < r; b++){
                length += alph[s[b]];
            }
            memo[s.substr(l-1, r - l + 1)] = length;
        }
        else
            length = memo[s.substr(l-1, r - l + 1)];
        results.push_back(length);  
    }
    for(auto b: results)
        cout << b << "\n";
}

My notes:

1. I think that I have successfully implemented DP with my code.
2. I have named the variables are according to problem requirements, not arbitrarily.

Answer 1

Don't do this:

#include<bits/stdc++.h>

I know coding sites say use it. But don't. Its not standard. It will get you into bad habits that will kick you in the butt one day.

---

Don't do this:

using namespace std;

Bad habit. Can get you banned from projects.

---

Unless you are building the library that has external stuff there is no need to use macros.

#define PII pair<int,int>

In C++ we moved away from this as we have in language better options.

/// C++03
typedef std::pair<int, int> PII

// C++11
using  PII = std::pair<int, int>;

But you don't even use this type.

---

Sure:

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

Standard optimization. Not going to buy you much in this code though.

---

This seems like a waste.

    map<char, int> alph;
    string latin = "abcdefghijklmnopqrstuvwxyz";
    for(int x = 0; x < (int)latin.length(); x++)
        alph[latin[x]] = x + 1;

Could you not replace all that with:

   int alpha(char x) {
       return x - 'a' + 1;
   }

---

OK. int n, q; cin >> n >> q;

---

Did the specs say that the string had zero spaces in it?

    string s;
    cin >> s;   // If there is a space in the input this breaks.

Knowing coding sites, there will be exactly one test that will test for this.

---

Why are you storing results?

    vector<int> results;

The output from each question is a number. There is no other output. So simply print the number when you work it out.

---

You are optimizing?

    map<string, int> memo;

Storing previously calculated results?
Creating these substrings (the key) is going to be really expensive. Not sure if you are saving much by caching this value, given the cost. Might want to use a std::string_view so you don't have to pay the cost of creating those substrings to store as the key. But I would test it first without the cache to see if it is worth even bothering to do this.

---

Sure:

    for(int k = 0; k < q; k++){
        int l,r, length;
        length = 0;
        cin >> l >> r;
        

---

Is this correct?

            for(int b= l-1; b < r; b++){
                length += alph[s[b]];
            }

I though the cost was the position in the sub-string not position in the alphabet.

---

You just did a find (after creating the substring). Now you are creating the substring again and repeating the search to get the value! The call to find above returns an iterator you can get the length from the iterator!

            length = memo[s.substr(l-1, r - l + 1)];


   std::string_view key(&s[l-1], &s[r]);
   auto find = memo.find(key);
   if (find == memo.end()) {
       length = memo[key] = calcLength();
   }
   else {
       length = find->second;
   }

---

Just print the value.

        results.push_back(length);  

This is just going to be slow as you are doing memory management here.

---

#include <iostream>
#include <string>
#include <sstream>
#include <string_view>
#include <map>

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::string line;
    std::getline(std::cin, line);
    std::stringstream linestream(std::move(line));

    int n, q;
    if (!(linestream >> n >> q) {
       throw std::runtime_error("Fail 1");
    }

    std::string s;
    std::getline(std::cin, s);

    // Personally, I need convincing this is a valid optimization
    // creating the tree is relatively trivial but still far
    // more costly than summing a set of integers. You would
    // have to have some long strings and lots of repeats before
    // this becomes worth it.

    // Also this technical could be improved by allowing for
    // totally enclosed substrings to be used in calculating the
    // length for larger strings. 
    std::map<std::string_view, int> memo;

    for(int loop = 0; loop < q; loop++){
        line.clear();
        std::getline(std::cin, line);
        std::stringstream linestream(std::move(line));

        int l,r, length;
        if (!(linestream >> l >> r)) {
            throw std::runtime_error("Fail 2");
        }

        std::string_view key(&s[l], (r - l + 1));

        auto find = memo.find(key);
        if (find == memo.end()) {
            length = 0;
            for(auto val: key) {
                // Not sure about this.
                // Need some unit tests.
                length += std::islower(val) ? val - 'a' + 1: 0;
            }
            memo[key] = length;
        }
        else {
            length = find->second;
        }
        std::cout << length << "\n";
    }
}

Answer 2

Algorithm

The idea, at a first glance, is to calculate some index on a string to make all queries as fast as possible. The second glance gives that \$length(l,r)=length(0,r)-length(0,l-1)\$. Just precalculate an array of \$length(0,i)\$ (it can be done in a single loop) and return the difference on a query.

Wrong use of a map

map<char, int> alph;

is a bad idea. Map is a tree structure; would you write a code for a tree for this matter? If not, map should not be used. Here, it is much easier and faster to use an array, subtracting 'a' from index:

int alph['z'-'a'+1];
...
alph[latin[x]-'a'] = x+1;
...
length += alph[s[b]-'a'];

Answer 3

Include the necessary standard headers; don't use compiler's internal private header.

Don't using namespace std;.

Prefer a using alias to the macro. Actually, nix the macro completely, since it's unused.

Get rid of the function call that always returns the same value in for loop test.

When streaming from an input, ensure that failure is considered (either by testing the stream's state after reading, or setting it to throw exceptions).

Print results as they are computed - no need to store them all and print at the end.