# Squared Subsequences April Long Challenge 2020

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;

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;
}
}
``````

try for the case:
1 3 5 2 1 3 5 2
according to the code, dpL[7]=6,but it should be 3.
I did the corrections.
Check here
https://www.codechef.com/viewsolution/31866566

1 Like

Thank you

How did you arrive at this formula?

Its simple PnC.
lets assume the case: 1 3 5 2 7 9 11
there are 4 (equal to left+1) ways to select the left numbers: 5, 3 5, 1 3 5 and nothing selected.
we can’t select 3 only as we have to include 2 in the subarray.
similar is the case on the right side