5
\$\begingroup\$

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.

Can someone please help me optimize this code or provide a better, less time-consuming solution?

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

            digit=in.readLine();

            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;
                int index=Integer.parseInt(in.readLine());
                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);
    }
}
\$\endgroup\$
2
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.