For the given question Question

Editorial solution

Probably the easiest problem I tried to approach it in different way by AP sum. Like for each step our total sum will decrease by 2 and finally stops when we reach 0 sum.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    long long int arr[n];
    long long int sum = 0;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
    }
    /*if(sum==0)
    {
        cout<<"YES"<<endl;
        return 0;
    }*/
    long long int x = 0;
    sum = sum+2;
    x = sum/2;
    if(sum%2==0)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
    
}

I am failing at 3 test case. Is this the wrong method or I am doing something wrong.. Thanks in advance

Statement of question is this. I read an approach to this question on stack overflow and it is :

1. Merge sort array A and create a copy (array B)

2. Take A[1] and find its position in sorted array B via a binary search. The number of inversions for this element will be one less than the index number of its position in B since every lower number that appears after the first element of A will be an inversion.

2a. accumulate the number of inversions to counter variable num_inversions.

2b. remove A[1] from array A and also from its corresponding position in array B
rerun from step 2 until there are no more elements in A.

Here’s an example run of this algorithm. Original array A = (6, 9, 1, 14, 8, 12, 3, 2)

1: Merge sort and copy to array B

B = (1, 2, 3, 6, 8, 9, 12, 14)

2: Take A[1] and binary search to find it in array B

A[1] = 6

B = (1, 2, 3, 6, 8, 9, 12, 14)

6 is in the 4th position of array B, thus there are 3 inversions. We know this because 6 was in the first position in array A, thus any lower value element that subsequently appears in array A would have an index of j > i (since i in this case is 1).

2.b: Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed).

A = (6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)

3: Rerun from step 2 on the new A and B arrays.

A[1] = 9

B = (1, 2, 3, 8, 9, 12, 14)

9 is now in the 5th position of array B, thus there are 4 inversions. We know this because 9 was in the first position in array A, thus any lower value element that subsequently appears would have an index of j > i (since i in this case is again 1). Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed)

A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 8, 9, 12, 14) = (1, 2, 3, 8, 12, 14)

Continuing in this vein will give us the total number of inversions for array A once the loop is complete.

Step 1 (merge sort) would take O(n * log n) to execute. Step 2 would execute n times and at each execution would perform a binary search that takes O(log n) to run for a total of O(n * log n). Total running time would thus be O(n * log n) + O(n * log n) = O(n * log n).

My question is in case of repeating elements like [4,7,4] what if we modify binary search for finding first occurrence of that element and using erase in vectors to erase the element. What will be the time complexity then ? According to me it is still O(nlogn).

Thanks in advance.

I have seen others solution for this question and most of them are using binary search. Can someone help me to get better understanding to this question.And why they are applying binary search

I'm stuck at this question for some time and referred to this solution and just wanted to ask how " maxH = max(maxH, (d[i+1]-d[i])/2+(h[i]+h[i+1])/2 ) " term can be derived. I am interpreting it as the minimum height in consecutive interval and taking max of them. How it can be derived. Thanks

Can someone suggest how to approach this question in a better way ???....

Can this problem be solved using dfs???....I have submitted the solution but getting TLE...

Given a matrix of ‘O’ and ‘X’, find the largest subsquare surrounded by ‘X’? Can there be a better solution than O(n^3) ??

Each letter, a-z, is assigned values in the following way: a: 1, b: 2, …, z: 26. You are given string, S, consisting of lowercase English letters and an integer, K. Find the lexicographically minimal string, whose sum is equal to K

You are given an array of n integers. You need to insert these elements into 2 binary search trees(BSTs), such that maximum(height(BST-1), height(BST-2)) could be minimized. Elements can be inserted into BST in any order. (Constraints — 1<=n<=10^5)