Sunday, May 24, 2015

CAPCITY SPOJ.com solution C++

Problem : spoj.com/problems/CAPCITY

Algorithm : Kosaraju's Algorithm ( Two pass, Strongly connected components, kernel dag )

Source: (C++ : AC)

```#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int V, E;
vector<vector<int> > G;
vector<vector<int> > GD;
vector<vector<int> > res;
vector<vector<int> > SCCconn;

vector<int> sortOrder;

bool *marked;
int *reg;
int groupNo;

void dfs(int vertex){
if(marked[vertex])return;
marked[vertex] = true;

for(int i=0;i<G[vertex].size();++i) dfs(G[vertex][i]);
sortOrder.push_back(vertex);
}

void dfs2(int vertex){
if(marked[vertex])return;
marked[vertex] = true;

for(int i=0;i<GD[vertex].size();++i)dfs2(GD[vertex][i]);
res[groupNo].push_back(vertex);
reg[vertex] = groupNo;
}

void dfs3(int callingGroup, int vertex){
if(marked[vertex]){
if(callingGroup!=reg[vertex])SCCconn[callingGroup].push_back(reg[vertex]);
return;
}
marked[vertex] = true;
for(int i=0;i<GD[vertex].size();++i){
dfs3(callingGroup, GD[vertex][i]);
}
}

int dfs4(int callingGroup){
int size=0;
for(int i=0;i<SCCconn[callingGroup].size();++i){
size+=dfs4(SCCconn[callingGroup][i]);
}
size+=res[callingGroup].size();
return size;
}

int main(){
scanf("%d %d", &V, &E);
marked = new bool[V];
reg = new int[V];

for(int i=0;i<V;++i)marked[i] = false;
for(int i=0;i<V;++i)reg[i] = -1;
groupNo = -1;

for(int i=0;i<V;++i){
vector<int> x,xx,xxx,xxxx;
res.push_back(x);
G.push_back(xx);
GD.push_back(xxx);
SCCconn.push_back(xxxx);
}

for(int i=0;i<E;++i){
int from, to;
scanf("%d %d", &from, &to);
from--;to--;
G[from].push_back(to);
GD[to].push_back(from);
}

if(V==1){
printf("%d\n%d", 1, V);
return 0;
}
for(int i=0;i<V;++i)dfs(i);
for(int i=0;i<V;++i)marked[i] = false;
for(int i=sortOrder.size()-1;i>=0;--i){
if(!marked[sortOrder[i]])groupNo++;
dfs2(sortOrder[i]);
}
vector<int> result;
for(int i=0;i<V;++i)marked[i] = false;
for(int i=0;i<V;++i){
if(res[i].size()==0)break;
for(int j=0;j<res[i].size();++j){
dfs3(i, res[i][j]);
}
}

for(int i=0;i<SCCconn.size();++i){
int sizeOfGroup = dfs4(i);
if(sizeOfGroup==V){
for(int j=0;j<res[i].size();++j){
result.push_back(res[i][j]);
}
}
}
printf("%d\n", result.size());
sort(result.begin(), result.end());

for(int i=0;i<result.size();++i)printf("%d ", result[i]+1);
printf("\n");
}```

SPOJ BOTTOM Solution : Strongly Connected Components : Kosaraju's Algorithm

Problem : http://www.spoj.com/problems/BOTTOM/

Source: C++ AC (0.02s):

