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

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.

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