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