```#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int V, E;
vector<vector<int> > G;
vector<vector<int> > GD;
vector<vector<int> > res;

vector<int> sortOrder;

bool *marked;
int *reg;
int groupNo;

void dfs(int vertex){
if(marked[vertex])return;
marked[vertex] = true;

for(int i=0;i<G[vertex].size();++i) dfs(G[vertex][i]);
sortOrder.push_back(vertex);
}

void dfs2(int vertex){
if(marked[vertex])return;
marked[vertex] = true;

for(int i=0;i<GD[vertex].size();++i)dfs2(GD[vertex][i]);
res[groupNo].push_back(vertex);
reg[vertex] = groupNo;
}

int main(){
while(true){
scanf(" %d", &V);
if(V==0)break;
scanf(" %d", &E);

marked = new bool[V];
for(int i=0;i<V;++i)marked[i] = false;
reg = new int[V];
for(int i=0;i<V;++i)reg[i] = -1;

sortOrder.clear();
G.clear();
GD.clear();
res.clear();
groupNo = -1;

for(int i=0;i<V;++i){
vector<int> t,tt,ttt;
res.push_back(t);
G.push_back(tt);
GD.push_back(ttt);
}

if(E!=0){
for(int j=0;j<E;++j){
int from, to;
scanf(" %d %d", &from, &to);
from--;
to--;
G[from].push_back(to);
GD[to].push_back(from);
}
}
for(int i=0;i<V;++i)dfs(i);
for(int i=0;i<V;++i)marked[i] = false;
for(int i=sortOrder.size()-1;i>=0;--i){
if(!marked[sortOrder[i]])groupNo++;
dfs2(sortOrder[i]);
}

vector<int> ans;
for(int i=0;i<res.size();++i){
if(res[i].size()>1){
int group = i;
bool flag = true;
for(int j=0;j<res[i].size();++j){
for(int k=0;k<G[res[group][j]].size();++k){
if(reg[G[res[group][j]][k]]!=group){
flag = false;
break;
}
}
if(!flag)break;
}
if(flag){
for(int j=0;j<res[i].size();++j)ans.push_back(res[i][j]);
}
}else if(res[i].size()==1){
if(G[res[i][0]].size()==0)ans.push_back(res[i][0]);
else if(G[res[i][0]].size()==1 && G[res[i][0]][0]==res[i][0])ans.push_back(res[i][0]);
}
}
std::sort(ans.begin(), ans.end());
for(int i=0;i<ans.size();++i){
printf("%d ", ans[i]+1);
}
printf("\n");
}
}```

Saturday, May 23, 2015

Strongly Connected Components : Kosaraju’s algorithm Implementation - Java

Source:

```import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class KosarajuSharirStronglyConnectedComponents {
static int V, E;
static ArrayList<ArrayList<Integer>> G = new ArrayList<>();
static ArrayList<ArrayList<Integer>> GD = new ArrayList<>();

static ArrayList<Integer> sortOrder = new ArrayList<>();

static boolean marked[];
static int reg[];
static int groupNo=0;

static void dfs(int vertex){
if(marked[vertex])return;

marked[vertex] = true;

for(int c:G.get(vertex)){
dfs(c);
}
}

static void dfs2(int vertex){
if(marked[vertex])return;

marked[vertex] = true;

for(int c:GD.get(vertex)){
dfs2(c);
}
reg[vertex] = groupNo;
}

public static void main(String[] args) throws Exception{
String s = null;

marked = new boolean[V];
reg = new int[V];

String d[] = s.split(" ");
int from, to;
from = Integer.parseInt(d[0]);
to = Integer.parseInt(d[1]);

}

for(int i=0;i<V;++i){
dfs(i);
}

System.out.println(sortOrder);
Collections.reverse(sortOrder);

Arrays.fill(marked, false);

for(int i:sortOrder){
if(!marked[i])groupNo++;
dfs2(i);
}

for(int i=0;i<reg.length;++i){
System.out.println("Node "+i+" group = "+reg[i]);
}
}
}```

Input Format:

Number of vertices V
Number of edges     E
Directed edges Node-from to Node-to
.
.
.
Eth edge

Input File (2 tests):

File #1 Contents:

13
20
0 1
0 5
2 0
2 3
3 2
3 5
4 2
6 0
6 8
6 4
6 9
7 6
7 9
8 6
9 10
9 11
10 12
11 12
11 4
12 9

File #2 Contents (Example case geeksforgeeks):

5
5
1 0
0 2
2 1
0 3
3 4

Output:

For Test #1:

[1, 2, 4, 3, 0]
Node 0 group = 1
Node 1 group = 1
Node 2 group = 1
Node 3 group = 2
Node 4 group = 3

