IIUM Code Jam 2015 Problem’s Solution ?>

IIUM Code Jam 2015 Problem’s Solution

Assalamualaikum everyone. In this post I’ll discuss on the problem given in IIUM Code Jam 2015. I’ve uploaded the dataset, which is basically the questions along with the hidden input/output and sample solutions.

IIUM Code Jam 2015 Dataset

In this competition, what we try to do is to make the question as trick-less as possible. Or in another word, we want to make the question in a way that it do not require heavy knowledge of programming, while at the same time, it require some hard work. It turns out, that is quite hard to do as a more complex question would require programming skills, and if we make the question too easy, the only thing it will test is your programming skill.

For example, If we do some math questions that involve decimal numbers, we would have problem with accuracy and therefore we need to tell the teams to output up to some certain decimal point, which require some knowledge of DecimalFormat in java or the iomanip library in C++. Plus, because this is the first IIUM Code Jam ever, we don’t know what level of skill the teams will have. What if we found some genius first year? We don’t want to bore them. So in the end, we just use some common sense and make some questions.

Another issues that came up is the bonus question. The bonus question is originally question D. However, I think that question A,B,C and D is just too easy. Bare in mind, my definition of ‘easy’ may not be the same as you guys. And we don’t know who are ‘you guys’ at that time. So question D was replaced with a harder BFS(Breadth First Search) problem, because a BFS and DFS(Depth First Search) are very common graph algorithm. You guys should already learn in in DSA (Data Structure and Algorithm) class.

Anyway, lets get started with our problem analysis with the first problem, A. Students.

A. Students

The idea of this question is that, it must be the easiest problem. And we don’t want to put an A+B problem because that is just too… lame. So we make an summation problem instead. Those of you who have problem with this question usually make the mistake of not outputting the result EXACTLY. And some of you make a mistake where you did not reset the summation between test cases. These are my solution, in C++ and Java.

C++ Code:

#include<bits/stdc++.h>
using namespace std;

// Solve it
int solve(){

    // Get the number of number
    int C;
    cin >> C;

    // Initialize a variable as holder
    int sum = 0;

    // Loop C times
    for(int i=0;i<C;i++){

        // Get the number
        int cur;
        cin >> cur;

        // Add it to sum
        sum += cur;
    }

    // Return the answer
    return sum;
}

int main(int argv, char** argc){

    int t;
    cin >> t;

    // Loop through test case
    for(int i=0;i<t;i++){
        cout << "Case " << i+1 << ": " << solve() << endl;
    }

    return 0;
}

Java Code:

import java.io.PrintStream;
import java.util.*;

public class Main{
    static Scanner in;
    static PrintStream out;

    public static int solve(){
        // Get the number of number
        int C = in.nextInt();

        // Initialize a variable as holder
        int sum = 0;

        // Loop C times
        for(int i=0;i<C;i++){

            // Get the number
            int cur = in.nextInt();

            // Add it to sum
            sum += cur;
        }

        // Return the answer
        return sum;
    }

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        // Loop through test case
        int t=in.nextInt();
        for(int i=0;i<t;i++){
            out.println("Case "+(i+1)+": "+solve());
        }
    }
}

B. Black and White

Black and White is a potentially easier problem. The actual task in this question is for you to analyse the problem and come up with a solution, which is actually very simple. All you need to do is to modulo the input by 3 and based on the result, print “White”, “Black” or “Gray”. Some of the group did the algorithm correctly, however did not output the answer EXACTLY. Some groups misspell “Gray” with “Grey” and some other forgot to put each test case answer it its own line. If you are not sure of how the output will be, write the sample input in a file, save it, then use the “test” button in PC2 to see what output the judge will see.

Solution in C++

#include<bits/stdc++.h>
using namespace std;

int main(int argv, char** argc){

    // Initialize the number of test case
    int t;
    cin >> t;

    // Loop t times
    for(int i=0;i<t;i++){

        // Input the number
        int num;
        cin >> num;

        // Print part of the answer
        cout << "Case " << i+1 << ":";

        // Switch based on num modulo 3
        // Which then print the colour
        switch(num%3){
            case 0:
                cout <<" Gray";
                break;
            case 1:
                cout <<" Black";
                break;
            case 2:
                cout <<" White";
                break;
        }

        // Output newline
        cout << endl;
    }

    return 0;
}

Solution in Java

import java.io.PrintStream;
import java.util.*;

public class Main{
    static Scanner in;
    static PrintStream out;

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        // Initialize the number of test case
        int t = in.nextInt();

        // Loop t times
        for(int i=0;i<t;i++){

            // Input the number
            int num = in.nextInt();

            // Print part of the answer
            out.print("Case " + (i+1) + ":");

            // Switch based on num modulo 3
            // Which then print the colour
            switch(num%3){
                case 0:
                    out.print(" Gray");
                    break;
                case 1:
                    out.print(" Black");
                    break;
                case 2:
                    out.print(" White");
                    break;
            }

            // Output newline
            out.println();
        }

    }
}

C. The Compounder

The Compounder is the third question. Basically, if the letter under the number is ‘X’, then add that number to a counter multiplied by 50. The mistake that most of you did is you input the first string as an integer. In the problem statement, it has been specified that the length of the string can be up to 10^5. If we convert that to binary number, that could require 33219 bit. And most processor nowadays can handle up to 64 bit. In short, input the first string as a string. And then get each character separately, then determine the number. Still, in the end, 8 teams manage to get this right.

C++ Solution

#include<bits/stdc++.h>
using namespace std;

// This function will solve it
int solve(){

    // Get the two string
    string s1,s2;
    cin >> s1 >> s2;

    // A temporary variable for total
    int total = 0;

    // Loop s1 size time
    for(int i=0;i<s1.size();i++){

        // If s2 is active
        if(s2[i] == 'X'){

            // Total add the number.
            // The -'0' part will convert the character to number
            total += s1[i]-'0';
        }
    }

    // Return the total multiplied by 50
    return total*50;
}

int main(int argv, char** argc){

    // Input the number
    int t;
    cin >> t;

    // Loop t times
    for(int i=0;i<t;i++){
        cout << "RM " << solve() << endl;
    }

    return 0;
}

