Filling a string at minimal cost

Question

I'm solving the following problem. Here is the problem statement:

You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string.

You are allowed to write data to the string in blocks of fixed size: character-by-character, you can write contiguous blocks of identical characters of length 2, 3 ... N: X, XX, XXX, etc. For example:

Block: XX, apply to the 2 position in X***Y*Z => X*XXY*Z

It is allowed to overwrite same characters:

Block: XX, apply to the 0 position in X***Y*Z => XX**Y*Z

When you choose the size of block you would like to use, let's say S, "preparation" costs occurs: S * L, where L - some input constant.
Let's say, you picked the size 2 (cost is 2 * L), then you are allowed to write XX, YY, and ZZ to the given string.

When you write a block of data to the given string, writing cost occurs - some input constant C that is independent of the block size. When you choose some block length, e.g. 2, you have to fill all blanks using block_size = 2, you are not allowed to decrease or increase it in the middle of writing. For example, if you write the first piece of data to the given string as XX, later you are allowed to use YY and ZZ only. The same with other sizes.

Your task is to identify the minimum possible cost to fill all blanks considering costs of writing data and preparing a block.

Let's consider the example above in details. We are given a string X***Y*Z, L = 20, C = 10. For each option, there are a plenty of variants how to fill blanks.

1) We can fill all blanks with a block of size 1 using any characters from {X, Y, Z}. Thus, total cost is 1 * 20 (prepare a block of size 1) + 4 * 10 (fill 4 wildcards) = 60. Possible results, there are plenty of them:

XYXZYXZ, XXXYYZZ ...

2) We can use block size = 2. For example: overwrite X* with XX, ** with XX, Y* with YY, the total cost is 2 * 20 (prepare the block of size 2) + 3 * 10 (perform 3 writing operations to fill all blanks), the total cost is 70.

Example:

Solution 1

Init: X***Y*Z

step1: write XX at 0 => XX**Y*Z

step2: write XX at 1 => XXX*Y*Z

step3: write YY at 3 => XXXYY*Z

step4: write ZZ at 4 => XXXXYYZ

My solution is pretty simple:

1. assume a data block's length equals M
2. Try to fill a string using DFS
3. Compute & update cost if neccessary
4. Increment block size, goto 1

It works pretty well but I'm wondering if performance can be better?

Code:

#include <iostream>

using namespace std;

int N = 0;
int L = 0;
int K = 0;

const int max_length = 101;

const int max_value = 1000000;

char s[max_length];
char buf[max_length];

int min (int a, int b) {
  return a < b ? a : b;
}

int print_string(char d, int start, int d_size, int depth) {
  if (start >= N) return max_value;
  if (start + d_size > N) return max_value;

  for (int i = start; i < start + d_size; ++i) {
    if (buf[i] != '*' && buf[i] != d) return max_value;
  }

  if (start + d_size == N) return depth;

  for (int i = start; i < start + d_size; ++i) { buf[i] = d; }

  int res = max_value;

  for (int i = start; i < start + d_size; ++i) {
    int xc = print_string('X', i+1, d_size, depth+1);
    int yc = print_string('Y', i+1, d_size, depth+1);
    int zc = print_string('Z', i+1, d_size, depth+1);

    res = min(res, min (xc, min (yc, zc)));
  }

  for (int i = start; i < start + d_size; ++i) { buf[i] = s[i]; }

  return res;
}

int compute() {
  // we always can solve with m == 1, so there is no point in checking it
  // assuming that it is maximum cost
  int cost = N * K + 1 * L;

  for (int m = 2; m <= N; ++m) {
//    cout << "size " << m << '\n';

    int xc = print_string('X', 0, m, 1);
    int yc = print_string('Y', 0, m, 1);
    int zc = print_string('Z', 0, m, 1);

    const int steps = min(xc, min(yc, zc));

    const int cur = K * steps + L * m;

    if (cur < cost) {
      cost = cur;
    }
  }


  return cost;
}

int main(int argc, char* argv[]) {
  int T = 0;
  cin >> T;

  for(int t = 1; t <= T; ++t) {
    cin >> N;
    cin >> L;
    cin >> K;

    for (int i = 0; i < N; ++i) { cin >> s[i]; buf[i] = s[i]; }

    int res = compute();

    int exp = 0;
    cin >> exp;
    cout << "#" << t << " " << res << "; expected = " << exp << '\n';
  }
  return 0;
}

Data sample:

7
48 10 10
XX****YY*X*ZXX****YY*X*ZXX****YY*X*ZXX****YY*X*Z
260
6 13 8
**X**Y
50
6 13 8
XXX**Z
50
6 13 8
XXX***
50
6 13 8
X*Y*X*
50
5 13 8
ZZZZZ
50
5 13 8
XYZYX
53

Answer 1

First of all, checking in a range if you can write a letter or not can be improved to a O(1) check, in my case I used letter_qty for that.

Another thing that can improve yours is adding a cache, because the longer the string (and the more * it has), the more repeats you are making in the recursive calls. In my case I used cache for that.

With just those 2 changes I think your code would be greatly improved.

