Thursday, March 16, 2017

UVa 434 - Matty's Blocks

Problem Statement:
UVa 434 - Matty's Blocks

Summary:
This problem pertains to a matrix of size K x K, where each entry is a non-negative integer.
Let the maximum values on each row be max_row[0 .. K-1], and the maximum values on each column be max_col[0 .. K - 1].

E.g.          
[ 1 4 2 5 3 ]  --> 5
[ 8 1 7 6 0 ]  --> 8
[ 3 3 4 1 5 ]  --> 5  max_row
[ 6 5 0 3 2 ]  --> 6
[ 2 4 1 6 6 ]  --> 6
  v v v v v
  8 5 7 6 5
  max_col

Our job is to fill in the matrix to fulfil those requirements. In general there are more than one way to do it. Compute:
1. Minimum sum of entries possible.
2. Maximum sum of entries possible.

Note that no constraint is placed on K in the original problem statement. It can be small, it can be very large.




Solution:
I like this problem, especially if you think of K as being a large values ( > 1 million). How would you do it?

Turns out this problem can be solved by means of sorting and scanning operations. Let's figure out how.

Minimum possible sum
Let's say we are in the middle of filling in the matrix by focusing on a column or a row at a time.

Consider i-th row of our matrix, whose maximum entry must be V = max_row[i]. Surely, V must occur in one of the columns in this row (Why?). So, we only want to fill in V once on one of the column so as to minimise the final total sum.

Surely, we cannot place V on column j where max_col[j] is smaller than V, because it will violate the max_col[j]'s requirement. Hence V can only be placed on columns j where V <= max_col[j].

If all of the column j has max_col[j] > V, then it is guaranteed that those columns j must be empty (Why?). Hence we can choose any one column to place V and proceed to the next row. (In this case, while we fulfil max_row[i], we still need one more entry on column j to fulfil max_col[j].)

On the other hand, in there are columns j where V = max_col[j]. If these columns are empty, then we should fill in V in one of these columns. This will allow us to fulfil both max_row[i] and max_col[j] with one entry. On the other hand, say that those columns are not empty. Then we know that to achieve minimum possible sum, those columns must contain V! (Otherwise, say it contains other V' < V, then since max_col[j] = V, it must have V somewhere else in the column to fulfil max_col[j], making V' redundant).

From the above, we see that the order in which we consider the columns and rows are not important.
Hence, instead of simulating the process, we can simply sort both max_row and max_col, and scan through each array using 2 pointers approach (similar to a merge operation in merge sort) which will bring down the complexity from O(K^2) to O(K lg K) + O(2K).

Maximum possible sum
Extending the idea from minimum possible sum, now instead of choosing a column j to fill in, we fill every single column with V in row i where max_col[j] >= V (and vice versa when we are considering columns). This is a much simpler process than the previous one. However the simulation will take O(K^2). Instead, we can also use the sorted max_row and max_col with 2 pointers scan as well. We can compute the total entries in each row and each column one by one, and then subtract the intersection. This will also achieve a complexity of O(K lg K) + O(2K).

The implementation below will give a clear idea of the 2 pointers approach.

Implementation:

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int K;
vector<int> values[2];

int64_t min_blocks() {
  int i = 0, j = 0;
  int64_t ans = 0;
  while (i < K && j < K) {
    int minval = min(values[0][i], values[1][j]);
    ans += minval;
    if (values[0][i] == minval) {
      ++i;
    }
    if (values[1][j] == minval) {
      ++j;
    }
  }
  while (i < K) {
    ans += values[0][i++];
  }
  while (j < K) {
    ans += values[1][j++];
  }
  return ans;
}

int64_t total_larger_than(vector<int>& first, vector<int>& second) {
  int j = 0;
  int64_t ans = 0;
  for (int i = 0; i < K; ++i) {
    while (j < K && second[j] < first[i]) ++j;
    ans += first[i] * (K - j);
  }
  return ans;
}

int64_t overlap(vector<int>& first, vector<int>& second) {
  int i = 0, j = 0;
  int64_t ans = 0;
  while (i < K && j < K) {
    int cur_val = min(first[i], second[j]);
    int len_1 = 0, len_2 = 0;
    while (i < K && first[i] == cur_val) {
      ++i;
      ++len_1;
    }
    while (j < K && second[j] == cur_val) {
      ++j;
      ++len_2;
    }
    ans += (int64_t) cur_val * len_1 * len_2;
  }
  return ans;
}

int64_t max_blocks() {
  int64_t ans = total_larger_than(values[0], values[1]);
  ans += total_larger_than(values[1], values[0]);
  ans -= overlap(values[0], values[1]);
  return ans;
}

void read() {
  scanf("%d",&K);
  values[0].clear();
  values[1].clear();
  int val;
  for (int j = 0; j < 2; ++j) {
    for (int i = 0; i < K; ++i) {
      scanf("%d",&val);
      values[j].push_back(val);
    }
  }
  for (int i = 0; i < 2; ++i) {
    sort(values[i].begin(), values[i].end());
  }
}

int main() {
  int tc;
  scanf("%d",&tc);
  while (tc --> 0) {
    read();
    int64_t N = min_blocks();
    int64_t M = max_blocks();
    printf("Matty needs at least %lld blocks, and can add at most %lld extra blocks.\n", N, M-N);
  }
  return 0;
}