# Code Knights Round 6 Results and Problem Analysis

Assalamualaikum everyone,

Last Saturday, the 6th round of Code Knights was held, with a total of….. 17 participants. Same as last round, which is also the same as the round before. This round is significantly harder than the last round, which was the easiest round by far.

How hard? Well.. if you compare it to Round 3, its.. *OK-lah*. The winner for this round goes to anas_95 from IIUM, who also won last round. anas_95 was the only participant who manage to solve 4 problems, but he did not solve problem D. It’s nice to see someone from IIUM winning again, but its starting to get boring. Can someone else win next time? stdLn maybe? Heck, I’m even waiting for lim2481284 to make a comeback.

You can find the dataset and PDF through the link below.

Like last time, before you go to the tutorial, please take some moment to fill up our feedback form.

## A. Binary Search – by Amjad

This problem is classified as giveaway problem. In fact the problem is explanatory type of problems where the description of the problem and the solution is provided in the problem statement. Although, the solution is provided in the problem statement, a few of the contestants could not solve it for some reason (They may have thought it is a trap or the name binary search could be scary enough to not want to solve it) or could be other reasons that I do not know. The problem utilizes binary search which is much more faster than linear search. If you try to solve the problem with linear search, you will end up with TLE verdict (Time limit exceeded). Therefore, binary uses [math]log n[/math] operation to quickly find elements in a sorted array.

**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 main(){ int n, a[2*100000], q, queryValue; int index; cin >> n ; for(int i=0;i<n;i++){ cin >> a[i]; } sort(a,a+n); cin >> q ; for(int i=0;i<q;i++){ cin >> queryValue; index = upper_bound(a,a+n,queryValue) - a; cout << n - index << endl; } return 0; }

**Java Solution**

import java.io.PrintStream; import java.util.Arrays; import java.util.Scanner; import java.util.TreeSet; public class Main{ public static void main(String args[]){ Scanner in = new Scanner(System.in); PrintStream out = System.out; int n = in.nextInt(); int[] inputArrays = new int[n]; for(int i=0; i<n ; i++){ inputArrays[i] = in.nextInt(); } Arrays.sort(inputArrays); int q = in.nextInt(); while(q>0){ int query = in.nextInt(); int index = indexOfHigherThanQuery(0,n-1,query,inputArrays); out.println(n - index); q--; } } public static int indexOfHigherThanQuery(int first, int last, int target,int array[]){ int tmp ; int counter, step ; counter = last+1 - first; while(counter>0){ tmp = first ; step = counter/2; tmp = tmp + step ; if ( !(target < array[tmp]) ){ first = ++tmp; counter -= step + 1; } else counter = step ; } return first; } }

## B. Zrog the Judge – by Zarir

The purpose of this problem was to introduce operator overloading and its usage with the built in sort function in both C++ and Java.

The first task is to write the overloading function which needs 3 doubles and 1 int to do the comparison, passing this 3 doubles and 1 int can be done in multiple ways, in this solution we used a custom struct/object to store them together and then sent the struct/object instance as parameter to the overloading function.

Once the function is complete we just need to use the built-in sort function in C++/Java and sort it, time complexity of the built-in sort is O(n*logn), this will work. If you implement a sorting algorithm with O(n*n) time complexity, then it will get Time Limit Exceeded verdict.

Check out the sample solution to further understand how to do operator overloading in C++, Java doesn’t support operator overloading, its a bit different, check the sample Java source code.

**C++ Solution**

#include <bits/stdc++.h> using namespace std; #define eps 0.001 // This is the custom data container for this solution struct Frog{ double h,w,l; // h->height, w->weight, l->length of jump int i; // i-> position in the original list Frog(){} // Empty Constructor, it is needed for sorting using sort function Frog(double _h, double _w, double _l, int _i){ h = _h; w = _w; l = _l; i = _i;} // Constructor for initializing // The following function defines the nature of the operator overloading // In this case the operator is the comparison function, defined by "()" symbol bool operator()(const Frog& a, const Frog& b){ // The follwing conditions decides whether 'a' should go before 'b' or not if(a.h<b.h){ return false; }else if(abs(a.h-b.h)<eps){ if(a.w>b.w){ return false; }else if(abs(a.w-b.w)<eps){ if(a.l<b.l){ return false; }else if(abs(a.l-b.l)<eps){ return a.i<b.i; } } } return true; } }; int main(){ int n; scanf("%d",&n); vector<Frog> frogs; double h,w,l; for(int i=0;i<n;i++){ scanf("%lf %lf %lf",&h,&w,&l); frogs.push_back(Frog(h,w,l,i+1)); // We store the list in a vector } sort(frogs.begin(), frogs.end(), Frog()); // We use the built-in sort function with our custom comparator to sort the list // Now we just simply print out the while list for(int i=0;i<frogs.size();i++){ printf("ID:%d H:%.2lf W:%.2lf L:%.2lf\n",frogs[i].i,frogs[i].h,frogs[i].w,frogs[i].l); } return 0; }

**Java Solution**

