The Great Dispatch Timeout

When solving this puzzle I get error:
Timeout: the program did not provide 1 input lines in due time…

I can’t figure out why.
Here is my java code

    import javax.swing.event.AncestorEvent;
    import java.util.*;
    import java.io.*;
    import java.math.*;

    /**
     * Auto-generated code below aims at helping you parse
     * the standard input according to the problem statement.
     **/
    class Player {

        public static void main(String args[]) {
            Scanner in = new Scanner(System.in);
            int boxCount = in.nextInt();
            float [][] packages = new float [boxCount][3];
            for (int i = 0; i < boxCount; i++) {
                float weight = in.nextFloat();
                float volume = in.nextFloat();
                packages[i][0] = weight;
                packages[i][1] = volume;
                packages[i][2] = (float)i;
            }
            
            Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
            
            int [] answer = new int [boxCount];
            
            int truckNr = 0;
            for (int i = 0; i < packages.length/2; i++)
            {
            	answer[(int)packages[i][2]] = truckNr;
            	answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
            	truckNr++;
            	if(truckNr == 100)
            	truckNr = 0;
            }

            // Write an action using System.out.println()
            // To debug: System.err.println("Debug messages...");

            for (int i = 0; i < answer.length; i++)
            {
            	if(i != answer.length)
            		System.out.print(answer[i] + " ");
            	else
            		System.out.print(answer[i]);
    		}
        }
    }

You need a carriage return.

Either use : System.out.println(); after your loop
Or : System.out.print(answer[i]+"\n"); for the last item.

PS: You will need to fix your condition since your never enter your else statement.

1 Like

Ok, now it works, but I exceeded max capacity of truck. I try to remedy it with code

 class Player {
	static int truckNr = 0;
	static int functionCalls = 0;

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int boxCount = in.nextInt();
        float [][] packages = new float [boxCount][3];
        float [] truckLoad = new float [100];
        for (int i = 0; i < boxCount; i++) {
            float weight = in.nextFloat();
            float volume = in.nextFloat();
            packages[i][0] = weight;
            packages[i][1] = volume;
            packages[i][2] = (float)i;
        }
        
        Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
        
        int [] answer = new int [boxCount];
        
        for (int i = 0; i < packages.length/2; i++)
        {
        	if(checkLoad(truckLoad))
        	{
        	answer[(int)packages[i][2]] = truckNr;
        	answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
        	}
        	truckLoad[truckNr] += packages[i][1];
        	truckNr++;
        	if(truckNr == 100)
        	truckNr = 0;
        }

        // Write an action using System.out.println()
        // To debug: System.err.println("Debug messages...");

        for (int i = 0; i < answer.length; i++)
        {
        	if(i < answer.length)
        		System.out.print(answer[i] + " ");
        	else
        		System.out.print(answer[i] + "\n");
		}
        
        }
    
    static boolean checkLoad(float [] truckLoad)
    {
    	if(functionCalls>100)
    		return false;
    	else
    		functionCalls++;
    	
    	if(truckLoad[truckNr] <= 100)
    		return true;
    	else
    	{
    		truckNr++;
    		if(truckNr == 100)
            	truckNr = 0;
    		checkLoad(truckLoad);
    	}
    	return true;
    }
}

but i still get timeout error.

if(i < answer.length - 1) instead of if(i < answer.length)

Ok I fixed that, but I exceeded lcapacity of truck 0, and didn’t know why, There is a lot of 0 in output. For example 0 0 50 0 0 95 0 0 50 0 0 4 14 0 0 0 26 0 0 0 70 0 0 93 0 0 0 0 0 0 0

Fixed it. It was problem with checkLoad function. I didn’t reset variable that counts function calls if it returns true.
Now i exceedes capacity of truck 95

