Help with ZCO 2025 practice problem

#	User	Rating
1	jiangly	3976
2	tourist	3815
3	jqdai0815	3682
4	ksun48	3614
5	orzdevinwang	3526
6	ecnerwala	3514
7	Benq	3482
8	hos.lyric	3382
9	gamegame	3374
10	heuristica	3357

#	User	Contrib.
1	cry	169
2	-is-this-fft-	166
3	Um_nik	161
3	atcoder_official	161
5	djm03178	157
6	Dominater069	156
7	adamant	154
8	luogu_official	152
9	awoo	151
10	TheScrasse	147

I am stuck on this problem.

Problem Synopsis:
You are given an array A of size N.
Consider an undirected edge-weighted graph with N nodes numbered from 1 to N such that for any two nodes i and j there is an undirected edge between i and j with weight |i-j| * max(A[i], A[j]).
Find the weight of the shortest path between two given nodes X and Y.

Input Format:
The first line contains a single integer T, the number of test cases.
The first line of each test case contains three integers N, X and Y.
The second line of each test case contains N integers, A[1] A[2] ... A[N].

Output Format
For each test case, print a single integer, the weight of the shortest path, on a separate line.

I have a working solution for the first 3 subtasks but have run out of ideas for the last one.
Any help would be appreciated.

my solution

#include <bits/stdc++.h>
using ll = long long;
using std::cin;
using std::cout;
using std::vector;
using std::min;
using std::max;
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--){
        ll n, dump;
        cin >> n >> dump >> dump;
        vector<ll> a(n);
        for (ll& x : a)
            cin >> x;
        vector<ll> ans(n), seq{0};
        for (ll idx = 1; idx < n; ++idx){
            ll safety = seq.front();
            while (!seq.empty() && a[seq.back()] > a[idx])
                seq.pop_back();
            ll prev_idx = seq.empty() ? safety : seq.back();
            ans[idx] = ans[prev_idx] + (idx - prev_idx) * max(a[prev_idx], a[idx]);
            seq.push_back(idx);
        }
        cout << ans.back() << '\n';
    }
}

f(n, k) = min(best_a, best_b) best_a = min( f(n-1, k-1) + sum_a(n, n), f(n-2, k-1) + sum_a(n-1, n), ..., f(1, k-1) + sum_a(2, n), ) best_b = min( f(n-1, k-1) + sum_b(n, n), f(n-2, k-1) + sum_b(n-1, n), ..., f(1, k-1) + sum_b(2, n), )

Comments (3)

Write comment?

Neev4321

6 weeks ago, # |

+13

I found the solution (which surprisingly, builds upon the last solution)!
Leaving this here for anyone also searching for the solution.

my code

#include <bits/stdc++.h>
using ll = long long;
using std::cin;
using std::cout;
using std::pair;
using std::vector;
using std::set;
using std::min;
using std::max;
using graph_t = vector<vector<pair<ll, ll>>>;
graph_t get_graph(const vector<ll>& a){
    ll n = a.size();
    graph_t graph(n);
    vector<ll> seq{0};
    auto add_node = [&](ll u, ll v){
        graph[u].emplace_back(std::abs(u - v) * max(a[u], a[v]), v);
    };
    auto update = [&](ll idx){
        while (!seq.empty() && a[seq.back()] > a[idx]){
            add_node(idx, seq.back());
            seq.pop_back();
        }
        if (!seq.empty())
            add_node(idx, seq.back());
        seq.push_back(idx);
    };
    for (ll i = 1; i < n; ++i)
        update(i);
    seq.clear();
    seq.push_back(n - 1);
    for (ll i = n - 2; i >= 0; --i)
        update(i);
    return graph;
}
vector<ll> get_dist(const graph_t& graph, ll start){
    vector<ll> ans(graph.size(), LLONG_MAX);
    ans[start] = 0;
    set<pair<ll, ll>> to_do;
    to_do.emplace(0, start);
    while (!to_do.empty()){
        ll node = to_do.begin()->second;
        to_do.erase(to_do.begin());
        for (const auto& [cost, neigh] : graph[node]){
            if (ans[node] + cost < ans[neigh]){
                to_do.erase({ans[neigh], neigh});
                ans[neigh] = ans[node] + cost;
                to_do.emplace(ans[neigh], neigh);
            }
        }
    }
    return ans;
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--){
        ll n, start, end;
        cin >> n >> start >> end;
        --start, --end;
        vector<ll> a(n);
        for (ll& x : a)
            cin >> x;
        cout << get_dist(get_graph(a), start)[end] << '\n';
    }
}

→ Reply

xsyncwave

Hello, Did you come up with any solution to solve Problem B: Two Arrays of the same contest? I would like to know your approach.

6 weeks ago, # ^ |

I used DP (dynamic programming) with the recurrence:

f(n, k) = min(
    f(n-1, k-1) + cost(n, n),
    f(n-2, k-1) + cost(n-1, n),
    ...,
    f(1, k-1) + cost(2, n)
)

This recurrence can be simplified to:

#include <bits/stdc++.h>
using ll = long long;
#define RANGE(x) std::begin(x), std::end(x)
using std::cin;
using std::cout;
using std::vector;
using std::min;
using std::max;
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n), b(n);
    for (ll& x : a)
        cin >> x;
    for (ll& x : b)
        cin >> x;
        
    vector<ll> a_prefix(n), b_prefix(n);
    std::partial_sum(RANGE(a), a_prefix.begin());
    std::partial_sum(RANGE(b), b_prefix.begin());
    auto cost = [&](ll l, ll r){
        if (l > r)
            return 0ll;
        ll a_cost = a_prefix[r] - ((l == 0) ? 0 : a_prefix[l - 1]);
        ll b_cost = b_prefix[r] - ((l == 0) ? 0 : b_prefix[l - 1]);
        return min(a_cost, b_cost);
    };
    auto add = [](ll x, ll y){
        if (x == LLONG_MAX || y == LLONG_MAX)
            return LLONG_MAX;
        return x + y;
    };
    
    vector<vector<ll>> dp(n, vector<ll>(k, LLONG_MAX));
    for (ll i = 0; i < n; ++i)
        dp[i][1] = cost(0, i);
    for (ll j = 2; j < k; ++j){
        ll best_a = LLONG_MAX, best_b = LLONG_MAX;
        for (ll i = 1; i < n; ++i){
            best_a = add(min(best_a, dp[i - 1][j - 1]), a[i]);
            best_b = add(min(best_b, dp[i - 1][j - 1]), b[i]);
            dp[i][j] = min(best_a, best_b);
        }
    }
    
    ll ans = LLONG_MAX;
    for (ll i = 0; i < n; ++i)
        ans = min(ans, add(dp[i][k - 1], cost(i + 1, n - 1)));
    cout << ans;
}

Neev4321's blog