ARDA1 SPOJ (Bruteforce / KMP) Solution C++

Bruteforce / KMP

With bruteforce - 0.01s

With KMP        - 0.17s

Solution (Bruteforce):

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std; 

char s[301][301];
char world[2001][2001]; 

int main(){
 int a, b;  
 scanf("%d %d", &a, &b);  
 for(int i=0;i<a;++i){scanf(" %s", s[i], sizeof(char)*b);}
 int x, y;
 scanf("%d %d", &x, &y); 
 for(int i=0;i<x;++i){scanf(" %s", world[i], sizeof(char)*y);}

 bool g = false; 

 for(int i=0;i<=x-a;++i){
  for(int j=0;j<=y-b;++j){

   if(world[i][j]==s[0][0]){
    bool f = true;
    for(int n=0, i2 = i;i2<i+a;++n, ++i2){
     for(int m=0, j2 = j;j2<j+b;++j2, ++m){
      if(s[n][m]!=world[i2][j2]){
       f = false;break;
      } 
     }
    }
    if(f){
     g = true;
     printf("(%d,%d)\n", i+1, j+1);
    } 
   }  
  } 
 }
 if(!g)printf("NO MATCH FOUND...\n"); 
 return 0;
}

Solution (KMP):

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

vector<int> indices;
class KMPSubstringMatch{
public:
 int W, R;
 int **dfa;
 char *s, *sub; 

 KMPSubstringMatch(char *s, char *sub, int subL, int R){
  this->s = s;
  this->W = subL;
  this->sub = sub;
  this->R = R;
  indices.clear();
  dfa = new int*[R];
  for(int i=0;i<R;++i){dfa[i] = new int[W];for(int j=0;j<W;++j)dfa[i][j]=0;}
 }

 ~KMPSubstringMatch(){
  for(int i=0;i<R;++i) delete[] (dfa[i]);
  delete[] dfa;
 }

 void constructDFA(){  
     int X=0;
     dfa[sub[0]][0] = 1;
     for(int i=1;i<W;++i){ 
         for(int j=0;j<R;++j){
             dfa[j][i] = dfa[j][X];
         }
         dfa[sub[i]][i] = i+1;
         X = dfa[sub[i]][X];
     }
 }

 void find(int slength, int sublen){
        int i, j;
        for(i=0, j=0;i<slength;++i){
            j=dfa[s[i]][j]; 
            if(j==W){ 
    indices.push_back(i-sublen+1); 
                j=0;
                i=(i-sublen+1);
            }
        }  
    } 
    
 static void find(char *s, char *sub, int slen, int subL){
        KMPSubstringMatch *kmp = new KMPSubstringMatch(s, sub, subL, 257); 
        kmp->constructDFA();
        kmp->find(slen, subL);
        delete kmp;
    }
};

char s[301][301];
char world[2001][2001];

int main(){
 int a, b;  
 scanf("%d %d", &a, &b);  
 for(int i=0;i<a;++i){scanf(" %s", s[i], sizeof(char)*b);}
 int x, y;
 scanf("%d %d", &x, &y); 
 for(int i=0;i<x;++i){scanf(" %s", world[i], sizeof(char)*y);}

 bool f = false; 
 for(int i=0;i<x;++i){
  int t=0;
  char *cur = world[i];
  KMPSubstringMatch::find(cur, s[t], y, b); 
  if(!indices.empty() && a>1){
   for(int z=0;z<indices.size();++z){
    int v = indices[z]; 
    bool fl = true;
    for(int i2=i, X=0;X<a;++X,++i2){
     for(int j2=v, Y=0;Y<b;++Y,++j2){
      if(s[X][Y]!=world[i2][j2]){fl=false;break;}
     }
     if(!fl)break;
    }
    if(fl){printf("(%d,%d)\n", i+1, v+1);f = true;}
   }
  }else if(!indices.empty() && a==1){
   for(int z=0;z<indices.size();++z){
    int v = indices[z];
    f = true;
    printf("(%d,%d)\n", i+1, v+1);
   }
  }
 }
 if(!f)printf("NO MATCH FOUND...\n");  
 return 0;
}

SPOJ BTCODE_H (Maths) Solution - Java

Test Case given-

N = 2, K = 2.

# of words containing only 0 and 1 that are of length 2 -> 4

00
01
10
11

Now insertion of words may happen as:

00 00                      
00 01           01 00
00 10           10 00
00 11           11 00

01 01      
01 10           10 01
01 11           11 01

