IIUM Code Jam 2016 Mock Contest Answer ?>

IIUM Code Jam 2016 Mock Contest Answer

Assalamualaikum guys. In this post I’ll discuss on the problem given in IIUM Code Jam 2016 Mock Contest. The questions in the mock contest is meant to be educational. Therefore, the harder question mainly have some ‘tricks’ and ‘quirks’ which are common on an actual ACM-ICPC competition. The question also have explanation or hint on how to solve the problems. Four of the question are made by me (Ashraf) and the last one is made by Bro. Amjad. You can download the dataset through the link below. The dataset uses the Polygon contest format, which is used in Codeforces and is compatible with our contest system.

IIUM Code Jam 2016 Mock Contest Dataset
PDF

Another thing, during the actual contest, a bug in the scoring module was uncovered where it was counting unnecessary wrong attempt. Therefore the previous ranking of the mock contest is invalid. The following is the updated ranking with the bug fixed.

result-update

Now, on to the solutions!

A. A plus B multiply C

This question is meant to show the basic mechanism of this contest. The participant needs to be able to input three integer, and output the result of the equation. The solution is also given in the problem statement. One issue we saw in the contest is that, some team try to make sure the addition is run before the multiplication, which would be incorrect. In math and programming, multiplication take precedence over addition. Even the solution in the problem statement clearly specify the bracket for the multiplication, even though it would still be correct without it.

C++ Solution:

#include<bits/stdc++.h>

using namespace std;

int main(){
    // Input it
    int A,B,C;
    cin >> A >> B >> C;

    // Output and doing the calculation at the same time
    cout << A + B * C << endl;
}

Java Solution:

import java.util.*;

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

        // Input it
        int A = in.nextInt(), B = in.nextInt(), C = in.nextInt();

        // Output and doing the calculation at the same time
        System.out.println(A+B*C);
    }
}

B. Sum N numbers.

The Sum N numbers question is designed to show a very common pattern in most problems where you need to input variable numbers of input. Usually the number of input is specified before the actual input, but sometimes the input ends with a marker.

C++ Solution:

#include<bits/stdc++.h>

using namespace std;

int main(){

    // First, input the number of input
    int N;
    cin >> N;

    // Where we will store the sum
    int sum = 0;

    // Make a loop for each input
    for(int i=0;i<N;i++){

        // Input each number and add it to the sum
        int d;
        cin >> d;
        sum = sum + d;
    }

    // Output the sum
    cout << sum;
}

Java Solution:

import java.util.*;

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

        // First, input the number of input
        int N = in.nextInt();

        // Where we will store the sum
        int sum = 0;

        // Make a loop for each input
        for(int i=0;i<N;i++){

            // Input each number and add it to the sum
            int d = in.nextInt();
            sum = sum + d;
        }

        // Output the sum
        System.out.println(sum);
    }
}

C. Big Number

The Big Number problem demonstrate a common mistake in competitive programming which is integer overflow. This mistake is commonly made even by seasoned participant. You are given a single integer, and you need to determine if the integer fell within the range that can be represented by a 32 bit signed integer. To make it even harder, the integers is represented by N factors. That means, to get the actual integer, you need to multiply N number. The number of factors can go up to 1000 and each factor’s absolute value can go up to 1000. That means, the range of the input number is about 1000 to the power of 1000, which is huge, even for 64 bit number. This is demonstrated with the third test case, where the number is 512 to the power of 8, which is about 2 to the power of 72. If the participant uses long long int, the participant would discover that when they multiply the numbers, the result would be 0. This is because, the result is a power of 2 which only have a single on bit. As it is multiplied by another power of 2 number, the single on bit moves further to the right, until it overflow and lost, resulting in a number with has no on bit, which is 0.

However, this problem can still be solved using 64 bit integer, by checking in each multiplication loop if it already overflow. Another solution would be to use Java’s BigInteger class. Some participant also uses the ‘long double’ datatype to solve this. That works, although it was not meant to be so.

C++ Solution:

#include<bits/stdc++.h>

using namespace std;

int main(){
    // How many factor
    int N;
    cin >> N;

    // Current will store the current number when multiplying
    // overflow is a flag that is set to true when the
    // number has been determined to overflow
    long long int current = 1;
    bool overflow = false;

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

        // Input and multiply the current number
        int d;
        cin >> d;
        current = current * d;

        // Check for overflow
        if(current > INT_MAX || current < INT_MIN){
            overflow = true;

            // We don't need to continue anymore as 
            // we already know it overflow
            break;
        }
    }

    // Print the result
    if(overflow){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
}

Java Solution with BigInteger:

import java.util.*;
import java.math.*;

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

        // How many factor
        int N = in.nextInt();

        // actual will store the actual number
        BigInteger actual = BigInteger.ONE;

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

            // Input and multiply the current number
            BigInteger d = in.nextBigInteger();
            actual = actual.multiply(d);
        }

        // This is how to compare BigIntegers
        // We determine if it is higher or lower than the range
        boolean higher = actual.compareTo(BigInteger.valueOf(Integer.MAX_VALUE)) > 0;
        boolean lower = actual.compareTo(BigInteger.valueOf(Integer.MIN_VALUE)) < 0;

        // Print the result
        if(higher || lower){
            System.out.println("No");
        }else{
            System.out.println("Yes");
        }
    }
}

D. Speed Lookup

This question introduce the participant with the concept of Time Limit Exceeded. It also introduce the use of container class such as the TreeMap. The solution is quite simple. The solution needs to input the N number into a suitable container class such as a set or map, and then for each M query, check if the string exist in the container class.

C++ Solution:

#include<bits/stdc++.h>

using namespace std;

int main(){

    // First, input N
    int N;
    cin >> N;

    // The container class
    // A map of bool will also work
    set<string> words;

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

        // Input the word and add it to the set
        string word;
        cin >> word;
        words.insert(word);
    }

    // Then, input M
    int M;
    cin >> M;

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

        // Input the query
        string query;
        cin >> query;

        // This is how to check if it is in the set
        if(words.find(query) != words.end()){
            cout << "In" << endl;
        }else{
            cout << "Out" << endl;
        }
    }
}

Java Solution:

import java.util.*;
import java.math.*;

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

        // First, input N
        int N = in.nextInt();

        // The container class
        // A HashSet will also work
        TreeSet<String> words = new TreeSet<String>();

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

            // Input the word and add it to the set
            String word = in.next();
            words.add(word);
        }

        // Then, input M
        int M = in.nextInt();

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

            // Input the query
            String query = in.next();

            // This is how to check if it is in the set
            if(words.contains(query)){
                System.out.println("In");
            }else{
                System.out.println("Out");
            }
        }
    }
}

E. Easy Mod Pow

Easy Mod Pow was originally made for the actual contest. It was put into the Mock Contest because it’s difficulty really depends if the contestant know the existence of the modPow function in Java’s BigInteger class. In the end, we put it here to show the participant that some obscure built in function can be very helpful in competitive programming competition. Without the built in function, the participant can also implement the function which is not extremely hard. The function works by exploiting the fact that [math]a^{b+c}[/math] is equal to [math]{a^b} \times {a^c}[/math]. If [math] b == c [/math], then we only need to calculate [math]a^b[/math] once, and then we already know [math]a^c[/math], so on that point, we reduced the time to calculate [math]a^{b+c}[/math] by half. Repeatedly reducing it on each step with recursion result in a [math]log_{2}n[/math] complexity.

C++ Solution:

#include<bits/stdc++.h>

using namespace std;

// First define the MOD, to make it cleaner
#define MOD 1000007

// Custom recursive modPow implementation.
int modPow(int base, int power){

    // Base case
    if(power == 0) return 1;
    if(power == 1) return base;

    // Calculate halfway
    long long int half = modPow(base, power/2);

    // Multiply halfway by itself
    // use long long int here as it can overflow 
    long long int answer = half*half;

    // If power is odd, then the answer is missing
    // another multiplication as power/2 will floor
    // the power to an integer.
    if(power%2 == 1){
        answer = answer * base;
    }

    // Return the answer modded with MOD
    return answer%MOD;
}

int main(){

    // How many test cases?
    int T;
    cin >> T;

    // For each test case
    for(int i=0;i<T;i++){
        // Input
        int x,n;
        cin >> x >> n;

        // Output according to the format along
        // with return value from modPow
        cout << "Case #" << i+1 << ": " << modPow(x,n) << endl;
    }
}

Java Solution:

import java.util.*;
import java.math.*;

public class Main{

    // Define the MOD. This time, as BigInteger
    static final BigInteger MOD = BigInteger.valueOf(1000007);

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

        // How many test cases?
        int T = in.nextInt();

        // For each test case
        for(int i=0;i<T;i++){

            // Input
            BigInteger x = in.nextBigInteger(), n = in.nextBigInteger();

            // Just call the function
            BigInteger answer = x.modPow(n, MOD);

            // Output according to the format along
            // with the answer
            System.out.println("Case #" + (i+1) + ": " + answer.toString());
        }
    }
}

Conclusion

Overall, the mock contest seems like a good approximation of the actual contest. Three teams answered all five questions. Almost half of the team answered 4 question, which is good. The mock contest also improve from the last IIUM Code Jam, where the mock contest back then is merely 1 hour before the actual contest. Next IIUM Code Jam, we will try to learn from this Mock Contest and perhaps find a similar balance for it’s mock contest.