TP 1 SDA

TP1.java

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;


class Murid {
    private char spesialisasi;
    private int jumlahDitunjuk;
    private int currentRanking;
    private int previousRanking;
    private boolean sempatMeningkat;
    private String rankingDiAtas;
    private String rankingDiBawah;

    public Murid(char spesialisasi, int currentRanking, String rankingDiAtas, String rankingDiBawah) {
        this.spesialisasi = spesialisasi;
        this.currentRanking = currentRanking;
        this.previousRanking = currentRanking;
        this.rankingDiAtas = rankingDiAtas;
        this.rankingDiBawah = rankingDiBawah;
    }

    // Implementasi method getter
    public char getSpesialisasi() {
        return this.spesialisasi;
    }

    public int getJumlahDitunjuk() {
        return this.jumlahDitunjuk;
    }

    public int getCurrentRanking() {
        return this.currentRanking;
    }

    public int getPreviousRanking() {
        return this.previousRanking;
    }

    public boolean getSempatMeningkat() {
        return this.sempatMeningkat;
    }

    public String getRankingDiAtas() {
        return this.rankingDiAtas;
    }

    public String getRankingDiBawah() {
        return this.rankingDiBawah;
    }
    
    // Implementasi method setter
    public void incJumlahDitunjuk() {
        this.jumlahDitunjuk ++;
    }

    public void setCurrentRanking(int currentRanking) {
        this.currentRanking = currentRanking;
    }

    public void setPreviousRanking(int previousranking) {
        this.previousRanking = previousranking;
    }

    public void setSempatMeningkat() {
        this.sempatMeningkat = true;
    }

    public void setRankingDiAtas(String rankingDiAtas) {
        this.rankingDiAtas = rankingDiAtas;
    }

    public void setRankingDiBawah(String rankingDiBawah) {
        this.rankingDiBawah = rankingDiBawah;
    }
}

public class TP1 {
    private static InputReader in;
    private static PrintWriter out;
    private static Map<String, Murid> rankingMurid;
    private static String kodeRankingTeratas;
    private static String kodeRankingTerbawah;
    private static int jumlahBakso;
    private static int jumlahSiomay;
    private static int[][] dp;
    private static boolean[][] calculated;