Java Solution

import java.io.PrintStream;
import java.util.*;

public class Main{
    static Scanner in;
    static PrintStream out;

    public static int solve(){

        // Get the two string
        String s1 = in.next(),s2 = in.next();

        // A temporary variable for total
        int total = 0;

        // Loop s1 size time
        for(int i=0;i<s1.length();i++){

            // If s2 is active
            if(s2.charAt(i) == 'X'){

                // Total add the number.
                // The -'0' part will convert the character to number
                total += s1.charAt(i)-'0';
            }
        }

        // Return the total multiplied by 50
        return total*50;
    }

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        int t=in.nextInt();
        for(int i=0;i<t;i++){
            out.println("RM " + solve());
        }
    }
}

D2. Square Tac Toe (The bonus question)

This is originally the D question before it was replaced with a harder question. However, it was given too late, and no team answer it. Still, I’ll discuss it here. The goal of Square Tac Toe is to detect a 2×2 pattern in the grid. To do that, we can just go to each cell of the grid, then check the right, bottom and right bottom cell if it has the same character.

C++ Solution

#include<bits/stdc++.h>
using namespace std;

void solve(){
    // Get the input
    int N,M;
    cin >> N >> M;

    // Get the grid
    string grid[N];
    for(int i=0;i<N;i++){
        cin >> grid[i];
    }

    // If it has dot, than it is not over yet
    bool has_dot = false;

    // Iterate through all cell
    for(int i=0;i<N;i++){
        for(int i2=0;i2<M;i2++){

            char cur = grid[i][i2];

            if(cur == '.'){
                has_dot = true;
            }else if(i < N-1 && i2 < M-1){ // If it is not the last row or column

                if(cur == 'X'){ // If it is X and also X in a square
                    if(grid[i][i2+1] == cur && grid[i+1][i2+1] == cur && grid[i+1][i2] == cur){
                        // Print Ahmad and return
                        cout << "Ahmad";
                        return;
                    }
                }else if(cur == 'O'){ // If it is O and also O in a square
                    if(grid[i][i2+1] == cur && grid[i+1][i2+1] == cur && grid[i+1][i2] == cur){
                        // Print Ali and return
                        cout << "Ali";
                        return;
                    }
                }

            }    

        }
    }

    // If no 2x2 square is found
    if(has_dot){
        cout << "Not over yet";
    }else{
        cout << "Draw";
    }

}

int main(int argv, char** argc){

    // Get the number of test case and loop it
    int t;
    cin >> t;
    for(int i=0;i<t;i++){
        cout << "Case " << i+1 << ": " ;
        solve();
        cout << endl;
    }

    return 0;
}

Java Solution

import java.io.PrintStream;
import java.util.*;

public class Main{
    static Scanner in;
    static PrintStream out;

    public static void solve(){

        // Get the input
        int N = in.nextInt(),M = in.nextInt();

        // Get the grid
        String grid[] = new String[N];
        for(int i=0;i<N;i++){
            grid[i] = in.next();
        }

        // If it has dot, than it is not over yet
        Boolean has_dot = false;

        // Iterate through all cell
        for(int i=0;i<N;i++){
            for(int i2=0;i2<M;i2++){

                char cur = grid[i].charAt(i2);

                if(cur == '.'){
                    has_dot = true;
                }else if(i < N-1 && i2 < M-1){ // If it is not the last row or column

                    if(cur == 'X'){ // If it is X and also X in a square
                        if(grid[i].charAt(i2+1) == cur && grid[i+1].charAt(i2+1) == cur && grid[i+1].charAt(i2) == cur){
                            // Print Ahmad and return
                            out.print("Ahmad");
                            return;
                        }
                    }else if(cur == 'O'){ // If it is O and also O in a square
                        if(grid[i].charAt(i2+1) == cur && grid[i+1].charAt(i2+1) == cur && grid[i+1].charAt(i2) == cur){
                            // Print Ali and return
                            out.print("Ali");
                            return;
                        }
                    }

                }    

            }
        }

        // If no 2x2 square is found
        if(has_dot){
            out.print("Not over yet");
        }else{
            out.print("Draw");
        }

    }

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        // Get the number of test case and loop it
        int t=in.nextInt();
        for(int i=0;i<t;i++){
            out.print("Case " +(i+1)+": ");
            solve();
            out.println();
        }
    }
}

D. The Walk

I admit, on second look, this is way too hard. Its not that BFS itself is a hard algorithm. Its that modeling the grid as a graph and then running BFS. That need some programming skill. Still, this is a common algorithm. And other judge says “Yes its hard, but put it because its a nice problem”. So its here.

C++ Solution

#include<bits/stdc++.h>
using namespace std;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int solve(){

    // Input R and C
    int R,C;
    cin >> R >> C;

    // Initialize array of string as the grid
    string grid[R];

    // Input the grid
    for(int i=0;i<R;i++){
        cin >> grid[i];
    }

    // A pair is a built in data structure that can store two element.
    // Useful when we want to store coordinate.

    // Start mark the start
    pair<int,int> start;

    // End mark the end
    pair<int,int> end;

    // This will store the distance of the coordinate
    int distance[R][C];

    // This will store if the coordinate have been queued
    bool queued[R][C];

    // Find the start and end
    // By going through every cell and checking for 'A' and 'B'
    //
    // Also, reset distance and queued
    for(int ir=0;ir<R;ir++){
        for(int ic=0;ic<C;ic++){

            distance[ir][ic] = 0;
            queued[ir][ic] = false;

            if(grid[ir][ic] == 'A'){
                start = make_pair(ir,ic);
            }
            if(grid[ir][ic] == 'B'){
                end = make_pair(ir,ic);
            }
        }
    }

    // Now we start the BFS algorithm

    // inque is basicaly a queue which is fundamental for the BFS algorithm
    queue<pair<int,int> > inque;

    // Now, lets mark the start of our algorithm by adding the start coordinate as the starting node.
    distance[start.first][start.second] = 0;
    queued[start.first][start.second] = true;
    inque.push(start);

    // While the queue is not empty,
    while(inque.size()){
        // Get the next item in the queue and pop it
        pair<int,int> current = inque.front(); inque.pop();

        // If the next item is the one we want to fine, return its distance
        if(current == end){
            return distance[current.first][current.second];
        }

        // For all direction, left, right, top, bottom
        for(int i=0;i<4;i++){

            // Got the next coordinate by using the current coordinate plus the delta that is hardcoded.
            pair<int,int> next = make_pair(current.first + dy[i], current.second + dx[i]);

            // If the next coordinate is out of range, continue, skipping processing
            if(next.first < 0 || next.second < 0 || next.first >= R || next.second >= C){
                continue;
            }

            // If the next coordinate is an obstacle, continue, skipping processing
            if(grid[next.first][next.second] == 'X'){
                continue;
            }

            // If the next coordinate has been queued, continue, skipping processing
            if(queued[next.first][next.second]){
                continue;
            }

            // Queue the next coordinate
            inque.push(next);
            queued[next.first][next.second] = true;

            // Here is where the magic lies.
            // We set the next coordinate's distance as the current coordinate's distance + 1
            distance[next.first][next.second] = distance[current.first][current.second]+1;
        }

    }

    // This means, we cannot reach the target
    return -1;

}