class Player {
	static int truckNr = 0;
	static int functionCalls = 0;
	static float [] truckLoad = new float [100];

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int boxCount = in.nextInt();
        float [][] packages = new float [boxCount][3];
        Arrays.fill(truckLoad, 0);
        for (int i = 0; i < boxCount; i++) {
            float weight = in.nextFloat();
            float volume = in.nextFloat();
            packages[i][0] = weight;
            packages[i][1] = volume;
            packages[i][2] = (float)i;
        }
        
        Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
        
        int [] answer = new int [boxCount];
        
        for (int i = 0; i < packages.length/2; i++)
        {
        	float v1 = packages[i][1];
        	float v2 = packages[packages.length - 1 - i][1];
        	if(checkLoad(v1, v2))
        	{
        	answer[(int)packages[i][2]] = truckNr;
        	answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
        	truckLoad[truckNr] += v1;
        	truckLoad[truckNr] += v2;
        	}else if(checkLoad(v1, 0))
        	{
        		answer[(int)packages[i][2]] = truckNr;
        		truckLoad[truckNr] += v1;
        		if(checkLoad(0, v2))
        		{
        			answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
                	truckLoad[truckNr] += v2;
        		}
			}
        	truckNr++;
        	if(truckNr == 100)
        	truckNr = 0;
        }

        // Write an action using System.out.println()
        // To debug: System.err.println("Debug messages...");

        for (int i = 0; i < answer.length; i++)
        {
        	if(i < answer.length - 1)
        		System.out.print(answer[i] + " ");
        	else
        		System.out.print(answer[i] + "\n");
		}
        
        }
    
    static boolean checkLoad(float volume1, float volume2)
    {
    	if(functionCalls>100)
    		return false;
    	else
    		functionCalls++;
    	
    	if(truckLoad[truckNr] + volume1 + volume2 <= 100)
    	{
    		functionCalls = 0;
    		return true;
    	}else
    	{
    		truckNr++;
    		if(truckNr == 100)
            	truckNr = 0;
    		checkLoad(volume1, volume2);
    	}
    	functionCalls = 0;
    	return true;
    }
}

I fixed truck 95 overload, but now it;s truck 0 again.

class Player {
	static int truckNr = 0;
	static int functionCalls = 0;
	static float [] truckLoad = new float [100];

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int boxCount = in.nextInt();
        float [][] packages = new float [boxCount][3];
        Arrays.fill(truckLoad, 0);
        for (int i = 0; i < boxCount; i++) {
            float weight = in.nextFloat();
            float volume = in.nextFloat();
            packages[i][0] = weight;
            packages[i][1] = volume;
            packages[i][2] = (float)i;
        }
        
        Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
        
        int [] answer = new int [boxCount];
        
        for (int i = 0; i < packages.length/2; i++)
        {
        	float v1 = packages[i][1];
        	float v2 = packages[packages.length - 1 - i][1];
        	if(checkLoad(v1, v2))
        	{
        	answer[(int)packages[i][2]] = truckNr;
        	answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
        	truckLoad[truckNr] += v1;
        	truckLoad[truckNr] += v2;
        	}else if(checkLoad(v1, 0))
        	{
        		answer[(int)packages[i][2]] = truckNr;
        		truckLoad[truckNr] += v1;
        		
        		for(int j = 0; j < 100; j++)
        		{
        			truckNr++;
        			if(truckNr >= 100)
        	        	truckNr = 0;
        			if(checkLoad(0, v2))
            		{
            			answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
                    	truckLoad[truckNr] += v2;
                    	break;
            		}
        		}
        		
			}else
			{
				for(int j = 0; j < 100; j++)
        		{
        			truckNr++;
        			if(truckNr >= 100)
        	        	truckNr = 0;
        			if(checkLoad(v1, v2))
            		{
        				answer[(int)packages[i][2]] = truckNr;
            			answer[(int)packages[packages.length - 1 - i][2]] = truckNr;
                    	truckLoad[truckNr] += v2;
                    	truckLoad[truckNr] += v1;
                    	break;
            		}
        		}
			}
        	truckNr++;
        	if(truckNr >= 100)
        	truckNr = 0;
        }

        // Write an action using System.out.println()
        // To debug: System.err.println("Debug messages...");

