Code Knights Round 3 Result and Problem Analysis ?>

Code Knights Round 3 Result and Problem Analysis

Salaam everyone,

Last Saturday night, the Code Knights Round 3 was held at 8:00 pm on 16th July and lasted for 4 hours. This time the round had 5 problems to solve and a bit tougher than the previous ones (Round 1 & Round 2).

finalScore
Congratulation to lim2481284 and all participants. Everyone managed to solve at least 1 problem

Needless to say, the participants did well.  The winner of this round is lim2481284 from uniten university who managed to solve 3 problems. Shahril from uitm managed also to solve 3 problems as well, both of them solved A, B and C. However, Shahril was not as fast as lim2481284 and therefore scored the second place. StdLn solved 2 problems, interesting enough he is the only one who solved problem E. It is also interesting to see Foinni who haven’t solved any problem before the freezing of the scoreboard, yet he managed to solve 2 problems in the last hour of the contest rendering him in the fifth place.

Dataset

PDF

Problem A. Collision Course – by Asyraf

Assume that the position of the first car is behind the second car. If not, just swap the two car. If the velocity of the first car is higher than the second car, they will collide. This works even if the value is negative.
C++ Solution

#include<iostream>
#include<vector>
#include<utility>

using namespace std;

int main(){

    int p1,v1,p2,v2;
    cin >> p1 >> v1 >> p2 >> v2;

    if(p1 > p2){
        swap(p1,p2);
        swap(v1,v2);
    }

    if(v1 > v2){
        cout << "Collision" << endl;
    }else{
        cout << "Safe" << endl;
    }

    return 0;
}

Problem B. Hexa Addition – by Amjad

The problem is to add two hexadecimal values. The way I go about it is by converting the hexadecimal values to decimal values then do normal addition then convert it back to hexadecimal. However, it is worth mentioning that I was surprised by some of the answers in Code Knights where they can have the input as hexadecimal and simply add both hexadecimal values.

C++ Solution

#include <iostream>
using namespace std;
int toInt(char x){ // this function will return the integer value of the passed character. 
    return ((x>='A' && x<='Z')?(x-'A'+10) : (x-'0'));
}
char toChar(int x){ // this function will return the character of the passed integer
    return (char)((x>9&&x<16)?(x+'A'-10):x+'0');
}
long long int findPow(int a, int b){ // find the power

    long long int total = 1 ;

    for(int i=0;i<b;i++){
        total *= a;
    }
    return total;
}
long long int toDecimal(string x){ // find the decimal value of the hexadecimal.

    long long int sum = 0 ;
    
    for(int i=x.length()-1,j=0;i>=0;i--,j++){
        sum+= toInt(x[i]) * findPow(16,j);
    }
    return sum;
}
string toHexa(long long int x){ // find the hexadecimal value of the decimal value
    string s = "" ;
    while(x>15){
        s=toChar(x%16) + s;
        x/=16;
    }
    s=toChar(x) + s;
    return s;
}
int main(){
    string tmp;
    cin >> tmp;
    long long int sum = toDecimal(tmp) ;
    cin >> tmp;
    sum+=toDecimal(tmp);
    cout << toHexa(sum) << endl;
    return 0;
}

Short C++ Solution

#include <iostream>
using namespace std;
int main(){
    long long a,b;
    cin >> hex >> a;
    cin >> hex >> b;
    cout << hex << uppercase << (a+b) << endl; 
    return 0;
}

Problem C. All About Those Primes – by Zarir

It can be done in different ways, using Java will give some advantage for this question, particularly as n is max 1000.

Using C++, we must first mark the primes in an array and then later check them one by one. As n is max 1000, we can use a naive brute force method to mark the primes, but if n is larger, let’s say 1 million or more, then we must be smarter in marking the primes. There is an algorithm known as Sieve of Eratosthenes which is used when n is larger. For this problem it’s not necessary.

