- Prepare
- Algorithms
- Strings
- Letter Islands
- Discussions
Letter Islands
Letter Islands
+ 0 comments C++ Solution
#include <algorithm> #include <climits> #include <cstdio> #include <cstring> #include <map> #include <set> #include <stack> #include <utility> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef long long ll; typedef pair<int, int> pii; #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) for (int i = 0; i < (n); i++) #define ROF(i, a, b) for (int i = (b); --i >= (a); ) struct Pos { static int id; set<int> a; tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> d; int countLT(int key) { return d.order_of_key(pii(key, 0)); } size_t size() { return a.size(); } void insert(int i) { a.insert(i); auto it = a.lower_bound(i); auto prev = it, next = it; if (it != a.begin()) --prev; if (it != a.end()) ++next; if (it != prev) { d.insert(pii{*it-*prev, id++}); if (it != next && next != a.end()) d.erase(d.lower_bound(pii{*next-*prev, 0})); } if (it != next && next != a.end()) d.insert(pii{*next-*it, id++}); } void join(Pos &b) { for (int x: b.a) insert(x); } Pos() = default; Pos(Pos &&b) { a.swap(b.a); d.swap(b.d); } Pos &operator=(Pos &&b) noexcept { a.swap(b.a); d.swap(b.d); return *this; } }; int Pos::id = 0, n, k; ll ans; namespace KoAluru { bool *t; int *b; template<typename T> void bucket(T a[], int n, int k, bool end) { fill_n(b, k, 0); REP(i, n) b[a[i]]++; if (end) FOR(i, 1, k) b[i] += b[i-1]; else { int s = 0; REP(i, k) s += b[i], b[i] = s-b[i]; } } template<typename T> void plus_to_minus(T a[], int sa[], int n, int k) { bucket(a, n, k, false); sa[b[a[n-1]]++] = n-1; REP(i, n-1) { int j = sa[i]-1; if (j >= 0 && ! t[j]) sa[b[a[j]]++] = j; } } template<typename T> void minus_to_plus(T a[], int sa[], int n, int k) { bucket(a, n, k, true); ROF(i, 0, n) { int j = sa[i]-1; if (j >= 0 && t[j]) sa[--b[a[j]]] = j; } } template<typename T> void ka(T a[], int sa[], int n, int k) { t[n-1] = false; ROF(i, 0, n-1) t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1]; bool minor = 2 * count(t, t+n, false) > n; bucket(a, n, k, minor); fill_n(sa, n, -1); if (minor) { REP(i, n) if (t[i]) sa[--b[a[i]]] = i; plus_to_minus(a, sa, n, k); minus_to_plus(a, sa, n, k); } else { sa[b[a[n-1]]++] = n-1; REP(i, n-1) if (! t[i]) sa[b[a[i]]++] = i; minus_to_plus(a, sa, n, k); plus_to_minus(a, sa, n, k); } int last = -1, name = 0, nn = count(t, t+n, minor); int *sa2, *pi; if (minor) sa2 = sa, pi = sa+n-nn; else sa2 = sa+n-nn, pi = sa; fill_n(b, n, -1); REP(i, n) if (sa[i] >= 0 && minor == t[sa[i]]) { bool diff = last == -1; int p = sa[i]; if (! diff) REP(j, n) { if (last+j >= n || p+j >= n || a[last+j] != a[p+j] || t[last+j] != t[p+j]) { diff = true; break; } else if (j > 0 && (minor == t[last+j] || minor == t[p+j])) break; } if (diff) { name++; last = p; } b[p] = name-1; } nn = 0; REP(i, n) if (b[i] >= 0) pi[nn++] = b[i]; if (name < nn) ka(pi, sa2, nn, name); else REP(i, nn) sa2[pi[i]] = i; ROF(i, 0, nn) t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1]; nn = 0; bucket(a, n, k, minor); if (minor) { REP(i, n) if (minor == t[i]) pi[nn++] = i; REP(i, nn) sa[i] = pi[sa2[i]]; ROF(i, 0, nn) { int j = sa[i]; sa[i] = -1; sa[--b[a[j]]] = j; } } else { REP(i, n) if (minor == t[i]) pi[nn++] = i; ROF(i, 0, nn) sa[n-nn+i] = pi[sa2[i]]; REP(i, nn) { int j = sa[n-nn+i]; sa[n-nn+i] = -1; sa[b[a[j]]++] = j; } } if (minor) plus_to_minus(a, sa, n, k); else minus_to_plus(a, sa, n, k); } template<typename T> void main(T a[], int sa[], int b[], int n, int k) { if (n > 0) { KoAluru::b = b; t = new bool[n]; ka(a, sa, n, k); delete[] t; } } template<typename T> void calc_rank_lcp(T a[], int sa[], int n, int rank[], int lcp[]) { REP(i, n) rank[sa[i]] = i; int k = 0; lcp[0] = 0; FOR(i, 0, n) if (rank[i]) { for (int j = sa[rank[i]-1]; i+k < n && j+k < n && a[i+k] == a[j+k]; k++); lcp[rank[i]] = k; k && k--; } } void calc_child(int lcp[], int n, int child[]) { stack<int> st; st.push(0); int last = -1; fill_n(child, n, -1); FOR(i, 1, n) { while (lcp[i] < lcp[st.top()]) { last = st.top(); st.pop(); if (lcp[i] <= lcp[st.top()] && lcp[st.top()] != lcp[last]) child[st.top()] = last; } if (last != -1) { child[i-1] = last; last = -1; } st.push(i); } while (0 < lcp[st.top()]) { last = st.top(); st.pop(); if (0 <= lcp[st.top()] && lcp[st.top()] != lcp[last]) child[st.top()] = last; } while (! st.empty()) st.pop(); st.push(0); FOR(i, 1, n) { while (lcp[i] < lcp[st.top()]) st.pop(); if (lcp[i] == lcp[st.top()]) { child[st.top()] = i; st.pop(); } st.push(i); } } void top_down(int sa[], int lcp[], int child[], int l, int h, int ht, Pos &data) { int ht2; if (l == h-1) { ht2 = n-sa[l]; data.insert(sa[l]); } else { int i = l < child[h-1] && child[h-1] < h ? child[h-1] : child[l]; ht2 = lcp[i]; { Pos cur; top_down(sa, lcp, child, l, i, ht2, cur); if (cur.size() > data.size()) swap(cur, data); data.join(cur); } for (; child[i] > i && lcp[child[i]] == lcp[i]; i = child[i]) { Pos cur; top_down(sa, lcp, child, i, child[i], ht2, cur); if (cur.size() > data.size()) swap(cur, data); data.join(cur); } { Pos cur; top_down(sa, lcp, child, i, h, ht2, cur); if (cur.size() > data.size()) swap(cur, data); data.join(cur); } } l = ht+1; h = ht2+1; while (l < h) { int mi = l+h >> 1; if (k < data.size()-data.countLT(mi+1)) l = mi+1; else h = mi; } int from = l; h = ht2+1; while (l < h) { int mi = l+h >> 1; if (k <= data.size()-data.countLT(mi+1)) l = mi+1; else h = mi; } ans += l-from; } }; const int N = 100000; char a[N+1]; int b[N], sa[N], rnk[N], lcp[N], child[N]; int main() { scanf("%s%d", a, &k); n = strlen(a); KoAluru::main(a, sa, b, n, 127); KoAluru::calc_rank_lcp(a, sa, n, rnk, lcp); KoAluru::calc_child(lcp, n, child); Pos data; KoAluru::top_down(sa, lcp, child, 0, n, 0, data); printf("%lld\n", ans); }
+ 0 comments https://zeroplusfour.com/letter-islands/
Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.
+ 0 comments I've already submitted the code and not all the test cases were correct. When I'm trying to submit again, the code which is working in my terminal is reportedly not clearing even sample test case.
I even downloaded some test cases from the previous submissions and checked on them in my terminal. They are also working fine.( test case #6) What should I do now
+ 1 comment Hello,
My code has passed 26 test cases and shows timeout for 7 test cases (#12 and 26-31). On "submissions" page I can see timeout as 3s but on my PC the code is producing correct output for #12 in about 2s and for #29 about 1s. Can anyone please tell me what is the real timeout?
Best Regards
+ 2 comments For Test Case #5. Here's the input and expected output: Input: aaaabababbaabaaabababbababaabaababaababaabaababaaa 3 Output: 5
However, should the output be 7? Here are the 7 substrings that I get that create 3 islands: aaa baaba aabaa ababaa babaa abaaba baabaa
Let me know your thoughts.
Sort 17 Discussions, By:
Please Login in order to post a comment