For Test #2:

[1, 5, 0, 3, 2, 4, 8, 12, 10, 11, 9, 6, 7]
Node 0 group = 6
Node 1 group = 8
Node 2 group = 5
Node 3 group = 5
Node 4 group = 4
Node 5 group = 7
Node 6 group = 2
Node 7 group = 1
Node 8 group = 2
Node 9 group = 3
Node 10 group = 3
Node 11 group = 3
Node 12 group = 3

Practice problems: SPOJ: http://www.spoj.com/problems/WEBISL/

Solution :Java: AC:

```import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class WEBISL {
static int V, E;
static ArrayList<ArrayList<Integer>> G = new ArrayList<>();
static ArrayList<ArrayList<Integer>> GD = new ArrayList<>();

static ArrayList<Integer> sortOrder = new ArrayList<>();

static boolean marked[];
static int reg[];
static int groupNo=-1;

static void dfs(int vertex){
if(marked[vertex])return;

marked[vertex] = true;

for(int c:G.get(vertex)){
dfs(c);
}
}
static int[] groups;
static void dfs2(int vertex){
if(marked[vertex])return;

marked[vertex] = true;

for(int c:GD.get(vertex)){
dfs2(c);
}
if(groups[groupNo]>vertex)groups[groupNo]=vertex;
reg[vertex] = groupNo;
}

public static void main(String[] args) throws Exception{
String s = null;

V = Integer.parseInt(fD[0]);
E = Integer.parseInt(fD[1]);
groups = new int[V];
Arrays.fill(groups, Integer.MAX_VALUE);
marked = new boolean[V];
reg = new int[V];

while(E-->0){
String d[] = s.split(" ");
int from, to;
from = Integer.parseInt(d[0]);
to = Integer.parseInt(d[1]);

}

for(int i=0;i<V;++i){
dfs(i);
}

//        System.out.println(sortOrder);
Collections.reverse(sortOrder);

Arrays.fill(marked, false);

for(int i:sortOrder){
if(!marked[i]){groupNo++;}
dfs2(i);
}

for(int i=0;i<reg.length;++i){
System.out.println(groups[reg[i]]);
}
//        System.out.println(Arrays.toString(groups));
//        System.out.println(Arrays.toString(reg));
}
}```

Friday, May 22, 2015

ROCK. SPOJ - ROCK solution

Problem: www.spoj.com/problems/ROCK

Source (Java), AC:

```import java.io.*;

class ROCK {

public static int[] data;
public static int[][] dp;

public static int solve(int from, int to) {
int ones = 0, zeros = 0;

if(from>to)return 0;
if (dp[from][to] != -1) return dp[from][to];

for (int i = from; i <= to; ++i) {
if (data[i] == 1) ones++;
else zeros++;
}

if(ones>zeros)return dp[from][to]=ones+zeros;

if(from==to) return data[to];
int max = 0;

for(int i=from;i<=to;++i){
int left = 0;
if(i!=to)left = solve(from, i);
int right = 0;
if(i+1!=from)right = solve(i+1, to);
if(left+right>max){max = left+right;}
}
return dp[from][to] = max;
}

public static void main(String[] args) throws Exception {
int nCases = IO.nextInt();
while (nCases-- > 0) {
int length = IO.nextInt();
data = IO.nextIntArray(length, "");
dp = new int[length + 1][length + 1];
for (int i = 0; i < length + 1; ++i) {
for (int j = 0; j < length + 1; ++j) {
dp[i][j] = -1;
}
}
IO.println(solve(1, length));
}
}
```
```    static class IO {

public static int[][] next2dInt(int rows, int cols, String seperator) throws Exception {
int[][] arr = new int[rows + 1][cols + 1];
for (int i = 1; i <= rows; ++i) {
arr[i] = nextIntArray(cols, seperator);
}
return arr;
}

public static int[] nextIntArray(int nInts, String seperator) throws IOException {
String[] sArray = ints.split(seperator);
int[] array = new int[nInts + 1];
for (int i = 1; i <= nInts; ++i) {
array[i] = Integer.parseInt(sArray[i - 1]);
}
return array;
}

public static long[] nextLongArray(int nLongs, String seperator) throws IOException {
String[] sArray = longs.split(seperator);
long[] array = new long[nLongs + 1];
for (int i = 1; i <= nLongs; ++i) {
array[i] = Long.parseLong(sArray[i - 1]);
}
return array;
}

public static double[] nextDoubleArray(int nDoubles, String seperator) throws IOException {
String[] sArray = doubles.split(seperator);
double[] array = new double[nDoubles + 1];
for (int i = 1; i <= nDoubles; ++i) {
array[i] = Double.parseDouble(sArray[i - 1]);
}
return array;
}

public static char[] nextCharArray(int nChars, String seperator) throws IOException {
String[] sArray = chars.split(seperator);
char[] array = new char[nChars + 1];
for (int i = 1; i <= nChars; ++i) {
array[i] = sArray[i - 1].charAt(0);
}
return array;
}

public static int nextInt() throws IOException {
return Integer.parseInt(in);
}

public static double nextDouble() throws IOException {
return Double.parseDouble(in);
}

public static long nextLong() throws IOException {
return Long.parseLong(in);
}

public static int nextChar() throws IOException {
return in.charAt(0);
}

public static String nextString() throws IOException {
}

public static void print(Object... o) {
for (Object os : o) {
System.out.print(os);
}
}

public static void println(Object... o) {
for (Object os : o) {
System.out.print(os);
}
System.out.print("\n");
}

public static void printlnSeperate(String seperator, Object... o) {
StringBuilder sb = new StringBuilder();
sb.delete(sb.length() - seperator.length(), sb.length());
System.out.println(sb);
}
}
}```

Friday, May 1, 2015

WORDS1 SPOJ.com Euler Path. Graph Theory.

Problem : http://www.spoj.com/problems/WORDS1/

http://en.wikipedia.org/wiki/Eulerian_path

http://www.quora.com/How-do-I-solve-the-SPOJ-Play-on-Words-problem

http://web.iiit.ac.in/~mayank.natani/SPOJ/WORDS1.cpp

My JAVA solution (Accepted):

