# IIUM Code Jam 2016 Problem Solution

Assalamualaikum guys. In this post, I’ll discuss on the question given on IIUM Code Jam 2016. The commentary for the questions are from the question author (Zarir, Ayesha and Amjad) with some addition from me. Overall, compared to IIUM Code Jam 2015, the questions in IIUM Code Jam 2016 was much more balanced. There are less very easy question but there are less very hard question too. This is reflected in the ranking which shows a typical ACM-ICPC scoreboard.

Fun fact, actually we made about 11 candidate questions. It turns out, most of it is a bit too hard but none of it is hard enough for the ‘impossible’ question. So we have to make one more giveaway question and one more really hard question. From the original 11, 6 were selected for IIUM Code Jam 2016, and 1 was put in the Mock Contest. One more very easy question were made as a giveway question. Two additional candidate question for the ‘impossible’ question is created, but only one were put in IIUM Code Jam 2016. The questions were made using the excellent Polygon system. Because of this, we could have multiple test case, it integrate well with Codeforces and it integrate well with the modified CMS we use.

Of the 8 question selected, 2 was not answered. There is a total of 270 submission with 75 of them being accepted. Originally, Java solutions were compiled with gcj. But during the contest, we discover a strange behavior. So we changed to OpenJDK 7. Because of the change, we have to increase the memory limit of all problem to 4GB as the system does not work well with OpenJDK if the memory limit is not high enough. All submission was recompiled and reevaluated after the change.

You can get the dataset from the link below. Without wasting more time, lets get to the answer.

IIUM Code Jam 2016 Dataset

PDF

*Disclaimer: The commentary here was written mainly by the problem author, not me (Ashraf). I modified some for better clarification, but mostly, I really don’t know how to modify the commentary without changing too much. So… if they say something like “too easy” or “just do this”… its not me… I’m innocent. If you have any question, you can post a comment down below.*

## A. Talal Assignment – by Amjad

The problem is classified as easy problem. It was intended that all teams should solve it. However, not all teams managed to solve it. The description of the problem is self explanatory, you are required to enter a string and then loop through it making sure to convert each small letter character to uppercase letter and then make the check for these characters : ( “A”, “O”, “Y”, “E”, “U” and “I” ). If you find one of these characters, then skip them. Otherwise, add “.” character before it. One common mistake made by the contestant is not including “Y” as a vowel. The “Y” character was added specifically so that the participant read the question carefully. One of the teams also figure out a trick using Java which effectively could answer the solution without a loop. However, they did not account for an extra ‘.’ generated at the end of the string.

C++ Solution

#include <iostream> using namespace std; int main(){ // Declare the string input, and initialize an empty string to store final answer. string input, ans=""; // Take input cin >> input ; // Loop through the length of the string for(int i=0;i<input.length();i++){ // Convert small case letters to upper case letters if ( input[i] >= 'a' && input[i] <= 'z' ) input[i] -= ( 'a' - 'A'); // check for these letters, if found then skip them. if ( input[i] == 'A' || input[i] == 'O' || input[i] == 'Y' || input[i] == 'E' || input[i] == 'U' || input[i] == 'I' ) continue; // Otherwise add a '.' // and then add the letter ans+= '.'; ans+= input[i]; } // print out answer. cout << ans << endl; return 0; }

Java Solution

import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner scan = new Scanner(System.in); // Declare and enter the string String input = scan.next(); // Convert the string to uppper case // then replace these characters wtih empty string // them replace empty place with '.' String replaced = input.toUpperCase() .replace("A","") .replace("O","") .replace("Y","") .replace("E","") .replace("E","") .replace("U","") .replace("I","") .replace("","."); // output it except for the last character System.out.println(replaced.substring(0, replaced.length()-1)); } }

## B. Speed Limit – by Ayesha

This problem is just an implementation/math problem. The trick is to realize that all you need to do it put the forces equal to each other and find the formula for the speed(V). Once you find the formula, it becomes a simple programming task. However, you also need to output it up to 8 decimal point. By default, if you use C++, it will only output up to 4 decimal point. You need to use the `setprecision`

function to output it correctly. Internally, the checker check if the output is correct up to 6 decimal point. Some team also tries to use integer. The input statement clearly mention that the input is a real number, which mean you should be doing it with floating point data type.

C++ Solution

#include <iostream> #include <cmath> #include <iomanip> using namespace std; int main(){ //initialize case number int t, i = 1; cin >> t; while(t--){ double mu, r, m, g = 9.8; cin >> mu >> r >> m; //considering precision based on problem cout << fixed << setprecision(8); //calculate the maximum speed cout << sqrt(g*mu*r) << endl; } return 0; }

