Table of contents

• Problem
  • Input
  • Output
• Explanation
• Time complexity
  • Bit exhaustive search
  • Greedy algorithm
• Solution
  • Bit exhaustive search
  • Greedy algorithm

# Problem

https://atcoder.jp/contests/arc029/tasks/arc029_1

# Input

$N$
$t_1$
$t_2$
...
$t_N$

• $N$ - The number of tasks
• $t_N$ - Time to process task$i$

# Output

The minimum total time to process all the tasks in 2 parallrl.

# Explanation

It can be solved with bit exhaustive search as each task has 2 choices.
$N$ is enough small.
On the other hand, it can be solved with greedy algorithm as well.
In general, greedy algorithms are faster if they can be applied.

# Time complexity

# Bit exhaustive search

$O(2^N)$

# Greedy algorithm

For sorting tasks $O(N \log{N})$.
For greedy algorithm $O(N)$.

$O(N \log{N})$

# Solution

# Bit exhaustive search

// 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;

Int N, _t;
vector<Int> T;

void input() {
  cin >> N;
  while (cin >> _t) T.push_back(_t);
}

Int dfs(Int t, Int time1, Int time2) {
  if (t >= N) return max(time1, time2);
  return min(
    dfs(t + 1, time1 + T[t], time2),
    dfs(t + 1, time1, time2 + T[t])
  );
}

void solve() {
  cout << dfs(0, 0, 0) << endl;
}

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

# Greedy algorithm

// 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;

Int greedy() {
  Int a = 0, b = 0;
  for (auto t: T) {
    if (a < b) a += t;
    else b += t;
  }
  return max(a, b);
}

void solve() {
  sort(span_all(T));
  reverse(span_all(T));
  cout << greedy() << endl;
}