Using Java it becomes very easier if we use BigInteger class, no need to generate the prime numbers, we just use the built in function isProbablePrime to check prime number.

After that we need to go through each number and check according to problem statement and print the answer.

C++ Solution

#include <bits/stdc++.h>

using namespace std;

#define MAX 1000

bool primes[MAX+5]; // Array to mark prime numbers, initially all false

int main(){
	primes[2] = true; // 2 is the only even prime
	bool isPrime;
	for(int i=3;i<=MAX;i+=2){ // We only check the odd numbers
		isPrime = true;
		for(int j=2;j<i;j++){
			if(i%j==0){ // means it is divisible by other than 1 and itself
				isPrime = false;
				break; // no need to check further, not a prime
			}
		}
		primes[i] = isPrime; // we mark it in the array for later use
	}
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		// We only check numbers greater than equal to 3
		// First check if the number itself is prime or not
		// Then check 2 postion behind and 2 position after
		// If all part is true then it has a twin
		if(i>=3 && primes[i] && (primes[i-2] || primes[i+2])){ 
			cout<<"Twin"<<endl;
		}else if(primes[i]){ // This means its a prime but has no twin
			cout<<"Lonely Prime"<<endl;
		}else{
			cout<<"Ordinary"<<endl;
		}
	}
	return 0;
}

Java Solution

import java.math.BigInteger;
import java.util.Scanner;
public class AllAboutThosePrimes {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		// We will use the BigInteger class to utilize its built in prime check function
		// No need to separately generate prime in this case
		// We will just check each number with the built in function isProbablePrime
		BigInteger num;
		for(int i=1;i<=n;i++){
			num = new BigInteger(""+i);
			if(num.isProbablePrime(100)){ // 100 means this function will return true when its 100% sure its a prime
				if((num.add(new BigInteger("2"))).isProbablePrime(100) || (num.subtract(new BigInteger("2"))).isProbablePrime(100)){
					System.out.println("Twin");
				}else{
					System.out.println("Lonely Prime");
				}
			}else{
				System.out.println("Ordinary");
			}
		}
	}
}

Problem D. I need my nap – by Ayesha

For this problem you just need to calculate gaps between appointments. It is also important to consider gaps between first appointment and 10:00 and last appointment and 18:00. For easier calculation you can multiple the hour with 60 and add it by minutes and easily do normal math operation with them and at the end just divide the whole thing by 60 to get the hour and get the mod by 60 to have minutes. For checking end of file you can different methods. For example in c++ you can use “while(scanf(“%d”, &a))” or “while(scanf(“%d”, &a) != EOF)”. In java you can use “while(in.hasNextLine())” which is a boolean function and check weather next line exists or not. For more information you can refer to Steven & Felix Halim’s Competitive Programming3, pages 17-19.

C++ Solution

#include <iostream>
#include <string>
using namespace std;

int main(){
	int n, i = 0; // initialize the counter

	while(scanf("%d", &n) == 1){ //read the input while checking if the line exists
		string s;
		int hours1 = 10 , min1 = 0, hours2, min2, maxMin = 0, keepMin = 0; //initializing the first hour at 10:00 and max nap time and start time for nap
		char ch;
		while(n--){ // read the n appointment  input lines
			cin >> hours2 >> ch >> min2; // get the starting time of the appointment
			int check = ((hours2*60)+min2) - ((hours1*60)+min1); // check the minutes difference between end of last appointment and start of this appointment
			if (check > maxMin){ // if the new gap is bigger, record the new gap and the start time of the gap in minutes  
				maxMin = check;
				keepMin = (hours1*60)+min1; // calculating the start time of the gap in minutes
			}
			cin >> hours1 >> ch >> min1; // getting the end of appointment time
			cin.ignore(); // ignore the blank space
			getline(cin, s); // getting the appointment title
		}
		hours2 = 18; // last possible time nap considers as 18:00
		min2 = 0;
		int check = ((hours2*60)+min2) - ((hours1*60)+min1); // calculating the last gap again with the 18:00
		if (check > maxMin){ // checking if the last gap is bigger than the last maximum gap we have already
			maxMin = check;
			keepMin = (hours1*60)+min1;
		}
		 // printing the output
		cout << "Day " << ++i << ": the longest nap starts at " << (keepMin/60) << ":" ;
		if((keepMin%60) < 10) // printing extra 0 for presentation of numbers last than 10 in mm format
			cout << 0;
		cout << (keepMin%60) << " and will last for " ;
		if ((maxMin/60) > 0) // checking if the nap minutes is more 60 then present in the hours and minutes format 
			cout << (maxMin/60) << " hours and ";
		cout << (maxMin%60) << " minutes." << endl;

	}
	return 0;
}

