Official

E - Product Simulation Editorial by Errichto

Hints

Hint 1, partial points The product is the sum of bunch of ones, e.g. $3 \cdot 4 = (1 + 1 + 1) \cdot (1 + 1 + 1 + 1)$.
Hint 2 To get full score, focus on powers of two.
Hint 3 Solve the following mini-problems:
  • multiply variable $x$ by a power of $2$
  • create every power of $2$
  • subtract two variables (or something similar to that)
  • get the binary representation of a variable.

One, Two, Three

Let’s create value \(1\) and put it in one cell (like \(a[3]\)) in order to reuse it multiple times.

ONE = (0 < (A + B))

This code doesn’t work if \(A = B = 0\) but fortunately any output is correct for this test because it’s impossible to create any non-zero.

After creating constant \(1\), you can also create values \(1, 2, \ldots, 10\) or \(2, 4, 8, \ldots, 2^{30}\) if necessary.

800 Points (\(A, B \leq 10\))

for(x = 0 .. 9)
    for(y = 0 .. 9)
        answer += (x < A) && (y < B);

This code can be implemented with addition and comparison operations. The last line becomes answer = answer + (1 < ((x < A) + (y < B))); where \(x\) and \(y\) are indices of precomputes values \(0, 1, \ldots, 9\). This line uses \(5\) operations, that’s \(500\) in total.

What’s the plan?

We’ll create a few functions that behave like blackboxes: they can compute something in particular complexity and we can just reuse them in the future. You might find this similar to simulating logical operations with NAND only.

Subtraction in \(O(MaxValue)\)

Let’s start with subtraction or actually \(max(0, x-y)\) because we can’t product negative values.

code 
int SUBTRACT(int i, int j) { // a[i] - a[j], linear version
  int difference = new_index();
  for(int rep = 0; rep < MAX_VALUE; ++rep) {
    int k = IS_SMALLER(j, i); // 0 or 1
    j = ADD(j, k);
    difference = ADD(difference, k);
  }
  return difference;
}

Here, every function returns index of the computed value. Every run of functions IS_SMALLER and ADD prints one operation to the output.

Ternary Operator

In order to simulate if-conditions, we need ternary operator x ? y : 0. This can be implemented as y - ((x==0) << 30).

code 
int BIN_SHIFT(int i, int by) { // a[i] << by
  for(int rep = 0; rep < by; ++rep) {
    i = ADD(i, i);
  }
  return i;
}
int NEGATION(int i) { // a[i] == 0
  return IS_SMALLER(i, VARIABLE_1);
}
int TERNARY(int i, int j) { // a[i] ? a[j] : 0
  return SUBTRACT(j, BIN_SHIFT(NEGATION(i), MAX_LOG));
}

Multiplication in \(O(MaxValue^2)\)

Repeatedly (\(i\) times) add \(j\) to the product.

code 
int MULTIPLY(int i, int j) {
  int product = new_index();
  int almost_i = new_index();
  for(int rep = 0; rep < MAX_VALUE; ++rep) {
    int should_add = IS_SMALLER(almost_i, i);
    product = ADD(product, TERNARY(should_add, j));
    almost_i = ADD(almost_i, VARIABLE_1);
  }
  return product;
}

Subtraction in \(O(\log^2 MaxValue)\)

Instead of increasing \(a[j]\) by \(1\) many times, let’s just move with powers of \(2\) from big to small. Here’s pseudocode:

code 
for(z = 29, 28, ..., 0) {
  power_of_two = 1 << z;
  if(a[j] + power_of_two < a[i]) {
    a[j] += power_of_two;
    difference += power_of_two;
  }
}

We can’t simulate the if-condition with TERNARY function because TERNARY already uses subtraction. Instead, we can do should_add = ((a[j] + power_of_two) < a[i]) and then a[j] += (should_add << z).

Multiplication in \(O(\log^3 MaxValue)\)

For every power of two from \(2^{29}\) down to \(2^0\), if \(a[i] \geq 2^e\), then a[i] -= 1<<e and product += a[j]<<e.

code 
int MULTIPLY(int i, int j) {
  i = ADD(i, VARIABLE_1);
  int product = new_index();
  int almost_i = new_index();
  for(int expo = MAX_LOG-1; expo >= 0; --expo) {
    int power_two = BIN_SHIFT(VARIABLE_1, expo); // can be precomputed
    int should_add = IS_SMALLER(ADD(almost_i, power_two), i);
    int j_or_zero = TERNARY(should_add, j);
    should_add = BIN_SHIFT(should_add, expo);
    almost_i = ADD(almost_i, should_add);
    product = ADD(product, BIN_SHIFT(j_or_zero, expo));
  }
  return product;
}

