I am practicing for the ACM contest next month. Some of the problems are real tricky. My best record so far is a problem of 8.2 difficulty rating. But even for the comparatively simple problem, there are some elegent solutions instead of brute force.
My sample java solution for the lexicography problem
The key of this problem is an algorithm to find nth permutation
import java.util.*;
public class Lexico
{
static ArrayList<Character> info = new ArrayList<Character>();
public static void main(String[] args)
{
Scanner sc= new Scanner(System.in);
String word;
//char[] info = new char[16];
int pos;
word = sc.next();
pos = sc.nextInt();
while(!(word.equals("#") && (pos==0)))
{
char[] hold= word.toCharArray();
Arrays.sort(hold);
for (int i=0; i<word.length(); i++)
{
info.add(hold[i]);
//System.out.println("hold: "+hold[i]);
}
int div=1;
int target=pos-1;
int rem[]= new int[16];
for (int i=0; i<16; i++)
{
rem[i] = 0; //fill rem[] with 0
}
int index=0;
while(target>0)
//get grab seq
{
int a= target%div;
System.out.print(a);
rem[index]= a;
target= (int)(target/div);
div++;
index++;
}
//grab and print
char perm[] = new char[index];
for (int i= hold.length-1; i>=0; i--)
{
char get = hold[rem[i]];
for (int k= rem[i]; k< hold.length-1; k++)
{
hold[ k ] = hold [k+1];
}
//perm[i] = get;
System.out.print(get);
}
System.out.print("\n");
//finishing one answer, reset and move to next
info.clear();
word = sc.next();
pos = sc.nextInt();
}
sc.close();
}
}My sample java solution for the amalgamated problem
The input will be contants for a function. and the last input is number of auto-incremented x values.
The program is deisgned to find the largest deline of values among all points efficiently.
import java.util.*;
import java.lang.Math;
class Amalgamated
{
static ArrayList<Double> prices;
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int p, a, b, c, d, n;
p= sc.nextInt();
a= sc.nextInt();
b= sc.nextInt();
c= sc.nextInt();
d= sc.nextInt();
n= sc.nextInt();
sc.close();
prices = new ArrayList <Double>();
if((n==0)||(n==1))
{
System.out.println(""+0);
return;
}
for (int i=1; i<=n; i++)
{
double price= p*(Math.sin(a*i+b)+Math.cos(c*i+d)+2);
prices.add(price);
}
System.out.println(findDec(0, prices.size()));
}
public static double findDec(int start, int end)
{
int [] A=findMaxMin(start, end);
int maxIndex=A[0];
int minIndex=A[1];
if(maxIndex==minIndex)
{
return 0;
}
else if (maxIndex<minIndex)
{
return (prices.get(maxIndex)-prices.get(minIndex));
}
else
{
double RMax=prices.get(maxIndex);
double RMin=prices.get(findMaxMin(maxIndex, prices.size())[1]);
double RMaxDec = RMax-RMin;
//System.out.println("Rmax:"+RMax+", RMin; "+ RMin+",,RDec: "+RMaxDec);
double T= Math.max(findDec(0, maxIndex-1), RMaxDec);
//System.out.println("found");
return T;
}
}
public static int[] findMaxMin(int start, int end)
{
double max, min;
int[] indexs = new int[2];
max=0;
min=prices.get(start);
for(int index=start; index < end; index++)
{
double num = prices.get(index);
if (max<num)
{
max=num;
indexs[0]=index;
}
if (min>=num)
{
min=num;
indexs[1]=index;
}
}
//System.out.println("Max: "+max+"Min: "+min);
return indexs;
}
}