int main(int argv, char** argc){

    // Get number of test case
    int t;
    cin >> t;

    // Loop t times
    for(int i=0;i<t;i++){
        cout << "Case " << i+1 << ": " << solve() << endl;
    }

    return 0;
}

Java Solution

import java.io.PrintStream;
import java.util.*;

public class Main{
    static Scanner in;
    static PrintStream out;

    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};

    // Define a class to represent a coordinate
    public static class Coordinate{
        int r = 0;
        int c = 0;
        public Coordinate(){
        }
        public Coordinate(int r,int c){
            this.r = r;
            this.c = c;
        }
        public boolean equals(Coordinate c){
            return c.r == r && c.c == this.c;
        }
    }

    public static int solve(){

        // Input R and C
        int R = in.nextInt(),C = in.nextInt();

        // Initialize array of string as the grid
        String grid[] = new String[R];

        // Input the grid
        for(int i=0;i<R;i++){
            grid[i] = in.next();
        }

        // Start mark the start
        Coordinate start = new Coordinate();

        // End mark the end
        Coordinate end = new Coordinate();

        // This will store the distance of the coordinate
        int distance[][] = new int[R][];

        // This will store if the coordinate have been queued
        boolean queued[][] = new boolean[R][];

        // Java do not have a true multidimentional array.
        // It has jagged array which basically means array of array.
        for(int i=0;i<R;i++){
            distance[i] = new int[C];
            queued[i] = new boolean[C];
        }

        // Find the start and end
        // By going through every cell and checking for 'A' and 'B'
        //
        // Also, reset distance and queued
        for(int ir=0;ir<R;ir++){
            for(int ic=0;ic<C;ic++){

                distance[ir][ic] = 0;
                queued[ir][ic] = false;

                if(grid[ir].charAt(ic) == 'A'){
                    start = new Coordinate(ir,ic);
                }
                if(grid[ir].charAt(ic) == 'B'){
                    end = new Coordinate(ir,ic);
                }
            }
        }

        // Now we start the BFS algorithm

        // inque is basicaly a queue which is fundamental for the BFS algorithm
        ArrayDeque<Coordinate> inque = new ArrayDeque<>();

        // Now, lets mark the start of our algorithm by adding the start coordinate as the starting node.
        distance[start.r][start.c] = 0;
        queued[start.r][start.c] = true;
        inque.add(start);

        // While the queue is not empty,
        while(inque.size() > 0){
            // Get the next item in the queue and pop it
            Coordinate current = inque.remove();

            // If the next item is the one we want to fine, return its distance
            if(current.equals(end)){
                return distance[current.r][current.c];
            }

            // For all direction, left, right, top, bottom
            for(int i=0;i<4;i++){

                // Got the next coordinate by using the current coordinate plus the delta that is hardcoded.
                Coordinate next = new Coordinate(current.r + dy[i], current.c + dx[i]);

                // If the next coordinate is out of range, continue, skipping processing
                if(next.r < 0 || next.c < 0 || next.r >= R || next.c >= C){
                    continue;
                }

                // If the next coordinate is an obstacle, continue, skipping processing
                if(grid[next.r].charAt(next.c) == 'X'){
                    continue;
                }

                // If the next coordinate has been queued, continue, skipping processing
                if(queued[next.r][next.c]){
                    continue;
                }

                // Queue the next coordinate
                inque.push(next);
                queued[next.r][next.c] = true;

                // Here is where the magic lies.
                // We set the next coordinate's distance as the current coordinate's distance + 1
                distance[next.r][next.c] = distance[current.r][current.c]+1;
            }

        }

        // This means, we cannot reach the target
        return -1;

    }

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        int t=in.nextInt();
        for(int i=0;i<t;i++){
            out.println("Case "+(i+1)+": "+solve());
        }
    }
}

E. Learning Number

I would say that this problem is the best problem in the competition. It do not require a lot of knowledge on STL or Graph. However it need hard work to get it right correctly because it have a lot of edge cases. Remember in the last minute of the competition, we say that we will ignore the empty space? It turns out, the judge’s output also have problem with empty space. So if you do it correctly, it would be judged as incorrect, which one team did do correctly at the last minute. Still, after we change the empty space rule, it does not matter. If you print it out in a human readable way, it would be considered correct. 4 teams do manage to answer this correctly. Congratulation to them.

C++ Solution

#include<bits/stdc++.h>

using namespace std;

// Function that gave out malay name for single digit number
string number_to_string(int n){
    switch(n){
        case 1:
            return "Satu";
        case 2:
            return "Dua";
        case 3:
            return "Tiga";
        case 4:
            return "Empat";
        case 5:
            return "Lima";
        case 6:
            return "Enam";
        case 7:
            return "Tujuh";
        case 8:
            return "Lapan";
        case 9:
            return "Sembilan";
        case 0:
            return "Kosong";
    }

    // This will crash the program
    assert(false);
}