10 10
10 11           11 10

11 11

Total # cases -> 16.

# cases where trie has 3 nodes = 4
                                4 nodes = 4
                                5 nodes = 8

Expected value of the number of nodes ->

(3*4 + 4*4 + 5*8)                                    68
----------------------         =             ---------------------             =              4.25
          16                                                16

Source (Java):

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;


public class BTCODE_HSimple {
    
    //Exponentiation by Repeated Sqauring
    public static double power(double a, int b){
        if(b==0)return 1;
        if(b==1)return a;
        if(b%2==1){
            return a*power(a*a, (b-1)/2);
        }else return power(a*a, b/2);
    }
    
    public static void main(String[] args){
        int n = IO.nextInt(); 
        while(n-->0){
            int N = IO.nextInt();
            int K = IO.nextInt();
            double ans = 1;
            for(int i=1;i<=K;++i){
                double p = power(0.5, i); 
                ans += 1;
                double op = 1-p; 
                for(int j=1;j<N;++j){ 
                    ans += power(op, j);
                } 
            }
            System.out.printf("%.2f\n", ans);
        }
    }



    /**************************************IO**************************************/
    
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

TAP2012D SPOJ (Trie with HashMaps) solution Java

You need to put all the names first and second team players in the same trie. If your logic involves putting the names of team1 into trie and then using team2 player names, you're likely to get WAs. For eg. changing the order of queries for team2 names will get you different answers in some cases.

Check out these test cases:-

5
H HE HER HEREB HEREBY
HEREBY HEREB HERE HER HE

7
THIS IS JUST A SE NT ENCE
SENTTH IS JU SIS AS SE THUS

Check out my solution if you're still stuck.

Source:

import java.io.*;
import java.util.*;
 
class Node{
    HashMap<Character, Integer> children;
    int first =  0;
    int second = 0; 
     
    Node(){
        children = new HashMap<>();  
    }
    
    void init(){
        children.clear(); 
        first = 0;
        second = 0; 
    }
}

class TrieMap {
    static final int MAX = 500000; 
    static int gIndex;
    static Node trie[]; 
    static int count=0;
    
    public static void insert(String s, int type){  
        int cIndex = 0;
      
        for(int i=0;i<s.length();++i){
            char c = s.charAt(i); 
            Integer nIndex = trie[cIndex].children.get(c); 
            if(nIndex==null){ 
                    trie[cIndex].children.put(c, ++gIndex);  
                    if(trie[gIndex]==null)trie[gIndex] = new Node(); 
                    trie[gIndex].init();
                    cIndex = gIndex; 
                    nIndex = cIndex;  
            }else{
                cIndex = nIndex;  
            }
            
            if(type==1)trie[nIndex].first++; 
            else       trie[nIndex].second++;
        }  
    } 
    
    static int ans=0;
    public static int query(int cIndex, int depth){  
        
        int sub = 0;
        for(Map.Entry<Character, Integer> me:trie[cIndex].children.entrySet()){ 
            int value = me.getValue();
            
            if(trie[value].first>0 && trie[value].second>0){
                int r = query(value, depth+1);
                sub+=r;
                trie[cIndex].first -= r;
                trie[cIndex].second -= r;
            }
        } 
        int min  = Math.min(trie[cIndex].first, trie[cIndex].second); 
        if(cIndex!=0)ans+=depth*min; 
        return min+sub;
    } 
    
    public static void main(String[] args){
          
        trie = new Node[MAX];  
        
        while(true){ 
            int n = IO.nextInt();
            if(n==-1)return;
            trie[0] = new Node();
            trie[0].init();  
            count=0;
            gIndex = 0;
            for(int i=0;i<n;++i){
                String s = IO.nextString(); 
                insert(s, 1);
            } 
            ans=0; 
            for(int i=0;i<n;++i){  
                insert(IO.nextString(), 2);  
            }   
            query(0, 0);
            IO.println(ans);
        }
    }
    




