Atcoder Beginner Content 143 D - Triangles

Calendar Clock iconCalendar Clock icon

atcoder

Table of contents

# Problem

https://atcoder.jp/contests/abc143/tasks/abc143_d

# Explanation

The range of the length of C is determined once the lengths of A and B are fixed.
Sort the edges according to their length.
Find the number of the edges which are included in the range by using binary search.

# Time complexity

O(N2)O(N^2) to fix A and B and O(logN)O(logN) to determind C with binary search.

O(N2logN)O(N^2logN)

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
#define MAX_N 2001

Int N;
vector<Int> L(MAX_N, -1);

void input() {
  cin >> N;
  loop(i,0,N) cin >> L[i];
}

void solve() {
  sort(span(L,0,N));  // sort edges by length asc
  
  Int count = 0;
  //O(N^2)
  loop(a,0,N-2) {
    loop(b,a+1,N) {
      Int min_c = L[a] - L[b] + 1;
      Int max_c = L[a] + L[b] - 1;
      // Binary search twice. O(2LogN)
      count += upper_bound(span(L,b+1,N), max_c) - lower_bound(span(L,b+1,N), min_c);
    }
  }
  cout << count << endl;
}

int main() {
  input();
  solve();
  return 0;
}

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

Comments