        for (int i = 0; i < answer.length; i++)
        {
        	if(i < answer.length - 1)
        		System.out.print(answer[i] + " ");
        	else
        		System.out.print(answer[i] + "\n");
		}
        
        }
    
    static boolean checkLoad(float volume1, float volume2)
    {
    	
    	if(truckLoad[truckNr] + volume1 + volume2 <= 100)
    		return true;
    	else
    		return false;
    }
}

I change code a little bit. I flll trucks at first empty spot and it works, but when i try to swap some packages trucks get full.

class Player {
	static int truckNr = 0;
	static float [] truckLoad = new float [100]; // volume in each truck
	static float [] truckWeight = new float [100]; // weight in each truck
	static long startTime = System.nanoTime();
	static float maxWeight = 0f;
	static float minWeight = 0f;
	static float delta = 0f;
	static int minWeightTruckNr = 0, maxWeightTruckNr = 0; 

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int boxCount = in.nextInt();
        float [][] packages = new float [boxCount][3];
        Arrays.fill(truckLoad, 0);
        for (int i = 0; i < boxCount; i++) {
            float weight = in.nextFloat();
            float volume = in.nextFloat();
            packages[i][0] = weight;
            packages[i][1] = volume;
            packages[i][2] = (float)i; //nr of package
        }
        
        Arrays.sort(packages, Comparator.comparingDouble(a -> a[0]));
        
        int [] answer = new int [boxCount]; //table with answers
        
        //initial fill
        for (int i = 0; i < packages.length; i++)
        {
        	float v1 = packages[i][1];
        	for(int j = 0; j < 101; j++)
        	{
        		if(checkLoad(truckNr, v1))
        		{
        			answer[(int)packages[i][2]] = truckNr;
        			truckLoad[truckNr] += v1; //add volume to truck
        			truckWeight[truckNr] = packages[i][0]; //add weight to truck
        			truckNr++;
            		if(truckNr == 100)
            			truckNr = 0;
        			break;
        		}
        		truckNr++;
        		if(truckNr == 100)
        			truckNr = 0;
        	}
        	
        }
        
		changeMaxMin();
        delta = maxWeight - minWeight;
        
