/**
* Notes during contest.
*
* ------ A ------
* In the example, (3,7,6,6) is the set of optimal pillars to select. Well, I assume
* that the subset of pillars shall be connected in order? First, sum all costs of
* pillars. The cost of pillars that are used will then be deducted from the total.
* Our dp formula is:
* dp[k] = min( dp[i] + (h[k] - h[i])^2 - c[k])
* = min( (dp[i] + h[i]^2) - 2h[i] * h[k] ) + (h[k]^2 - c[k])
* This looks like sth that can be solved with dynamic convex hull trick. IMO this
* is like the only way to AC this problem. Unfortunately, I don't know how to code
* one using std::set<>, nor do I know LiChao tree. Maybe I'll just head to problem
* C.
* [After contest]
* First of all, I think i should've noticed the small size of |w_i| in [S2] allows
* us to store things in a std::set<> for each value of w_i. Now, without a time
* limit, let's try LiChao tree in impl2, and perhaps the dynamic convex hull trick
* optimization in impl3 (notoriously difficult to code...).
*
* ------ B ------
* [S1-2] is solvable with a O(n^2) dp (Z-array + dp). I also have a hunch that we
* can pass [S3] too (#time_limit = 10s). Oh no... I really suck at str processing
* problems... I guess 60 points would be my limit.
* [After contest]
* Well, so sad that I wasn't sure about the greedy approach (which turned out to be
* correct): each time we try to chunk off the shortest prefix & suffix of our str.
* Why is this correct? Suppose that the greedy algo. and an optimal way of chunking
* differs at a certain point, i.e. the greedy algo proposes to remove a prefix &
* suffix C but in the optimal case C' is removed. Note that C would be a prefix of
* C'. When |C| <= |C'| / 2, C' = CXC (concat, X is a possibly empty str), so
* (C)(X)(C) would be a better partition. This gives us the courage to deduce further
* properties. The way i came up with proving this is to use the lemma in
* https://cses.fi/problemset/task/1733; this shows that a prefix of
* C'.substr(0,|C'|-|C|) is a period of C'. So just take the front portion of the
* period, (X) and the last part of the period in C' to form a better partition.
*
* ------ C ------
* Can we score some partials here? Clearly, when Tom visits the route, only the
* last node has pigeons, so #pigeons_Tom_meets = #last_node_in_route. OK. Let V be
* the set of nodes in the route, so |V| <= v and
* #pigeons_Tom_meets = sum{ p_i : i is adjacent to at least one node in V
* or i is in V }. (Wrong, see below)
* We also know that #pigeons_Jerry_meets = p_i where i is the first node. This means
* we can solve [S1-3]. Looks like DFS + dp on tree is good enough to solve the whole
* problem!
* --------------------------------- After contest -----------------------------------
* I totally misunderstood the problem... Took me over an hour in the contest.. The
* stuff above is wrong... Full solution is a standard dfs + dp on tree in O(nv).
*
* Time Complexity 1: O(n * log(n))
* Time Complexity 2: O(n * log(n)) (non-deterministic)
* Time Complexity 3: O(n * v)
* Implementation 2 (Full solution, str hashing)
*/
#include <bits/stdc++.h>
typedef int64_t int_t;
typedef std::vector<int_t> vec;
inline int_t pow(int_t a, int_t b, int_t mod) {
int_t res = 1;
while (b > 0) {
if (b % 2 == 1)
res = res * a % mod;
a = a * a % mod, b /= 2;
}
return res;
}
// Rolling hash class. Each element of params is a pair of (p, m)
struct RH { // rolling hash
std::vector<vec> ps;
std::vector<vec> pre_hash;
RH(std::vector<vec> params, const std::string& str) {
ps = params;
int_t sets = params.size(), n = str.size();
pre_hash.assign(sets, vec(n + 1));
for (int_t s = 0; s < sets; s++) {
int_t p = params[s][0], m = params[s][1];
pre_hash[s][0] = 0;
for (int_t k = 0; k < n; k++)
pre_hash[s][k + 1] = pre_hash[s][k] * m % p + (str[k] - 'a');
}
}
bool equal(int_t s1, int_t l1, int_t s2, int_t l2) {
bool is = true;
for (int_t s = 0; s < int_t(ps.size()) && is; s++) {
int_t p = ps[s][0], m = ps[s][1];
int_t h1 = pre_hash[s][s1 + l1] - pre_hash[s][s1] * pow(m, l1, p) % p;
int_t h2 = pre_hash[s][s2 + l2] - pre_hash[s][s2] * pow(m, l2, p) % p;
h1 = (h1 % p + p) % p, h2 = (h2 % p + p) % p;
is &= (h1 == h2);
}
return is;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int_t T;
std::cin >> T;
for (int_t tc = 1; tc <= T; tc++) {
std::string str;
std::cin >> str;
int_t n = str.length();
// 3 is a primitive root of 998244353 (well-known)
RH hash({{998244353, 3}, {int_t(1e9) + 7, 5}}, str);
int_t count = 0;
for (int_t left = 0, right = n - 1; left <= right; ) {
int_t len = 1;
while (2 * len <= right - left + 1
&& !hash.equal(left, len, right - len + 1, len)) {
len++;
}
if (2 * len <= right - left + 1) {
count += 2, left += len, right -= len;
} else {
count += 1;
break;
}
}
std::cout << count << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
10 ms |
568 KB |
Output is correct |
| 11 |
Correct |
7 ms |
492 KB |
Output is correct |
| 12 |
Correct |
9 ms |
552 KB |
Output is correct |
| 13 |
Correct |
5 ms |
528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
10 ms |
568 KB |
Output is correct |
| 11 |
Correct |
7 ms |
492 KB |
Output is correct |
| 12 |
Correct |
9 ms |
552 KB |
Output is correct |
| 13 |
Correct |
5 ms |
528 KB |
Output is correct |
| 14 |
Correct |
1299 ms |
28460 KB |
Output is correct |
| 15 |
Correct |
1048 ms |
27488 KB |
Output is correct |
| 16 |
Correct |
1301 ms |
27136 KB |
Output is correct |
| 17 |
Correct |
324 ms |
16400 KB |
Output is correct |
