Maximum Perimeter Triangle

Solutions

This problem simulates the situation when you need some additional “domain knowledge” to find a solution. In this case the domain is “geometry” and you have to find (or recall) the Triangle inequality:

for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side

In other terms, for any three sticks \(a, b, c\), the following must be true:

\( a > b + c\)
\( b > a + c\)
\( c > a + b\)

Since we want the maximum perimeter triangle, we can sort the sticks in descending order and check for each triple of adjacent sticks if the inequality is verified:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int n;
cin >> n;
vector<int> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
sort(begin(v), end(v), greater<>{});
for (auto i=0; i<n-2; ++i)
{
    if (v[i+2] + v[i+1] > v[i])
    {
        cout << v[i+2] << " " << v[i+1] << " " << v[i];
        return 0;
    }
}
cout << -1;

Note that we only check:

\( b + c > a\)

since:

\( a > b > c\)

If the former is verified, we know that:

\( a + c > b\)

since \( a > b\)

And \( a + b > c\)

since \( a > c\)

The final cost is \( O(N \cdot log N) \).

We can improve code design by declaring a Triangle type and using std::optional to represent the “no solution” case:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


using Sticks = std::vector<int>;

struct Triangle {
  int a;
  int b;
  int c;
};

std::optional<Triangle> solve(Sticks sticks) {
  std::sort(sticks.begin(), sticks.end(), std::greater<>());

  for (int i = 2; i < sticks.size(); ++i) {
    Triangle t{
        sticks[i],
        sticks[i - 1],
        sticks[i - 2],
    };

    if (t.b + t.c > t.a) {
      return t;
    }
  }

  return std::nullopt;
}

Sticks read_sticks() {
  int n;
  std::cin >> n;
  Sticks sticks;
  sticks.resize(n);
  std::copy_n(std::istream_iterator<int>(std::cin), n, std::begin(sticks));
  return sticks;
}

std::ostream& operator<<(std::ostream& s, const Triangle& triangle) {
  std::cout << triangle.a << " ";
  std::cout << triangle.b << " ";
  std::cout << triangle.c;
  return s;
}

int main() {
  auto result = solve(read_sticks());

  if (result.has_value()) {
    std::cout << *result;
  } else {
    std::cout << "-1";
  }

  return 0;
}

Here is a fluent solution in Python:

1
2
3
4


def maximumPerimeterTriangle(sticks):
    sticks = sorted(sticks, reverse=True)
    sticks = zip(sticks, sticks[1:], sticks[2:])
    return next( ([x3,x2,x1] for (x1,x2,x3) in sticks if x3+x2>x1), [-1])

A similar solution in Rust. Rust standard library zip can only zip two iterators, so we need to zip twice and use map to get an iterator over a tuple of three elements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


struct Triangle {
    a: usize,
    b: usize,
    c: usize,
}

struct Sticks(Vec<usize>);

fn solve(sticks: Sticks) -> Option<Triangle> {
    let mut v = sticks.0;

    // Sort in descending order (in place)
    v.sort_by(|a, b| b.cmp(a));

    v.iter()
        .zip(v.iter().skip(1))
        .zip(v.iter().skip(2))
        .map(|((&a, &b), &c)| Triangle { a, b, c })
        .find(|t| t.b + t.c > t.a)
}

Using strict types (Triangle and Sticks instead of Vec<usize>) let us define input parsing and output serialization as implementations of BufRead and Display traits:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


impl std::fmt::Display for Triangle {
    fn fmt(
        &self,
        f: &mut std::fmt::Formatter<'_>,
    ) -> std::fmt::Result {
        write!(f, "{} {} {}", self.c, self.b, self.a)
    }
}

impl<T: std::io::BufRead> From<T> for Sticks {
    fn from(input: T) -> Self {
        let v = input
            .lines()
            .skip(1)
            .next()
            .unwrap()
            .unwrap()
            .split_whitespace()
            .filter_map(|x| x.parse().ok())
            .collect();

        Sticks(v)
    }
}

fn main() {
    let sticks = std::io::stdin().lock().into();

    if let Some(triangle) = solve(sticks) {
        print!("{}", triangle);
    } else {
        print!("-1");
    }
}

greedy math