0
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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";
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ I know it is not allowed to reply with "Thank you" to an answer but I do appreciate your suggestions. Thanks! \$\endgroup\$ – Halil Karabacak Jul 21 at 4:34
  • \$\begingroup\$ It's pretty certain that it is the position in the alphabet that counts, given the example abbcbabbbbcccbb. In reality, given that we only need to report the length, we're just summing the numeric values of all the letters. If it were position in the string, we wouldn't need to even read the string, as it would just be an operation on triangular numbers. The example could have been better if it didn't have so much overlap between the character values and positions! \$\endgroup\$ – Toby Speight Jul 21 at 7:10
  • \$\begingroup\$ The description says "The song is a string consisting of lowercase English letters", so we're probably entitled to do anything except UB if that precondition is violated. Take out the std::islower() test. That saves me having to remind you to make val an unsigned char rather than auto! One more thing: it seems that there's one string and many queries, so the std::getline() and initial processing needs to be outside the loop. \$\endgroup\$ – Toby Speight Jul 21 at 7:21
4
\$\begingroup\$

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'];
\$\endgroup\$
4
  • 1
    \$\begingroup\$ We don't even need alph at all: length += s[b] + 1 - 'a'. \$\endgroup\$ – Toby Speight Jul 20 at 14:36
  • \$\begingroup\$ Saying using map is a bad idea is a bit strong (it's not the best idea given the problem). I would have used map to start with. Then I could verify the result. Swapping the map out for an array is then trivial (now that you can easily test that your new array and map can generate the same results). I would say it is easier to use the map (the array unless wrapped) requires some index manipulation and validation but probably faster to use the array. \$\endgroup\$ – Martin York Jul 20 at 18:53
  • \$\begingroup\$ Actually, on second thoughts, the alph lookup is good for portability (though I would make it an array of size UCHAR_MAX). The code here with subtraction won't work with environments where the Latin letters are non-contiguous (notably EBCDIC systems). \$\endgroup\$ – Toby Speight Jul 21 at 7:14
  • 1
    \$\begingroup\$ @TobySpeight There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors. \$\endgroup\$ – Deduplicator 2 days ago
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Using istream::exceptions() is very esoteric. Easier to just test the state of the stream after a read. \$\endgroup\$ – Martin York Jul 20 at 18:55
  • \$\begingroup\$ I wouldn't call it esoteric; arguably it's easier and could well have been the default, rather than having to check status after each operation as we do in C. But I've edited anyway to mention both styles. \$\endgroup\$ – Toby Speight Jul 21 at 7:02
  • \$\begingroup\$ Practicing my one new word a day :-) \$\endgroup\$ – Martin York 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.