Code Knights Round 1 Result and Problem Analysis ?>

Code Knights Round 1 Result and Problem Analysis

Update: Announcement on round 2 is up. See here for details.

Assalamualaikum everyone,

Last Saturday, the first round of Code Knights was held from 10 PM to 2 AM. We received 18 registration, however only 8 participated likely due to miscommunication of the contest time. The following are the final scoreboard of the round.

Ranking - Google Chrome_063-2

Congratulation to Omar Salim from IIUM who won the first round and is the only participant who manage to solve the ‘Fix the Fence’ problem in time. All participant managed to solve the FizzBuzz problem and most participant answered Yeoh’s Parking. You can download the dataset through the following link:

Dataset

PDF

The following are the problem analysis and sample solution for the problems:

Fix The Fence – by Zarir

Fix The Fence was only solved in time by Omar Salim. The problem requires a straight forward implementation.

At first by traversing the given grid we need to count the number of total fences (X), also count how many are on the border.

Then we need to calculate how many fences are required to surround the farm by calculating the perimeter using the formula (2*n+2*(m-2)). Majority of the submission failed because there is one critical case when n or m is 1 which needs to be handled separately.

Now, if perimeter and the number of fences on border are the same, then no further calculation is needed as the farm is surrounded. But if perimeter is bigger, then we need further calculation to determine the cost to surround the farm with fences.

If the cost of buying new fence is less than replacing, then we just multiply nc with the number of fences needed. But if rc < nc, then we replace as much as possible, even after replacing if we need even more, then we buy the rest.

C++ Solution

#include <bits/stdc++.h>

using namespace std;

#define MAX 105
#define onBorder(r,c,n,m) ((r==0 || r==n-1) || (c==0 || c==m-1)) // condition to check if (r,c) is on border or not

int main(){
	char field[MAX];
	int n, m, nc, rc, ft=0, inplace=0;
	int cost=0;
	scanf("%d %d %d %d", &n, &m, &nc, &rc);
	for(int i=0;i<n;i++){
		scanf("%s", field);
		for(int j=0;j<m;j++){
			if(field[j]=='X'){
				if(onBorder(i,j,n,m)){
					inplace++; // counting X (fences) only on border
				}
				ft++; // counting total number of X (fences)
			}
		}
	}
	// calculating perimeter for total number of required fences
	int peri = (n==1 || m==1) ? n*m : (2*n+2*(m-2));
	
	// dif < 0 means, farm not surrounded
	// dif == 0 means, farm is surrounded
	// extra is the total number of fences that can be replaced if needed 
	int dif = inplace - peri, extra = ft - inplace;
	
	if(dif<0){ // farm is not surrounded, need to calculate further
		dif *= -1; // changing sign of dif
		cost = dif*nc; // calculating cost with new fences
		if(rc<nc){ // if cost of replacing is less than buying new fence
			n = extra - dif; // calculating how many we can replace
			if(n<0){ // n < 0 means we dont have enough to replace all, also need to buy new fences along with the replacements 
				n *= -1; // changing sign of n
				cost = rc*extra+n*nc; // calculating cost both for replacing and buying new fences
			}else{ // there is enough extra fences to replace all
				cost = rc*dif; // calculating cost only with replacement
			}
		}
	}
	printf("%d", cost); // printing the cost
	return 0;
}

Java Solution

import java.util.Scanner;

public class A {
	
	public static boolean onBorder(int r, int c, int n, int m){
		if((r==0 || r==n-1) || (c==0 || c==m-1)){
			return true;
		}
		return false;
	}
	
	public static void main(String[] args) {
		String line;
		int n, m, nc, rc, ft=0, inplace=0;
		int cost=0;
		
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		nc = scan.nextInt();
		rc = scan.nextInt();
		for(int i=0;i<n;i++){
			line = scan.next();
			for(int j=0;j<line.length();j++){
				if(line.charAt(j)=='X'){
					if(onBorder(i,j,n,m)){
						inplace++; // counting X (fences) only on border
					}
					ft++; // counting total number of X (fences)
				}
			}
		}
		
		// calculating perimeter for total number of required fences
		int peri = (n==1 || m==1) ? n*m : (2*n+2*(m-2));
		
		// dif < 0 means, farm not surrounded
		// dif == 0 means, farm is surrounded
		// extra is the total number of fences that can be replaced if needed 
		int dif = inplace - peri, extra = ft - inplace;
		
		if(dif<0){ // farm is not surrounded, need to calculate further
			dif *= -1; // changing sign of dif
			cost = dif*nc; // calculating cost with new fences
			if(rc<nc){ // if cost of replacing is less than buying new fence
				n = extra - dif; // calculating how many we can replace
				if(n<0){ // n < 0 means we dont have enough to replace all, also need to buy new fences along with the replacements 
					n *= -1; // changing sign of n
					cost = rc*extra+n*nc; // calculating cost both for replacing and buying new fences
				}else{ // there is enough extra fences to replace all
					cost = rc*dif; // calculating cost only with replacement
				}
			}
		}
		System.out.println(cost); // printing the cost
	}
}

Yoeh’s Parking – by Ayesha

In this problem the optimize parking is simply any place between the closest and the furthest shopping mall. Because any parking between these two spots, Yoeh has to walk the whole distance twice. Once to get to all the shopping and malls and finally coming back to the car. So what you need to do is to read all the inputs and find the smallest and largest numbers and find their distance and multiple by 2.

C++ Solution

#include <iostream>
using namespace std;

