# 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.

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.