    /***********************************IO***************************************/
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

LEONARDO SPOJ (Implementation) Solution - JAVA

Algorithm :-

1. Odd length cycles are OK.
2. The graph should have two even length cycles of the same length if even cycles exist. (There may be multiple even cycles).
3. Self loops are OK.

Point #2:

Consider an alphabet having only 6 letters i.e. ABCDEF. Now we have to apply the same permutation twice to get "CDEABF". The permutation we apply is "BCDAEF". Applying it twice (steps):-

|--->CDABEF
P
|--->BCDAEF
P
|----ABCDEF

Where P stands for the application of the permutation "BCDAEF". Now if we only consider the final alphabet string and the original one,

CDABEF

ABCDEF

Notice our even length cycle "BCDA" has split up into two even cycles of equal length. (CA and DB).

You can similarly figure out that odd length cycles remain odd length cycles and of course, self loops have no effect.

Self loops:

There are two self loops in the above example E-E and F-F.

Now just write code to check whether there are even number of even length cycles. If this is the case, the answer is yes, otherwise no.

Source (Java):

import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;


public class LEONARDO { 
    
    public static void main(String[] args){
        int n = IO.nextInt();
        String REF = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        while(n-->0){
            String s = IO.nextString();
            
            int[] pos = new int[256];
          
            for(int i=0;i<s.length();++i){
                pos[s.charAt(i)] = i;
            }
            
            boolean m[] = new boolean[256]; 
            
            int cyclesReg[] = new int[26]; 
            for(int i=0;i<s.length();++i){
                char c = s.charAt(i); 
                boolean f = false;
                int length =0 ;
                while(!m[c]){  
                    f = true;
                    length++;
                    m[c] = true;
                    int p = pos[c];
                    c = REF.charAt(p);
                } 
                if(f){ 
                    cyclesReg[length]++;
                }
            }
             
            boolean f = true;
            for(int i=0;i<cyclesReg.length;++i){
                if(i%2==0 && cyclesReg[i]%2!=0){f =  false;break;}
            }
            if(f)IO.println("Yes");
            else IO.println("No");
        }
    }
    
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

SUBXOR SPOJ (Trie) Solution - C++

Algorithm:

1. If you want to get XOR of array elements in range [I, J], you can do it by taking the XOR of [1, I-1] with XOR[1, J]. (How does this solve the problem? - See next points.)
2. Make a trie of the bit representation of the XOR of elements.

Suppose the array is: 4, 1, 3, 2, 7. and k = 2.

      Binary Rep.     XOR    K=2 Bin = 010

4    100                  100
1    001                  101
3    011                  110
2    010                  100  <-- (example case below)
7    111                  011

For each element of the array,

1. Insert the value 0 to the Trie (test for cases like when there is only one element present and is less than k).
2. Find it's XOR with the previous value (0 if first). Now find how many subarrays are present whose XOR is less than k. How? ->

Consider the case when you've inserted XOR with element 3 and considering the element 2 to pass its XOR to query.
Now k = 2 its binary rep. is 010. Now you take this representation of k and the current XOR value's (for 2 = 100) binary representation to guide your search through the trie.

k1 = 0. Now above the value 2 in the array, all those XORs whose bit at index = 1 is = 1, when taken XOR with "1"00 will give a value 0. These XORs are the ones who may be less than or equal to the value k. Those XOR values who have a 0 in the first bit when taken XOR with "1"00 will give 1 which means that all those XORs are greater than k. Here's the full detail-

Check the first bits below:-

100 ^ 100 -> 000 = (0 in the first position). Can be less than k. This represents the XOR of 1,3,2 as you are taking xor of 4,1,3,2 with 4 so you get xor of 1,3,2.

100 ^ 101 -> 001 = (0 in the first position again). Can be less than k. This represents the XOR of 4,1 with XOR of 4,1,3,2 = XOR of 3, 2.

100 ^ 110 -> 010 = (0 in the first position again). Can be less than k. This represents the XOR of 4,1,3 with XOR of 4,1,3,2 = XOR of 2.

100 ^ 000 (the first 0 we inserted in the trie) -> represents the XOR of 4,1,3,2.

So all the possible sequences ending at 2 have been considered. A trie thus helps to get the answer fast.

3. Do this until the last element of the array has been considered.

Code (C++):

#include <stdio.h>

#define MAX 200000

struct node{
 int nL, nR;
 int leftIndex, rightIndex;

