Code Knights Round 5 Results and Problem Analysis ?>

Code Knights Round 5 Results and Problem Analysis

Assalamualaikum everyone,

Last saturday, Code Knights Round 5 was held with a total of 17 participant… which is pretty much the same with round 4. The winner (finally…) goes to anas_95 from IIUM by the virtue of answering all problems faster with less penalty (which is 0). This round is (unfortunately) the easiest round ever with 6 participant answering all problems.

Selection_087

The second place goes to UncleWong from UM and the third place goes to joscmw95 from UTAR. foreveralone, winner of round 4 is at the fourth place. Notable mention includes two time winner lim2481284 from UNITEN which continues his effort of not even trying. You can find the dataset and pdf through the link below:

PDF

Dataset

Before we go to the answers, we would be grateful if you could answer a short 5 minute feedback form about Code Knights. Your feedback will go a long way to improve Code Knights.

A. Aladeen or Aladeen! – by Zarir

The solution is very aladeen. The naive way will also work which is of time complexity [math]O(n * m)[/math] for the given [math]n[/math] and [math]m[/math] , here [math]n \leq 300[/math] and [math]m \leq 1000[/math] .

In the naive way we store all the words in an array, and then later for each query word we check the array linearly for a match.

A smarter way is to use the Map data structure which is built-in in C++ and Java(TreeMap). The time complexity then becomes [math]O(n logn)[/math], then for each query word the search will be done in the map, as the map is actually an AVL tree, it will take only [math]logn[/math] time to find a particular key.

C++ Solution

#include <bits/stdc++.h>

using namespace std;

int main(){
	map<string, string> dict;
	int n,m;
	string word;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>word;
		dict[word] = "Aladeen";
	}
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>word;
		if(dict.find(word)==dict.end()) cout<<word<<endl;
		else cout<<dict[word]<<endl;
	}
	return 0;
}

Java Solution

import java.util.Scanner;
import java.util.TreeMap;

public class AladeenOrAladeen {

	public static void main(String[] args) {
		TreeMap<String, String> dict = new TreeMap<String, String>();
		int n,m;
		String word;
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		for(int i=0;i<n;i++){
			word = scan.next();
			dict.put(word, "Aladeen");
		}
		m = scan.nextInt();
		for(int i=0;i<m;i++){
			word = scan.next();
			if(dict.containsKey(word)){
				System.out.println(dict.get(word));
			}else{
				System.out.println(word);
			}
		}
	}
}

B. Math Task – by Amjad

This problem is meant to be the giveway problem. It is straight forward. you are given inputs and all formulas and you just need to apply them.

C++ Solution

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main(){
    int T,a,b;
    cin >> T;
    for(int i=0;i<T;i++){
        cin >> a >> b ;
        cout << fixed << setprecision(2) << (a*b/2.0) << "," << sqrt(a*a+b*b) << endl;
    }
    return 0;
}

C. Keep me healthy buddy! – by Ayesha

This problem is a simple implementation you just need to do as the problem said. Basically you just need to add up the calories he eats during the day and if he passes the limited keep track of the foods that causes him passing the limit. The one to keep in mind is that we should consider that he doesn’t eat the foods causing him passing the limit so the calories of those should not be added to his calories intake of the day. And finally if he did not pass his limit by overeating you need to make sure that he did not eat less than calories required so you basically need to get the difference of the calories intake and minimum calories required.

C++ Solution

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

int main(){
	int n, max, min, count = 0;
	cin >> n;
	cin >> min >> max;
	while (n--){
		int m, sum = 0, calories;
		bool overeat = false;
		string name, output = "Perfect day! Good job.";

		cin >> m;

		while(m--){
			cin >> name >> calories;
			if((sum + calories) > max){
				if(overeat){
					output += (" " + name);
				}
				else{
					overeat = true;
					output = "Slow down dude! You should not eat: " + name;
				}
			}
			else{
				sum += calories;
			}
		}

		if(sum < min && !overeat){
			output = "Good day but not enough. Eat at least " + to_string(min - sum) + " more calories.";
		}

		cout << "Day " << ++count <<": " << output << endl;
	}
}

Java Solution

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

public class Main2{
    static Scanner in;
    static PrintStream out;
    static PrintStream err;

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

        boolean enable_debug = true;
        if(!enable_debug){
            err = new PrintStream(new OutputStream(){
                public void write(int b){
                    // NO-OP
                }
            });
        }
    }

    public static <T> void dbg(String s,T val){
        err.print(s+": ");
        err.println(val);
    }

        static int min;
        static int max;
    public static void solve(int day){

        int m = in.nextInt();
        int current = 0;
        ArrayList<String> shouldNot = new ArrayList<String>();

        for(int i=0;i<m;i++){
            String s = in.next();
            int food = in.nextInt();

            int nextCurrent = current+food;
            if(nextCurrent > max){
                shouldNot.add(s);
            }else{
                current = nextCurrent;
            }
        }

        
        out.print("Day "+day+": ");
        if(current < min){
            out.println("Good day but not enough. Eat at least "+(min-current)+" more calories.");
        }else if(shouldNot.size() > 0){
            out.print("Slow down dude! You shouldn’t eat:");
            for(String s:shouldNot){
                out.print(" "+s);
            }
            out.println();
        }else{
            out.println("Perfect day! Good job.");
        }

    }

    public static void main(String[] args){

        int n = in.nextInt();
        min = in.nextInt();
        max = in.nextInt();

        for(int i=0;i<n;i++){
            solve(i+1);
        }

    }
}

D. Triangleable Hexagon – by Ashraf

