Code Knights Round 14 Result and Problem Analysis ?>

Code Knights Round 14 Result and Problem Analysis

Assalamualaikum everyone. Its been awhile since I did a written analysis instead of a video or straight up, not doing it at all. Although recording a video is much more convenient that writing a blog, nothing beats creating a well authored blog post. That, and also the fact I did not finish this round, resulted in this post, albeit, late, because it takes time to type down these things.

Anyway, Round 14 is the second round after the last round which IIUM’s DSA student is scored for participation. Additionally, its kinda exam period for IIUM student… so… we are seeing a much lower participation, even after including participant from Hebron University, Palestine. In fact, looking at the ranking list, 6 out of 10 participant actually came from Hebron! If they did not participate, we would be looking at only 4 participant!

7b3cefd1-3daa-415e-8850-4cf98524ec77Anyway, back to the matters at hand, the winner of this round is.. not stdLn. Its capayam (formerly known as shahril). Both him and stdLn solved 3 out of 5 question, although I can personally say that capayam nearly solved C. Congratulation to capayam. Their name will forever be carved in the newly created Code Knights Hall of Fame, at least until I run out of money to pay for this server. Just kidding, Amjad would pay for it if I can’t afford to do so. On to the solutions:

Problem A: Baby Swapping by Zarir

This is a giveaway problem and its looks like everyone solved it. Giveaway requirement, achieved! Although the task says that you need to figure out how many swap is needed, the output does not requires it. You just need to output the used characters in upper case. Which means, you don’t actually need to swap and do things as the question asked you too. Its a trick to make you think too hard and stress you out!

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

typedef long long int ll;
typedef pair<ll,ll> pii;
#define REP(i,n) for(ll i=0;i<n;i++)

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

int main(){
    set<char> sets;

    string s;
    cin >> s;

    for(char c: s){
        if(c <= 'z' && c >= 'a'){
            c -= 'a'-'A';
        }else{
        }
        sets.insert(c);
    }

    for(char c: sets){
        cout << c;
    }
}

Problem B: Swapping by Zarir

The problem involve detecting if the rows are sorted or not, then swap them with the last row. You must do this one after another. I did not understand the (lack of) story or the rational of this problems. But if you do it as ordered, you should be fine. I personally got into trouble thinking that by “sorted” it need to be strictly increasing or decreasing. It does not need to be so. If all the numbers in a row is the same, it is considered to be sorted.

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

typedef long long int ll;
typedef pair<ll,ll> pii;
#define REP(i,n) for(ll i=0;i<n;i++)

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

int main(){
    int rows[3][3];
    int inOrder[3];
    REP(i, 3){
        cin >> rows[i][0];
        cin >> rows[i][1];
        cin >> rows[i][2];

        if(rows[i][0] <= rows[i][1] && rows[i][1] <= rows[i][2]){
            inOrder[i] = true;
        }else if(rows[i][0] >= rows[i][1] && rows[i][1] >= rows[i][2]){
            inOrder[i] = true;
        }else{
            inOrder[i] = false;
        }
    }

    if(!inOrder[0]){
        REP(i, 3){
            swap(rows[0][i], rows[2][i]);
        }
    }
    if(!inOrder[1]){
        REP(i, 3){
            swap(rows[1][i], rows[2][i]);
        }
    }

    REP(i, 3){
        cout << rows[i][0] << " " << rows[i][1] << " " << rows[i][2] << endl;
    }
}

Problem C: Abu’s Receipt by Ashraf

I was thinking about the fact that many people criticize competitive programming due to the lack of practical use of all these algorithms/technique that we use. Its not that these knowledge are useless, its just that only a handful of (well paid) programmer need to actually know these stuff. Most of us would just use what these people had created.  So I want to make a problem that you may actually encounter in your everyday life, in this case, parse an input whose format is inconsistent. The (suggested) solution for this problem involve using a regular expression, which you are more likely to use in real life than say… a binary search. Unfortunately it turns out, the C++ compiler on the server does not support C++11’s regular expression. So, you’ll need to use python or java to solve this problem. Admittedly, the constraint and explanation of the problem need more work, but hey, I have to start somewhere.

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

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){
        Pattern p = Pattern.compile("^[^:]+: *([0-9]+) *: *[^0-9\\.]*([0-9\\.]+) *$");

        double total = 0;

        while(in.hasNextLine()){
            String line = in.nextLine();
            Matcher m = p.matcher(line);
            if(m.matches()){
                int quant = Integer.valueOf(m.group(1));
                double amount = Double.valueOf(m.group(2));
                total += quant*amount;
            }
        }
        out.println(total);
    }
}

Problem D: Waleed and sum ranges by Amjad

