AOC04 - Editorial

PROBLEM LINK:

AOC04

Author: Nagulan S

DIFFICULTY:

Easy

PREREQUISITES:

Basic observations.

PROBLEM:

It’s Chef’s first day as the Head Chef. He has N dishes in mind for his menu. Each dish weighs W[i] Kg. There are totally N burners in the kitchen and each can cook 1kg of food in 1 second. The chef now cooks each dish in different burners such that no two dishes are cooked on the same burner, and dishes cannot be moved once it is assigned to a burner. Now the chef wants to know what is the minimum time required such that all dishes are cooked.

EXPLANATION

Now we need to find the minimum time required to cook all the dishes. So it is given in the question that there are N burners and N dishes. And all the burners cook at the same speed of 1 kg of food per second. So in order to improve our efficiency, we have to cook all the dishes simultaneously in unique burners. As all the burners cook at the same speed, we can place any dish on any burner. Now assuming all the dishes are assigned to a burner and are cooking simultaneously, the time taken to cook all the dishes will be decided by the dish with maximum weight as it will take the maximum time to get cooked as compared to others. So the answer is nothing but finding the dish with the maximum weight. As 1kg of a dish can be cooked in 1 second, the minimum time taken will be the maximum weight itself.

TIME COMPLEXITY

Time complexity is O(N) per test case, as we have to traverse linearly and find the maximum weight dish.

SOLUTIONS:

Setter's Solution ( Python )
for _ in range(int(input())):
    n=int(input())
    w=[int(x) for x in input().split()]
    print(max(w))
Setter's Solution ( Java )
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{

    /*FastReader & FastWriter are used to reduce time taken to input & output. All Java coders are recommended to use this */

	static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

	float nextFloat() {
            return Float.parseFloat(next());
        }

	double nextDouble() {
            return Double.parseDouble(next());
        }
    }
	
	static class FastWriter{
	    BufferedWriter bw;
	    FastWriter(){
	        bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    }
	    void print(Object object) throws IOException{
	        bw.append(""+object);
	    }
	    void println(Object object) throws IOException{
	        print(object);
	        bw.append("\n");
	    }
	    void close() throws IOException{
	        bw.close();
	    } 
	}
	
	public static void main(String[] args) throws IOException {
		FastReader ob=new FastReader();
		FastWriter ou=new FastWriter();
		int t,i,n,max,wi;
		t=ob.nextInt();
		while(t-->0) {
			n=ob.nextInt();
			max=0;
			for(i=0;i<n;i++) {
			    wi=ob.nextInt();
			    if(wi>max)
			        max=wi;
			}
			ou.println(max);
		}
		ou.close();
	}
}

2 Likes