Dynamic Programming : ZigZag : TCCC03 Semi Final 3 level 1

December 31, 2012
	public int longestZigZag(int[] sequence){
		if(sequence.length == 1) return 1;
		int[] L = new int[sequence.length];
		int[] diff = new int[sequence.length-1];
		int maxLength = 1;
		boolean maxValue;
		
		for(int j =0; j<(sequence.length - 1);j++){
			diff[j] = sequence[j+1] - sequence[j];
		}
		if(diff[0] >= 0) maxValue = true;
		else maxValue = false;
		
		for(int j = 1; j< diff.length;j++){
			boolean curValue= maxValue;
			if(diff[j] > 0 ) curValue = true;
			else if(diff[j]<0) curValue = false;
			if(curValue != maxValue){
				maxLength++;
				maxValue = curValue;
			}
		}
		
		return maxLength+1;
	}
Advertisements

SRM 208 Div 1 : TallPeople

December 25, 2012

public int[] getPeople(String[] people) {
int[] ret = new int[2];
int R=people.length,C=people[0].split(" ").length;
int[][] arr = new int[R][C];

for(int i = 0;i<R;i++){
String[] split = people[i].split(" ");
for(int j=0;j<C;j++){
arr[i][j] = Integer.parseInt(split[j]);
}
}

int maxMinRow = Integer.MIN_VALUE;
for(int i = 0;i<R;i++){
int minRow = Integer.MAX_VALUE;
for(int j=0;j<C;j++){
if(arr[i][j]< minRow)
minRow = arr[i][j];

}
if(maxMinRow < minRow)
maxMinRow = minRow;
}
ret[0] = maxMinRow;

int minMaxCol = Integer.MAX_VALUE;
for(int i = 0;i<C;i++){
int maxCol = Integer.MIN_VALUE;
for(int j=0;j<R;j++){
if(arr[j][i]> maxCol)
maxCol = arr[j][i];

}
if(minMaxCol > maxCol)
minMaxCol = maxCol;
}
ret[1] = minMaxCol;

return ret;
}


SRM 236 Div 1 : BusinessTasks

December 25, 2012

Hello Competitive Programming ! My first entry into topcoder :

SRM236 Div 1 : BusinessTasks


public class BusinessTasks
{
public String getTask(String[] list, int n)
{
List<String> myList = new ArrayList<String>();
for(int i=0;i<list.length;i++) {
myList.add(list[i]);
}
int pos = 0;
while (myList.size() > 1) {
pos = (pos + n - 1)%myList.size();
myList.remove(pos);
pos = pos % myList.size();
}
return myList.get(0);
}
}

Related Links :

  1. Josephus problem
  2. A variant of this also appeared in Amazon interviews