Challenge: Powercode
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464813127
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/powercode/problem
Cerinta
The longer the code, the stronger the code. The power number (**P**) of a code determines the strength of a code.
While computing the power number of a code we should ignore the keywords in the code. A few sample key words would be _int, unsigned, string, etc_. The power of a code can be determined by the number of characters in the code that **do not** belong to any of the keywords.
More formally, for each keyword **K**, consider all the occurrences of **K** in the code, ignore all these matching substrings while computing the power. See the example for clarity.
**Example:**
If you take a code to be
```
int main() { mlinteger a; return 0; }
```
The above code has **37** characters in total.
If the key words are
```
int
return
lint
integer
```
Then the power of the above code would be **20**, **spaces need to be counted**:
```
" main() { " --> 10
"m a; " --> 5
" 0; }" --> 5
```
The codes can be concatenated to be made more powerful. If we have two codes **C1**, **C2** with power **P1**, **P2**, the power of code **C1 $ C2** (here **$** denotes concatenation) will be **P1 + P2**.
While concatenating two codes, a **%** character gets inseted in between the two codes. For example if **C1** was `print 5;` and **C2** was `print 6;`, **C1 $ C2** = `print 5;%print 6;`
You are given **N** codes, **K** keywords, you can use each code as many number of times as you want. You are to output the largest power **X**, that can't be attained by concatinating the codes.
**Note:**
All the following operations are possible.
+ Two same codes can be concatenated with each other.
+ Some codes need not be used in the concatenation.
+ Each code can be used any number of times.
**Input Format**
First line contains **N**. In the following **N** lines, the **i**<sup>th</sup> line represents the code **C<sub>i</sub>**. The following line contains **K** the number of keywords. The following K lines one keyword each.
**Output Format**
Print a single line containing **X** as described above.
**Constraints**
```
1 <= N <= 10
1 <= |C_i| <= 100000
1 <= K <= 100
1 <= each keyword length <= 1000
```
**Note:**
+ Key words do not contain spaces. Both the code and the key words do not contain **%** character. They can contain any other ASCII character.
+ If the answer is infinite then print **-1**.
**Sample Input: #1**
```
5
lint maint lllint
int maint lllintl
lint maint lllint
lint maint lllint
lint maint lllint
2
int
lint
```
**Sample Output: #1**
```
29
```
**Sample Input: #2**
```
3
ababaac
babab
abcbab
1
bab
```
**Sample Output: #2**
```
5
```
**Explanation:**
In sample 1, the powers of codes are 6, 7, 6, 6. And hence the maximum unattainable power by combination is 29. In sample 2, the powers are 4, 0, 3, and hence the result is 5.Cod sursa
#include <bits/stdc++.h>
using namespace std;
struct Aho {
struct Node {
int next[128];
int link;
vector<int> out; // pattern lengths ending here
Node() : link(0) { memset(next, -1, sizeof(next)); }
};
vector<Node> t;
Aho() { t.emplace_back(); }
void addPattern(const string& s) {
int v = 0;
for (unsigned char ch : s) {
int c = (int)ch;
if (t[v].next[c] == -1) {
t[v].next[c] = (int)t.size();
t.emplace_back();
}
v = t[v].next[c];
}
t[v].out.push_back((int)s.size());
}
void build() {
queue<int> q;
for (int c = 0; c < 128; ++c) {
int u = t[0].next[c];
if (u == -1) {
t[0].next[c] = 0;
} else {
t[u].link = 0;
q.push(u);
}
}
while (!q.empty()) {
int v = q.front();
q.pop();
int lk = t[v].link;
if (!t[lk].out.empty()) {
auto &o = t[v].out;
o.insert(o.end(), t[lk].out.begin(), t[lk].out.end());
}
for (int c = 0; c < 128; ++c) {
int u = t[v].next[c];
if (u == -1) {
t[v].next[c] = t[lk].next[c];
} else {
t[u].link = t[lk].next[c];
q.push(u);
}
}
}
}
int powerOfCode(const string& code) const {
int n = (int)code.size();
vector<int> diff(n + 1, 0);
int v = 0;
for (int i = 0; i < n; ++i) {
unsigned char ch = (unsigned char)code[i];
int c = (int)ch;
if (c < 0 || c >= 128) c = 0;
v = t[v].next[c];
for (int L : t[v].out) {
int l = i - L + 1;
if (l >= 0) {
diff[l] += 1;
diff[i + 1] -= 1;
}
}
}
int covered = 0;
int cur = 0;
for (int i = 0; i < n; ++i) {
cur += diff[i];
if (cur > 0) ++covered;
}
return n - covered;
}
};
static inline void trimCR(string& s) {
if (!s.empty() && s.back() == '\r') s.pop_back();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string line;
if (!getline(cin, line)) return 0;
trimCR(line);
int N = stoi(line);
vector<string> codes(N);
for (int i = 0; i < N; ++i) {
getline(cin, codes[i]);
trimCR(codes[i]);
}
getline(cin, line);
trimCR(line);
int K = stoi(line);
Aho aho;
vector<string> keys(K);
for (int i = 0; i < K; ++i) {
getline(cin, keys[i]);
trimCR(keys[i]);
aho.addPattern(keys[i]);
}
aho.build();
vector<int> vals;
vals.reserve(N);
for (const string& c : codes) {
int p = aho.powerOfCode(c);
if (p > 0) vals.push_back(p);
}
if (vals.empty()) {
cout << -1 << '\n';
return 0;
}
auto gcd_int = [](int a, int b){ while (b){ int t = a % b; a = b; b = t; } return a < 0 ? -a : a; };
int g = 0;
for (int x : vals) g = gcd_int(g, x);
if (g != 1) {
cout << -1 << '\n';
return 0;
}
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int m = vals[0];
const long long INF = (1LL << 62);
vector<long long> dist(m, INF);
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto cur = pq.top();
pq.pop();
long long d = cur.first;
int r = cur.second;
if (d != dist[r]) continue;
for (int c : vals) {
int nr = (r + c) % m;
long long nd = d + c;
if (nd < dist[nr]) {
dist[nr] = nd;
pq.push({nd, nr});
}
}
}
long long mx = 0;
for (long long d : dist) mx = max(mx, d);
cout << (mx - m) << '\n';
return 0;
}
HackerRank Combinatorics – Powercode