void solve(){

    // Get the number
    int num;
    cin >> num;

    // Using a stack, we will reverse the digit
    stack<int> reverser;

    // While the number is still there
    while(num){

        // Insert the least significant digit into the stack
        reverser.push(num%10);

        // Divide the number by 10, effectively shifting the digits to the right
        num/=10;
    }

    // Special case. If no digit is in the reverser, because the number is 0, output Kosong
    if(reverser.size() == 0){
        cout << "Kosong" << endl;
        return;
    }

    // ostringstream is like a cin but instead of printing directly, it print into a string.
    // We use this because we need to remove the last space.
    ostringstream oss;

    // While there is still some digit left.
    while(reverser.size()){

        if(reverser.size() == 4){
            // If no of digit is 4, then its ribu
            int num = reverser.top();reverser.pop();

            // Do nothing if digit is 0
            if(num != 0){
                if(num == 1){
                    oss << "Seribu ";
                }else{
                    oss << number_to_string(num) << " Ribu ";
                }
            }
        }else if(reverser.size() == 3){
            // If no of digit is 3, then its ratus
            int num = reverser.top();reverser.pop();

            // Do nothing if digit is 0
            if(num != 0){
                if(num == 1){
                    oss << "Seratus ";
                }else{
                    oss << number_to_string(num) << " Ratus ";
                }
            }
        }else if(reverser.size() == 2){
            // If no of digit is 2, then something complicated happen
            int num = reverser.top();reverser.pop();

            // If the number is 0, the we can just skip this
            if(num != 0){

                // If the number is greater than or equal to two, we can use the normal "Puluh" rule.
                if(num >= 2){
                    oss << number_to_string(num) << " Puluh ";
                }else{

                    // However, if not, we have to consider "Belas"
                    int num2 = reverser.top();reverser.pop();
                    if(num2 == 0){
                        oss << "Sepuluh ";
                    }else if(num2 == 1){
                        oss << "Sebelas ";
                    }else{
                        oss << number_to_string(num2) << " Belas ";
                    }

                }
            }
        }else if(reverser.size() == 1){

            // If no of digit number is 1
            // We can just output it, except the case of 0
            int num = reverser.top();reverser.pop();
            if(num != 0){
                oss << number_to_string(num) << " ";
            }

        }else{
            assert(false);
        }

    }

    // To remove the last space, we get the string from the ostringstream
    string output = oss.str();

    // Then we get the substring but reduce the size by one
    output = output.substr(0,output.size()-1);

    // Print it
    cout << output << endl;

}

int main(int argv, char** argc){

    // Get the number of test case
    int t;
    cin >> t;

    // Loop t times
    for(int i=0;i<t;i++){
        solve();
    }

    return 0;
}

Java Solution

import java.io.PrintStream;
import java.util.*;

public class Main{
    static Scanner in;
    static PrintStream out;

    // Function that gave out malay name for single digit number
    static String number_to_string(int n){
        switch(n){
            case 1:
                return "Satu";
            case 2:
                return "Dua";
            case 3:
                return "Tiga";
            case 4:
                return "Empat";
            case 5:
                return "Lima";
            case 6:
                return "Enam";
            case 7:
                return "Tujuh";
            case 8:
                return "Lapan";
            case 9:
                return "Sembilan";
            case 0:
                return "Kosong";
        }

        // This will crash the program
        assert(false);
        return "";
    }

    static void solve(){

        // Get the number
        int the_num = in.nextInt();

        // Using a stack, we will reverse the digit
        ArrayDeque<Integer> reverser = new ArrayDeque<>();

        // While the number is still there
        while(the_num > 0){

            // Insert the least significant digit into the stack
            reverser.push(the_num%10);

            // Divide the number by 10, effectively shifting the digits to the right
            the_num/=10;
        }

        // Special case. If no digit is in the reverser, because the number is 0, output Kosong
        if(reverser.size() == 0){
            out.println("Kosong");
            return;
        }

        String result = "";

        // While there is still some digit left.
        while(reverser.size() > 0){

            if(reverser.size() == 4){
                // If no of digit is 4, then its ribu
                int num = reverser.pop();

                // Do nothing if digit is 0
                if(num != 0){
                    if(num == 1){
                        result = result + "Seribu ";
                    }else{
                        result = result + number_to_string(num) + " Ribu ";
                    }
                }
            }else if(reverser.size() == 3){
                // If no of digit is 3, then its ratus
                int num = reverser.pop();

                // Do nothing if digit is 0
                if(num != 0){
                    if(num == 1){
                        result = result + "Seratus ";
                    }else{
                        result = result + number_to_string(num) + " Ratus ";
                    }
                }
            }else if(reverser.size() == 2){
                // If no of digit is 2, then something complicated happen
                int num = reverser.pop();

                // If the number is 0, the we can just skip this
                if(num != 0){

                    // If the number is greater than or equal to two, we can use the normal "Puluh" rule.
                    if(num >= 2){
                        result = result + number_to_string(num) + " Puluh ";
                    }else{

                        // However, if not, we have to consider "Belas"
                        int num2 = reverser.pop();
                        if(num2 == 0){
                            result = result + "Sepuluh ";
                        }else if(num2 == 1){
                            result = result + "Sebelas ";
                        }else{
                            result = result + number_to_string(num2) + " Belas ";
                        }

                    }
                }
            }else if(reverser.size() == 1){

                // If no of digit number is 1
                // We can just output it, except the case of 0
                int num = reverser.pop();
                if(num != 0){
                    result = result + number_to_string(num) + " ";
                }

            }else{
                assert(false);
            }

        }

        // Then we get the substring but reduce the size by one
        result = result.substring(0,result.length()-1);

        // Print it
        out.println(result);

    }

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        int t=in.nextInt();
        for(int i=0;i<t;i++){
            solve();
        }
    }
}

F. The Troublemaker