        //loop responsible for packages swapping
        while ((System.nanoTime() - startTime) < 49900000000L) //check if time for calculation passed
        {
        	float tempMinWeightVolume = 0f, tempMaxWeightVolume = 0f; //volume of packages from min and max weight truck
        	float tempMaxWeightPackage = 0f, tempMinWeightPackage = 0f; //weight of packages from min and max weight truck
        	boolean maxVFound = false, minVFound = false;
        	int tempMinWeightTruckNr = minWeightTruckNr;
        	int tempMaxWeightTruckNr = maxWeightTruckNr;
        	int minAnswerNr = 0, maxAnswerNr = 0;
        	// find packages to swap
        	for(int i = 0; i < boxCount; i++)
        	{
        		//find package from max weight truck
        		if(!maxVFound && answer[i] == maxWeightTruckNr)
        		{
        			tempMaxWeightPackage = packages[i][0]; //get package weight
        			tempMaxWeightVolume = packages[i][1]; //get package volume
        			maxAnswerNr = (int)packages[i][2]; //get package nr
        			maxVFound = true;
        		}
        		//find package from min weight truck
        		if(!minVFound && answer[i] == minWeightTruckNr)
        		{
        			tempMinWeightPackage = packages[i][0]; //get package weight
        			tempMinWeightVolume = packages[i][1];  //get package volume
        			minAnswerNr = (int)packages[i][2]; //get package nr
        			minVFound = true;
        		}
        		//break loop if packages found
        		if(minVFound && maxVFound)
        			break;
        	}
        	
        	if(checkLoad(tempMaxWeightTruckNr, tempMinWeightVolume, tempMaxWeightVolume) &&
        			checkLoad(tempMinWeightTruckNr, tempMaxWeightVolume, tempMinWeightVolume)) //check if packages can be swapped
        	{
        		//change load of trucks
        		truckLoad[tempMaxWeightTruckNr] = truckLoad[tempMaxWeightTruckNr] + tempMinWeightVolume - tempMaxWeightVolume;
        		truckLoad[tempMinWeightTruckNr] = truckLoad[tempMinWeightTruckNr] + tempMaxWeightVolume - tempMinWeightVolume;
        		//change answer
        		answer[minAnswerNr] = tempMaxWeightTruckNr;
        		answer[maxAnswerNr] = tempMinWeightTruckNr;
        		//change weight
        		truckWeight[tempMaxWeightTruckNr] = truckWeight[tempMaxWeightTruckNr] + tempMinWeightPackage - tempMaxWeightPackage;
        		truckWeight[tempMinWeightTruckNr] = truckWeight[tempMinWeightTruckNr] + tempMaxWeightPackage - tempMinWeightPackage;
        	}
        	
        	changeMaxMin();
        	float newDelta = maxWeight - minWeight; //calculate new delta
        	if(newDelta < delta)
        	{
        		delta = newDelta;
        	}else
        	{
        		//reverse changes
        		truckLoad[tempMaxWeightTruckNr] = truckLoad[tempMaxWeightTruckNr] + tempMaxWeightVolume - tempMinWeightVolume;
        		truckLoad[tempMinWeightTruckNr] = truckLoad[tempMinWeightTruckNr] + tempMinWeightVolume - tempMaxWeightVolume;
        		answer[minAnswerNr] = tempMinWeightTruckNr;
        		answer[maxAnswerNr] = tempMaxWeightTruckNr;
        		truckWeight[tempMaxWeightTruckNr] = truckWeight[tempMaxWeightTruckNr] + tempMaxWeightPackage - tempMinWeightPackage;
        		truckWeight[tempMinWeightTruckNr] = truckWeight[tempMinWeightTruckNr] + tempMinWeightPackage - tempMaxWeightPackage;
        		changeMaxMin();
        	}
        	
        	if(delta < 20f)
        		break;
        }
        // Write an action using System.out.println()
        // To debug: System.err.println("Debug messages...");
        
        for (int i = 0; i < answer.length; i++)
        {
        	if(i < answer.length - 1)
        		System.out.print(answer[i] + " ");
        	else
        		System.out.print(answer[i] + "\n");
		}
        
        }
    
    // check if added load exceed truck's limit
    static boolean checkLoad(int truckNr, float volume1)
    {
    	
    	if(truckLoad[truckNr] + volume1 <= 100)
    		return true;
    	else
    		return false;
    }
    
    //check if swapped load exceed truck's limit
    static boolean checkLoad(int truckNr, float volume1, float volume2)
    {
    	
    	if(truckLoad[truckNr] + volume1 - volume2 <= 100)
    		return true;
    	else
    		return false;
    }

    // find max and min weight and corresponding trucks
    static void changeMaxMin()
    {
    	minWeight = truckWeight[0];
		maxWeight = truckWeight[0];
		minWeightTruckNr = 0; //nr of truck that has min weight
		maxWeightTruckNr = 0; //nr of truck that has max weight
    	for (int i = 0; i < 100; i+=2)
        {
    		if(truckWeight[i] < truckWeight[i+1])
    		{
    			if(minWeight > truckWeight[i])
            	{
            		minWeight = truckWeight[i];
            		minWeightTruckNr = i;
            	}
    			
    			if(maxWeight < truckWeight[i+1])
            	{
            		maxWeight = truckWeight[i+1];
            		maxWeightTruckNr = i + 1;
            	}
    		}else
    		{
    			if(minWeight > truckWeight[i+1])
            	{
            		minWeight = truckWeight[i+1];
            		minWeightTruckNr = i + 1;
            	}
    			
    			if(maxWeight < truckWeight[i])
            	{
            		maxWeight = truckWeight[i];
            		maxWeightTruckNr = i;
            	}
    		}
        }
    }
}