The complexity is \(O(\log^3 (10^9))\) and the actual output has 32089 operations.

full code 
#include  // Product Simulation, by Errichto
using namespace std;
 
const int MAX_LOG = 30;
int arr[10 * 1000 * 1000];
int __nxt = 10; // next available slot
int get() { return __nxt++; }
int CONSTANT_1;
vector> operations;
 
int IS_SMALLER(int i, int j) {
  int k = get();
  arr[k] = arr[i] < arr[j];
  operations.push_back({'<', i, j, k});
  // printf("< %d %d %d\n", i, j, k);
  return k++;
}
int ADD(int i, int j) {
  int k = get();
  arr[k] = arr[i] + arr[j];
  operations.push_back({'+', i, j, k});
  return k++;
}
// arr[i] << by
int BIN_SHIFT(int i, int by) {
  for(int rep = 0; rep < by; ++rep) {
    i = ADD(i, i);
  }
  return i;
}
// max(0, arr[i] - arr[j])
int SUB(int i, int j) {
  i = ADD(i, CONSTANT_1);
  int where_diff = get();
  for(int expo = MAX_LOG - 1; expo >= 0; --expo) {
    int power_two = BIN_SHIFT(CONSTANT_1, expo); // can be precomputed
    int should_add = IS_SMALLER(ADD(j, power_two), i);
    should_add = BIN_SHIFT(should_add, expo);
    where_diff = ADD(where_diff, should_add);
    j = ADD(j, should_add);
  }
  return where_diff;
}
int NEGATION(int i) {
  return IS_SMALLER(i, CONSTANT_1);
}
// arr[i] ? arr[j] : 0,    arr[i] is 0 or 1
int TERNARY(int i, int j) {
  assert(arr[i] == 0 || arr[i] == 1); // just for testing
  return SUB(j, BIN_SHIFT(NEGATION(i), MAX_LOG));
  // return SUB(j, SUB(j, BIN_SHIFT(i, MAX_LOG)));
}
// arr[i] * arr[j]
int MULTIPLY(int i, int j) {
  i = ADD(i, CONSTANT_1);
  int product = get();
  int almost_i = get();
  for(int expo = MAX_LOG-1; expo >= 0; --expo) {
    int power_two = BIN_SHIFT(CONSTANT_1, expo);
    int should_add = IS_SMALLER(ADD(almost_i, power_two), i);
    int j_or_zero = TERNARY(should_add, j);
    should_add = BIN_SHIFT(should_add, expo);
    almost_i = ADD(almost_i, should_add);
    product = ADD(product, BIN_SHIFT(j_or_zero, expo));
  }
  return product;
}
 
void test() {
  CONSTANT_1 = get();
  arr[CONSTANT_1] = 1; // actually should be: (0<(a+b))
  const int i = 8;
  const int j = 9;
  for(int a = 0; a <= 10; ++a) {
    for(int b = 0; b <= 10; ++b) {
      arr[i] = a;
      arr[j] = b;
      assert(arr[ADD(i,j)] == a + b);
      assert(arr[SUB(i,j)] == max(0, a - b));
      if(a<2) assert(arr[TERNARY(i,j)] == (a ? b : 0));
      // cerr << a << " * " << b << " = " << arr[MULTIPLY(i,j)] << endl;
      assert(arr[MULTIPLY(i,j)] == a * b);
      // assert(arr[MIN(i,j)] == min(a,b));
    }
  }
  cerr << "all OK" << endl;
}
 
int main() {
  CONSTANT_1 = IS_SMALLER(2, ADD(0, 1));
  int answer = MULTIPLY(0, 1);
  
  operations.push_back({'+', answer, 2, 2}); // copy answer to arr[2] as asked in statement
  arr[2] = arr[answer] + arr[2];
  
  cerr << arr[0] << "*" << arr[1] << "=" << arr[2] << endl;
  cerr << operations.size() << " operations" << endl;
  
  printf("%d\n", (int) operations.size());
  for(auto ope : operations) {
    cout << get<0>(ope) << " " << get<1>(ope) << " " << get<2>(ope) << " " << get<3>(ope) << "\n";
  }
}

Faster Solution

Here’s an outline of \(O(\log^2)\) solution found by latte0119, one of testers. You need to first find the binary representations of \(A\) and \(B\) in \(O(\log^2)\) and then:

for(int k = 58; k >= 0; k–) {
    answer *= 2;
    for(int i = 0; i <= k; i++){
        int j = k - i;
        if(i < 30 && j < 30) {
            answer += 1<(a_bits[i]+b_bits[j]);
        }
    }
}

posted:
last update: