In this HackerEarth Minimize a product problem solution You are given an array A of N integers. 

Also, you are given Q queries of the following type:

  1. 1 x v: Change the value of the element at xth index to v i.e. set A[x] = v.
  2. 2 l r: Determine the number of pairs (i,j) such that:
  • l <= i < j <= r
  • A[i] x A[j] is minimum possible among all such possible pairs of elements
Your task is to determine the sum of answers for queries of Type 2 overall Q queries.


HackerEarth Minimize a product problem solution


HackerEarth Minimize a product problem solution.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 9;
bool grid[MAX_N][MAX_N];
int ans;

void bt() {
    for (int i = 0; i < MAX_N; ++i)
        for (int j = 0; j < MAX_N; ++j)
            if (grid[i][j]) {
                if (grid[i][j + 1]) {
                    grid[i][j] = grid[i][j + 1] = false;
                    bt();
                    grid[i][j] = grid[i][j + 1] = true;
                }
                if (grid[i + 1][j]) {
                    grid[i][j] = grid[i + 1][j] = false;
                    bt();
                    grid[i][j] = grid[i + 1][j] = true;
                }
                return;
            }
    ++ans;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    for (int i = 0; i < MAX_N - 1; ++i)
        for (int j = 0; j < MAX_N - 1; ++j)
            grid[i][j] = i >= 3 && i <= 4 || j >= 3 && j <= 4;
    bt();
    cout << ans << '\n';
}