```import java.io.*;
import java.math.*;
import java.util.*;

public class WORDS1Attempt2 {

public static boolean checkConnections(int index) {
/*
If broken connections equal total number of connections, we are done, the graph is connected.
*/
if(broken == connections)return true;
int row = index;

for(int i=1;i<27;++i){
/*
either this vertex can reach some other vertex or some other vertex can reach this vertex. Means they are connected.
*/
if(graph[row][i]||graph[i][row]){
if(graph[row][i])broken++;
graph[row][i] = false;
if(graph[i][row])broken++;
graph[i][row] = false;
if(checkConnections(i))return true;
}
}
//Else if it is not the case, return false.
return false;
}

static boolean[][] graph;
static int connections = 0;
static int broken=0;

public static void main(String[] args) throws Exception {
int nCases = IO.nextInt();
while (nCases-- > 0) {
connections=0;
broken=0;
graph = new boolean[27][27];
int[] reg = new int[27];
int nWords = IO.nextInt();
int f, s;
String[] words = new String[nWords];

for (int i = 0; i < nWords; ++i) {
words[i] = IO.nextString();
reg[f =(words[i].charAt(0) - 96)]++;
reg[s =(words[i].charAt(words[i].length() - 1) - 96)]--;

//Check the number of unique connections in the graph to be later
//used when checking the graph for connectivity
if(graph[f][s]==false)connections++;
graph[f][s]=true;
}

boolean possible = true;

//No of minus one values (-1) in the array reg. this array stores the difference (in-out) connections.
int mO = 0;
int pO = 0;
//No of zeros in the array reg.
int zeros=0;

for (int i = 1; i < reg.length; ++i) {
if (reg[i] != 0) {
if (reg[i] == 1) pO++;
else if (reg[i] == -1) mO++;
else {
possible = false;
break;
}
}else zeros++;
}

/*
If in reg array (reg array stores the difference (no of incomming connections - no out outgoing connections)
number of minus ones (mO) found is 1 and number of plus one found is 1,
the graph may have an euler path (necessary but not sufficient condition).
Even if mO and pO equal one, the graph could be a disconnected one for example
in case
abc
cba

qcr
rcx

This graph would be disconnected, yet has mO = 1 and pO = 1.
for this, we need to check if every vertice is
connected (no matter the direction of connection) to every other vertice.
*/
if (!(mO==1 && pO==1)){
/*
If there is no +1 or -1, all the vertices should have out-in connection difference = 0
for the graph to have the possibility of having an euler path.
*/
if(zeros!=26) possible=false;
}

if(possible){
/*
The vertex (index in graph) to start the dfs procedure from
This must be the vertex having |in-out connections| value = 1.
*/
int in=-1;

/*
In case there is no such vertex. (All reg[i] values are 0.
This means that the graph is of the form

abc
cbd
dca

This still has an euler path. The end can be joined to the beginning. (This doesn't bother us for the question).
In this case, we can select any vertex as the starting vertex to see if it is connected to every other vertex.
*/
for(int i=1;i<27;++i){if(reg[i]==1||reg[i]==-1)in = i;}
if(in==-1)for(int i=1;i<27;++i){for(int j=1;j<27;++j)if(graph[i][j])in=i;}

//checkConnections() checks if every vertice is connected in a single graph.
possible = checkConnections(in);
}

if (possible) System.out.println("Ordering is possible.");
else System.out.println("The door cannot be opened.");
}
}

static class IO {

public static int[][] next2dInt(int rows, int cols, String seperator) throws Exception {
int[][] arr = new int[rows + 1][cols + 1];
for (int i = 1; i <= rows; ++i) {
arr[i] = nextIntArray(cols, seperator);
}
return arr;
}

public static int[] nextIntArray(int nInts, String seperator) throws IOException {
String[] sArray = ints.split(seperator);
int[] array = new int[nInts + 1];
for (int i = 1; i <= nInts; ++i) {
array[i] = Integer.parseInt(sArray[i - 1]);
}
return array;
}

public static long[] nextLongArray(int nLongs, String seperator) throws IOException {
String[] sArray = longs.split(seperator);
long[] array = new long[nLongs + 1];
for (int i = 1; i <= nLongs; ++i) {
array[i] = Long.parseLong(sArray[i - 1]);
}
return array;
}

public static double[] nextDoubleArray(int nDoubles, String seperator) throws IOException {
String[] sArray = doubles.split(seperator);
double[] array = new double[nDoubles + 1];
for (int i = 1; i <= nDoubles; ++i) {
array[i] = Double.parseDouble(sArray[i - 1]);
}
return array;
}

public static char[] nextCharArray(int nChars, String seperator) throws IOException {
String[] sArray = chars.split(seperator);
char[] array = new char[nChars + 1];
for (int i = 1; i <= nChars; ++i) {
array[i] = sArray[i - 1].charAt(0);
}
return array;
}

public static int nextInt() throws IOException {
return Integer.parseInt(in);
}

public static double nextDouble() throws IOException {
return Double.parseDouble(in);
}

public static long nextLong() throws IOException {
return Long.parseLong(in);
}

public static int nextChar() throws IOException {
return in.charAt(0);
}

public static String nextString() throws IOException {
}

public static void print(Object... o) {
for (Object os : o) {
System.out.print(os);
}
}

public static void println(Object... o) {
for (Object os : o) {
System.out.print(os);
}
System.out.print("\n");
}

public static void printlnSeperate(String seperator, Object... o) {
StringBuilder sb = new StringBuilder();
sb.delete(sb.length() - seperator.length(), sb.length());
System.out.println(sb);
}
}
}```

Check sample cases:

2
4
isq
mri
bac
cab
10
ab
bc
cd
cd
cd
cd
dc
dc
dc
duck

Output:
(not possible output)
(possible)

1
2
abcd
dcba

Output:
(possible)