There are multiple way to check if the hexagon fit the criteria. Among other includes rotate each point by 120 degree and compare the last point. But one of the simplest one is this, for each two consecutive side, the sum of the length of the two side must be equal to the sum of the length of the opposite two side. Formally, [math]$a_{i \% 6} + a_{(i+1) \% 6} = a_{(i+3) \% 6} + a_{(i+4) \% 6}$[/math] for all [math]$i$[/math]. So checking that for three consecutive [math]$i$[/math] should be enough.

C++ Solution

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

using namespace std;

int main(){

    int sides[6];
    for(int i=0;i<6;i++){
        cin >> sides[i];
    }

    bool ok = true;
    for(int i=0;i<3;i++){
        int cside = sides[i]+sides[i+1];
        int oside = sides[(i+3)%6]+sides[(i+4)%6];
        
        if(cside != oside){
            ok = false;
        }
    }

    if(ok){
        cout << "Triangleable Hexagon" << endl;
    }else{
        cout << "Ugly Hexagon" << endl;
    }

    return 0;
}

E. Product Sets – by Amjad

There are different methods to solve this problem. This problem is also our first problems that can have multiple output. That means, the output for a specific input could vary from one solution to another.
Example:

# Input:
 4
 3 -6 7 0

# output: (One possible answer)
 1 -6
 2 3 7
 1 0

# output: (Another possible answer)
 2 -6 3
 1 7
 1 0

All these outputs are correct as long as you meet the conditions in the problem description.

Our solution to this problem is to have the inputs sorted in ascending order. Then append the first element in the sorted array to the first set (The product of this set is negative), then check if the last element in the sorted array is zero then we need to append the second and third element to the second set. (when the last element in the sorted array is zero means that we do not have any postive integer in the set and therefore we need to push two negative numbers the second set in order to make the product positive). Now if the last element is not zero then push the last element to the second set.

The third set would include all other numbers including zero to make the product equal to zero.

C++ Solution

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

#define ABS(x) ((x)<0 ? -(x) : (x))
#define REP(i,n) for(int i=0, _e(n); i<_e; i++)
#define FOR(i,a,b) for(int i(a), _e(b); i<=_e; i++)
#define FORD(i,a,b) for(int i(a), _e(b); i>=_e; i--)
#define FORIT(i, m) for (__typeof((m).begin()) i=(m).begin(); i!=(m).end(); ++i)
#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )

#define inf_int (1<<31)-1
#define inf_long (1<<63)-1
#define sz size()
#define pb push_back
#define VI vector<int>
#define VS vector<string>

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;


#ifdef DEBUG
#define dbg(x) x
#define dbgp(x) cerr << x ;
#else
#define dbg(x) //x
#define dbgp(x) //cerr << x << endl;
#endif

int n , a[100] ;

int main(){
    cin >> n ; 
    REP(i,n){
        cin >> a[i]; 
    }
    sort(a,a+n);
    cout << 1 << " " << a[0] << endl; 
    if ( a[n-1] == 0 ) {
        cout << 2 << " " << a[1] << " " << a[2] << endl; 
        cout << n-3 ;
        for(int i=3;i<n;i++) cout << " " << a[i];
        cout << endl;
    }
    else {
        cout << 1 << " " << a[n-1] << endl; 
        cout << n-2 ;
        for(int i=1;i<n-1;i++) cout << " " << a[i];
        cout << endl;
    }
    return 0;
}

Java Solution

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

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

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

        boolean enable_debug = true;
        if(!enable_debug){
            err = new PrintStream(new OutputStream(){
                public void write(int b){
                    // NO-OP
                }
            });
        }
    }

    public static <T> void dbg(String s,T val){
        err.print(s+": ");
        err.println(val);
    }

    public static void main(String[] args){

        int n = in.nextInt();

        ArrayList<Integer> negatives = new ArrayList<Integer>();
        ArrayList<Integer> positives = new ArrayList<Integer>();
        ArrayList<Integer> zeroes = new ArrayList<Integer>();

        for(int i=0;i<n;i++){
            int d = in.nextInt();

            if(d == 0){
                zeroes.add(0);
            }else if(d < 0){
                negatives.add(d);
            }else{
                positives.add(d);
            }
        }

        if(positives.size() == 0){
            int removed1 = negatives.remove(negatives.size()-1);
            int removed2 = negatives.remove(negatives.size()-1);
            positives.add(removed1);
            positives.add(removed2);
        }

        if(negatives.size()%2 == 0){
            int removed1 = negatives.remove(negatives.size()-1);
            zeroes.add(removed1);
        }

        out.print(negatives.size());
        for(int d: negatives){
            out.print(" "+d);
        }
        out.println();

        out.print(positives.size());
        for(int d: positives){
            out.print(" "+d);
        }
        out.println();

        out.print(zeroes.size());
        for(int d: zeroes){
            out.print(" "+d);
        }
        out.println();

    }
}

Conclusion

For the first time ever in Code Knights history, the number of participant did not increase. Well… that was depressing. Have we reached our plateau? Regardless with how many participant, we will still continue. Next round, you can bet that we have been pressured by this round to create a much harder problem. Will the problem setter exercise some restraint? Find out on the next round.

The narrator don’t have much medieval remark idea anymore. It kinda feels strange because in Code Knights, one person’s win does not necessarily mean another person’s loss, which is unlike actual physical battle, with swords and such. Anyway… just imagine I said something fancy with the following content: UncleWong answer all first, followed by anas_95 which overtook him because UncleWong have 5 wrong submission at that time. stdLn also answered all problems without any wrong submission, but he came late. lim2481284 have two wrong submission for problem A because of a typo. And he did not manage to solve D. Shahril is MIA for 2 round now… Where is him?