DWW19I - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ankush Khanna

DIFFICULTY:

Easy

PREREQUISITES:

Basic Mathematics, GCD

PROBLEM:

Given a sequence A of N integers denoting gaps, we need to fill these gaps with wires of equal length. Determine the length of each wire so as to minimize the number of wires used.

QUICK EXPLANATION:

The best wire length is the GCD of all the gaps, so the minimum possible cost is \Bigg(\frac{\sum\limits_{i = 1}^{N}{A_{i}}}{\gcd(A_{1 \dots N})}\Bigg) \space (which is the number of wires needed).

EXPLANATION:

We need to choose an appropriate length for the wires such that they fit in all the N integer gaps mentioned in A. We can join two or more wires to cover a gap, but we cannot break any wire into two or more wires of smaller lengths. Also, an important thing is the end note provided in the problem statement which states:
You cannot make a connection which requires a wire piece of length X with a wire piece of length Y if X \neq Y.
Let’s call this as the fit property.
This means that we need to have wires (or create them by joining two or more) of exact lengths as the gaps.

Summing up all of the above mentioned constraints, we can easily figure out that length 1 is always a solution. But another thing to consider is the following:

It is also mentioned that we have to minimize the total expenditure on wires, where the cost of each wire is 1. This straightaway implies that we have to minimize the number of wires. Another implication of this fact is that we should always choose the length of the wire as large as possible.

A simple proof of this argument is that if we choose the wire length as large as possible, then the total number of wires will be minimized. Another thing worth making note here is that the total length of all the wires is \sum\limits_{i = 1}^{N}{A_{i}}. This can be easily inferred from the fit property.
Let’s say that the number of wires required are K, then the length of each wire is \space \Bigg(\frac{\sum\limits_{i = 1}^{N}{A_{i}}}{K}\Bigg). This even shows us the inverse relation and hence proves the fact that maximizing the length of each wire will minimize the number of wires, and hence the total cost (expenditure).

Now that we know what we want, we just need to know how to do it. The length should also divide each of the N integers in A, to be able to follow the fit property (after being single or being joined with one or more wires). Also, it should be as large as possible. Hey, that’s what the GCD of N integers is!

So, we just need to find the GCD of the A_{1 \dots N}, which will serve as the length of each wire, and hence the minimum cost will be \Bigg(\frac{\sum\limits_{i = 1}^{N}{A_{i}}}{\gcd(A_{1 \dots N})}\Bigg).

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        long sum = 0L, ans = 0L;
        for (int i = 0; i < n; i++) {
            long x;
            cin >> x;
            sum += x;
            ans = __gcd(ans, x);
        }
        cout << ans << ' ' << (sum / ans) << '\n';
    }
    return 0;
}

COMPLEXITY:

Time complexity: As Euclidean Algorithm for calculating GCD of two numbers a and b works in O(\log{\max\{a, b\}}), and we do this for all of the N integers in A in each test, therefore, the total time complexity is O(N \log \max\{A_{1 \dots N}\}) per test.

Space Complexity: O(1) auxiliary space per test.

Feel free to share your approach. If you have any queries, they are always welcome.