To be frank, we don’t expect anyone to answer this. This question is a classical dynamic programming question called the 0-1 Knapsack. Google as I don’t really know how to explain it. Included here are two solution, a top bottom solution and a bottom up solution. Personally, I think the top bottom solution is easier to understand. The dynamic programming solution works in by considering several rules.

  • If the current cost is equal to the current mischief cost, then we can take the current mischief value as the answer when considering current mischief technique.
  • If the current mischief is not the first mischief being considered, we can consider the maximum value we can get when considering the previous mischief given the same amount of cost.
  • If the current mischief is not the first mischief being considered and the current cost is higher than the cost of current mischief, we can consider the value as the current mischief value plus the maximum value we can get when considering the previous mischief given the cost current cost minus the cost of current mischief.

Confused? That is why we don’t expect anyone to answer this. Still, team “Error” manage to answer this. And they have been training for some time now. So that is why they can answer it.

C++ Top Down Solution

#include<bits/stdc++.h>

using namespace std;

int e,p;
int costs[1001];
int values[1001];
int memo[1001][1001];

// Find the maximum value when considering until current_technique with only current_cost
int find_max_value(int current_technique, int current_cost){

    // If we already found the value, return it
    if(memo[current_technique][current_cost] != -1){
        return memo[current_technique][current_cost];
    }

    // We initialize the answer as 0
    int answer = 0;

    // If the current_cost is equal to the cost of the current technique,
    // Then the answer is at least the value of the current technique because he can use all his
    // energy to use current technique
    if(current_cost == costs[current_technique]){
        answer = values[current_technique];
    }

    // If the current_technique is greater than 0,
    // then he can also consider the result of previous current_technique
    if(current_technique > 0){

        // If the value when considering the previous technique on the same cost is higher, then use it.
        answer = max(answer, find_max_value(current_technique-1,current_cost));

        // This is where the magic happen
        // If the current_cost is greater then the cost of current technique,
        // we can consider the maximum value when considering the previous technique, on the cost less than the current cost
        // of current technique. Because we consider it on the cost less than the current cost, we can use the current technique, so the
        // value we get from that query, we add with the value of current technique.
        if(current_cost > costs[current_technique]){
            answer = max(answer, find_max_value(current_technique-1,current_cost-costs[current_technique]) + values[current_technique] );
        }
    }

    // memoization is important in dynamic programming approach, because this function
    // will be called with the same parameter a lot of time. Without this, it would take a very long time
    // and you will get a Time Limit Exceeded verdict.
    memo[current_technique][current_cost] = answer;

    // Return the answer
    return answer;
}

int solve(){
    // Get e and p
    cin >> e >> p;

    // Initialize and input the cost and values
    for(int i=0;i<p;i++){
        cin >> costs[i];
        cin >> values[i];
    }

    // Cleanup the memo
    for(int ip=0;ip<p;ip++){
        for(int ie=0;ie<e+1;ie++){
            memo[ip][ie] = -1;
        }
    }

    // Check the maximum one on the last p for every cost
    int max_v = 0;
    for(int ie=0;ie<e+1;ie++){
        max_v = max(max_v,find_max_value(p-1,ie));
    }

    return max_v;
}

int main(int argv, char** argc){

    int p;
    cin >> p;

    // Loop P times
    for(int i=0;i<p;i++){
        cout << "Day " << i+1 << ": " << solve() << endl;
    }

    return 0;
}

Java Top Down Solution

import java.io.PrintStream;
import java.util.*;
import static java.lang.Math.*;

public class Main2{
    static Scanner in;
    static PrintStream out;

    public static class Solution{
        int e,p;
        int costs[] = new int[1001];
        int values[] = new int[1001];
        int memo[][] = new int[1001][];

        public Solution(){
            for(int i=0;i<1001;i++){
                memo[i] = new int[1001];
            }
        }

        // Find the maximum value when considering until current_technique with only current_cost
        int find_max_value(int current_technique, int current_cost){

            // If we already found the value, return it
            if(memo[current_technique][current_cost] != -1){
                return memo[current_technique][current_cost];
            }

            // We initialize the answer as 0
            int answer = 0;

            // If the current_cost is equal to the cost of the current technique,
            // Then the answer is at least the value of the current technique because he can use all his
            // energy to use current technique
            if(current_cost == costs[current_technique]){
                answer = values[current_technique];
            }

            // If the current_technique is greater than 0,
            // then he can also consider the result of previous current_technique
            if(current_technique > 0){

                // If the value when considering the previous technique on the same cost is higher, then use it.
                answer = max(answer, find_max_value(current_technique-1,current_cost));

                // This is where the magic happen
                // If the current_cost is greater then the cost of current technique,
                // we can consider the maximum value when considering the previous technique, on the cost less than the current cost
                // of current technique. Because we consider it on the cost less than the current cost, we can use the current technique, so the
                // value we get from that query, we add with the value of current technique.
                if(current_cost > costs[current_technique]){
                    answer = max(answer, find_max_value(current_technique-1,current_cost-costs[current_technique]) + values[current_technique] );
                }
            }

            // memoization is important in dynamic programming approach, because this function
            // will be called with the same parameter a lot of time. Without this, it would take a very long time
            // and you will get a Time Limit Exceeded verdict.
            memo[current_technique][current_cost] = answer;

            // Return the answer
            return answer;
        }

        int solve(){
            // Get e and p
            e = in.nextInt();
            p = in.nextInt();

            // Initialize and input the cost and values
            for(int i=0;i<p;i++){
                costs[i] = in.nextInt();
                values[i] = in.nextInt();
            }

            // Cleanup the memo
            for(int ip=0;ip<p;ip++){
                for(int ie=0;ie<e+1;ie++){
                    memo[ip][ie] = -1;
                }
            }

            // Check the maximum one on the last p for every cost
            int max_v = 0;
            for(int ie=0;ie<e+1;ie++){
                max_v = max(max_v,find_max_value(p-1,ie));
            }

            return max_v;
        }
    }

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        Solution sol = new Solution();

        int t=in.nextInt();
        for(int i=0;i<t;i++){
            out.println("Day " + (i+1) +": " + sol.solve());
        }
    }
}

C++ Bottom Up Solution

#include<bits/stdc++.h>

using namespace std;