Java Solution

import java.io.PrintStream; import java.util.*; import java.text.DecimalFormat; public class Main{ static Scanner in; static PrintStream out; public static void main(String[] args){ in = new Scanner(System.in); out = System.out; int t = in.nextInt(); for(int i = 1 ; i <= t ; i++){ double mu = in.nextDouble(); double r = in.nextDouble(); double m = in.nextDouble(); double g = 9.8; //calculate the maximum speed double answer = Math.sqrt(g*mu*r); //considering precision based on problem System.out.println(new DecimalFormat("#0.00000000").format(answer)); } } }

## C. Talal Coins – by Amjad

The problem is classified as a medium to hard problem. In the problem, given a total sum and number of coin types. You need to find the least number of coins to construct the “sum”. if the coins given cannot construct the “sum” then print -1. At first glance, the problem looks like a greedy problem. The greedy solution would try to use the largest coin if possible at any point. Which would not work. Most of the contestants fell in this trap. Let me give an example: given a sum of 11 and 3 types of coin(2,3,5), in this example, a greedy answer would yield -1 because greedy answer would suggest that two 5s makes (5+5) 10, and then it looks at other coins and it did not find a coin of type 1 to make 11 and therefore greedy concludes by -1 which is incorrect answer. Because, you can make 11 by having (3+3+3+2) and the answer is 4 coins. The problem is actually a classical Dynamic Programming (DP) problem. There is a slight difference between DP and Greedy. In greedy problems, you would find the best choice at each point and take it (being greedy) and keep going to the next stage and again pick the best answer at the moment and keep going. In DP problems, it is very similar to Greedy, However, at each point take the best answer BASED on a previously MEMORIZED list of found answers. (DP is a brute force but in a smart way).

C++ Solution

#include <iostream> #include <algorithm> using namespace std; // Maximum number of coins #define MAX 10000 // S is total sum, and N is the number of coin types int N,S; // array to store coins int a[MAX]; // array to store the number of coins used to construct sum i int dp[MAX+1]; int main(){ // Enter N (number of coin types) and S is the total sum cin >> N >> S; // Loop to enter coins values for(int i=0;i<N;i++){ cin >> a[i]; } // Sort coins in ascending order sort(a,a+N); // initialize DP array to a fairly large number for(int i=0;i<MAX+1;i++){ dp[i] = 9999999; } // Initial State: sum 0 would equal to 0 number of coins dp[0] = 0 ; // Start at sum 1 and end at sum S for(int i=1;i<=S;i++){ // For each sum state: loop through the coins lesser than the sum for(int j=0;j<N;j++){ if ( a[j] <= i ) { // Most important line: the current sum - the coin would give us the number of coins // used to construct (sum - the coin) dp[i-a[i]] is already found answer. so just add 1 to it dp[i] = min(dp[i],dp[i-a[j]] + 1) ; } } } // if the number of coins is faily large that means it could not construct the answer and therefore printed -1 if ( dp[S] == 9999999 ){ cout << -1 << endl; return 0; } // otherwise print the number of coins to construct sum S. cout << dp[S] << endl; return 0; }

Java Solution

import java.util.*; import static java.lang.Math.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); // Enter N (number of coin types) and S is the total sum int N = in.nextInt(); int S = in.nextInt(); // Loop to enter coins values ArrayList<Integer> coins = new ArrayList<Integer>(); for(int i=0;i<N;i++){ coins.add(in.nextInt()); } // Sort coins in ascending order Collections.sort(coins); // initialize DP array up to S+1 int dp[] = new int[S+1]; // initialize DP array to a fairly large number for(int i=0;i<S+1;i++){ dp[i] = 9999999; } // Initial State: sum 0 would equal to 0 number of coins dp[0] = 0; // Start at sum 1 and end at sum S for(int i=1;i<=S;i++){ // For each sum state: loop through the coins lesser than the sum for(int coin: coins){ if(coin <= i) { // Most important line: the current (sum - the coin) would give us the number of coins // used to construct (sum - the coin). dp[i-a[i]] is already found answer. so just add 1 to it dp[i] = min(dp[i], dp[i-coin]+1); } } } if(dp[S] == 9999999){ // if the number of coins is faily large that means it could not construct the answer and therefore printed -1 System.out.println(-1); }else{ // otherwise print the number of coins to construct sum S. System.out.println(dp[S]); } } }

## D. Sleep Issue – by Ashraf

The Sleep Issue is the giveaway question which is meant so that everyone will be able to answer this question…. which everyone did. The story is inspired by me having sleep issue thinking can you guys answer the problems (instead of you guys thinking how can you answer the problem). The problem is simple. Given an integer N, print 1 to N. Its as simple as a single basic loop.

C++ Solution

#include <iostream> #include <algorithm> using namespace std; int main(){ // Input N int N; cin >> N; // Make a loop that output from 1 to N for(int i=1;i<=N;i++){ cout << i << endl; } }

Java Solution

import java.util.*; import static java.lang.Math.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); // Input N int N = in.nextInt(); // Make a loop that output from 1 to N for(int i=1;i<=N;i++){ System.out.println(i); } } }

## E. Perfect Cube – by Amjad

The problem is classified as a relatively easy problem. In the problem, given two integers A and B, determine how many perfect cubes are in between the range A and B inclusive. Perfect cube number is defined as number who is cube root is an integer. Example give: 8 is Perfect cube because the cube root of 8 is equal to 2 which integer. However, 9 is not a Perfect cube because the cube root is 2.08 which is not an integer. The approach to this problem is simple. Make a loop to find all cubes of all numbers less than (2 billion) 2000000000. Rather than finding the cube root of a number, find the cube of a number and store them in an array or vector. Alternatively, you can try to find the cube root of A and B, then subtract the cube root to find the answer. Looping from A to B and checking if each number is a cube root will result in a Time Limit Exceeded as the range between B and A is quite high. Fun fact: This problem also appeared in one of Malaysia’s National ACM-ICPC competition. So its actually a national level competition problem.

C++ Solution

#include <iostream> #include <vector> using namespace std; // vector to store all perfect cube less than 2 billion vector<int> v; // Number of test cases int T; // The given range int a,b; // These to store the indexes of the perfect cube in the vector int indexA,indexB; int main(){ // loop through the numbers from 1 to a fairly a big number for(int i=1;i<=2000000000;i++){ // each time find the cube of that number long long res = i*i*i; // check if the cube of that number is greater than 2 billion then break the loop if ( res > 2000000000 ) break; // Otherwise push the cube of that number to a vector v.push_back(res); } // Enter how many test cases cin >> T; // Counter for outputing cases int counter=0; while(T--){ // Enter range cin >> a >> b ; // loop to find the index of the first perfect cube greater than or equal to "a" for(int i=0;i<v.size();i++){ if ( a > v[v.size()-1] ){ indexA = v.size();break; } if ( v[i] >= a ) { indexA = i; break; } } // Loop to find the index of the last cube less than or equal to "b" for(int i=v.size()-1;i>=0;i--){ if ( v[i] <= b ) { indexB = i+1; break; } } // Then output the number of perfect cube in the range by substracting indexb and indexA. cout << "Case #"<< (++counter) << ": " << (indexB - indexA) << endl; } return 0; }

Java Solution

import java.util.Scanner; import java.lang.*; public class Main{ public static void main(String args[]){ Scanner scan = new Scanner(System.in); // Enter number of test cases int T = scan.nextInt(); // Counter to keep track of cases int counter=0; while(T>0){ // Enter the first boundary of the range int a = scan.nextInt(); // Enter the last boundary of the range int b = scan.nextInt(); // Find the cube root int ar = (int)Math.cbrt(a); // This is done so that it include ar if(ar*ar*ar == a){ ar = ar-1; } // We add 0.000000001 here to make sure it correctly coerce to integer int br = (int)(Math.cbrt(b)+0.0000001); // output the answer in the specified format. System.out.println("Case #" + (++counter) + ": " + (br-ar)); T--; } } }

## F. Rescue the Princess – by Zarir

Any programming contest generally have one ‘impossible’ question where we expect no one to solve it. This is that problem for this contest. One needs to know 3 different algorithms to actually able to solve this. This problem also introduces the notion of combining different algorithms and transforming the given data into a different format so that the next consecutive algorithms can work with it, finally after going through all the stages of transformation the result is produced.

Participants needed to know both basic number theory and shortest path calculation in a graph. Number theory was essential for generating the prime numbers and lastly BFS (Breadth First Search) was needed to calculate the shortest path. In short, this problem is a BFS problem (A graph problem) in which each magical brick is the node and the other magical brick that appear when the climber is at the former magical brick is the adjacent node (which require prime factorization to find).

At first, the constraint was set to only 1000 and the time limit was 2 second, then we found out that this will also except a naive O(n^2) solution (courtesy of Brother Amjad). Then we did several test to find out the desired limit which will not accept a brute force solution, it then became 40000.

Unfortunately, no one was able to solve it in time, the princess is still all alone waiting to be rescued……. or not.

C++ Solution

#include<bits/stdc++.h> using namespace std; #define MAX_Y 40100 // Store the primes vector<int> primes; // Store the prime factors of a number vector<int> primeFactors[MAX_Y]; void solve(){ // Input the start and ending point (X and Y) int X,Y; cin >> X >> Y; // Start the BFS with X as the initial state queue<int> que; que.push(X); // 9999999 means it has not been set vector<int> depth(MAX_Y, 9999999); depth[X] = 0; // Part of BFS while(que.size()){ int cur = que.front(); que.pop(); // Final state found if(cur == Y) break; // For each prime factor for(int p: primeFactors[cur]){ // Next is the next state int next = cur+p; if(next > Y) continue; if(depth[next] == 9999999){ depth[next] = depth[cur]+1; que.push(next); } } } if(depth[Y] != 9999999){ // If depth of final state has been set, then we found the number of step cout << depth[Y] << endl; }else{ // If not, final state cannot be reached cout << -1 << endl; } } int main(){ // Generating primes using sieve of eratosthenes algorithm vector<bool> sieve(MAX_Y); for(int i=2;i<MAX_Y;i++){ if(sieve[i]) continue; for(int j=i*i;j<MAX_Y;j+=i){ sieve[j] = true; } primes.push_back(i); } // Find the prime factors for each number for(int i=1;i<MAX_Y;i++){ for(int n: primes){ if(n >= i) break; if(i%n == 0) primeFactors[i].push_back(n); } } // Input number of test case int T; cin >> T; // For each test case for(int i=1;i<=T;i++){ printf("Case %d: ", i); solve(); } }

Java Solution

import java.util.*; import java.lang.*; public class Main{ static Scanner in = new Scanner(System.in); static final int MAX_Y = 40100; // Store the primes static List<Integer> primes = new ArrayList<Integer>(); // Store the prime factors of a number static List<List<Integer> > primeFactors = new ArrayList<List<Integer> >(); static void solve(){ // Input the start and ending point (X and Y) int X = in.nextInt(),Y = in.nextInt(); // Start the BFS with X as the initial state Queue<Integer> que = new LinkedList<Integer>(); que.add(X); // 9999999 means it has not been set int depth[] = new int[MAX_Y]; for(int i=0;i<MAX_Y;i++) depth[i] = 9999999; depth[X] = 0; // Part of BFS while(que.size() > 0){ int cur = que.remove(); // Final state found if(cur == Y) break; // For each prime factor for(int p: primeFactors.get(cur)){ // Next is the next state int next = cur+p; if(next > Y) continue; if(depth[next] == 9999999){ depth[next] = depth[cur]+1; que.add(next); } } } if(depth[Y] != 9999999){ // If depth of final state has been set, then we found the number of step System.out.println(depth[Y]); }else{ // If not, final state cannot be reached System.out.println(-1); } } public static void main(String args[]){ // Generating primes using sieve of eratosthenes algorithm boolean sieve[] = new boolean[MAX_Y]; Arrays.fill(sieve, false); for(int i=2;i<MAX_Y;i++){ if(sieve[i]) continue; for(int j=i*i;j<MAX_Y;j+=i){ sieve[j] = true; } primes.add(i); } // Find the prime factors for each number primeFactors.add(new ArrayList<Integer>()); // For index 0 for(int i=1;i<MAX_Y;i++){ primeFactors.add(new ArrayList<Integer>()); // For index i for(int n: primes){ if(n >= i) break; if(i%n == 0) primeFactors.get(i).add(n); } } // Input number of test case int T = in.nextInt(); // For each test case for(int i=1;i<=T;i++){ System.out.print("Case "+i+": "); solve(); } } }

## G. Oldest of them all – by Zarir

The idea of this problem came to me because of my roommate’s class assignment. He was supposed to make a calendar for event management using JavaScript and HTML. But he was having some trouble with making it interactive, he asked me If I can shed some light on that. At that moment I observed in his code that he was manually setting the date for each box, which did not seem a good idea at all.

That gave me the idea of a problem where one needs to dynamically generate the calendar of a month if they are just given a particular date of that month. At the beginning I though this might be a difficult, but after working on it a bit I figured that calculating the initial offset is all that is needed to solve the problem. At that point, to increase the difficulty a notch I changed the output format so that numbers greater than 9 must be replaced with characters (it looked better like this).

Only one team was able to solve it despite it being a relatively easy problem, I think the output format made the contestants think that this is a hard problem, there is a good lesson for you guys here, difficult output does not necessarily mean it is a hard problem, so always give it a try.

Originally this question is meant to accurately depict actual Gregorian calendar. That means, in Java you should be able to just `new GregorianCalendar(year, month-1, 1).get(Calendar.DAY_OF_WEEK)-1`

to get the offset. However, it was later discovered that the input generator for this question is faulty and can output impossible in real life input. So to solve this, you really need to use the input given instead of using built in libraries.

C++ Solution

#include<bits/stdc++.h> using namespace std; // A function to helps with greater than 9 monthDay char dayChar(int i){ if(i <= 9) return '0'+i; return (i-10)+'A'; } int main(){ // Input the number int dayOfWeek,dayOfMonth,month,year; cin >> dayOfWeek >> dayOfMonth >> month >> year; // Determine if it is a leap year bool leap = false; if(year % 4 == 0) leap = true; if(year % 100 == 0) leap = false; // Set an array of month days int month_days[] = { 31, leap ? 29 : 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; // Make it 0 based dayOfWeek -= 1; month -= 1; // Determine the day of week on the first day of the month dayOfWeek += 7*31; dayOfWeek -= (dayOfMonth-1); dayOfWeek %= 7; // Should be the first day now // Print days printf("M T W T F S S\n"); // This loop is for the first day offset for(int i=0;i<dayOfWeek;i++){ cout << " "; } // Print the day for(int i=1;i<=month_days[month];i++){ cout << dayChar(i) << " "; dayOfWeek++; if(dayOfWeek == 7){ // If the next dayOfWeek would go out of the week, // Then make a new line, reset the dayOfWeek cout << endl; dayOfWeek = 0; } } }

Java Solution

import java.util.*; import static java.lang.Math.*; public class Main{ // A function to helps with greater than 9 monthDay static char dayChar(int i){ if(i <= 9) return (char)((int)'0'+i); return (char)((i-10)+(int)'A'); } public static void main(String[] args){ Scanner in = new Scanner(System.in); // Input the number int dayOfWeek = in.nextInt(),dayOfMonth = in.nextInt(),month = in.nextInt(),year = in.nextInt(); // Still useful for number of day in a month Calendar cal = new GregorianCalendar(year, month-1, 1); // Make it 0 based dayOfWeek -= 1; month -= 1; // Determine the day of week on the first day of the month dayOfWeek += 7*31; dayOfWeek -= (dayOfMonth-1); dayOfWeek %= 7; // Should be the first day now // Print days System.out.println("M T W T F S S"); // This loop is for the first day offset for(int i=0;i<dayOfWeek;i++){ System.out.print(" "); } // Print the day for(int i=1;i<=cal.getActualMaximum(Calendar.DAY_OF_MONTH);i++){ System.out.print(dayChar(i)); System.out.print(" "); dayOfWeek++; if(dayOfWeek == 7){ // If the next dayOfWeek would go out of the week, // Then make a new line, reset the dayOfWeek System.out.println(); dayOfWeek = 0; } } } }

## H. Task management – by Ayesha

The idea behind this problem was introducing greedy problems to contestants. In this problem what you need to consider is that you have two limits, one is the budget and another one is number of tasks. Fortunately the problem’s input is already in increasing order and we need to get maximum tasks possible within the limit, you just need to add cost of tasks from the first one until the one which cross either budget or maximum number of tasks. So basically only one if condition while getting the input can help you to solve the problem.

C++ Solution

#include <iostream> using namespace std; int main(){ // get number of test case int t; cin >> t; //initialize number of test case int k = 1; while(t--){ // intialize your output as zero int n, p, q, z , outPut = 0; // get number of tasks, maximum number of tasks and budget limit cin >> n >> p >> q; while(n--){ // get tasks cin >> z; // if still didn't cross maximum tasks limit and the budget // left is less than new tasks budget, consider the task if(p && q >= z){ // maximum tasks limit minus the one you just considered --p; //maximum budget minus the budget of task q -= z; //increasing number of tasks able to do ++outPut; } } cout << "Case " << k++ << ": " << outPut << endl; } return 0; }

Java Solution

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; int t=in.nextInt(); for(int i=0;i<t;i++){ int n=in.nextInt(); int p=in.nextInt(); int q=in.nextInt(); int outPut = 0; for(int j=0 ; j<n ; j++){ // get tasks int z=in.nextInt(); // if still didn't cross maximum tasks limit and the budget // left is less than new tasks budget, consider the task if((p > 0) && (q >= z)){ // maximum tasks limit minus the one you just considered p -= 1; //maximum budget minus the budget of task q -= z; //increasing number of tasks able to do outPut += 1; } } out.println("Case "+(i+1)+": "+ outPut); } } }

**Conclusion**

Overall I think the problems are good for a university level programming competition. Maybe next time we will try a similar levels of questions. What do you guys think? Leave a comment.