Code Knights Round 4 Results and Problem Analysis ?>

Code Knights Round 4 Results and Problem Analysis

Update: Announcement for round 5 is out.

Assalamualaikum everyone,

Last Saturday 8 PM (as usual), Code Knights Round 4 was held at… online. This time, we have 17 contestant including several new participant from UM, UTAR, UKM and others. lim2481284, the winner of the last 2 round seems to have lost his edge, finishing at the 14th place. He is probably busy and have other stuff to do.   Meanwhile, shahril, the consistent second-finisher did not participate this time, breaking his consistent-second-place record from the first round and leaving HarshRalph to represent UiTM. The winner for this round goes to a newcomer, foreveralone from UM. He is a newcomer in a sense that he just registered in Code Knights, but not in the sense that he is new in competitive programming. Interestingly joscmw95 actually solved all problem first, but he submitted more wrong submission than foreveralone, resulting in an extra 13 minute penalty compared to foreveralone (each score point is approximately 1 minutes).

Tooltip_073
Who in the world is capayam? Tell him if we don’t get his phone number, we will ban him.

As you can see in the scoreboard, all problem was solved. Unfortunately, no single question was solved by everyone. Three participant managed to solve all 5 problems. All of these three participant are new participant. The difficulty of the problems this time seems to be more towards the easy side, but then again, if foreveralone, joscmw95 and UncleWong did not participate, (remember, they were new participant) no one would solve all 5 problems… except for lim2481284 or shahril (if they actually participate). In terms of balance, we probably need to work on making the difficulty ‘spread out’ more. Additionally, there were some issues with problem C and D.

PDF

Dataset

The problemset can be downloaded through the link above. As usual, for IIUM student, the problems can also be accessed from the IIUM ICPC Team codeforces group. Now, if only they would actually practice, that would be great…. On to the problem analysis!

A. Summation – by Amjad

The question is to sum numbers from 1 to N. The normal procedure is to run a loop to sum all numbers or use the formula. However, the resulting sum cannot be placed in 32 bit integer. Instead, you should be using 64 bit data type like long long to store the sum.

C++ Solution

#include <iostream>
using namespace std;
int main(){
    long long sum = 0 ; 
    int n ;
    cin >> n ; 
    for(int i=1;i<=n;i++){
        sum+=i;
    }
    cout << sum << endl; 
    return 0;
}

B. FizzBuzz V3 – by Ashraf

The FizzBuzz V3 problem is among the most boring problem in this round. It is the second most answered question with only 5 wrong submission. All who tried this problem managed to solve it. There are no particular tricks with this question, you just need to implement it with the use of some array or vector and inner loops.

C++ Solution

#include<iostream>
#include<vector>

using namespace std;

int main(){

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

    vector<int> ds;
    vector<string> ss;

    for(int i=0;i<n;i++){
        int d;
        string s;
        cin >> d >> s;
        ds.push_back(d);
        ss.push_back(s);
    }

    if(a <= b){
        for(int i=a; i<=b; i++){
            bool divisible = false;
            for(int j=0;j<n;j++){
                if(i%ds[j] == 0){
                    divisible = true;
                    cout << ss[j];
                }
            }
            if(!divisible){
                cout << i;
            }
            cout << endl;
        }
    }else{
        for(int i=a; i>=b; i--){
            bool divisible = false;
            for(int j=0;j<n;j++){
                if(i%ds[j] == 0){
                    divisible = true;
                    cout << ss[j];
                }
            }
            if(!divisible){
                cout << i;
            }
            cout << endl;
        }
    }

    return 0;
}

C. Simple Recursion – by Amjad

The first challenge was to avoid recursion for solving the problem. The recursion description was deceptive to lure you into thinking that this problem can be solved using recursion. However, I want to mention that some did solve the problem using recursion but the recursion was very unnecessary as they only recur one time, so not exactly recursion. Therefore, continuing on the problem lies in figuring out what the recursion is supposed to do. and if look at recursion it only reduces N by 11 in each recurrence, therefore knowing this you know that you avoid recursion and simply do N%11. Also there was another case the contestant has to cater for which the N%11 = 10 when this happen the result should -1. otherwise just print N%11.

The second challenge was input/output bound (Time it takes to output the result). Since the number of test cases can go up to 250,000 test case this presented another challenge particularly for java users. Since some of the contestant used System.out.printf which is slower than System.out.println. Therefore, java users had to suffer even though they solved the question in O(1). Luckily Ashraf figured that the problem is I/O bound which had led us to increase the time to 5 seconds and reevaluate all submissions for that particular problem. However, having done that, still it does not change the verdict of the submission since using System.out.printf in somewhat slower than System.out.println. Next time, when using such problem we would hint the contestant to use the proper input and output methods.

C++ Solution

#include<iostream>
using namespace std;
int main(){
    int n;
    while(cin >> n,n!=0){
        cout << "f(" << n << ") = " << (((n%11)==10)?-1:n%11) << endl;
    }
}