This is a classical dynamic programming problem, the range sum problem. Its pretty well known and can be considered ‘elementary’ for dynamic programming, although it can be unclear how can this be considered dynamic programming. Some of you uses a segment tree to solve this, which do work, but overkill. The trick is, for each query, you should not actually count the numbers between the two range. That would be too slow. Instead, you first create an array of cumulative sum of the original array. With that, you can get the answer for each query in constant time by simply subtracting the cumulative sum at the end of the range with the cumulative sum at the start of the range. See the code for more information.

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

typedef long long int ll;
typedef pair<ll,ll> pii;
#define REP(i,n) for(ll i=0;i<n;i++)

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

int main(){
    int n;
    cin >> n;

    int nums[n+1];
    nums[0] = 0;

    REP(i, n){
        cin >> nums[i+1];
    }

    REP(i, n){
        nums[i+1] += nums[i];
    }

    int q;
    cin >> q;

    REP(iq, q){
        int l, r;
        cin >> l >> r;
        cout << nums[r] - nums[l-1] << endl;
    }
}

Problem E: Find the Distances by Ayesha

Have you ever found a problem where you think that there is no way that would work and then you read the tutorial and found a valid solution with a perfectly reasonable explanation? Well, if you did not solve this problem, then this is that kind of problem. First, the limit for A and B is actually much higher, up to the limit of 32 bit integer which is about 2*10^9. So, a normal sieve of aristotle would take too much memory and time. The limit specified which is 10^6 is the different between A and B. Naturally, you would think of iterating from A to B and checking for primes. But how would you check for the primes? You can’t create a sieve of size 10^9 to directly check if that number is a prime. The trick is, to determine if a number is prime or not, you can check if the number is divisible by any prime number lower that the square root of that number. If no prime number within that range can divide the number, the number must be a prime. There is a proof for it, but I’ll let you sleep on it. That means with all the prime numbers less than 2^18, you can effectively check if a number less than 2^32 is a prime number or not. Check the solution for more information. Fun fact: if I pass a long long to the isPrime function instead of an int, it would actually take twice the time, which means it may get TLE.

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

typedef long long int ll;
typedef pair<ll,ll> pii;
#define REP(i,n) for(ll i=0;i<n;i++)

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

#define SIEVE_SIZE 100001

bool sieve[SIEVE_SIZE];
vector<int> primes;
ll compcount = 0;

bool isPrime(int num){
    if(num <= 1) return false;
    int lim = sqrt(num)+1;
    for(int i=0;i<primes.size() && primes[i] < lim;i++){
        if(num%primes[i] == 0) return false;
    }
    return true;
}

void solve(ll a, ll b){
    pii lowest = {-1, INT_MAX-100};
    pii highest = {-1, -1};
    ll lowDiff = INT_MAX;
    ll highDiff = 0;

    ll prev = -1;
    ll next = -1;
    for(ll i=a;i<=b;i++){
        if(isPrime(i)){
            if(prev == -1){
                prev = i;
            }else{
                next = i;

                ll diff = next-prev;
                if(diff < lowDiff){
                    lowest = { prev, next };
                    lowDiff = diff;
                }
                if(diff > highDiff){
                    highest = { prev, next };
                    highDiff = diff;
                }

                prev = next;
            }
        }
    }

    if(lowest.first == -1){
        printf("No two primes exist\n");
    }else{
        printf("Closest = %d,%d and Furthest: %d,%d\n", lowest.first, lowest.second, highest.first, highest.second);
    }
}

int main(){
    REP(i, SIEVE_SIZE){
        sieve[i] = 0;
    }

    //cerr << "gen " << endl;
    for(ll i=2;i<SIEVE_SIZE;i++){
        if(sieve[i]) continue;
        //cerr << "gen " << i << endl;
        primes.push_back(i);
        for(ll j=i*i;j<SIEVE_SIZE;j+=i){
            sieve[j] = true;
        }
    }

    assert(isPrime(11));
    assert(isPrime(13));
    assert(isPrime(17));

    int a, b;
    while(cin >> a >> b){
        solve(a, b);
    }
}

Conclusion

This round is rather typical. Unfortunately, the turnup is quite low. Not sure what should I do to bring it up. Maybe I should giveaway my ‘mi band pulse’ to the winner which I never use anyway, if only I could find it… Again, I want to reiterate that 60% of this round’s participant (which is only 6 people) is from Palestine. So, only 4 participant is from Malaysia. Wait.. stdLn is a Bangladeshi, which means there are only 3 Malaysian here (assuming kinah_97 and sir_zia is a Malaysian)… hmm.. the terms “for Malaysia’s University student” is getting rather blurry. At least capayam won. Anyway, will we see an increase in participation next week? Or will we see an increase in Palestinian participation next week, forcing us to change Code Knights home country to Palestine? Either way, I still can’t find my ‘mi band pulse’. Tune in next week for Round 15 and for more… drama!… Or I’ll end up not making another analysis.. who knows?…

Dataset
Thats all folks! Good bye and Assalamualaikum.