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 x v: Change the value of the element at xth index to v i.e. set A[x] = v.
- 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.
#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';
}
0 Comments