    private static void ubahRanking(String kodeDitunjuk, int operasi) {
        /*
        Method ini mengubah atribut rankingDiBawah dan rankingDiAtas dari murid
        yang ditunjuk. Posisi yang ditinggalkan murid tersebut dan posisi tertinggi/terendah
        diatur juga rankingnya sehingga menjadi satu kesatuan ranking lagi.
        */

        // Case kalau jumlah murid hanya 1, tidak perlu ubah-ubah ranking
        if ((jumlahBakso + jumlahSiomay) == 1) {
            return;
        }

        Murid muridDitunjuk = rankingMurid.get(kodeDitunjuk);
        muridDitunjuk.incJumlahDitunjuk();
        if (operasi == 0) {
            // Case kalau paling bawah mau naik ke atas
            if (muridDitunjuk.getRankingDiBawah().equals("LOWEST")) {
                // Urus hubungan ranking yg ditinggalkan oleh muridDitunjuk
                String kodeMuridDiAtas = muridDitunjuk.getRankingDiAtas();
                Murid muridDiAtas = rankingMurid.get(kodeMuridDiAtas);
                muridDiAtas.setRankingDiBawah("LOWEST");
                kodeRankingTerbawah = kodeMuridDiAtas;

                // Urus hubungan muridDitunjuk dan ranking tertinggi sebelumnya
                muridDitunjuk.setRankingDiAtas("HIGHEST");
                muridDitunjuk.setRankingDiBawah(kodeRankingTeratas);
                rankingMurid.get(kodeRankingTeratas).setRankingDiAtas(kodeDitunjuk);

                // Terakhir, jadiin kodeDitunjuk kodeRankingTeratas
                kodeRankingTeratas = kodeDitunjuk;
                return;
            }

            // Case kalau udh paling atas trus mau naik ke atas lagi
            if (muridDitunjuk.getRankingDiAtas().equals("HIGHEST")) {
                return;
            }

            // Case kalau selain dua di atas
            // Urus hubungan ranking yg ditinggalkan oleh muridDitunjuk
            String kodeMuridDiAtas = muridDitunjuk.getRankingDiAtas();
            Murid muridDiAtas = rankingMurid.get(kodeMuridDiAtas);
            String kodeMuridDiBawah = muridDitunjuk.getRankingDiBawah();
            Murid muridDiBawah = rankingMurid.get(kodeMuridDiBawah);
            muridDiAtas.setRankingDiBawah(kodeMuridDiBawah);
            muridDiBawah.setRankingDiAtas(kodeMuridDiAtas);

            // Urus hubungan muridDitunjuk dan ranking tertinggi sebelumnya
            muridDitunjuk.setRankingDiAtas("HIGHEST");
            muridDitunjuk.setRankingDiBawah(kodeRankingTeratas);
            rankingMurid.get(kodeRankingTeratas).setRankingDiAtas(kodeDitunjuk);

            // Terakhir, jadiin kodeDitunjuk kodeRankingTeratas
            kodeRankingTeratas = kodeDitunjuk;
        }
        else {
            // Case kalau paling atas mau turun ke bawah
            if (muridDitunjuk.getRankingDiAtas().equals("HIGHEST")) {
                // Urus hubungan ranking yg ditinggalkan oleh muridDitunjuk
                String kodeMuridDiBawah = muridDitunjuk.getRankingDiBawah();
                Murid muridDiBawah = rankingMurid.get(kodeMuridDiBawah);
                muridDiBawah.setRankingDiAtas("HIGHEST");
                kodeRankingTeratas = kodeMuridDiBawah;

                // Urus hubungan muridDitunjuk dan ranking terendah sebelumnya
                rankingMurid.get(kodeRankingTerbawah).setRankingDiBawah(kodeDitunjuk);
                muridDitunjuk.setRankingDiBawah("LOWEST");
                muridDitunjuk.setRankingDiAtas(kodeRankingTerbawah);

                // Terakhir, jadiin kodeDitunjuk kodeRankingTerbawah
                kodeRankingTerbawah = kodeDitunjuk;
                return;
            }

            // Case kalau udh paling bawah trus mau turun ke bawah lagi
            if (muridDitunjuk.getRankingDiBawah().equals("LOWEST")) {
                return;
            }

            // Case selain dari dua di atas
            // Urus hubungan ranking yg ditinggalkan oleh muridDitunjuk
            String kodeMuridDiAtas = muridDitunjuk.getRankingDiAtas();
            Murid muridDiAtas = rankingMurid.get(kodeMuridDiAtas);
            String kodeMuridDiBawah = muridDitunjuk.getRankingDiBawah();
            Murid muridDiBawah = rankingMurid.get(kodeMuridDiBawah);
            muridDiAtas.setRankingDiBawah(kodeMuridDiBawah);
            muridDiBawah.setRankingDiAtas(kodeMuridDiAtas);

            // Urus hubungan muridDitunjuk dan ranking terendah sebelumnya
            muridDitunjuk.setRankingDiAtas(kodeRankingTerbawah);
            muridDitunjuk.setRankingDiBawah("LOWEST");
            rankingMurid.get(kodeRankingTerbawah).setRankingDiBawah(kodeDitunjuk);

            // Terakhir, jadiin kodeDitunjuk kodeRankingTerbawah
            kodeRankingTerbawah = kodeDitunjuk;
        }
    }