int solve(){
    // Get e and p
    int e,p;
    cin >> e >> p;

    // Initialize and input the cost and values
    int costs[p];
    int value[p];
    for(int i=0;i<p;i++){
        cin >> costs[i];
        cin >> value[i];
    }

    // Initialize a two dimentional array for the dynamic programming
    // Set them all to 0
    int dp[p][e+1];
    for(int ip=0;ip<p;ip++){
        for(int ie=0;ie<e+1;ie++){
            dp[ip][ie] = 0;
        }
    }

    // For all the p, which is the mischief technique
    for(int ip=0;ip<p;ip++){

        // At least on prolep ip cost ip, the value is when picking
        // ip only, which is the value of ip
        if(costs[ip] <= e)
            dp[ip][costs[ip]] = value[ip];

        // If ip is greater than 0, we can refer to the previous ip
        if(ip > 0){

            for(int ie=0;ie<e+1;ie++){

                // At any particular cost,
                // The maximum value we can get is the current value, or the current value
                // when considering the last ip
                dp[ip][ie] = max(dp[ip][ie], dp[ip-1][ie]);

                // At any particular cost greater than the current ip cost,
                // We can also consider the value of previous ip, on cost minus cost of current ip, plus the value of current ip
                if(ie >= costs[ip]){
                    dp[ip][ie] = max(dp[ip][ie], dp[ip-1][ie-costs[ip]] + value[ip]);
                }
            }
        }
    }

    // Check the maximum one on the last p
    int max_v = 0;
    for(int ie=0;ie<e+1;ie++){
        max_v = max(max_v,dp[p-1][ie]);
    }

    return max_v;
}

int main(int argv, char** argc){

    int p;
    cin >> p;

    // Loop P times
    for(int i=0;i<p;i++){
        cout << "Day " << i+1 << ": " << solve() << endl;
    }

    return 0;
}

Java Bottom Up Solution

import java.io.PrintStream;
import java.util.*;
import static java.lang.Math.*;

public class Main{
    static Scanner in;
    static PrintStream out;

    public static int solve(){

        // Get e and p
        int e = in.nextInt(),p = in.nextInt();

        // Initialize and input the cost and values
        int costs[] = new int[p];
        int value[] = new int[p];
        for(int i=0;i<p;i++){
            costs[i] = in.nextInt();
            value[i] = in.nextInt();
        }

        // Initialize a two dimentional jagged array for the dynamic programming
        // Set them all to 0
        int dp[][] = new int[p][];
        for(int ip=0;ip<p;ip++){
            dp[ip] = new int[e+1];
            for(int ie=0;ie<e+1;ie++){
                dp[ip][ie] = 0;
            }
        }

        // For all the p, which is the mischief technique
        for(int ip=0;ip<p;ip++){

            // At least on prolep ip cost ip, the value is when picking
            // ip only, which is the value of ip
            if(costs[ip] <= e)
                dp[ip][costs[ip]] = value[ip];

            // If ip is greater than 0, we can refer to the previous ip
            if(ip > 0){

                for(int ie=0;ie<e+1;ie++){

                    // At any particular cost,
                    // The maximum value we can get is the current value, or the current value
                    // when considering the last ip
                    dp[ip][ie] = max(dp[ip][ie], dp[ip-1][ie]);

                    // At any particular cost greater than the current ip cost,
                    // We can also consider the value of previous ip, on cost minus cost of current ip, plus the value of current ip
                    if(ie >= costs[ip]){
                        dp[ip][ie] = max(dp[ip][ie], dp[ip-1][ie-costs[ip]] + value[ip]);
                    }
                }
            }
        }

        // Check the maximum one on the last p
        int max_v = 0;
        for(int ie=0;ie<e+1;ie++){
            max_v = max(max_v,dp[p-1][ie]);
        }

        return max_v;
    }

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        int t=in.nextInt();
        for(int i=0;i<t;i++){
            out.println("Day " + (i+1) +": " + solve());
        }
    }
}

G. Budget Cut

You think F is hard? Come look at Budget Cut. Budget cut is basically a MST(Minimum Spanning Tree) question. It can be solved using two algorithm, the Prim’s Minimum Spanning Tree and Kruskal Minimum Spanning tree. It is probably easier to understand compared to F. However, implementing it require more skills. And if you use Kruskal’s technique, a plain DFS or BFS check for connectivity is not fast enough. My solution uses a union find structure to accelerate it, and that is the fastest solution.

C++ Prim

#include<bits/stdc++.h>

using namespace std;

/*
 * This solve uses the Prim's algorithm for finding mimimum spanning tree
 */
int solve(){

    // Input them
    int N,M,K;
    cin >> N >> M >> K;

    // A weighted graph representation that can be used like an adjacency matrix
    // but works in logarithmic time and can be iterated, so faster traversal
    // than an adjacency matrix.
    map<int,int> graph[N];

    // Store the current total distance
    int total_distance = 0;

    // Iterate through M, input the edges and at the same time, add to total distance
    for(int i=0;i<M;i++){
        int a,b,w;
        cin >> a >> b >> w;
        a--;b--;
        graph[a][b] = w;
        graph[b][a] = w;
        total_distance += w;
    }

    // Store the new distance for the MST
    int new_distance = 0;

    // Flag if the node has been added
    bool added[N];
    for(int i=0;i<N;i++){
        added[i] = false;
    }

    // Current minimum distance of the nodes with the current minimum spanning tree
    int curmin[N];
    for(int i=0;i<N;i++){
        curmin[i] = INT_MAX;
    }

    // Using a multiset as the priority queue
    // The first int is the distance, the second is the node
    multiset<pair<int,int> > queue;

    // Add the first node, which we consider the first
    queue.insert(make_pair(0,0));
    curmin[0] = -1;

    while(queue.size()){

        // Begin will get the first element which is the least element
        // and because we are using pair, the element with the least distance.
        // Get it and remove it from queue.
        pair<int,int>  cur = *queue.begin();
        queue.erase(queue.begin());

        // Get the node and distance into a variable
        int cur_node = cur.second;
        int distance = cur.first;

        // Mark it as added to the MST
        // Note that we do not actually get the MST
        // We only get the total weight of the MST
        added[cur_node] = true;

        // If this is not the first node, add the distance to the new_distance
        // Which we will use to calculate the different in distance
        if(curmin[cur_node] != -1){
            new_distance += distance;
        }

        // What this do is, it iterate through all neighboring node of cur_node
        // A bit confusing, but faster than an adjacency matrix
        for(map<int,int>::iterator it=graph[cur_node].begin(); it!=graph[cur_node].end(); it++){

            // Get the neighboaring node
            int nnode = it->first;
            // And weight
            int nweight = it->second;
            // If it has been added to the MST, ignore it
            if(added[nnode]) continue;

            // If the current minimum distance is higher that what is possible
            if(curmin[nnode] > nweight){

                // Remove the old distance from the queue
                queue.erase(make_pair(curmin[nnode],nnode));

                // Put the new distance to the queue
                // along with the current minimum
                queue.insert(make_pair(nweight,nnode));
                curmin[nnode] = nweight;
            }
        }
    }

    // After we go through the MST, we get the new distance.
    // So all we need to do is get the difference and multiply by K
    int distance_diff = total_distance-new_distance;
    return distance_diff*K;

}

