Sherlock’s Array Merging Algorithm – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Sherlock’s Array Merging Algorithm HackerRank Solution
#include <bits/stdc++.h>
#define __INIT_CC__ ios::sync_with_stdio(false); \
cin.tie(0);
#ifdef __WIN32__
char getchar_unlocked() {return getchar();}
#endif
#define FOR(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i<(_t);++(_i))
#define FORN(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i<=(_t);++(_i))
#define FORD(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i>=(_t);--(_i))
#define FORLL(_i,_n,_m) for(long long (_i)=(_n),_t=(_m);_i<(_t);++(_i))
#define FORNLL(_i,_n,_m) for(long long (_i)=(_n),_t=(_m);(_i)<=(_t);++(_i))
#define FORDLL(_i,_n,_m) for(long long (_i)=(_n),_t=(_m);(_i)>=(_t);--(_i))
#define FOREACH(_i,_a) for (__typeof(_a.begin()) _i=_a.begin();_i!=_a.end();++_i)
#define RESET(_a,_value) memset(_a,_value,sizeof(_a))
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define ff first
#define ss second
#define mp make_pair
#define SIZE(_a) (int)_a.size()
#define VSORT(_a) sort(_a.begin(),_a.end())
#define SSORT(_a,_val) sort(_a,_a+(_val))
#define ALL(_a) _a.begin(),_a.end()
#define mt make_tuple
#define _get(_tuple,_i) get<_i>(_tuple)
#define eb emplace_back
using namespace std;
const int dr[] = { 1, 0,-1, 0, 1, 1,-1,-1};
const int dc[] = { 0, 1, 0,-1, 1,-1,-1, 1};
const double eps = 1e-9;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<ll> vll;
typedef pair<double,double> pdd;
typedef vector<pdd> vpdd;
const int INF = 0x7FFFFFFF;
const ll INFLL = 0x7FFFFFFFFFFFFFFFLL;
const double pi = acos(-1);
template <class T> T take(queue<T> &O) {T tmp=O.front();O.pop();return tmp;}
template <class T> T take(stack<T> &O) {T tmp=O.top();O.pop();return tmp;}
template <class T> T take(priority_queue<T> &O) {T tmp=O.top();O.pop();return tmp;}
template <class T> inline void getint(T &num)
{
bool neg = 0;
num = 0;
char c;
while ((c = getchar_unlocked()) && (!isdigit(c) && c != '-'));
if (c == '-')
{
neg = 1;
c = getchar_unlocked();
}
do num = num * 10 + c - '0';
while ((c = getchar_unlocked()) && isdigit(c));
if (neg) num = -num;
}
template <class T> inline bool inRange(T z, T a, T b){return a <= z && z <= b;}
void OPEN(string in = "input.txt",string out = "output.txt")
{
freopen(in.c_str(), "r", stdin);
freopen(out.c_str(), "w", stdout);
return ;
}
//using sokokaleb's template v3.1
#define N 1205
const int MOD = 1000000007;
int dp[N][N];
int n, arr[N];
int f(int pos, int bef) {
int& res = dp[pos][bef];
if (res != -1) return res;
if (pos == n) return res = 1;
int pengali = 1;
res = 0;
FORN (i, 1, bef) {
if (i > 1 && arr[pos + i - 1] <= arr[pos + i - 2]) break ;
pengali = (1LL * pengali * (bef - i + 1)) % MOD;
res += (1LL * pengali * f(pos + i, i)) % MOD;
if (res >= MOD) res -= MOD;
}
return res;
}
int main(int argc, char** argv) {
__INIT_CC__
cin >> n;
FOR (i, 0, n) {
cin >> arr[i];
}
RESET(dp, -1);
int ans = 0;
bool valid = 1;
FORN (i, 1, n) {
if (i > 1) valid &= (arr[i - 1] > arr[i - 2]);
if (!valid) break ;
ans += f(i, i);
if (ans >= MOD) ans -= MOD;
}
cout << ans << "\n";
}
Java Sherlock’s Array Merging Algorithm HackerRank Solution
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
SherlocksArrayMergingAlgorithm solver = new SherlocksArrayMergingAlgorithm();
solver.solve(1, in, out);
out.close();
}
static class SherlocksArrayMergingAlgorithm {
public int mod = 1000000007;
public boolean[][] inc;
public long[] fact;
public long[] ifact;
public int n;
public long[][] dp;
public void solve(int testNumber, InputReader in, OutputWriter out) {
n = in.nextInt();
long[][] w = Factorials.getFIF(2 * n, mod);
fact = w[0];
ifact = w[1];
int[] arr = in.readIntArray(n);
inc = new boolean[n][n];
for (int i = 0; i < n; i++) {
inc[i][i] = true;
for (int j = i + 1; j < n; j++) {
inc[i][j] = inc[i][j - 1] && (arr[j] > arr[j - 1]);
}
}
dp = new long[n][n];
for (long[] x : dp) Arrays.fill(x, -1);
long ans = 0;
for (int i = 0; i < n && inc[0][i]; i++) {
ans = (ans + dfs(i + 1, i + 1)) % mod;
}
out.println(ans);
}
public long dfs(int curidx, int lastblock) {
if (curidx == n) return 1;
if (dp[curidx][lastblock] != -1) return dp[curidx][lastblock];
long ret = 0;
for (int next = curidx; next < n && next < curidx + lastblock && inc[curidx][next]; next++) {
int cblock = (next - curidx + 1);
ret = (ret + fact[lastblock] * ifact[lastblock - cblock] % mod * dfs(next + 1, cblock)) % mod;
}
return dp[curidx][lastblock] = ret;
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int[] readIntArray(int tokens) {
int[] ret = new int[tokens];
for (int i = 0; i < tokens; i++) {
ret[i] = nextInt();
}
return ret;
}
public int nextInt() {
return Integer.parseInt(next());
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void close() {
writer.close();
}
public void println(long i) {
writer.println(i);
}
}
static class Factorials {
public static long[][] getFIF(int max, int mod) {
long[] fact = new long[max];
long[] ifact = new long[max];
long[] inv = new long[max];
inv[1] = 1;
for (int i = 2; i < max; i++) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
fact[0] = 1;
ifact[0] = 1;
for (int i = 1; i < max; i++) {
fact[i] = fact[i - 1] * i % mod;
ifact[i] = ifact[i - 1] * inv[i] % mod;
}
return new long[][]{fact, ifact, inv};
}
}
}
C Sherlock’s Array Merging Algorithm HackerRank Solution
#include <stdio.h>
#define ll long
ll MOD = 1000000000 + 7;
ll dp[1300][1300];
int m[1300];
int main(){
int n; scanf("%d",&n);
for(int m_i = 1; m_i <= n; m_i++) scanf("%d",&m[m_i]);
int i = 1;
while (i <= n && (i == 1 || m[i] > m[i-1])){
dp[i][i] = 1;
i++;
}
for (int i = 1;i < n;i++){
for (int j = 1;j<=n;j++){
if (dp[i][j] == 0) continue;
ll v = (j*dp[i][j])%MOD;
for (int nj = 1;nj+i<=n && nj <= j && (nj == 1 || m[i+nj]>m[i+nj-1]);nj++){
dp[i+nj][nj] = (dp[i+nj][nj]+v)%MOD;
v = (v * (j-nj))%MOD;
}
}
}
ll sol = 0;
for (int i=1;i <= n;i++){
sol = (sol + dp[n][i])%MOD;
}
printf("%ld",sol);
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