    private static void panutan(int q) {
        /*
        Method ini mengimplementasikan operasi Panutan dengan mencetak
        q murid dengan ranking tertinggi
        */
        int kangBaksoCounter = 0;
        int kangSiomayCounter = 0;
        String kode = kodeRankingTeratas;
        Murid muridDicetak = rankingMurid.get(kode);
        while (q != 0) {
            if (muridDicetak.getSpesialisasi() == 'B') {
                kangBaksoCounter ++;
            }
            else {
                kangSiomayCounter ++;
            }

            // Update flag
            q--;
            kode = muridDicetak.getRankingDiBawah();
            if (kode.equals("LOWEST")) {
                break;
            }
            muridDicetak = rankingMurid.get(kode);
        }
        out.println(kangBaksoCounter + " " + kangSiomayCounter);
    }

    private static void kompetitif() {
        /*
        Method ini mengimplementasikan operasi Kompetitif, yaitu
        mencetak murid-murid yang paling banyak ditunjuk
        */
        int maxDitunjuk = 0;
        String kodeTerbanyakDitunjuk = "";
        String kode = kodeRankingTeratas;
        Murid muridDitunjuk = rankingMurid.get(kode);

        // Handle case hanya 1 murid
        if ((jumlahBakso + jumlahSiomay) == 1) {
            out.println(kode);
            return;
        }

        while (true) {
            if (muridDitunjuk.getJumlahDitunjuk() > maxDitunjuk) {
                maxDitunjuk = muridDitunjuk.getJumlahDitunjuk();
                kodeTerbanyakDitunjuk = kode;
            }

            // update flag
            kode = muridDitunjuk.getRankingDiBawah();
            if (kode.equals("LOWEST")) {
                break;
            }
            muridDitunjuk = rankingMurid.get(kode);
        }
        out.println(kodeTerbanyakDitunjuk + " " + maxDitunjuk);
    }

    private static void evaluasi() {
        /*
        Method ini mengimplementasikan operasi Evaluasi dengan
        mencetak siapa saja yang tidak pernah meningkat rank-nya
        dibandingkan hari sebelumnya
        */
        boolean adaYangKenaEvaluasi = false;
        String kode = kodeRankingTeratas;
        Murid muridDitunjuk = rankingMurid.get(kode);

        // Handle case hanya 1 murid
        if ((jumlahBakso + jumlahSiomay) == 1) {
            out.println(kodeRankingTeratas);
            return;
        }

        while (true) {
            if (!muridDitunjuk.getSempatMeningkat()) {
                out.print(kode + " ");
                adaYangKenaEvaluasi = true;
            }

            // Update flag
            kode = muridDitunjuk.getRankingDiBawah();
            if (kode.equals("LOWEST")) {
                break;
            }
            muridDitunjuk = rankingMurid.get(kode);
        }
        if (!adaYangKenaEvaluasi) {
            out.println("TIDAK ADA");
            return;
        }
        out.println();
    }

    private static void duo() {
        /*
        Method ini mengimplementasikan operasi Duo dengan membuat
        dua array berbeda (tergantung spesialisasi) dan mencetak
        pasangan-pasangan yang mungkin dibuat dan yang tidak dapat
        */
        // Handle case hanya 1 murid
        if ((jumlahBakso + jumlahSiomay) == 1) {
            out.println("TIDAK DAPAT: " + kodeRankingTeratas);
            return;
        }

        String[] kangBakso = new String[jumlahBakso];
        String[] kangSiomay = new String[jumlahSiomay];
        int kangBaksoIndex = 0;
        int kangSiomayIndex = 0;

        String kode = kodeRankingTeratas;
        Murid muridDitunjuk = rankingMurid.get(kode);
        while (true) {
            if (muridDitunjuk.getSpesialisasi() == 'B') {
                kangBakso[kangBaksoIndex] = kode;
                kangBaksoIndex ++;
            }
            else {
                kangSiomay[kangSiomayIndex] = kode;
                kangSiomayIndex ++;
            }

            // Update flag
            kode = muridDitunjuk.getRankingDiBawah();
            if (kode.equals("LOWEST")) {
                break;
            }
            muridDitunjuk = rankingMurid.get(kode);
        }

        if (jumlahBakso > jumlahSiomay) {
            for (int i = 0; i < jumlahSiomay; i++) {
                out.println(kangBakso[i] + " " + kangSiomay[i]);
            }
            out.print("TIDAK DAPAT: ");
            for (int i = jumlahSiomay; i < jumlahBakso; i++) {
                out.print(kangBakso[i] + " ");
            }
            out.println();
        }
        else if (jumlahBakso == jumlahSiomay) {
            for (int i = 0; i < jumlahSiomay; i++) {
                out.println(kangBakso[i] + " " + kangSiomay[i]);
            }
        }
        else {
            for (int i = 0; i < jumlahBakso; i++) {
                out.println(kangBakso[i] + " " + kangSiomay[i]);
            }
            out.print("TIDAK DAPAT: ");
            for (int i = jumlahBakso; i < jumlahSiomay; i++) {
                out.print(kangSiomay[i] + " ");
            }
            out.println();
        }
    }