int main(int argv, char** argc){
    int t;
    cin >> t;
    // Loop t times
    for(int i=0;i<t;i++){
        cout << "Case " << i+1 << ": " << solve() << endl;
    }

    return 0;
}

Java Prim

import java.io.PrintStream;
import java.util.*;

public class Main{
    static Scanner in;
    static PrintStream out;

    /*
     * This is the class we use to represent distance->node pair.
     * We need to implement comparable for the priority queue to work correctly
     * We need to override equals and hashCode to prevent bugs
     */
    static class DistanceNode implements Comparable<DistanceNode>{
        int distance;
        int node;
        public DistanceNode(int distance,int node){
            this.distance = distance;
            this.node = node;
        }

        @Override
        public int compareTo(DistanceNode node){
            if(distance < node.distance){
                return -1;
            }else if(distance > node.distance){
                return 1;
            }else{
                if(this.node < node.node){
                    return -1;
                }else if(this.node > node.node){
                    return 1;
                }else{
                    return 0;
                }
            }
        }

        @Override
        public boolean equals(Object o){
            if(super.equals(o))return true;

            if(o instanceof DistanceNode){

                if(compareTo((DistanceNode)o) == 0){
                    return true;
                }
            }

            return false;
        }

        @Override
        public int hashCode(){
            return distance+node;
        }
    }

    public static int solve(){
        // Input them
        int N = in.nextInt(),M = in.nextInt(),K = in.nextInt();

        // A weighted graph representation that can be used like an adjacency matrix
        // but works in logarithmic time and can be iterated, so faster traversal
        // than an adjacency matrix.
        // We use an ArrayList here because Java do not allow array of generic type.
        ArrayList<TreeMap<Integer,Integer> > graph = new ArrayList<TreeMap<Integer,Integer> >();
        for(int i=0;i<N;i++){
            graph.add( new TreeMap<Integer,Integer>() );
        }

        // Store the current total distance
        int total_distance = 0;

        // Iterate through M, input the edges and at the same time, add to total distance
        for(int i=0;i<M;i++){
            int a = in.nextInt(),b = in.nextInt(),w = in.nextInt();
            a--;b--;
            graph.get(a).put(b, w);
            graph.get(b).put(a, w);
            total_distance += w;
        }

        // Store the new distance for the MST
        int new_distance = 0;

        // Flag if the node has been added
        boolean added[] = new boolean[N];
        for(int i=0;i<N;i++){
            added[i] = false;
        }

        // Current minimum distance of the nodes with the current minimum spanning tree
        int curmin[] = new int[N];
        for(int i=0;i<N;i++){
            curmin[i] = Integer.MAX_VALUE;
        }

        // We have no option but to use a priority queue as java do not have a built in MultiSet implementation
        // The first int is the distance, the second is the node
        PriorityQueue<DistanceNode> queue = new PriorityQueue<DistanceNode>();

        // Add the first node, which we consider the first
        queue.add(new DistanceNode(0,0));
        curmin[0] = -1;

        while(queue.size() > 0){

            // Begin will get the first element which is the least element
            // Which is the element with the least distance.
            // Get it and remove it from queue.
            DistanceNode cur = queue.poll();

            // Get the node and distance into a variable
            int cur_node = cur.node;
            int distance = cur.distance;

            // Mark it as added to the MST
            // Note that we do not actually get the MST
            // We only get the total weight of the MST
            added[cur_node] = true;

            // If this is not the first node, add the distance to the new_distance
            // Which we will use to calculate the different in distance
            if(curmin[cur_node] != -1){
                new_distance += distance;
            }

            // What this do is, it iterate through all neighboring node of cur_node
            // We can use java's for loop for iterator to simplify this operation
            for(Map.Entry<Integer,Integer> entry:graph.get(cur_node).entrySet()){

                // Get the neighboaring node
                int nnode = entry.getKey();
                // And weight
                int nweight = entry.getValue();
                // If it has been added to the MST, ignore it
                if(added[nnode]) continue;

                // If the current minimum distance is higher that what is possible
                if(curmin[nnode] > nweight){

                    // Remove the old distance from the queue
                    queue.remove(new DistanceNode(curmin[nnode],nnode));

                    // Put the new distance to the queue
                    // along with the current minimum
                    queue.add(new DistanceNode(nweight,nnode));
                    curmin[nnode] = nweight;
                }
            }
        }

        // After we go through the MST, we get the new distance.
        // So all we need to do is get the difference and multiply by K
        int distance_diff = total_distance-new_distance;
        return distance_diff*K;

    }

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        int t=in.nextInt();
        for(int i=0;i<t;i++){
            out.println("Case "+(i+1)+": "+solve());
        }
    }
}

C++ Kruskal

#include<bits/stdc++.h>
using namespace std;

/*
 * Part of the function of the union find data structure
 * Get which group a particular node belong to
 */
