In this HackerEarth Sherlock and Special, Count problem solution Let's say P= [P1, P2 . . . PN] is a permutation of all positive integers less than or equal to N. A function called "special count" F(P) is defined as:

F(P) = sigma(i=1,N)|Pi - i|

Now Watson gives an N and K to Sherlock and asks if K is a possible special count for any permutation of first N positive integers.


HackerEarth Sherlock and Special Count problem solution


HackerEarth Sherlock and Special Count problem solution.

#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n) 
{LL ret=1;LL b=a;while(n) {if(n&1) 
    ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
int main()
{
    int t;
    sd(t);
    while(t--){
        int n,k;
        sd(n),sd(k);
        if(k%2 or k>(n*n/2))cout << "NO\n";
        else cout << "YES\n";
    }
    return 0;
}


Second solution

#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define sz size()

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

int main() {
  int t;
  S(t);
  assert(t >= 1 && t <= 100);
  while(t--) {
    int n,k;
    S2(n,k);
    assert(n >= 1 && n <= 40);
    assert(k >= 0 && k <= 2000);
    int val = 0;
    rep(i,1,n+1) {
      val += abs(n - i - i);
    }

    if(k&1 || k > val) {
      printf("NO\n");
    } else {
      printf("YES\n");
    }
  }
  return 0;
}