import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class ZrogTheJudge implements Comparable<ZrogTheJudge>{ // This works as the custom data container for this solution double h,w,l; int i; static final double eps = 0.001; public ZrogTheJudge(double _h, double _w, double _l, int _i){ h = _h; w = _w; l = _l; i = _i; } // The following function is used by the sort function to do comparison // 1 means the 'other' object will go before 'this' // -1 means the 'other' object will go after 'this' @Override public int compareTo(ZrogTheJudge other) { if(this.h<other.h){ return 1; }else if(Math.abs(this.h-other.h)<eps){ if(this.w>other.w){ return 1; }else if(Math.abs(this.w-other.w)<eps){ if(this.l<other.l){ return 1; }else if(Math.abs(this.l-other.l)<eps){ return (this.i<other.i) ? -1:1; } } } return -1; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); ArrayList<ZrogTheJudge> frogs = new ArrayList<ZrogTheJudge>(); for(int i=0;i<n;i++){ frogs.add(new ZrogTheJudge(scan.nextDouble(), scan.nextDouble(), scan.nextDouble(), i+1)); } Collections.sort(frogs); for(int i=0;i<n;i++){ System.out.format("ID:%d H:%.2f W:%.2f L:%.2f\n", frogs.get(i).i,frogs.get(i).h,frogs.get(i).w,frogs.get(i).l); } } }

## C. Switch data transfer – by Ashraf

**Fun fact**: This problem was made for the first Code Knights round. But it keeps getting replaced with other problems. The solution need to represent the number as a binary and loop through the bit from the least significant bit to the most significant bit and count how many times the bit change, assuming that the initial toggle state is the starting bit. This can be done easily with some bitwise operation. Although some participants uses bitset and convert the bitset to string, which also work. Just remember to loop starting from the least significant bit.

**C++ Solution**

#include<iostream> using namespace std; int main() { string init; cin >> init; bool current = init == "ON"; unsigned int num; cin >> num; int count = 0; for(int i=0;i<32;i++){ bool on = (num & (1LL << i)) != 0; if(on != current){ count++; } current = on; } cout << count; }

**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 = false; 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){ String init = in.next(); int num = in.nextInt(); int count = 0; boolean cur = init.equals("ON"); for(int i=0;i<32;i++){ int bit = (1<<i)# boolean on = bit != 0; if(on != cur){ count++; } cur = on; } out.println(count); } }

## D. Zrog and Grog – by Ashraf

**Fun fact**: This problem was one of the candidate for the ‘impossible’ problem for IIUM Code Jam 2. But it was not chosen as the other one is hard enough. Personally I think this one harder.

Those who are accustomed to such grid like pattern and the ‘shortest distance’ clue would probably think that this is a BFS (Breath first search) problem. You are correct, but not just any BFS problem because it have the restriction that the Frogs must not collide. To solve this problem, you need to store both of the frog’s position as a state. So it is a state space search problem, which is still basically BFS. But in normal BFS on such ‘grid-like’ problem, the state are usually current position. In this case, it is both position.

The adjacent vertex (or state) are all possible combination of move from the two frog, which are not only up, down, left and right, but also stay. So for each state, there are 25 next state. To detect the collision issue, you need prune the state in which both of the position is the same and the state where the position are swapped from the previous state. Now it become a normal BFS problem which you can get the ‘depth’ of each state. You can store the depth information as a map, but it would be (much) faster if you store it as a four dimensional array.

**C++ Solution**

#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int dr[] = { 0, 1, 0, -1, 0 }; int dc[] = { 1, 0, -1, 0, 0 }; int main(){ int R,C; cin >> R >> C; string grid[R]; for(int i=0;i<R;i++){ cin >> grid[i]; } pii pos1; pii pos2; for(int i=0;i<R;i++){ for(int ic=0;ic<C;ic++){ if(grid[i][ic] == 'A'){ pos1 = make_pair(i,ic); }else if(grid[i][ic] == 'B'){ pos2 = make_pair(i,ic); } } } // Each state is represented by a pair of a pair of integer queue<pair<pii,pii> > queu; map<pair<pii,pii>, int> depth; pair<pii,pii> initial_state = make_pair(pos1, pos2); pair<pii,pii> final_state = make_pair(pos2, pos1); depth[initial_state] = 0; queu.push(initial_state); while(queu.size()){ pair<pii,pii> state = queu.front(); queu.pop(); if(state == final_state){ break; } for(int i=0;i<5;i++){ pii modified_first = make_pair(state.first.first+dr[i], state.first.second+dc[i]); if(modified_first.first >= R || modified_first.first < 0 || modified_first.second >= C || modified_first.second < 0){ continue; } if(grid[modified_first.first][modified_first.second] == 'X'){ continue; } for(int j=0;j<5;j++){ pii modified_second = make_pair(state.second.first+dr[j], state.second.second+dc[j]); if(modified_second.first >= R || modified_second.first < 0 || modified_second.second >= C || modified_second.second < 0){ continue; } if(grid[modified_second.first][modified_second.second] == 'X'){ continue; } if(modified_first == modified_second) continue; // Same place? pair<pii,pii> nstate = make_pair(modified_first, modified_second); if(nstate == make_pair(state.second, state.first)){ // Swapping? continue; } if(depth.find(nstate) != depth.end()){ // Added already continue; } queu.push(nstate); depth[nstate] = depth[state]+1; } } } if(depth.find(final_state) == depth.end()){ cout << -1 << endl; }else{ cout << depth[final_state] << 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); } static class State implements Comparable<State>{ public State(){ } public State(State c){ ar = c.ar; ac = c.ac; br = c.br; bc = c.bc; } int ar; int ac; int br; int bc; public int compareTo(State s){ if(ar != s.ar) return ar-s.ar; if(br != s.br) return br-s.br; if(ac != s.ac) return ac-s.ac; return bc-s.bc; } public boolean aSwap(State s){ return s.ar == br && s.br == ar && s.ac == bc && s.bc == ac; } public String toString(){ return "ar"+ar+" ac"+ac+" br"+br+" bc"+bc; } } public static void main(String[] args){ int n = in.nextInt(); int m = in.nextInt(); String gridS[] = new String[n]; for(int i=0;i<n;i++){ gridS[i] = in.next(); } boolean canGo[][] = new boolean[n][m]; State init = new State(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ char c = gridS[i].charAt(j); canGo[i][j] = c!='X'; if(c == 'A'){ init.ar = i; init.ac = j; } if(c == 'B'){ init.br = i; init.bc = j; } } } State finalS = new State(); finalS.ar = init.br; finalS.br = init.ar; finalS.ac = init.bc; finalS.bc = init.ac; int dr[] = { 0, 1, 0, -1, 0 }; int dc[] = { 1, 0, -1, 0, 0 }; TreeMap<State, Integer> depth = new TreeMap<State, Integer>(); Queue<State> que = new LinkedList<State>(); depth.put(init, 0); que.add(init); int answer = -1; //err.println("M is "+m); while(que.size() > 0){ State cur = que.poll(); int cdepth = depth.get(cur); //err.println("cur is "+cur+" depth "+cdepth); if(cur.compareTo(finalS) == 0){ answer = depth.get(cur); //err.println("Break"); break; } for(int i=0;i<5;i++){ State base = new State(cur); base.ar += dr[i]; base.ac += dc[i]; if(base.ar < 0 || base.ar >= n || base.ac < 0 || base.ac >= m) continue; if(!canGo[base.ar][base.ac]) { //err.println("Cannot go"); continue; } for(int i2=0;i2<5;i2++){ State next = new State(base); next.br += dr[i2]; next.bc += dc[i2]; if(next.br < 0 || next.br >= n || next.bc < 0 || next.bc >= m) { continue; } if(!canGo[next.br][next.bc]){ //err.println("Cannot go"); continue; } if(depth.containsKey(next)) continue; if(cur.aSwap(next)) continue; if(cur.ar == cur.br && cur.ac == cur.bc) continue; //err.println("adding "+next); depth.put(next, cdepth+1); que.add(next); } } } out.println(answer); } }

## E. Naughty Sisters – by Ayesha

Naughty sister is a math problem and all you need to do is to find the LCM (Least Common Multiple) of two numbers. Calculating LCM with the traditional way could be challenging, time consuming and most probably at the end you would get TLE. But fortunately the Euclidean Algorithm with O(n) can help us to calculate the GCD (for more information check this link http://bit.ly/1jxmUvL) and as (LCM(a,b)*GCD(a,b))= (a*b) you can easily calculate LCM.

**C++ Solution**

#include <iostream> using namespace std; typedef long long ll; ll GCD(ll a, ll b) { //Euclidean Algorithm return b == 0 ? a : GCD(b, a % b); } int main() { ll a,b; cin >> a >> b; while(a && b){ cout << (a*b)/GCD(a,b) << endl; //calculating LCM(a,b) = (a*b)/GCD(a,b) cin >> a >> b; } }

**Java Solution**

import java.util.*; import java.lang.*; import java.io.*; class main { public static long GCD(long a, long b) { //Euclidean Algorithm return b == 0 ? a : GCD(b, a % b); } static Scanner in; static PrintStream out; public static void main (String[] args) throws java.lang.Exception { in = new Scanner(System.in); out = System.out; long a = in.nextInt(); long b = in.nextInt(); while(a > 0 && b > 0){ // check whether they are greater than zero or not out.println((a*b)/GCD(a,b)); //calculating LCM(a,b) = (a*b)/GCD(a,b) a = in.nextInt(); b = in.nextInt(); } } }

## Conclusion

This round is particularly hard. I did mention in last round’s analysis that we will be pressured to make hard problems and we did, so this happen. As usual, we all imagine that the difficulty of this round would be just right, but it did not happen. Did I mention that making a balanced round is really hard? Overall, I think it is a good round, but personally, last round was more fun.

Next week (3 September) we will have a special contest, which is not considered a normal round because it can be unfair to some participant and we (the organizer) don’t have to do much work for it. How unfair? Well, I can’t tell you that right now because it would be even more unfair. So stay tune for the next announcement.