Table of Contents
Recording Episodes – 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++ Recording Episodes HackerRank Solution
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
struct SCC{
int n,used[SIZE],order[SIZE],gg[SIZE];
vector<int>e[SIZE],ae[SIZE],ge[SIZE],emp;
int id,gn;
void init(int _n){
n=_n;
memset(used,0,sizeof(int)*n);
REP(i,n){
e[i]=ae[i]=ge[i]=emp;
}
}
void add_edge(int x,int y){
e[x].PB(y^1);
ae[y^1].PB(x);
e[y].PB(x^1);
ae[x^1].PB(y);
}
void dfs1(int x){
if(used[x]==1)return;
used[x]=1;
REP(i,SZ(e[x])){
int y=e[x][i];
dfs1(y);
}
order[--id]=x;
}
void dfs2(int x){
if(used[x]==2)return;
gg[x]=gn;
used[x]=2;
REP(i,SZ(ae[x])){
int y=ae[x][i];
if(used[y]!=2)dfs2(y);
}
}
bool good(){
gn=0;
id=n;
REP(i,n)
dfs1(i);
REP(i,n){
if(used[order[i]]!=2){
dfs2(order[i]);
gn++;
}
}
REP(i,n){
if(gg[i]==gg[i^1])return 0;
i++;
}
return 1;
}
}scc;
int input[100][2][2];
bool XX(int x1,int y1,int x2,int y2){
return !((y1<x2)||(y2<x1));
}
int main(){
CASET{
DRI(n);
REP(i,n)REP(j,4)RI(input[i][j>>1][j&1]);
int rr=1;
int an1=1,an2=0;
REP(i,n){
if(i+an1>=n)break;
while(rr<n){
scc.init((rr-i)*2+2);
REPP(k2,i,rr+1)
REPP(k1,i,k2){
REP(j1,2)REP(j2,2){
if(XX(input[k1][j1][0],input[k1][j1][1],input[k2][j2][0],input[k2][j2][1])){
scc.add_edge((k1-i)*2+j1,(k2-i)*2+j2);
}
}
}
if(!scc.good())break;
else rr++;
}
if(rr-i>an1){an1=rr-i;an2=i;}
}
an2++;
printf("%d %d\n",an2,an2+an1-1);
}
return 0;
}
Java Recording Episodes HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class F {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
for(int T = ni();T > 0;T--){
int n = ni();
int[][] rs = new int[n][];
for(int i = 0;i < n;i++){
rs[i] = na(4);
}
int[] from = new int[20005];
int[] to = new int[20005];
// !(a and b)
int maxlen = 0;
int argi = -1;
int argj = -1;
outer:
for(int i = 0;i < n;i++){
int p = 0;
for(int j = i;j < n;j++){
for(int k = i;k < j;k++){
for(int u = 0;u < 2;u++){
for(int v = 0;v < 2;v++){
if(Math.max(rs[k][u*2], rs[j][v*2]) <=
Math.min(rs[k][u*2+1], rs[j][v*2+1])){
from[p] = k*2+u; to[p] = j*2+v^1; p++;
from[p] = j*2+v; to[p] = k*2+u^1; p++;
}
}
}
}
if(j-i+1 <= maxlen)continue;
// tr(Arrays.copyOf(from, p));
// tr(Arrays.copyOf(to, p));
int[][] g = packD(n*2, from, to, p);
int[] clus = decomposeToSCC(g);
for(int k = i;k <= j;k++){
if(clus[2*k] == clus[2*k+1]){
continue outer;
}
}
if(j-i+1 > maxlen){
maxlen = j-i+1;
argi = i;
argj = j;
}
}
}
out.println(argi+1 + " " + (argj+1));
}
}
public static int[] decomposeToSCC(int[][] g)
{
int n = g.length;
int[] stack = new int[n+1];
int[] ind = new int[n+1];
int[] ord = new int[n];
Arrays.fill(ord, -1);
int[] low = new int[n];
Arrays.fill(low, -1);
int sp = 0;
int id = 0; // preorder
int[] clus = new int[n];
int cid = 0;
int[] cstack = new int[n+1];
int csp = 0;
boolean[] incstack = new boolean[n];
for(int i = 0;i < n;i++){
if(ord[i] == -1){
ind[sp] = 0;
cstack[csp++] = i;
stack[sp++] = i;
incstack[i] = true;
while(sp > 0){
int cur = stack[sp-1];
if(ind[sp-1] == 0){
ord[cur] = low[cur] = id++;
}
if(ind[sp-1] < g[cur].length){
int nex = g[cur][ind[sp-1]];
if(ord[nex] == -1){
ind[sp-1]++;
ind[sp] = 0;
incstack[nex] = true;
cstack[csp++] = nex;
stack[sp++] = nex;
}else{
// shortcut
// U.tr(cur, nex, incstack[nex], low[nex], stack);
if(incstack[nex])low[cur] = Math.min(low[cur], low[nex]);
ind[sp-1]++;
}
}else{
if(ord[cur] == low[cur]){
while(csp > 0){
incstack[cstack[csp-1]] = false;
clus[cstack[--csp]] = cid;
if(cstack[csp] == cur)break;
}
cid++;
}
if(--sp >= 1)low[stack[sp-1]] = Math.min(low[stack[sp-1]], low[stack[sp]]);
}
}
}
}
return clus;
}
public static int[][] packD(int n, int[] from, int[] to, int sup)
{
int[][] g = new int[n][];
int[] p = new int[n];
for(int i = 0;i < sup;i++)p[from[i]]++;
for(int i = 0;i < n;i++)g[i] = new int[p[i]];
for(int i = 0;i < sup;i++){
g[from[i]][--p[from[i]]] = to[i];
}
return g;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new F().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Recording Episodes HackerRank Solution
#True if two intervals interesects
def has_intersection(I1,I2):
if I1[0] >= I2[0] and I1[0] <= I2[1]: return True
if I1[1] >= I2[0] and I1[1] <= I2[1]: return True
if I2[0] >= I1[0] and I2[0] <= I1[1]: return True
if I2[1] >= I1[0] and I2[1] <= I1[1]: return True
return False
#Given the SAT Graph, return the longest interval with a dual-complete graph
def max_range(G,GT):
size = len(G)/4
maxRange = [0,1]
maxSize = 1
a = 0
b = 2
while b <= size:
SCC = []
SCC = get_strong_connected_components(G,GT, a*4, b*4)
newSize = b-a
if is_satisfiable(SCC):
if newSize > maxSize:
maxRange = [a,b]
maxSize = newSize
b+=1
else:
if newSize == maxSize + 1:
b+=1
a+=1
return maxRange
#Get the components only considering vertices between a (inclusive) and b (exclusive) indices
def get_strong_connected_components(G, GT, a, b):
SCC = []
numVertices = b-a
compQueue = []
Visited = [0 for c1 in range(numVertices)]
for c1 in range(a,b):
build_queue(G, a, b, compQueue, Visited, c1)
while len(compQueue) > 0:
i = compQueue.pop(-1)
C = []
build_component(GT, a, b, Visited, C, i)
if len(C)>0: SCC.append(C)
return SCC
def build_queue(G,a,b,compQueue, Visited, i):
if Visited[i-a] == 1: return
Visited[i-a] += 1
for j in G[i]:
if j>=a and j<b:
build_queue(G, a, b, compQueue, Visited, j)
compQueue.append(i)
return
def build_component(GT, a, b, Visited, C, i):
if Visited[i-a] == 2: return
Visited[i-a] += 1
for j in GT[i]:
if j>=a and j<b:
build_component(GT, a, b, Visited, C, j)
C.append(i)
return
#returns False if for some a, a and not a are in the same component
def is_satisfiable(SCC):
for C in SCC:
C.sort()
for c1 in range(len(C)-1):
if C[c1+1]-C[c1] == 1 and C[c1]%2==0: return False
return True
def build_digraph(S):
size = len(S)*4
G = []
GT = []
for c1 in range(size):
G.append([])
GT.append([])
for c1 in range(len(S)):
i = c1*4
G[i+1].append(i+2)
GT[i+2].append(i+1)
G[i+3].append(i)
GT[i].append(i+3)
for c1 in range(len(S)):
for c2 in range(2):
i = c2*2
tr1 = [S[c1][i],S[c1][i+1]]
for c3 in range(c1, len(S)):
for c4 in range(2):
if c1==c3 and c2==c4: continue
j = c4*2
tr2 = [S[c3][j],S[c3][j+1]]
if has_intersection(tr1,tr2):
k = c1*4
l = c3*4
G[k+i].append(l+j+1)
GT[l+j+1].append(k+i)
if c1!=c3:
G[l+j].append(k+i+1)
GT[k+i+1].append(l+j)
return [G,GT]
#main
q = int(input())
for c1 in range(q):
n = int(input())
S = []
for c2 in range(n):
s = input().split(' ')
for c3 in range(len(s)):
s[c3] = int(s[c3])
S.append(s)
G,GT = build_digraph(S)
maxRange = max_range(G,GT)
print(f'{maxRange[0]+1} {maxRange[1]}')
Python 2 Recording Episodes HackerRank Solution
import sys
import copy
T = input()
def overlaps(t1, t2):
if t1[0] > t2[0]:
t1,t2 = t2,t1
if t1[1] >= t2[0]:
return True
return False
for _ in range(T):
times = []
epi = input()
for _ in range(epi):
s1,e1,s2,e2 = map(int, raw_input().strip().split(' '))
times.append([(s1, e1), (s2, e2)])
#print 'times:'
#print times
cur_seq = 0
max_seq = float('-inf')
current_t = []
max_s_e = []
for i in range(len(times)):
#print cur_seq
if len(current_t) == 0:
current_t = [[times[i][0]], [times[i][1]]]
cur_s_e = i
cur_seq = 1
else:
for j in range(len(current_t)):
overlap1 = False
overlap2 = False
for k in range(len(current_t[j])):
if overlaps(current_t[j][k], times[i][0]) is True:
# create new slot if both are able to get in
overlap1 = True
if overlaps(current_t[j][k], times[i][1]) is True:
overlap2 = True
if overlap1 is True and overlap2 is True:
break
if overlap1 is False and overlap2 is True:
current_t[j].append(times[i][0])
cur_seq += 1
#print '1: '
#print current_t
elif overlap1 is True and overlap2 is False:
current_t[j].append(times[i][1])
cur_seq += 1
#print '2: '
#print current_t
elif overlap1 is False and overlap2 is False:
current_t.append(copy.copy(current_t[j]))
current_t[j].append(times[i][0])
current_t[len(current_t) - 1].append(times[i][1])
cur_seq += 1
#print '3: '
#print current_t
# both overlap, cannot continue
#else:
# current_t = [[times[i][0]], [times[i][1]]]
# cur_s_e = i
# cur_seq = 1
# print '4: '
# print current_t
if overlap1 is True and overlap2 is True:
current_t = []
else:
current_t = [x for x in current_t if len(x) == cur_seq]
# cannot continue, start new
if len(current_t) == 0:
if cur_seq > max_seq:
max_seq = cur_seq
max_s_e = [cur_s_e, i-1]
current_t = [[(times[i][0][0], times[i][0][1])], [(times[i][1][0], times[i][1][1])]]
if cur_seq > max_seq:
max_seq = cur_seq
max_s_e = [cur_s_e, i-1]
#print current_t
#print max_seq
#print cur_s_e
print max_s_e[0] + 1, max_s_e[1] + 2
C Recording Episodes HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
void clean_table();
void insert_edge(int x,int y,int w);
int check();
void dfs1(int x);
void dfs2(int x);
int checkx(int x);
int l,r,n,st,c,a[4][100],mark[400],component[400],s[400];
lnode *table[400]={0},*rtable[400]={0};
int main(){
int q,max,maxi,i,j;
scanf("%d",&q);
while(q--){
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d%d%d",&a[0][i],&a[1][i],&a[2][i],&a[3][i]);
for(i=0;i<n;i++){
insert_edge(2*n+i,n+i,1);
insert_edge(3*n+i,i,1);
for(j=0;j<n;j++){
if(i==j)
continue;
if(!(a[0][i]>a[1][j] || a[0][j]>a[1][i]))
insert_edge(i,2*n+j,1);
if(!(a[2][i]>a[1][j] || a[0][j]>a[3][i]))
insert_edge(n+i,2*n+j,1);
if(!(a[0][i]>a[3][j] || a[2][j]>a[1][i]))
insert_edge(i,3*n+j,1);
if(!(a[2][i]>a[3][j] || a[2][j]>a[3][i]))
insert_edge(n+i,3*n+j,1);
}
}
max=1;
maxi=0;
for(i=0;i<n;i++)
for(j=max+1;i+j<=n;j++){
l=i;
r=i+j-1;
if(check()){
max=j;
maxi=i;
}
else
break;
}
printf("%d %d\n",maxi+1,maxi+max);
clean_table();
}
return 0;
}
void clean_table(){
int i;
lnode *p,*pp;
for(i=0;i<400;i++)
if(table[i]){
p=table[i];
while(p){
pp=p->next;
free(p);
p=pp;
}
table[i]=NULL;
}
for(i=0;i<400;i++)
if(rtable[i]){
p=rtable[i];
while(p){
pp=p->next;
free(p);
p=pp;
}
rtable[i]=NULL;
}
return;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=rtable[y];
rtable[y]=t;
return;
}
int check(){
int i;
st=c=0;
memset(mark,0,sizeof(mark));
memset(component,0,sizeof(component));
for(i=0;i<4*n;i++)
if(!mark[i] && checkx(i))
dfs1(i);
memset(mark,0,sizeof(mark));
while(st){
if(!mark[s[st-1]]){
c++;
dfs2(s[st-1]);
}
st--;
}
for(i=0;i<2*n;i++)
if(component[i]==component[i+2*n] && component[i] && checkx(i) && checkx(i+2*n))
return 0;
return 1;
}
void dfs1(int x){
lnode *p;
mark[x]=1;
for(p=table[x];p;p=p->next)
if(!mark[p->x] && checkx(p->x))
dfs1(p->x);
s[st++]=x;
return;
}
void dfs2(int x){
lnode *p;
mark[x]=1;
for(p=rtable[x];p;p=p->next)
if(!mark[p->x] && checkx(p->x))
dfs2(p->x);
component[x]=c;
return;
}
int checkx(int x){
return (x>=l && x<=r || x>=l+n && x<=r+n || x>=l+2*n && x<=r+2*n || x>=l+3*n && x<=r+3*n);
}
Leave a comment below
