Code Knights Round 2 Result and Problem Analysis ?>

Code Knights Round 2 Result and Problem Analysis

Update: Announcement on next round is available here

Assalamualaikum everyone,

Last Saturday (2nd July), the second Code Knights was held from 10 PM to 2 AM. The winner goes to lim2481284 from UNITEN who quite handily solve all 4 questions. shahril and HarshRalph also solve all 4 questions, but not nearly as early as lim. b0608d62-788e-41ec-8efb-09c8a4ab44c3

Congratulation to Lim Kien Seng from UNITEN. All participant managed to solve problem A and D. You can download the dataset through the following link:

Dataset

PDF

Also, for IIUM student, the round is available in the IIUM ICPC Team codeforces group. The following are the problem analysis and sample solution for the problems:

Problem A. Weleed’s Thankfulnes – by Ayesha

For this problem you simply just need to have initial sum of thankfulness as zero and get the input while checking whether it is greater than 0 or not. If it was greater the sum would be add up by one otherwise deduced by one. Finally print out the sum. The only tricky part is to make sure to update your initial sum for each test case.

C++ Solution

#include <iostream>
using namespace std;

int main(){
	int N, i = 0; // initilizing the test case number 
	while(scanf("%d", &N), N){ // getting the N and check whether it's greater than zero or not
		int sum = 0, k; // initilizing sum 
		while(N--){ // getting N inputs 
			cin >> k;
			sum += k > 0 ? 1 : (-1); // checking if the input is greater than zero then add by 1 otherwise add by -1
		}
		cout << "Case " << ++i << ": " << sum << endl; // priting out the result while increasing the test case number 
	}
	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;
		int N = in.nextInt(); // getting N  
		int i = 0; // initilizing the test case number 
		while(N > 0){ // check whether it's greater than zero or not
			int sum = 0, k; // initilizing sum 
			for(int j = 0 ; j < N ; j++){ // getting N inputs 
				k = in.nextInt();;
				sum += k > 0 ? 1 : (-1); // checking if the input is greater than zero then add by 1 otherwise add by -1
			}
			out.println("Case " + (++i) + ": " + sum); // priting out the result while increasing the test case number
			N = in.nextInt();
		}
	}
}

Problem B. To Marry or Not To Marry – by Zarir

Those who solved this problem, Congrats, you can now consider yourself an expert in finding a spouse for yourself … or not.

Anyhow, this is a very easy problem which requires 2 nested loop and a match counter, for each item of John, check in Jane’s list if it’s there or not, if match found then increment the counter. After search is completed for each item in John’s list, we will know the total match count.

Now we just need to divide the total match count by n (John’s total item) to get the percentage. Then just print the answer based on the percentage.

C++ Solution

#include <bits/stdc++.h>

using namespace std;

int main(){
	int n,m,mc=0;
	string thing;
	vector<string> john, jane;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>thing;
		john.push_back(thing); // take johns item input
	}
	cin>>m;
	for(int j=0;j<m;j++){
		cin>>thing;
		jane.push_back(thing); // take janes item input
	}
	bool marry = true;
	if(m>=(n/2)){ // when m>=(n/2), only then there is a chance of 50% match or more
		
		// in the following nested loop, for each item of john we search in janes item for a match
		for(int i=0;i<john.size();i++){
			for(int j=0;j<jane.size();j++){
				if(john[i]==jane[j]){
					mc++; // if a match is found then the counter is incremented
					break; // break and then check with johns next item
				}
			}
		}
		double percentage = (mc*1.0)/n; // to get the percentage divide matched count by johns total item
		if(percentage>=0.5){ 
			marry = false; // when percentage is >= 50%, make condition marry false
		}
	}
	if(marry) cout<<"Alive"<<endl;
	else cout<<"Forever Dead"<<endl;
	return 0;
}

Java Solution

import java.util.ArrayList;
import java.util.Scanner;

public class ToMarryOrNotToMarry {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n, m, mc = 0;
		ArrayList<String> john, jane;
		
		john = new ArrayList<String>();
		n = scan.nextInt();
		for(int i=0;i<n;i++){
			john.add(scan.next()); // take johns item input
		}
		
		jane = new ArrayList<String>();
		m = scan.nextInt();
		for(int i=0;i<m;i++){
			jane.add(scan.next()); // take janes item input
		}
		
		boolean marry = true;
		
		if(m>=(n/2)){ // when m>=(n/2), only then there is a chance of 50% match or more
		
		  // in the following nested loop, for each item of john we search in janes item for a match
			for(int i=0;i<john.size();i++){
				for(int j=0;j<jane.size();j++){
					if(john.get(i).equals(jane.get(j))){
						mc++; // if a match is found then the counter is incremented
						break; // break and then check with johns next item
					}
				}
			}
			double p = (mc*1.0)/n;  // to get the percentage divide matched count by johns total item
			if(p>=0.5) marry = false; // when percentage is >= 50%, make condition marry false
		}
		
		if(marry) System.out.println("Alive");
		else System.out.println("Forever Dead");
	}
}

Problem C. Nasi Lemak Stall – by Amjad

There are a number of solutions to this problem.

The most straigtforward solution is Brute Force which will yield Time Limit Exceed (TLE) verdict.

However, no one in the contest tried that. I was hoping that some of the contestant would encouter TLE.

The second solution lies in figuring out the pattern. which is not difficult let me show you:

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
1 | 2 | 3 | 4 | 5 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 1 | 1 | 1 | 2 | 2 |