Java Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class main
{
	static Scanner in;
    static PrintStream out;
	public static void main (String[] args) throws java.lang.Exception
	{
		in = new Scanner(System.in);
       	out = System.out;
		String checkInput  = null;
		int i = 0; // initialize the counter

		while(in.hasNextLine()){ //check if the next line exists 
			checkInput = in.nextLine(); // getting the n as string 
			String s;
			char ch;
			int n = Integer.parseInt(checkInput); // convert string to integer 
			int hours1 = 10 , min1 = 0, hours2 , min2, maxMin = 0, keepMin = 0; //initializing the first hour at 10:00 and max nap time and start time for nap
			for(int k = 0 ; k < n ; k++){ // read the n appointment  input lines
				checkInput = in.nextLine();
				// get the starting time of the appointment
				hours2 = Integer.parseInt(checkInput.substring(0, 2).trim());
				min2 = Integer.parseInt(checkInput.substring(3, 5).trim());
				int check = ((hours2*60)+min2) - ((hours1*60)+min1); // check the minutes difference between end of last appointment and start of this appointment
				if (check > maxMin){ // if the new gap is bigger, record the new gap and the start time of the gap in minutes  
					maxMin = check;
					keepMin = (hours1*60)+min1; // calculating the start time of the gap in minutes
				}
				// getting the end of appointment time
				hours1 = Integer.parseInt(checkInput.substring(6, 8).trim());
				min1 = Integer.parseInt(checkInput.substring(9, 11).trim());
			}
			hours2 = 18; // last possible time nap considers as 18:00
			min2 = 0;
			int check = ((hours2*60)+min2) - ((hours1*60)+min1); // calculating the last gap again with the 18:00
			if (check > maxMin){ // checking if the last gap is bigger than the last maximum gap we have already
				maxMin = check;
				keepMin = (hours1*60)+min1;
			}
			 // printing the output
			out.print("Day " + (++i) + ": the longest nap starts at " + (keepMin/60) + ":");
			if((keepMin%60) < 10) // printing extra 0 for presentation of numbers last than 10 in mm format
				out.print(0);
			out.print( (keepMin%60) + " and will last for " );
			if ((maxMin/60) > 0) // checking if the nap minutes is more 60 then present in the hours and minutes format 
				out.print( (maxMin/60) + " hours and ");
			out.println( (maxMin%60) + " minutes.");
	
		}
	}
}

Problem E. Zrog the Frog – by Zarir

If you have solved this problem then you are at Apprentice level of learning Frog language, keep it up. It seems only one of you knew what the Frogs were saying, specially Zrog

This is an implementation heavy problem but otherwise the steps are simple.

At first, we store the predefined symbols from the problem statement into an array for checking later. Now for each line of input, we must split it using spaces and then store the parts for verification.

For example, let’s consider the following equation … X + Y = Z

