PROBLEM LINK:
Practice
Contest, div. 1
Contest, div. 2
Author: Utkarsh Sinha
Tester: Zhong Ziqian
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP, bitmasks
PROBLEM:
You’re given array A_1,\dots,A_N, you have to split it into K segments to maximize sweetness of this partition, which is defined as follows: Firstly each A_i will be multiplied by some number t_i. Then sweetness S_i of each segment is defined as sum of sweetnesses of all elements in it. Sweetness of the whole partition is defined as S_1 * S_2 * \dots * S_k where * is defined as follows:
You will have Q queries with given t_i for each query, constraints:
- 1 \leq Q \leq 10
- 1 \leq K, N \leq 10^5
- 1 \leq A_i \leq 10^{15}
- 0 \leq t_i \leq 10
- At most 50 of t_i will not be equal to zero.
QUICK EXPLANATION:
Just a bit of bit magic and observations.
EXPLANATION:
You may immediately recognize that x*y is simply bitwise and of x and y. Then you should note that there is no reason to have any segment with sweetness 0, thus we may simply ignore all indexes i having t_i = 0 and assume that N \leq 50. Let’s deal with the following subproblem: Given number mask you have to check if there’s a partition such that mask is a submask of its sweetness. It may be done via simple DP in O(m^2 k):
bool check(vector<int> a, int mask, int k) {
int m = a.size();
int dp[m + 1][k + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 1; i <= m; i++) {
int sum = 0;
for(int j = i; j > 0; j--) {
sum += a[j - 1];
if((sum & mask) == mask) {
for(int t = 1; t <= k; t++) {
dp[i][t] |= dp[j - 1][t - 1];
}
}
}
}
return dp[m][k];
}
With this function we may greedily check bits in answer and set them to 1 whenever possible. Assume that ta is the array of non-zero t_i A_i, then solution looks like this:
if(k > ta.size()) {
cout << 0 << "\n";
} else {
int l = 0, r = 1LL << 55;
while(r - l > 1) {
int m = (l + r) / 2;
if(check(ta, m, k)) {
l = m;
} else {
r = m;
}
}
cout << l << endl;
}
Note that though we used binary search here, function is not monotonic in common sense but it’s monotonic in terms of logic functions, that is if u is submask of v then f(u) \leq f(v). Turns out it’s also enough to utilize simple binary search in particular case of l=0 and r=2^k and it will find lexicographically largest mask on which check is equal to 1.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.