int main(){
	int t;
	cin >> t;
	while(t--){
		int n, max = 0, min = 100, x;
		cin >> n;
		while(n--){
			cin >> x;
			max = max > x ? max : x;
			min = min > x ? x : min;
		}
		cout << 2 * (max - min) << 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;
		int t = in.nextInt(); // get the number of test case
		for(int i = 0 ; i < t ; i++){
			int n = in.nextInt(); // get the number of shopping malls 
			int max = 0, min = 100; // initialize the maximum to the lowest it can be and initialize minimum to the largest it can be
			for(int j = 0 ; j < n ; j++){ int x = in.nextInt(); // get shopping mall’s distance max = max > x ? max : x; // check if the new distance is larger than current maximum, if yes replace it
				min = min > x ? x : min; // check if the new distance is smaller than current minimum, if yes replace it
			}
			out.println(2 * (max - min)); // print the twice of the distance of the closest and the furthest shopping malls 
		}
	}
}

Challenge – by Amjad

In this problem you are asked to write a code to identify a 2×2 square of the same color (Black or White) in a given 4×4 field. However, you have also the ability to repaint at most one cell to any color you want. So for example, given the following 4×4 field:

.@.@
@@.@
..@.
@@@.

Black Cell is represented by ‘@’. White Cell is represented by ‘.’. Notice the first 3 black cells.

.@
@@

You can repaint the ‘.’ (White cell) to ‘@’ black and then the shape will look like:

@@
@@

which is a 2×2 square of the same color. Therefore, print “YES”. Otherwise, print “NO”.

Solution: Run a nested loop starting from (0,0), and in each iteration count the neighboring cells color. Count how many blacks and how many whites adjacent to (0,0). if the count of any color is more than or equal to 3. Then print “YES” because you can form a 2×2 square of the same color. Otherwise move on to (0,1), again count. So the loop will go through the following points: (0,0)->(0,1)->(0,2) (1,0)->(1,1)->(1,2) (2,0)->(2,1)->(2,2) Notice that I did not go to (0,3) because I know it will not form a 2×2 square. Same case for (3,0).

Half of the participant managed to answer this problem. Some come close, but did not consider the fact that if there are already 2×2 square of the same color, you should print “YES”. Tips: It is only impossible if the number of a color in a 2×2 square is exactly 2.

C++ Solution

#include <iostream>
using namespace std;

char square[4][4];

bool check(int x,int y){
    int whites=0;
    int blacks=0;
    if (square[x][y]=='.')whites++;
    else blacks++;

    if (square[x][y+1]=='.')whites++;
    else blacks++;

    if (square[x+1][y]=='.')whites++;
    else blacks++;

    if (square[x+1][y+1]=='.')whites++;
    else blacks++;

    if ( blacks >= 3 || whites >= 3 )
        return true;

    return false;
}

int main(){
    for(int i=0;i<4;i++) // nested loop to input the square
        for(int j=0;j<4;j++) cin >> square[i][j];

    for(int i=0;i<3;i++){ // nested loop to go from (0,0) to (2,2)
        for(int j=0;j<3;j++){
            if (check(i,j)) { // count blacks and white if any of them more than 3 then print "YES" and then exit.
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl; // print "NO" if "YES" was not printed.
    return 0;
}

Java Solution

import java.util.Scanner;
public class Main {
 public static void main(String args[]) {
  Scanner scan = new Scanner(System.in);
  String square[] = new String[4];
  for (int i = 0; i < 4; i++) {
   square[i] = scan.next();
  }
  for (int i = 0; i < 3; i++) {
   for (int j = 0; j < 3; j++) {
    if (check(i, j, square)) {
     System.out.println("YES");
     return;
    }
   }
  }
  System.out.println("NO");
 }
 public static boolean check(int x, int y, String[] square) {
  int blacks = 0;
  int whites = 0;
  if (square[x].charAt(y) == '.') whites++;
  else blacks++;
  if (square[x].charAt(y + 1) == '.') whites++;
  else blacks++;
  if (square[x + 1].charAt(y) == '.') whites++;
  else blacks++;
  if (square[x + 1].charAt(y + 1) == '.') whites++;
  else blacks++;
  if (blacks >= 3 || whites >= 3) {
   return true;
  }
  return false;
 }
}

FizzBuzz – by Ashraf

The problem is in fact inspired by actual interview question. If you read the link given in the Code Knight round 1 post, you should know about it. I personally wanted to test out if it is true that many programmer have a hard time answering this question, because in actual contest, this problem would likely be considered as a ‘giveway’ problem. Luckily, all participant managed to answer this question fairly easily. But then again, those who participate in Code Knight is probably above average anyway. The only problem encountered during the contest is that some participant missed a character in the output. Remember, you must print you the output EXACTLY.

C++ Solution

#include<iostream>

using namespace std;

int main(){

    int a,b;
    cin >> a >> b;

    for(int i=a;i<=b;i++){
        if(i%3==0 && i%5==0){
            cout << "FizzBuzz" << endl;
        }else if(i%3==0){
            cout << "Fizz" << endl;
        }else if(i%5==0){
            cout << "Buzz" << endl;
        }else{
            cout << i << endl;
        }
    }
}

Java Solution

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

        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

Overall, despite the relatively low number of participant, Code Knight Round 1 is an excellent and fun round, especially considering that this is the first round. Next time, we hope to replicate the success of this round and invite more participant. You too can invite your friends on the next round. Stay tune for announcement on Round 2.

“As the ashes from the battle settle down, Omar emerge at the top of the hill with the crown of Code Knights. He looks upon the fallen with a slight grin. However, one by one other warriors enter the battlefield seeking for the crown themselves. The fallen will not stay idle and will stand again, even stronger than before. Surrounded, will Omar retain his throne? Or will a new king unseat him?”

ps: I do not know if Omar have a “slight grin on his face” or not. The crown is metaphorical, please don’t ask for a real one. The hill is also metaphorical and I don’t know if Omar is on a hill. But he did win.