Kaleido Kronos Cheers at i-Fest!
A celestial salute to the coding virtuosos who dazzled in the i-Relay coding contest at i-Fest! Your passion and commitment to refining your coding prowess make gatherings like these truly extraordinary. Let the echoes of applause resound for each and every one of you!
Here are the stellar solutions with illuminating explanations:
Setting $$$x_i = 1$$$ for all $$$i$$$ or $$$y_i = 1$$$ achieves the minimum value of $$$f = \sum_{i=1}^{n} x_i \cdot y((i+1)\%n)$$$. This choice ensures each $$$a_i$$$ fully contributes to the sum, simplifying the expression to $$$\sum_{i=1}^{n} 1 \cdot y((i+1)\%n)$$$. Alternatively, selecting $$$y_i = 1$$$ yields the same result.
With this, $$$f$$$ is minimized to $$$\sum_{i=1}^{n} 1 \cdot (a_i - 1) = \sum_{i=1}^{n} a_i - n$$$, resulting from $$$y_i$$$ being $$$a_i - 1$$$ due to $$$x_i = 1$$$ or $$$y_i = 1$$$. Thus, the total sum of $$$y_i$$$ is $$$\sum_{i=1}^{n} (a_i - 1) = \sum_{i=1}^{n} a_i - n$$$.
The minimum value of $$$f$$$ is achieved by selecting $$$x_i = 1$$$ or $$$y_i = 1$$$, ensuring $$$y_i = a_i - 1$$$ for all $$$i$$$.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
long long int sum = 0;
for(int i = 0; i < n; i++){
sum += arr[i];
}
long long int ans = sum - n;
cout << ans << "\n";
}
Given an array $$$a$$$ of integers, we aim to efficiently process multiple queries. For each query, we calculate $$$c$$$, representing the count of all elements in the subsegment $$$[a_l, a_r]$$$.
To optimize this process, we compute the prefix sums of the binary representation of array elements in O $$$(n \log(\max(a)))$$$. The array $$$Pre[i][j]$$$ denotes the count of $$$j$$$-th bits in the binary representation of the first $$$i$$$ elements of $$$a$$$.
For each query, we identify bits present in all elements of $$$[a_l, a_r]$$$ by checking $$$Pre[r][j] - Pre[l-1][j] = r - l + 1$$$ for each bit $$$j$$$. If true, the $$$j$$$-th bit is set in the result.
Utilizing a difference array for XOR, we create array $$$b$$$. For each query, $$$b[l] = c$$$ and $$$b[r+1] = c$$$. After all queries, we XOR the prefix sum of $$$b$$$ with elements of $$$a$$$.
The final result is stored in array $$$ans$$$, where $$$ans[i]$$$ reflects the result after processing queries up to the $$$i$$$-th element.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int v[n];
for(int i = 0; i < n; i++) cin >> v[i];
int pre[n+1][30];
for(int i = 0; i < 30; i++) pre[0][i] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < 30; j++){
pre[i+1][j] = pre[i][j];
pre[i+1][j] += ((v[i] >> j) & 1);
}
}
int q;
cin >> q;
int ans[n] = {0};
while(q--){
int l, r;
cin >> l >> r;
int result = 0;
for(int i = 0; i < 30; i++){
if(pre[r][i] - pre[l-1][i] == r - l + 1){
result |= (1 << i);
}
}
ans[l-1] ^= result;
if(r != n)
ans[r] ^= result;
}
for(int i = 1; i < n; i++){
ans[i] ^= ans[i-1];
}
for(int i = 0; i < n; i++){
ans[i] ^= v[i];
cout << ans[i] << " ";
}
cout << "\n";
}
We are solving the problem by utilizing Dynamic Programming. Let $$$dp[i]$$$ represent the maximum sum achievable when considering the substring from $$$s[0]$$$ to $$$s[i]$$$. For each $$$i$$$ from $$$0$$$ to $$$n-1$$$, we iterate through the previous $$$k$$$ positions and calculate the Maximum sum if we place a '+' sign at that position. The idea is to find the optimal placement of '+' signs to Maximize the sum.
So, the recursive relation is defined as follows: $$$dp[i] = \max(dp[i - j] + (s[i - j] - $$$'0'$$$))$$$ where the maximum is taken over all valid values of $$$j$$$ (from $$$1$$$ to $$$k$$$), and we ensure that the index $$$i - j$$$ is within bounds.
The final result is given by $$$dp[n - 1]$$$, which represents the maximum sum achievable considering the entire string. This dynamic programming approach efficiently explores all possible placements of '+' signs and computes the maximum sum.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
ll rev(ll i, string &s, vector<ll> &dp, ll k) {
if (dp[i] != -1)
return dp[i];
ll mx = INT_MIN;
ll curr = s[i] - '0';
ll p = 10;
for (ll j = 1; j <= k; j++) {
if (i - j >= 0) {
mx = max(mx, rev(i - j, s, dp, k) + curr);
curr = (s[i - j] - '0') * p + curr;
p *= 10;
} else {
mx = max(mx, curr);
break;
}
}
return dp[i] = mx;
}
void solve() {
ll n, k;
cin >> n >> k;
string s;
cin >> s;
vector<ll> dp(n, -1);
rev(n - 1, s, dp, k);
cout << dp[n - 1] << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t = 1;
for (ll T = 1; T <= t; T++) {
solve();
}
return 0;
}