Another observation is that it is not necessary to try for each index writing the 3 letters. When we have a wildcard, we only need to try using the letter from previous index and the letter that is more ahead (str[index + n]) because the third letter has no inference in that range. When we don´t have a wildcard, there is only 1 choice of letter to make.

My final observation is that if there is "nothing for a long way", it is not necessary to try writing at several indexes thinking it is necessary to "leave space" in case we have a different letter "soon". This completely cuts the branching in these cases, which further helps on performance. I defined "long way" as block_size * 2 as I am sure that is enough, but maybe it can be less than that.

Took me a while but can´t find anything else to improve. Although my code works for your test cases, more testing should be done as there might be some bugs. Your code took me 12s to solve, haven´t meassured mine but its definitely under 1s .

Here is my own solution with all these ideas:

    #include <iostream>
    #include <algorithm>

    #include <vector>
    #include <math.h>

    using namespace std;


    vector<int> next_letter;
    vector<int> letter_qty[3];
    vector<int> cache[3];
    int block_size;
    string str;

    const int MAX = 1000000;

    int solve(int index, char last_char);

    int idx(char c) {
        return c - 'X';
    }

    // O(1) check if we can write block_size times want character starting at str[index]
    int solve2(int index, char want) {
        if (letter_qty[idx(want)][index] != letter_qty[idx(want)][min(index + block_size - 1, (int)str.length() - 1)]) return MAX;


        return solve(index + block_size, want);
    }

    //this is what truly speeds up the algorithm as it cuts branching if there "are not obstacles"
    //the idea is that if we want to write an X, if there is no Y or Z "far ahead" (from index to index + block_size * 2), we can just write it instead of writing on all possible positions
    bool obstaclesInTheWay (int index, char last_char) {
        return index + block_size * 2 >= str.length() || last_char == '*' || letter_qty[idx(last_char)][index] != letter_qty[idx(last_char)][index + block_size * 2];
    }

    //index is where we are, last_char is the last_char used for writing. There is always at least block_size times the last_char before index. This way we avoid using a buffer to know what´s behind
    int solve(int index, char last_char) {

        if (index == str.length()) return 0;
        if (index > str.length()) return MAX;

        if (cache[idx(last_char)][index] != -1) return cache[idx(last_char)][index]; //avoid recalculating

        int sol = MAX;

        if (str[index] == '*') { // if there is wildcard, we can either use next letter to write or expand from lower indexes with last_char
            sol = solve2(index, next_letter[index]);
        } else { // if not, our only choice is to write with that letter
            sol = solve2(index, str[index]);
            if (last_char != str[index]) return cache[idx(last_char)][index] = sol + 1; // if that letter is not the same as last one, there is no sense in trying to expand from lower indexes
        }

        if (obstaclesInTheWay(index, last_char)) { // try using last_char in range [index - block_size + 1, index]
            for (int i = max(index - (block_size - 1), 0); i <= index; i++) {
                sol = min(sol, solve2(i, last_char));
            }
        }

        return cache[idx(last_char)][index] = sol + 1;

    }

    int compute(int L, int C) {
        int best_cost = str.length() * C + L; // always possible with size 1

        for (block_size = 2; block_size <= str.length(); block_size++) {
            int estimated_cost = ceil(str.length() / block_size) * C + L * block_size; // a lower bound of the cost, no sense in trying if lower bound will be greater than best
            if (estimated_cost >= best_cost) continue;

            for(int j = 0; j < 3; j++) {
                fill(cache[j].begin(), cache[j].end(), -1); //clearing cache
            }

            int writings = solve(0, 'X');
            best_cost = min(best_cost, writings * C + L * block_size);

            if (writings >= MAX) break; // if its not possible to make with size block_size, won´t be possible with any greater size either
        }

        return best_cost;
    }

    //for each index we want to know the next letter ahead (not counting *)
    void fillNextLetter () {
        int idx = 0;

        for (int i = 1; i < str.length(); i++) {
            if (str[i] != '*') {
                while(idx < i) {
                    next_letter[idx++] = str[i];
                }
            }
        }

        // for cases where the end is filled with *, we put any letter as next
        while(idx < str.length()) {
            next_letter[idx++] = 'X';
        }
    }

    //we store for each letter, how many different letters appeared up to index i. With this, we can know if in a range there are only X (allowing *) or there is a Y or Z
    void fillLetterQty () {
        for (int j = 0; j < 3; j++) {
            letter_qty[j][0] = 0;
            for (int i = 1; i < str.length(); i++) {
                letter_qty[j][i] = letter_qty[j][i - 1] + (str[i] != 'X' + j && str[i] != '*'); 
            }
        }
    }

    int main () {
        int cases, L, C, N, expected;
        cin >> cases;


        for (int i = 1; i <= cases;i++) {
            cin >> N >> L >> C;
            cin >> str;

            next_letter.resize(N);

            for (int j = 0; j < 3; j++) {
                letter_qty[j].resize(N);
                cache[j].resize(N);
            }

            fillNextLetter();
            fillLetterQty();

            cin >> expected;
            cout << "#" << i << " " << compute(L, C) << "; expected = " << expected << '\n';
        }
    }