The very first part after the split, we expect it to be an operand for a valid equation. In this case its (X) and it’s an operand, so it checks out. The second part must be an operator or divider for it to be correct, in this case its (+) and it’s an operator. After an operator the next must be an operand, its (Y) in this case. Now again we expect the next one to be an operator or divider, this time it’s the divider (=), still the equation is ok. Once we have found the divider, we will not expect a divider anymore for this problem. Time to expect another operand after the divider and it will continue same way as before as long as it meets the expectation, the moment it fails we declare that it is wrong and not from Zrog.

C++ Solution

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

string symbols[2][5] = {{"=","<",">","<=",">="},{"+","-","*","/","%"}};
#define DIVIDER 0
#define OPERATOR 1
#define OPERAND 2

int getType(string part){
	// Given a part this will return its type
	// 0 is divider, 2 is operand, 1 is operator
	for(int i=0;i<2;i++){
		for(int j=0;j<5;j++){
			if(part==symbols[i][j]){
				return i;
			}
		}
	}
	return 2;
}

vector<string> getParts(string statement){
	// Splitting the line using space and storing the parts in the vector
	vector<string> parts;
	string part = "";
	int len = statement.length();
	for(int i=0;i<len;i++){
		if(statement[i]==' ' || i==len-1){
			if(statement[i]!=' ') part += statement[i];
			parts.push_back(part);
			part = "";
		}else{
			part += statement[i];
		}
	}
	return parts;
}

int main(){
	int n; cin>>n;
	cin.ignore();
	while(n--){
		string statement;
		getline(cin, statement);
		
		vector<string> parts = getParts(statement);
		// These are the booleans to keep track of expected symbol type
		// Turning on/off and keeping track of these variable is the key to the solution
		bool divider = true, operand = true, oprt = false, zrog = true; 
		// Initially, we expect an operand and not an operator, we also want a divider
		// 'zrog' is also true until turned false
		
		for(int i=0;i<parts.size();i++){
			int type = getType(parts[i]); // For each part we first identify its type
			if(type==DIVIDER){ // This indicates the type of the part we are checking right now
				if(divider){ // This 'divider' will be true if we are expecting it
					if(operand==true || oprt==false){ // This will check if the very first part is a divider or not
						zrog = false;
						break;
					}
					divider = false; // The only divider is found, we turn this flag off
					operand = true;  // The next part must be an operrand
					oprt = false; // The next part cannot be an operator
				}else{
					zrog = false;
					break;
				}
			}else if(type==OPERAND){ // This indicates the type of the part we are checking right now
				if(operand){ // This 'operand' will be true if we are expecting it
					operand = false; // So the next part cannot be an operand
					oprt = true; // The next part should be an operator
				}else{
					zrog = false;
					break;
				}
			}else if(type==OPERATOR){ // This indicates the type of the part we are checking right now
				if(oprt){ // This 'oprt' will be true if we are expecting it
					oprt = false; // So the next part cannot be an operator
					operand = true; // The next part must be an operrand
				}else{
					zrog = false;
					break;
				}
			}
		}
		// At the end, we should not be expecting an operand, we should have already found the divider
		// And for each part our expectation were met, then print 'Zrog'
		if(zrog && divider==false && operand==false){
			cout<<"Zrog"<<endl;
		}else{
			cout<<"Frog"<<endl;
		}
	}
	return 0;
}

Summary

Overall, it was an amazing night with code knight especially that it was lightly raining with wonderful breeze (at least where I was at the time). I also would like to mention that I hinted one of the participants to solve problem A during the contest which was unfair to others. Thankfully, Asyraf reminded me to announce that on the contest platform. I felt relieved after the annoucenment. This will not happen again in the future inshAllah. I chose to tell you this because I want to maintain a level of transparency where we can have a fair ground for all.

All in all, it was a good contest, and thanks for everyone who joined. Stay tuned for the upcoming round !

“After long hours of search we failed to acquire any knowledge about our narrators current whereabouts. Thus we hope he reveals himself to us with his dramatic remarks in the coming round!! …”

ps: no comment