D. Fail or Success – by Ayesha

This is basically a straight forward problem. All you need to do it getting the hours for each course and record them in an array and as luckily the maximum number of course if small (only 20) there would be no issue with the memory limit. Also you need to consider if the course is taken or not which a Boolean array can help you to handle it. Rather than those rest of problem can be solved by some if and else statements which need to check whether the course is taken at the moment or not. If it is taken just drop the course and update the sum. If it is not taken then add the course and update the sum. Also make sure that in each time a course is mention it’s situation need to toggle. Something that might get missed also is the extra line which needs to be printed after each test case.

C++ Solution

#include <iostream>
using namespace std;

int main(){
	int n, m, c, keep = 0;	//Initializing the semester counter  
	while (scanf("%d %d %d", &n, &m, &c), (n || m ||c)){ //getting the input while checking weather all three sre greather than zero
		bool course[20], fail = false; //Defining a booling array to keep track if coure is taken or not
		// Initializing fail factor as false
		int hours[20], sum = 0, x, max = 0; //Defining an integer array to keep hours of each course
		//initializing maximum and also sum of hours by zero

		for (int i = 0 ; i < n ; i++){ //getting hours of each course and record them
			cin >> hours[i];
			course[i] = false; // initilizing that a course is not taken
		}

		while(m--){
			cin >> x;
			if(!course[x-1]){ //is the course is not taken
				sum += hours[x-1]; // add it to the sum of hours
				course[x-1] = true; //take the course
				if(sum > c){ //check if it's a fail or not
					fail = true;
				}
				max = max > sum ? max : sum; //check for the maximum sum of hours
			}
			else{ // if the course is taken
				sum -= hours[x-1]; // deduce it from sum of hours
				course[x-1] = false; // drop the course
			}
		}
		cout << "Semester " << ++keep; //increasing the semsester counter by one
		if(fail){// if the semester is a fail
			cout << " was a fail." << endl;
		}
		else{// if the semester is a success 
			cout << " was a success." << endl;
			cout << "Maximal hours was " << max << "." << endl;
		}
		cout << 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 n = in.nextInt();
        int m = in.nextInt();
        int c = in.nextInt(); 
        int keep = 0;	//Initializing the semester counter

        while(n > 0 && m > 0 && c > 0){ // check whether they are greater than zero or not
            boolean[] course = new boolean[20];
            boolean fail = false; //Defining a booling array to keep track if coure is taken or not
            // Initializing fail factor as false
            int[] hours = new int[20]; 
            int sum = 0, x, max = 0; //Defining an integer array to keep hours of each course
            //initializing maximum and also sum of hours by zero

            for (int i = 0 ; i < n ; i++){ //getting hours of each course and record them
                hours[i] = in.nextInt();
                course[i] = false; // initilizing that a course is not taken
            }

            for (int i = 0 ; i < m ; i++){
                x = in.nextInt();
                if(!course[x-1]){ //is the course is not taken
                    sum += hours[x-1]; // add it to the sum of hours
                    course[x-1] = true; //take the course
                    if(sum > c){ //check if it's a fail or not
                        fail = true;
                    }
                    max = max > sum ? max : sum; //check for the maximum sum of hours
                }
                else{ // if the course is taken
                    sum -= hours[x-1]; // deduce it from sum of hours
                    course[x-1] = false; // drop the course
                }
            }
            out.print("Semester " + (++keep)); //increasing the semsester counter by one

            if(fail){// if the semester is a fail
                out.println(" was a fail. \n");
            }
            else{// if the semester is a success
                out.println(" was a success.");
                out.println("Maximal hours was " + max + ".\n" );
            }
            n = in.nextInt();
            m = in.nextInt();
            c = in.nextInt(); 
        }
    }
}

E. Rotating Twins – by Zarir

It is a very straight forward implementation problem. One can write the code for all 4 state of rotation, but a smarter thing to do would be to write a function “rotate()” which rotates one of the square either clockwise or anti-clockwise and then check with the other square. Then just call the function 4 times inside a loop and check if it matches or not.

Total 4 possible states are there after rotation, the original, after 1 rotation, after 2 rotation and lastly after 3 rotation. Now, one critical insight is that the state after 3rd rotation in clockwise manner can also be reached by just doing 1 rotation in anti-clockwise manner, from the original state. So, for 1 and 3 rotation it is “Normal”, 2 rotation is “Rival” and 0 rotation means “Perfect”.

Before checking for matching pattern, the two square must be of the same dimension.

C++ Solution

#include <bits/stdc++.h>

using namespace std;

vector<string> box1, box2; // Storing the square as vector of string, 2D grid

// The rotate function rotates box2 in a clockwise manner only once
// The n-th column (from bottom to top) becomes the n-th row (from left to right) after rotation
void rotate(){
	vector<string> temp; // Temporary string vector to store the rotated box2
	for(int c=0;c<box2.size();c++){
		string row = "";
		for(int r=box2.size()-1;r>=0;r--){
			row += box2[r]; // Keep adding column values from bottom to top
		}
		temp.push_back(row); // Then here add it as a row in the new one
	}
	box2 = temp; // Once done update box2
}