The first row represents the number of nasi lemak that is being served.
The second row represents who ate that nasi lemak represented by numbers 1: Amjad, 2:Asyraf… etc.
To figure out the pattern, look at number 1 occurrences:
The first occurence is at position 1 ( first nasi lemak )
The second occurence is at position 6 ( 6th nasi lemak )
The third occurence is at position 16 ( 16th nasi lemak )
The fourth occurence is at position 31 ( 31th nasi lemak )

and from there you notice that you keep adding the multiple of 5

1 + 5 = 6
6 + 10 = 16
16 + 15 = 31
31 + 20 = 51

Brute Force (TLE) – correct but slow

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

int N ;

int main(){
    cin >> N ; 
    int counter = 0 ;
    for(int i=0;i<10000000;i++){
        for(int j=0;j<i+1;j++){
            counter++;
            if ( counter == N ) {cout << "Amjad" << endl; return 0;}
        }
        for(int j=0;j<i+1;j++){
            counter++;
            if ( counter == N ) {cout << "Asyraf" << endl; return 0;}
        }
        for(int j=0;j<i+1;j++){
            counter++;
            if ( counter == N ) {cout << "Ayeshah" << endl; return 0;}
        }
        for(int j=0;j<i+1;j++){
            counter++;
            if ( counter == N ) {cout << "Zarir" << endl; return 0;}
        }
        for(int j=0;j<i+1;j++){
            counter++;
            if ( counter == N ) {cout << "Samir" << endl; return 0;}
        }
    }

    return 0;
}

C++ Solution

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
int main(){
    string names[5] = { "Amjad", "Asyraf", "Ayeshah", "Zarir", "Samir" };
    int level = 1, sum=5, k=0, i=1, res,n;
    cin >> n ; 
    while(n>(sum+=(k))){
        level=pow(2,i++);
        if (k==0)k=5;
        k*=2;
    }
    sum-=(k);
    if (n<=5)
        res = n;
    else res = n-sum;
    res = ceil((double)res/level);
    cout << names[res-1] << endl; 
    return 0;
}

Problem D. FizzBuzz V2 – by Ashraf

This problem is a upgrade from the last contest’s FizzBuzz question. But instead of a fixed number for “Fizz” and “Buzz” the number is made variable. Also, the number can also be in decreasing order, which is where most participant get confused. The number must be from a to b. If b is lower than a, then a must be higher than b which means the number would be in decreasing order. The simplest solution is to simply create two separate loop for ascending or descending order and checking if b is lower than a to choose between the two loops. You can also use only a single loop with the help of ternary operators.

C++ Solution (Fancy single loop)

#include<iostream>

using namespace std;

int main(){

    int a,b,c,d;
    cin >> a >> b >> c >> d;

    int delta = a <= b ? 1 : -1;

    for(int i=a; (a<=b?i<=b:i>=b); i+=delta){
        if(i%c==0 && i%d==0){
            cout << "FizzBuzz" << endl;
        }else if(i%c==0){
            cout << "Fizz" << endl;
        }else if(i%d==0){
            cout << "Buzz" << endl;
        }else{
            cout << i << endl;
        }
    }
}

Java Solution (Simple dual loop)

import java.io.PrintStream;
import java.util.*;
import java.io.*;

public class Main{
    static Scanner in;
    static PrintStream out;

    static {
        in = new Scanner(System.in);
        out = System.out;
    }

    public static void main(String[] args){
        int a = in.nextInt(), b = in.nextInt(), c = in.nextInt(), d = in.nextInt();

        if(a <= b){
            for(int i=a; i<=b; i++){
                if(i%3==0 && i%5==0){
                    out.println("FizzBuzz");
                }else if(i%3==0){
                    out.println("Fizz");
                }else if(i%5==0){
                    out.println("Buzz");
                }else{
                    out.println(i);
                }
            }
        }else{
            for(int i=a; i>=b; i--){
                if(i%3==0 && i%5==0){
                    out.println("FizzBuzz");
                }else if(i%3==0){
                    out.println("Fizz");
                }else if(i%5==0){
                    out.println("Buzz");
                }else{
                    out.println(i);
                }
            }
        }
    }
}

Summary

The timing of this round was not particularly great. The original date was 9’th July, but considering that is right after Eid, it is not very suitable. We either should delay the round by one week or advance the round by one week. So, we choose the later because, having more contest seems to be the better of the two. However, I do not consider that because the Eid was in the middle of the week, many family would take the whole week off and in that case, the good time to “Balik Kampung” is actually, on the same weekend. Considering that, we should have less participant this time. Additionally, we don’t really have much time to really prepare for the round considering that we only have one week and each of us have our own obligations.

The good news is, our campaign received multiple new registration. Up until now, we have about 32 registrations, which is about 14 more than last round. Of course, not all actually participated. The system reported about 13 participant logged in on that day, but only 9 participant submit anything, which is understandable considering the late hours and the Ramadan is nearly ending, so some participant are getting very busy.

Next round however, we will have a more suitable time. With that, hopefully we can get more participant. We will try to make a more challenging but balanced problem. Stay tune for the announcement on the next round.

“Riding a Great Horse, lim2481284 enter the arena equipped with a full set of armor and a long-sword forged from Mount Doom. Oh, and he brings a Dragon. He effortlessly rode to the top of the hill and the crown seems to be in his hand all along. After awhile, the other knights enter the arena.”

ps: Mount Doom is a reference from The Lord of The Ring. I don’t know if lim2481284 have a dragon next to him when he code, but it sure feels like it.