Weighted Uniform String

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

string s; cin >> s;
int q, i; cin >> q;
vector<int> w;
char last = 0;
for (auto c : s)
{
    if (c == last)
        w.push_back(w.back()+c-'a'+1);
    else
        w.push_back(c-'a'+1);
    last = c;
}
sort(begin(w), end(w));
while (q--)
{
    cin >> i;
    cout << (binary_search(begin(w), end(w), i) ? "Yes" : "No") << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

string s; cin >> s;
int q, i; cin >> q;
set<int> w;

int last = 0;
int sum = 0;

for (auto c : s)
{
    int x = c-'a'+1;
    w.insert(x == last ? sum+x : x);
    sum = x == last ? sum+x : x;
    last = x;
}

while (q--)
{
    cin >> i;
    cout << (w.count(i) ? "Yes" : "No") << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import Data.List (sort)
import Data.Set (Set,member,fromList)

weight c = (fromEnum c) - (fromEnum 'a') + 1

-- Search q in the list
query :: Set Int -> Int -> Bool
query ws q = (member q ) ws

-- The list is optimized for searching
optimizeString :: String -> Set Int
optimizeString = fromList . sort . sumWeights . fmap weight

-- Map each number to the sum of previous equal numbers
-- e.g.: [1,2,3,3,4,4,4,5] -> [1,2,3,6,4,8,12,5]
sumWeights xs = ys where (_, _, ys) = foldl sumAdj (0, 0, []) xs

sumAdj (last, s, xs) x =
  if x == last
  then (x, s+x, s+x:xs)
  else (x,   x,   x:xs)

yesNo True = "Yes"
yesNo False = "No"

main = do
    contents <- getContents
    let (s:_:queries) = words contents
    let ws = optimizeString s
    putStrLn $ unlines $ yesNo <$> query ws <$> read <$> queries

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

'use strict';

// The actual solution
function weightedUniformStrings(s, queries) {
    const result = s.match(/([a-z])(\1)*/g);
    const values = result.flatMap((m) => Array.from(new Array(m.length),(val,index)=>(m.charCodeAt(0) - 97 + 1) * (index + 1)));
    return queries.map((q) => values.includes(q) ? 'Yes' : 'No')
}


// Boilerplate code
Array.prototype.flatMap = function(lambda) {
    return Array.prototype.concat.apply([], this.map(lambda));
};

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const s = readLine();

    const queriesCount = parseInt(readLine(), 10);

    let queries = [];

    for (let i = 0; i < queriesCount; i++) {
        const queriesItem = parseInt(readLine(), 10);
        queries.push(queriesItem);
    }

    let result = weightedUniformStrings(s, queries);

    ws.write(result.join("\n") + "\n");

    ws.end();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

string s; cin >> s;
int q, i; cin >> q;

map<char, int> weights;

char last = 0;
int count = 1;
s += '\0';
for (auto c : s)
{
    if (c == last) {
        ++count;
    } else if (last != 0) {
        weights[last-'a'+1] = max(weights[last-'a'+1], count * (last-'a'+1));
        count = 1;
    }
    last = c;
}

for (auto cw : weights) {
    cerr << int(cw.first) << " " << cw.second << "\n";
}

while (q--)
{
    cin >> i;

    bool found = false;
    for (auto cw : weights) {
        if (cw.second >= i && (i % cw.first == 0))
            found = true;
    }

    cout << (found ? "Yes" : "No") << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

std::string s;
int n;
std::cin >> s;
std::cin >> n;

/* Constraints:
 * w is at most 26
 * s length is at most 100'000
 * -> at most 2600000 possible substrings
 */
static constexpr int maxSubstrNum = 26 * 10e5;

/*
 * Please note that the default stack size on MSVC is 1 MB so allocating an
 * array of 2600000 bools will result in a stack overflow.
 * To workaround this issue you may use one of those:
 * - std::vector<usigned char> table(maxSubstrNum,0)
 * - std::vector<usigned char> table(26*s.size(),0)
 */
bool table[maxSubstrNum];
auto it = s.begin();
int last = 0;
int lastSum = 0;

/* Lazy evaluation of string character */
auto tryNext = [&](){
    if (it == s.end()) return false;

    int w = *it - 'a' + 1;

    if (w == last) {
        lastSum += w;
    } else {
        last = w;
        lastSum = w;
    }

    table[lastSum] = true;

    ++it;
    return true;
};

while (n--) {
    int x;
    std::cin >> x;

    /* If x is greater than 2600000, we already know it
     * cannot match without searching.
     * Evaluate next character in string only if we cannot find
     * any match in the already evaluated substrings.
     */
    while (x < maxSubstrNum && !table[x] && tryNext()); /* empty while body */

    /* At this point: match is found or all the substrings have been evaluated
     * without finding any match. */
    std::cout << (x < maxSubstrNum && table[x] ? "Yes\n" : "No\n");
}