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.

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

// 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 $a^{b+c}$ is equal to ${a^b} \times {a^c}$. If $b == c$, then we only need to calculate $a^b$ once, and then we already know $a^c$, so on that point, we reduced the time to calculate $a^{b+c}$ by half. Repeatedly reducing it on each step with recursion result in a $log_{2}n$ 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){
}

// Return the answer modded with 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