 node(){
  nL = 0;
  nR = 0;
  leftIndex=-1;
  rightIndex=-1;
 }
};
  
int gIndex=0;

void insert(int value, int index, int depth, node *tree){
 for(int i = depth-1;i>=0;--i){
  int bit = value>>i & 1;
  if(bit){
   tree[index].nR++; 
   if(tree[index].rightIndex==-1){ 
    tree[index].rightIndex = ++gIndex;
    index = gIndex;
   }else index = tree[index].rightIndex;
  }else{ 
   tree[index].nL++;
   if(tree[index].leftIndex==-1){
    tree[index].leftIndex = ++gIndex;
    index = gIndex;
   }else index = tree[index].leftIndex; 
  }
 } 
}

int query(int value, int compare, int index, int depth, node* tree){
 int ans=0;
 for(int i=depth-1;i>=0;--i){
  int vBit = value>>i & 1;
  int cBit = compare>>i & 1;
  if(cBit){ 
   if(vBit){ans += tree[index].nR; index = tree[index].leftIndex;}
   else{ans += tree[index].nL; index = tree[index].rightIndex;} 
  }else{ 
   if(vBit) index = tree[index].rightIndex;
   else  index = tree[index].leftIndex;
  }
  if(index==-1)break; 
 }
 return ans;
}

int main(){
 int d;
 scanf("%d", &d);
 while(d--){ 
  node tree[MAX];
  gIndex=0;
  int n, k;
  scanf(" %d %d", &n, &k);
  int XOR = 0, t=0;
  long long ans=0;
  insert(0, 0, 20, tree);
  while(n--){
   scanf(" %d", &t);
   XOR = XOR ^ t;
   ans += query(XOR, k, 0, 20, tree);  
   insert(XOR, 0, 20, tree);
  }
  printf("%lld\n", ans);
 }
}

PRHYME SPOJ (Trie) Solution - C++

Algorithm:

1. Each node stores the number of children that each of its subtree has.

2. Every node stores information about two strings. The first string is the one which is smallest at that node (lexicographically; amongst all the strings that pass though that node) and the second one is the second smallest string.

3. Strings are inserted in reverse order into the trie.

4. For answering the queries, traverse the trie, check the number of nodes the current node has for the next character of the string. If it equals one, check if the best string stored at that node is the string being processed. If this is true, print the second string, else print the first string.

C++: 

#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

#define debug if(0)
#define W 250001
#define L 31
#define INF 0x7fffffff

struct node{
 int children[26]; 
 int num[26];
 int fs, ss; 

 void init(){
  for(int i=0;i<26;++i){
   children[i] = 0;
   num[i]=0;
   fs = INF;
   ss = INF;
  }
 }
};

int gIndex; 
node trie[800000];
char dict[W][31];
int sorted[W]; 

void add(char *s, int jz, int cI, int len, int rank){
 int q[31];int qI=0;
 q[qI++] = cI; 
 for(int i=len-1;i>=0;--i){  
  int nI = trie[cI].children[s[i]-'a']; 
  int cS = cI;
  if(nI==0){
   trie[cI].children[s[i]-'a'] = ++gIndex;
   cI = gIndex;  
   trie[cI].init();
  }else{
   cI = nI;
  }
  trie[cS].num[s[i]-'a']++; 
  q[qI++] = cI;
 }
  
 for(int i=qI-1;i>=0;--i){
  int v = q[i];  
  if(rank<trie[v].fs){
   trie[v].ss = trie[v].fs;
   trie[v].fs = rank; 
  }else if(rank<trie[v].ss){ 
   trie[v].ss = rank; 
  } 
 }
}


void find(char *s, int len){
  int cI = 0;  
   if(trie[0].num[s[len-1]-'a']==1){  
   if(strcmp(s, dict[sorted[trie[cI].fs]])==0){puts(dict[sorted[trie[cI].ss]]);}
   else {puts(dict[sorted[trie[cI].fs]]);} 
   return;
   }

  for(int i=len-1;i>=0;--i){
   cI = trie[cI].children[s[i]-'a']; 
   if((i-1)<0 || trie[cI].num[s[i-1]-'a']==1){
    if(strcmp(s, dict[sorted[trie[cI].fs]])==0){puts(dict[sorted[trie[cI].ss]]);}
    else {puts(dict[sorted[trie[cI].fs]]);}
    return;
   }
  }
}

inline bool comp(int a, int b){
 return strcmp(dict[a], dict[b])<0;
}

int main(){
 char s[31];
 int n=0, i;
 while(gets(dict[n]) && dict[n][0])n++;
 for(i=0;i<n;++i)sorted[i] = i;
 sort(sorted, sorted+n, comp);  

 trie[0].init(); 
 gIndex= 0;
 for(i=0;i<n;++i){
  int len = strlen(dict[sorted[i]]);
  add(dict[sorted[i]], len-1, 0, len, i); 
 }
 while(gets(s)&&s[0]){
  find(s, strlen(s)); 
 }
}