int group(vector<int> &union_find, int n){

    // If belong to itself, then return itself.
    if(union_find[n] == n){
        return n;
    }

    // If not, return who it belong to, recursively
    int ans = group(union_find,union_find[n]);

    // Then assign to answer to itself,
    // This is a form of acceleration called path compression
    union_find[n] = ans;

    // Return the answer
    return ans;
}

/*
 * Part of the function of the union find data structure
 * Merge the two group that these two number belong to.
 */
int merge_group(vector<int> &union_find, int a, int b){
    int g1 = group(union_find, a);
    int g2 = group(union_find, b);
    union_find[g1] = g2;
}

/*
 * This one uses Kruskal's mimimum spanning tree algorithm with a union-find data structure
 * to accelerate the operation of finding if two node is already connected or not.
 * Kruskal MST without this acceleration will result in a Time Limit Exceeded.
 *
 * This algorithm is also, strangely faster than the Prim's one.
 */
int solve(){

    // Input the variables
    int N,M,K;
    cin >> N >> M >> K;

    // Initialize an array of edges.
    // Note that the first element in the pair is the weight,
    // because it will need to be sorted later.
    pair<int,pair<int,int> > edges[M];

    // Store the total distance of the graph
    int total_distance = 0;

    // Store the total distance of the MST
    int new_distance = 0;

    // Input the edges while adding the total_distance
    for(int i=0;i<M;i++){
        int a,b,w;
        cin >> a >> b >> w;
        a--;b--;
        edges[i] = make_pair(w,make_pair(a,b));
        total_distance += w;
    }

    // Sort the edges in ascending order
    sort(edges,edges+M);

    // Initialize the union_find data structure
    vector<int> union_find;
    for(int i=0;i<N;i++){
        union_find.push_back(i);
    }

    // For each of the edges in ascending order
    for(int i=0;i<M;i++){

        pair<int,pair<int,int> > lowest = edges[i];
        int weight = lowest.first;
        int a = lowest.second.first;
        int b = lowest.second.second;

        // If a and b do not belong to the same group, that means they are not connected.
        if(group(union_find,a) != group(union_find,b)){

            // So we assume we connect them in the MST
            new_distance += weight;

            // Which can be represented by joining the group of these two
            merge_group(union_find,a,b);
        }
    }

    // Return the different multiplied by K
    return (total_distance - new_distance)*K;

}

int main(int argv, char** argc){

    int t = 0;
    cin >> t;
    // Loop this t times and print out the result of solve.
    for(int i=0;i<t;i++){
        cout << "Case " << i+1 << ": " << solve() << endl;
    }

    return 0;
}

Java Kruskal

import java.io.PrintStream;
import java.util.*;

public class Main2{
    static Scanner in;
    static PrintStream out;

    /*
     * We create an edge class and implement Comparable so that
     * Arrays.sort sort it correctly according to weight
     */
    static class Edge implements Comparable<Edge>{
        int a;
        int b;
        int distance;
        public Edge(int a,int b,int distance){
            this.a = a;
            this.b = b;
            this.distance = distance;
        }

        @Override
        public int compareTo(Edge node){
            int wdiff = distance-node.distance;
            if(wdiff == 0){
                int adiff = a - node.a;
                if(adiff == 0){
                    int bdiff = b - node.b;
                    return bdiff;
                }
                return adiff;
            }
            return wdiff;
        }

        @Override
        public boolean equals(Object o){
            if(super.equals(o))return true;

            if(o instanceof Edge){

                if(compareTo((Edge)o) == 0){
                    return true;
                }
            }

            return false;
        }

        @Override
        public int hashCode(){
            return a+b+distance;
        }

    }

    /*
     * Union find data structure can helps to determine of
     * two item belong to the same group in a constant amortized time
     */
    static class UnionFind{
        int groups[];
        public UnionFind(int N){
            groups = new int[N];
            for(int i=0;i<N;i++){
                groups[i] = i;
            }
        }

        public int group(int item){
            int group = groups[item];
            if(group == item){
                return group;
            }
            int answer = group(group);
            groups[item] = answer;
            return answer;
        }

        public void merge_group(int a,int b){
            int g1 = group(a);
            int g2 = group(b);
            groups[g1] = groups[g2];
        }
    }

    public static int solve(){

        // Input the variables
        int N = in.nextInt(),M = in.nextInt(),K = in.nextInt();

        // Initialize an array of edges.
        Edge edges[] = new Edge[M];

        // Store the total distance of the graph
        int total_distance = 0;

        // Store the total distance of the MST
        int new_distance = 0;

        // Input the edges while adding the total_distance
        for(int i=0;i<M;i++){
            int a = in.nextInt(),b = in.nextInt(),w = in.nextInt();
            a--;b--;
            edges[i] = new Edge(a,b,w);
            total_distance += w;
        }

        // Sort the edges in ascending order
        Arrays.sort(edges);

        // Initialize the union_find data structure
        UnionFind union_find = new UnionFind(N);

        // For each of the edges in ascending order
        for(int i=0;i<M;i++){

            Edge lowest = edges[i];
            int distance = lowest.distance;
            int a = lowest.a;
            int b = lowest.b;

            // If a and b do not belong to the same group, that means they are not connected.
            if(union_find.group(a) != union_find.group(b)){

                // So we assume we connect them in the MST
                new_distance += distance;

                // Which can be represented by joining the group of these two
                union_find.merge_group(a,b);
            }
        }

        // Return the different multiplied by K
        return (total_distance - new_distance)*K;

    }

    public static void main(String[] args){
        in = new Scanner(System.in);
        out = System.out;

        int t=in.nextInt();
        for(int i=0;i<t;i++){
            out.println("Case "+(i+1)+": "+solve());
        }
    }
}

Conclusion

Overall I think the question did simulate a good programming competition for a university level. Most of you got 3 out of 7 question and that is quite good. Last year national ACM ICPC level, my team manage to get 5 out of 10 question. But our rank is 8 over 48. Quite good. Next IIUM Code Jam, we’ll try to make it more… algorithmic and less programming. Before you go, we are making a survey on IIUM Code Jam, so please spend some time filling out the survey. Your response can help us better plan the next IIUM Code Jam. Thank you for reading, Assalamualaikum.

IIUM Code Jam 2015 Survey