HackerRank Recording Episodes problem solution

YASH PAL,

In this HackerRank Recording Episodes problem solution Given the programming schedule for each season, find L and R episode numbers for the largest range of consecutive episodes Dave can record during that season and print these respective values as two space-separated integers on a new line. If two or more such intervals exist, choose the one having the smallest L value.

HackerRank Recording Episodes problem solution

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static class Graph {
    int[] ptr;
    int[] nxt;
    int[] suc;
    int index = 1;

    public Graph(int nodes, int egges) {
      ptr = new int[nodes];
      nxt = new int[egges];
      suc = new int[egges];
    }

    void add(int u, int v) {
      nxt[index] = ptr[u];
      ptr[u] = index;
      suc[index++] = v;
    }

    void reset() {
      index = 1;
      Arrays.fill(ptr, 0);
    }
  }

  static class TarjanSCC {
    public int count;
    boolean[] marked;
    int[] id;
    int[] low;
    int pre;
    Stack<Integer> stack;
    int n;

    public TarjanSCC(Graph g, int n) {
      this.n = n;
      marked = new boolean[n];
      stack = new Stack<Integer>();
      id = new int[n];
      low = new int[n];
      for (int v = 0; v < n; v++) {
        if (!marked[v]) {
          dfs(g, v);
        }
      }
    }

    void dfs(Graph g, int v) {
      int w;
      marked[v] = true;
      low[v] = pre++;
      int min = low[v];
      stack.push(v);
      for (int i = g.ptr[v]; i > 0; i = g.nxt[i]) {
        w = g.suc[i];
        if (!marked[w]) {
          dfs(g, w);
        }
        if (low[w] < min) {
          min = low[w];
        }
      }
      if (min < low[v]) {
        low[v] = min;
        return;
      }

      do {
        w = stack.pop();
        id[w] = count;
        low[w] = n;
      } while (w != v);
      count++;
    }

    public boolean stronglyConnected(int u, int v) {
      return id[u] == id[v];
    }
  }

  static class Sat2 {
    int n = 0;
    Graph edges = null;

    public Sat2(int n, Graph edges) {
      this.n = n;
      this.edges = edges;
      edges.reset();
    }

    public int c_not(int a) {
      return -a - 1;
    }

    int c_convert(int a) {
      return a < 0 ? (c_not(a) << 1) ^ 1 : a << 1;
    }

    void c_must(int a) {
      edges.add(a ^ 1, a);
    }

    void c_or(int a, int b) {
      edges.add(a ^ 1, b);
      edges.add(b ^ 1, a);
    }

    public void c_xor(int a, int b) {
      c_or(a, b);
      c_or(a ^ 1, b ^ 1);
    }

    void c_and(int a, int b) {
      edges.add(a, b);
      edges.add(b, a);
    }

    void c_not_and(int a, int b) {
      edges.add(a, b ^ 1);
      edges.add(b, a ^ 1);
    }

    public int not(int a) {
      return c_not(a);
    }

    public void must(int a) {
      c_must(c_convert(a));
    }

    public void or(int a, int b) {
      c_or(c_convert(a), c_convert(b));
    }

    public void xor(int a, int b) {
      c_xor(c_convert(a), c_convert(b));
    }

    public void and(int a, int b) {
      c_and(c_convert(a), c_convert(b));
    }

    public void notAnd(int a, int b) {
      c_not_and(c_convert(a), c_convert(b));
    }

    public boolean possible() {
      TarjanSCC scc = new TarjanSCC(edges, n*2);
      for (int v = 0; v < n; v++) {
        if (scc.stronglyConnected(v << 1, (v << 1) ^ 1)) {
          return false;
        }
      }
      return true;
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int q = Integer.parseInt(st.nextToken());

    int[][] se = new int[200][2];
    boolean[][] ol = new boolean[200][200];
    Graph edges = new Graph(200, 500);

    for (int itr = 0; itr < q; itr++) {
      st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());

      for (int i = 0; i < n; i++) {
        st = new StringTokenizer(br.readLine());
        int sl = Integer.parseInt(st.nextToken());
        int el = Integer.parseInt(st.nextToken());
        int sr = Integer.parseInt(st.nextToken());
        int er = Integer.parseInt(st.nextToken());
        se[i * 2][0] = sl;
        se[i * 2][1] = el;
        se[i * 2 + 1][0] = sr;
        se[i * 2 + 1][1] = er;
      }

      for (int i = 0; i < n * 2 - 1; i++) {
        for (int j = i + 1; j < n * 2; j++) {
          ol[i][j] = (se[i][0] <= se[j][1] && se[j][0] <= se[i][1]);
          ol[j][i] = ol[i][j];
        }
      }

      int ll = 0;
      int rr = 0;

      int l = ll;
      int r = rr;
      while (true) {
        Sat2 sat2 = new Sat2(n, edges);
        for (int x = l; x < r; x++) {
          for (int y = x + 1; y <= r; y++) {
            if (ol[x * 2][y * 2]) {
              sat2.or(x, y);
            }
            if (ol[x * 2 + 1][y * 2]) {
              sat2.or(sat2.not(x), y);
            }
            if (ol[x * 2][y * 2 + 1]) {
              sat2.or(x, sat2.not(y));
            }
            if (ol[x * 2 + 1][y * 2 + 1]) {
              sat2.or(sat2.not(x), sat2.not(y));
            }
          }
        }
        if (sat2.possible()) {
          if (r - l > rr - ll) {
            ll = l;
            rr = r;
          }
          if (r == n - 1) {
            break;
          }
          r++;
        } else {
          l++;
          if (r < l) {
            r = l;
          }
        }
      }

      bw.write((ll + 1) + " " + (rr + 1));
      bw.newLine();
    }

    bw.close();
    br.close();
  }
}

{“mode”:”full”,”isActive”:false}

Problem solution in C++.

#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 %dn",an2,an2+an1-1);
    }
    return 0;
}

{“mode”:”full”,”isActive”:false}

Problem solution in C.

#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 %dn",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);
}

{“mode”:”full”,”isActive”:false}

Algorithms coding problems solutions