    private static int deploy(String[] arrRanking, int jumlahDeploy, int pointerKiri) {
        /*
        Method ini melakukan rekursi untuk mencari jumlah kelompok yang bisa dibuat
        dengan banyak kelompok jumlahDeploy
        */
        int jumlah = 0;
        // Base case
        // Case kalau jumlahDeploy sudah terpakai semua sedangkan belum sampai ujung
        if (jumlahDeploy == 0 && pointerKiri != arrRanking.length) {
            return 0;
        }
        
        // Case kalau jumlahDeploy sudah terpakai semua dan sudah sampai ujung juga
        if (jumlahDeploy == 0 && pointerKiri == arrRanking.length) {
            return 1;
        }

        // Case kalau pointerKiri sudah samapi ujung tetapi jumlahDeploy blm terpakai semua
        if (jumlahDeploy != 0 && pointerKiri == arrRanking.length) {
            return 0;
        }

        // Case kalau ranking terakhir tidak di-include di kelompok yang ada
        if (pointerKiri == arrRanking.length - 1) {
            return 0;
        }

        // Recursive case
        List<Integer> indexJenisSama = new ArrayList<>();
        char jenisPointerKiri = rankingMurid.get(arrRanking[pointerKiri]).getSpesialisasi();
        for (int i = pointerKiri+1; i < arrRanking.length; i++) {
            if (rankingMurid.get(arrRanking[i]).getSpesialisasi() == jenisPointerKiri) {
                indexJenisSama.add(i);
            }
        }

        for (Integer index: indexJenisSama) {
            if (calculated[jumlahDeploy-1][index]) {
                jumlah += dp[jumlahDeploy-1][index];
            }
            else {
                dp[jumlahDeploy-1][index] = deploy(arrRanking, jumlahDeploy-1, index+1);
                calculated[jumlahDeploy-1][index] = true;
                jumlah += dp[jumlahDeploy-1][index];
            }
        }
        return jumlah;
    }

    private static void deployDriver(int jumlahDeploy) {
        /*
        Method ini membuat array arrRanking berisi kodeUnik mulai dari
        ranking teratas sampai terendah, menginisiasi cache untuk dynamic
        programming, lalu memanggil method Deploy.
        */
        // Handle case hanya 1 murid
        if ((jumlahBakso + jumlahSiomay) == 1) {
            out.println("0");
            return;
        }

        String[] arrRanking = new String[jumlahBakso + jumlahSiomay];
        int arrRankingIndex = 0;
        dp = new int[jumlahDeploy + 1][jumlahBakso+jumlahSiomay];
        calculated = new boolean[jumlahDeploy + 1][jumlahBakso+jumlahSiomay];

        String kode = kodeRankingTeratas;
        Murid muridDitunjuk = rankingMurid.get(kode);
        while (true) {
            arrRanking[arrRankingIndex] = kode;

            // Update flag
            arrRankingIndex ++;
            kode = muridDitunjuk.getRankingDiBawah();
            if (kode.equals("LOWEST")) {
                break;
            }
            muridDitunjuk = rankingMurid.get(kode);
        }  
        out.println(deploy(arrRanking, jumlahDeploy, 0) % (1000000000 + 7));
    }

    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        in = new InputReader(inputStream);
        OutputStream outputStream = System.out;
        out = new PrintWriter(outputStream);