int main(){
	string row;
	int n,m;
	bool related;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>row;
		box1.push_back(row);
	}
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>row;
		box2.push_back(row);
	}
	if(n==m){ // If dimensions dont match then not related
		for(int i=0;i<4;i++){ // Check with box1 and then rotate box2 only once, do this 4 times for 4 state
			related = true;
			for(int r=0;r<n;r++){
				for(int c=0;c<n;c++){
					if(box1[r]!=box2[r]){
						related = false;
						break;
					}
				}
				if(!related) break;
			}
			if(related){
				if(i==0){ // Means no rotation was needed
					cout<<"Perfect Twins"<<endl;
				}else if(i==1 || i==3){ // Means 1 or 3 rotation was needed
					// 1 and 3 both is normal because we can do 1 anti-clockwise rotation to reach that state
					cout<<"Normal Twins"<<endl;
				}else{ // Means 2 Rotation was needed
					cout<<"Rival Twins"<<endl;
				}
				return 0;
			}
			if(i<3) rotate(); // Calling rotation
		}
	}
	cout<<"Not Related"<<endl;
	return 0;
}

Java Solution

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

public class RotatingTwins {
	
	static ArrayList<String> box1, box2; // Storing the square as vector of string, 2D grid
	
	// The rotate function rotates box2 in a clockwise manner only once
	// The n-th column (from bottom to top) becomes the n-th row (from left to right) after rotation
	public static void rotate(){ 
		ArrayList<String> temp = new ArrayList<String>(); // Temporary string vector to store the rotated box2
		for(int c=0;c<box2.size();c++){
			String row = "";
			for(int r=box2.size()-1;r>=0;r--){
				row += box2.get(r).charAt(c); // Keep adding column values from bottom to top
			}
			temp.add(row); // Then here add it as a row in the new one
		}
		box2 = temp; // Once done update box2
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		box1 = new ArrayList<String>();
		for(int i=0;i<n;i++){
			box1.add(scan.next());
		}
		int m = scan.nextInt();
		box2 = new ArrayList<String>();
		for(int i=0;i<m;i++){
			box2.add(scan.next());
		}
		boolean related = true;
		if(n==m){ // If dimensions dont match then not related
			for(int i=0;i<4;i++){ // Check with box1 and then rotate box2 only once, do this 4 times for 4 state
				related = true;
				for(int r=0;r<n;r++){
					for(int c=0;c<n;c++){
						if(box1.get(r).charAt(c)!=box2.get(r).charAt(c)){
							related = false;
							break;
						}
					}
					if(!related) break;
				}
				if(related){
					if(i==0){ // Means no rotation was needed
						System.out.println("Perfect Twins");
					}else if(i==1 || i==3){ // Means 1 or 3 rotation was needed
						// 1 and 3 both is normal because we can do 1 anti-clockwise rotation to reach that state
						System.out.println("Normal Twins");
					}else{ // Means 2 Rotation was needed
						System.out.println("Rival Twins");
					}
					break;
				}
				if(i<3) rotate(); // Calling rotation
			}
		}
		if(!related) System.out.println("Not Related");
		//--end--
	}
}

Conclusion

Throughout the execution of Code Knights, we have seen the number of participant gradually increase, the problems becomes harder (and 5 problems instead of the original 4) and one by one, more university participate in these rounds. Round 4 has the highest number of participant, problem submission and more importantly, drama. I believe it is quite fitting to say that Round 4 is the best round yet. You can help make the next Code Knights Round even better. Tell your friends about Code Knights. Represent your university. Don’t let UM win all the time. It will get boring. Boring is the root of all procrastination. Procrastination leads to lower productivity. Lower productivity leads to economic slowdown, lower quality of life, poverty, starvation and so on. You get the point.

The next round should be on 13 August 2016. There will be a proper announcement soon. If you have any suggestion, criticism, question and such, feel free to comment down below. Maybe you want support for another programming language. Maybe you want the ‘Asdacap’ guy to pipe down. Maybe you want us to focus on a particular topic. Comment down your inquiry below.

Midway through the battle, lim2481284, king of Code Knights hill, rode his dragon out to another realm. He seems to be in a hurry.  Meanwhile, newcomer foreveralone, joscmw95 and UncleWong was locked in a tight battle. Other knights did not stay idle either. Sword by sword, shield by shield, Code Knights hill has never seen such intense battle before. Their battle cry can be heard from miles away… “Python! I choose you!”… “What? What is happening? It can’t be IO limited!”. In the end, foreveralone claims his victory, but only barely.

ps: When Amjad told me to enable python, I was like… “which student in Malaysia would actually use Python? Oh well, I just need to click on a checkbox.”. For those of you who don’t know about it, some participant actually use Python in this round… and last round.