Hello Everyone,
Here is my approach for Squared Subsquence in April Long Challenge 2020.
I have converted Array into array like this.
If arr[i] is odd → arr[i] = 1
If arr[i] is multiple of 4 → arr[i] = 4
If arr[i] is multiple of 2 but not multiple of 4 → arr[i] = 2
After that I have calculated number of odds on the left side of 2 and on the right side of 2 for every 2s in modified array. After that I have found number of elements which contain exactly one 2 with others are odd like this. sum += (left + 1) * (right + 1); So I will get number of sub arrays which contains exactly one times number 2 with all others are odd.
After that I have subtracted this sum from total number of sub arrays.
Means total = (n * (n + 1)) / 2;
final_answer = total - sum.
Now can anyone tell me, what is wrong with this approach.
Here is link for the problem.
Here is my solution.
#include <iostream>
#define int long long int
#define endl "\n"
using namespace std;
int solve(int arr[], int n)
{
//int arr[12] = {1, 1, 1, 1, 2, 2, 1, 1, 1, 4, 2, 2};
//int dpL[12] = {1, 2, 3, 4, 4, 0, 1, 2, 3, 0, 0, 0};
//int dpR[12] = {4, 3, 2, 1, 0, 3, 3, 2, 1, 0, 0, 0};
int sum = 0;
/*Conditions for dpL*/
int dpL[n] = { 0 };
for (int i = 0; i < n; i++) {
if (i == 0) {
if (arr[i] == 1) {
dpL[i] = 1;
}
else if (arr[i] == 2 || arr[i] == 4) {
dpL[i] = 0;
}
}
else {
if (arr[i] == 1) {
dpL[i] = dpL[i - 1] + 1;
}
else if (arr[i] == 2) {
if (arr[i - 1] == 1) {
dpL[i] = dpL[i - 1];
}
else if (arr[i - 1] == 2 || arr[i - 1] == 4) {
dpL[i] = 0;
}
}
else if (dpL[i] == 4) {
dpL[i] = 0;
}
}
}
/*Conditions for dpR*/
int dpR[n] = { 0 };
for (int i = n - 1; i >= 0; i--) {
if (i == (n - 1)) {
if (arr[i] == 1) {
dpR[i] = 1;
}
else if (arr[i] == 2 || arr[i] == 4) {
dpR[i] = 0;
}
}
else {
if (arr[i] == 1) {
dpR[i] = dpR[i + 1] + 1;
}
else if (arr[i] == 2) {
if (arr[i + 1] == 1) {
dpR[i] = dpR[i + 1];
}
else if (arr[i + 1] == 2 || arr[i + 1] == 4) {
dpR[i] = 0;
}
}
else if (dpR[i] == 4) {
dpR[i] = 0;
}
}
}
for (int i = 0; i < n; i++) {
if (arr[i] == 2) {
sum += (dpL[i] + 1) * (dpR[i] + 1);
}
}
return sum;
}
int32_t main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
int total = (n * (n + 1)) / 2;
int arr[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
if (arr[i] < 0)
arr[i] = (arr[i] * -1);
if (arr[i] % 4 == 0)
arr[i] = 4;
else if (arr[i] % 2 == 0)
arr[i] = 2;
else if (arr[i] % 2 == 1)
arr[i] = 1;
}
int ans = solve(arr, n);
cout << total - ans << endl;
}
}