# Calculate difference of indices

The challenge is to reconstruct an n-digit number using the following information:

On each step, you choose an index x from 1 to n. For all indices y (y < x), you calculate the difference by = ax - ay.

You then calculate B1 — sum of all by which are greater than 0 and B2 — sum of all by which are less than 0.

The answer for this step is B1 - B2.

Input

The first line contains two integers n and m, denoting the number of digits and number of steps. The second line contains n digits (without spaces) a1, a2, ..., an. Each of the next m lines contains a single integer x denoting the index for the current step.

Output

For each of m steps print single number in a line - answer of the step.

import java.io.*;
import java.util.*;
public class Chefs
{
DataInputStream in;
PrintWriter out;
HashMap<Integer,Integer> mymap=new HashMap<Integer,Integer>();
int a[],n,m,b1,b2;
public Chefs()
{
in=new DataInputStream(System.in);
out=new PrintWriter(System.out,true);
calchef();
}
{
try
{
String split[]=digit.split("\\s+");
n=Integer.parseInt(split[0]);
m=Integer.parseInt(split[1]);
a=new int[n];

for(int i=0;i<digit.length();i++)
a[i]=digit.charAt(i);
}
catch(Exception e)
{
e.printStackTrace();
}
}
void calchef()
{
for(int i=0;i<m;i++)
{
try
{
b1=0;
b2=0;
if(mymap.containsKey(index))
{
int ans=mymap.get(index);
out.println(ans);
}
else
{
for(int j=0;j<index-1;j++)
{
if(a[index-1]-a[j]>0)
{
b1+=(a[index-1]-a[j]);
}
else
{
b2+=(a[index-1]-a[j]);
}
}
int ans=b1-b2;
out.println(ans);
mymap.put(index,ans);
}
}
catch(Exception e)
{
e.printStackTrace();
}
}
}
public static void main(String[] args)
{
//long startTime = System.currentTimeMillis();
Chefs c=new Chefs();
//long endTime   = System.currentTimeMillis();
//long totalTime = endTime - startTime;
//System.out.println(totalTime);
}
}


1) I would change the inner for loop this way (very little optimization, unlikely it will bring better performance)

int ans=0;
int y=index-1;
for(int j=0; j<y; j++)
{
int diff = a[y] - a[j];

if(diff > 0)
ans += diff;
else
ans -= diff;
}


2) You never store ans in the map.

• ya ya i forgot to add the updated code here,i missed that part,its added now. Apr 8, 2014 at 18:14
• even after ur code,it exceeds my 1sec time limit,cant it be further optimized Apr 8, 2014 at 18:23