        int banyakBatch = in.nextInt();
        for (int i = 0; i < banyakBatch; i++) {
            // Definisikan di sini supaya ke-reset tiap batch
            rankingMurid = new HashMap<>();
            jumlahBakso = 0;
            jumlahSiomay = 0;

            int banyakMurid = in.nextInt();  
            String previousKodeUnik = "";
            for (int j = 0; j < banyakMurid; j++) {
                String kodeUnik = in.next();
                char spesialisasi = in.next().charAt(0);

                if (spesialisasi == 'B') {
                    jumlahBakso ++;
                }
                else {
                    jumlahSiomay ++;
                }

                // Murid pertama
                if (j == 0) {
                    rankingMurid.put(kodeUnik, new Murid(spesialisasi, j+1, "HIGHEST", ""));
                    kodeRankingTeratas = kodeUnik;
                    previousKodeUnik = kodeUnik;
                }

                // Murid terakhir
                else if (j == banyakMurid - 1) {
                    rankingMurid.put(kodeUnik, new Murid(spesialisasi, j+1, previousKodeUnik, "LOWEST"));
                    rankingMurid.get(previousKodeUnik).setRankingDiBawah(kodeUnik);
                    kodeRankingTerbawah = kodeUnik;
                }
                else {
                    rankingMurid.get(previousKodeUnik).setRankingDiBawah(kodeUnik);
                    rankingMurid.put(kodeUnik, new Murid(spesialisasi, j+1, previousKodeUnik, ""));
                    previousKodeUnik = kodeUnik;
                }
            }

            int hariPelatihan = in.nextInt();

            for (int j = 0; j < hariPelatihan; j++) {
                int jumlahPenunjukkan = in.nextInt();

                for (int k = 0; k < jumlahPenunjukkan; k++) {
                    String kodeDitunjuk = in.next();
                    int operasi = in.nextInt();
                    ubahRanking(kodeDitunjuk, operasi);
                }

                String kode = kodeRankingTeratas;
                Murid muridDicetak = rankingMurid.get(kode);
                int latestRank = 1;
                while (true) {
                    out.print(kode + " ");

                    // Case kalau muridnya hanya 1
                    if ((jumlahBakso + jumlahSiomay) == 1) {
                        break;
                    }

                    muridDicetak.setPreviousRanking(muridDicetak.getCurrentRanking());
                    muridDicetak.setCurrentRanking(latestRank);

                    if (latestRank < muridDicetak.getPreviousRanking()) {
                        muridDicetak.setSempatMeningkat();
                    }

                    // Update flag
                    latestRank++;
                    kode = muridDicetak.getRankingDiBawah();
                    if (kode.equals("LOWEST")) {
                        break;
                    }

                    muridDicetak = rankingMurid.get(kode);
                }
                out.println();
            }

            String evaluasiAkhir = in.next();
            if (evaluasiAkhir.equals("PANUTAN")) {
                int q = in.nextInt();
                panutan(q);
            }
            else if (evaluasiAkhir.equals("KOMPETITIF")) {
                kompetitif();
            }
            else if (evaluasiAkhir.equals("EVALUASI")) {
                evaluasi();
            }
            else if (evaluasiAkhir.equals("DUO")) {
                duo();
            }
            else {
                int jumlahDeploy = in.nextInt();
                deployDriver(jumlahDeploy);
            }
        }
        out.flush();
    }


    // taken from lab 3 SDA with following information
    // taken from https://codeforces.com/submissions/Petr
    // together with PrintWriter, these input-output (IO) is much faster than the usual Scanner(System.in) and System.out
    // please use these classes to avoid your fast algorithm gets Time Limit Exceeded caused by slow input-output (IO)
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
    }
}