Google Kick Start Round A 2020 - Need Help
Difference between en1 and en2, changed 2 character(s)
Hi Guys,↵

I was trying to solve the plates problem from the last kickstart round. I tried one approach which is not failing i dont know where the mistake is. Please help me resolving this.↵

Approach :↵
1. Processing from the last stack of plates. ↵
2. In the last stack the max beauty i can get will be the K plates from that stack, so i'll copy it. At this point, if my P value is 1 to K, it is straightway the no of plates in the stack.↵
3. Now i'll come to the N-1th stack, now i'll compare with previously processed one and i'll process the different combinations of plates. Ex : If i want one plate, i can either take it from the current stack(N-1) or check the prev calculated and update the current result. This process goes on.↵
4. Step 3 will be going on till i'm on the 1st stack.↵
5. When i'm in the first stack i'll have the best beauties of picking up the (N * K) plates.↵

This is the approach i tried and it is failing. Please help me to rectify it. Thanks in advance  ↵

import java.io.BufferedReader;↵
import java.io.IOException;↵
import java.io.InputStreamReader;↵
import java.util.StringTokenizer;↵

public class Round_A_Plates {↵
    public static void main(String[] args) {↵
        FastReader reader = new FastReader();↵
        int T = Integer.parseInt(reader.nextLine());↵
        int cases = 1;↵
        while(T > 0) {↵
            String[] input = reader.nextLine().split(" ");↵
            int N = Integer.parseInt(input[0]);↵
            int K = Integer.parseInt(input[1]);↵
            int P = Integer.parseInt(input[2]);↵

            int[][] stackOfPlates = new int[N][K];↵
            for(int i = 0;i < N;i++) {↵
                input = reader.nextLine().split(" ");↵
                for (int j = 0; j < K;j++)↵
                    if(j == 0)↵
                        stackOfPlates[i][j] = Integer.parseInt(input[j]);↵
                    else↵
                        stackOfPlates[i][j] = stackOfPlates[i][j - 1] + Integer.parseInt(input[j]);↵
            }↵

            int[] prev = null;↵
            for(int i = N - 1, plates = 1;i >= 0;i--, plates++) {↵
                int[] res = new int[plates * K];↵

                if(i == N - 1) {↵
                    System.arraycopy(stackOfPlates[i], 0, res, 0, plates * K);↵
                    prev = res;↵
                }↵
                else{↵
                    for(int j = 0, k = 0;j < K;j++) {↵
                        res[j] = Math.max(stackOfPlates[i][j], prev[j]);↵
                        for(k = 0;k < prev.length;k++) {↵
                            int currentVal = stackOfPlates[i][j] + prev[k];↵
                            int total = j + k + 1;↵
                            res[total] = (total < prev.length) ? Math.max(prev[total], currentVal) : Math.max(res[total] , currentVal);↵
                        }↵
                    }↵
                    prev = res;↵
                }↵
            }↵


            System.out.println("Case #" + cases + ": " +prev[P - 1]);↵
            T--;↵
            cases++;↵
        }↵
    }↵

    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());↵
        }↵

        double nextDouble()↵
        {↵
            return Double.parseDouble(next());↵
        }↵

        String nextLine()↵
        {↵
            String str = "";↵
            try↵
            {↵
                str = br.readLine();↵
            }↵
            catch (IOException e)↵
            {↵
                e.printStackTrace();↵
            }↵
            return str;↵
        }↵
    }↵
}↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English urnothing21 2020-03-28 13:30:33 1217 Tiny change: 'of plates.\n2. In th' -> 'of plates. <br>\n2. In th'
en2 English urnothing21 2020-03-28 13:21:21 2 Tiny change: 'ach :\n1. Processin' -> 'ach :\n1. Processin'
en1 English urnothing21 2020-03-28 13:20:53 4330 Initial revision (published)