SCPC Week 5 Tutorial

Kavya’s Flip Flops

Original Problem Link: https://codeforces.com/contest/2209/problem/A

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
void solve() {
    ll n, c, k;
    cin >> n >> c >> k;
    
    vector<ll> monsters(n);
    for (int i = 0; i < n; i++) {
        cin >> monsters[i];
    }
 
    sort(monsters.begin(), monsters.end());
 
    for (int i = 0; i < n; i++) {
        if (monsters[i] <= c) {
            int flop = min(k, c - monsters[i]);
            c += monsters[i] + flop;
            k -= flop;
        } else {
            break;
        }
    }
 
    cout << c << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; 
    cin >> t;
    while (t--) solve();
}

Lasers

Original Problem Link: https://codeforces.com/contest/2148/problem/B

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
void solve() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
 
    int temp;
    for (int i = 0; i < n; i++) {
        cin >> temp;
    }
 
    for (int i = 0; i < m; i++) {
        cin >> temp;
    }
 
    cout << n + m << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; 
    cin >> t;
    while (t--) solve();
}

SCPC.zip

Original Problem Link: https://codeforces.com/contest/2254/problem/B

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
 
    int ans = 1;
    int minus = 0;
    for (int i = 1; i < n; i++) {
        if (s[i] != s[i - 1]) 
            ans += 1;
 
        if (i < n - 1 and s[i] != s[i - 1] and s[i] != s[i + 1]) {
            if (s[i - 1] == s[i + 1])
                minus = 2;
            else
                minus = max(minus, 1);
        }
    }
 
    cout << ans - minus << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; 
    cin >> t;
    while (t--) solve();
}

Ryan and Arrays

Original Problem Link: https://codeforces.com/contest/1899/problem/C

Prefix Sum Solution:

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
void solve() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
 
    int sum = nums[0];
    int max_sum = nums[0];
    int min_sum = min(0, nums[0]);
    for (int i = 1; i < n; i++) {
        if (abs(nums[i] % 2) == abs(nums[i - 1] % 2)) {
            sum = 0;
            min_sum = 0;
        }
 
        sum += nums[i];
        max_sum = max(max_sum, sum - min_sum);
        min_sum = min(min_sum, sum);
    }
 
    cout << max_sum << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; 
    cin >> t;
    while (t--) solve();
}

Kadane’s Algorithm Solution:

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
void solve() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
 
    int sum = nums[0];
    int max_sum = nums[0];
    for (int i = 1; i < n; i++) {
        if (abs(nums[i] % 2) == abs(nums[i - 1] % 2))
            sum = 0;
            
        sum = max(nums[i], sum + nums[i]);
        max_sum = max(max_sum, sum);
    }
 
    cout << max_sum << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; 
    cin >> t;
    while (t--) solve();
}

Fair and Square

Original Codeforces Link: https://codeforces.com/contest/2241/problem/E

Straightforward Solution:

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
const int N = 1e6;
vector<int> adj[N];
int parent[N];
int visited[N];
ll subtree_size[N];
 
 
ll fill_size(int u) {
    if (visited[u]) 
        return 0;
    else
        visited[u] = true;
 
    ll sum = 1;
    for (auto v: adj[u]) {
        if (visited[v]) continue;
 
        parent[v] = u;
        sum += fill_size(v);
    }
    
    subtree_size[u] = sum;
    return sum;
}
 
void solve() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        adj[i].clear();
        parent[i] = -1;
        visited[i] = false;
        subtree_size[i] = 0;
    }
 
    vector<ll> node_num(n);
    for (int i = 0; i < n; i++) {
        cin >> node_num[i];
    }
 
    int a, b;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        adj[a - 1].push_back(b - 1);
        adj[b - 1].push_back(a - 1);
    }
 
    fill_size(0);
 
    ll sum = 0, pairs = 0, triplets = 0, total_sum = 0;
    for (int i = 0; i < n; i++) {
        if ((ll) sqrtl(node_num[i]) * (ll) sqrtl(node_num[i]) == node_num[i]) {
            sum = subtree_size[0] - subtree_size[i];
            pairs = 0, triplets = 0;
            
            for (auto v : adj[i]) {
                if (parent[i] == v) continue;
 
                triplets += subtree_size[v] * pairs;
                pairs += subtree_size[v] * sum;
                sum += subtree_size[v];
            }
            
            total_sum += pairs + triplets;
        }
    }
 
    cout << total_sum << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; 
    cin >> t;
    while (t--) solve();
}

Simplified Solution:

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
const int N = 1e6;
vector<int> adj[N];
int visited[N];
ll node_num[N];
ll subtree_size[N];
ll total_sum;
 
ll dfs(int n, int u) {
    if (visited[u]) 
        return 0;
    else
        visited[u] = true;
 
    subtree_size[u] = 1;
 
    bool is_square = (ll) sqrt(node_num[u]) * (ll) sqrt(node_num[u]) == node_num[u];
    ll sze = 0, sum = 0, pairs = 0, triplets = 0;
    for (auto v: adj[u]) {
        if (visited[v]) continue;
 
        sze = dfs(n, v);
        subtree_size[u] += sze;
 
        if (is_square) {
            triplets += sze * pairs;
            pairs += sze * sum;
            sum += sze;
        }
    }
 
    if (is_square) {
        triplets += (n - subtree_size[u]) * pairs;
        pairs += (n - subtree_size[u]) * sum;
    }
                 
    total_sum += pairs + triplets;
    
    return subtree_size[u];
}
 
void solve() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        adj[i].clear();
        visited[i] = false;
        node_num[i] = 0;
        subtree_size[i] = 0;
    }
 
    for (int i = 0; i < n; i++) {
        cin >> node_num[i];
    }
 
    int a, b;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        adj[a - 1].push_back(b - 1);
        adj[b - 1].push_back(a - 1);
    }
 
    total_sum = 0;
    dfs(n, 0);
 
    cout << total_sum << endl;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; 
    cin >> t;
    while (t--) solve();
}