SPOJ THRBL using Sparse Table

SPOJ THRBL : Catapult that ball is a pretty straightforward RMQ problem. I will formalize the problem in short below-

Given a array containing N integers, answer Q queries asking maximum element in the array lying within offset A and B.

Example:
Array = [8, 5, 3, 4, 7, 1, 9, 2, 6]
A = 1, B = 5 (0 based offset)
Then the subarray between A to B is [5, 3, 4, 7, 1] and the answer is 7.

You can study how to construct sparse table in this tutorial.

Defining entries in sparse table - ST[i][j] = maximum element in range [i, i+2^j]

The Sparse Table for above array will look like-

Once this table (call it ST) is constructed in O(n log n) time, you can answer queries in O(1) time.
Like for A=1, B=5 -

• First find the log base 2 of length of sub array. And subtract one from it. That is log(B-A+1) - 1 = log(5 - 1 + 1) - 1= 3 - 1 = 2. Let this quantity be L.
• Answer is simply maximum of ST[A][L], ST[B-2^L][L]

The customary code follows-

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

vector< int > v;
vector< vector< int > > st;

int log2(int x)
{
    int i=0;
    while (x){
        x>>=1;
        i++;
    }
    return i;
}

void constructsparsetable(int n)
{
    int c = log2(n);
    st = vector< vector< int > >(n, vector< int >(c));

    //Initialize
    for (int i = 0; i < n; i++){
        st[i][0] = v[i];
    }
    for (int i = 1; i < c; i++){
        for (int j = 0; j < (n - (1<<(i-1))); j++){
            st[j][i] = max(st[j][i-1], st[j+(1<<(i-1))][i-1]);
        }
    }
}

int querysparsetable(int a, int b)
{
    int l = log2(b - a + 1);
    return max(st[a][l-1], st[b-(1<<(l-1))][l-1]);
}

int main()
{
    int n, m, h, a, b;
    scanf("%d %d", &n, &m);
    v.reserve(n);
    for (int i = 0; i < n; i++){
        scanf("%d", &h);
        v.push_back(h);
    }

    constructsparsetable(n);

    int c = 0;
    for (int i = 0; i < m; i++){
        scanf("%d %d", &a, &b);
        if (querysparsetable(a, b-2) <= v[a-1])
            c++;
    }
    printf("%d\n", c);
}

8085 Assembler program in C++

In my Compiler Design lab, there was an assignment on making a 2 pass assembler for 8085 Micro processor. This assembler takes a 8085 assembly program (in mnemonics like MOV A, B) and outputs the corresponding Machine code in hexadecimal characters.
NOTE - This is just a lab work for demonstrating how a assembler works. It is not a real assembler for producing binaries.

First Download the 8085 zip

Files present in archieve-
1. assembler.cpp
2. assembler.h
3. test_assembler.cpp
4. symbols8085.txt
5. sample.asm
6. sample2.asm
7. README

Currently there are 208 commands for 8085 which can be processed. You can modify/add commands by editing "symbols.txt".

Instructions for Linux

1. First extract the contents of archieve in some folder. Lets call this folder WORK
2. Open terminal and change directory to WORK. To do this, run "cd WORK"
3. Now compile the files using "g++ -o 8085assembler test_assembler.cpp"
4. Test the sample file (sample.asm) using "./8085assembler sample.asm". You should get a string consisting of hexadecimal characters on a single line. For output to be displayed on seperate lines (for each instruction) use "./8085assembler sample.asm -n"

You can create your own 8085 input files. Just pass them as an argument to ./8085assembler
For any query, just post a comment.

Reasons for preferring C++ over Java in Coding competitions

Some time back, a question was asked on Codechef that "Why majority of programmers use C++ and not Java for submitting solutions". I posted an answer which was well received, here is my blog version of the answer.

Lets first understand the question-

It is a known fact that C++, C and Java dominate the domain of systems programming. And they are quite close in terms of popularity, in terms of usage. But the scene on programming competition sites like TopCoder, Codechef, SPOJ etc. is rather lopsided. Majority of programmers use C or C++. In fact for a typical problem C/C++ submissions are as high as 85%. Java getting second position at some ~10%, and rest is C#, python, pascal etc. You can research on your own, by going through All Submissions of Codechef.

So here are my reasons in point form-

1. Main reason is definitely the speed of execution. C or C++ is far ahead of Java in this. I won't elaborate as to why C++ is faster here.
2. Also in C++ you can get away with procedural style of programming, but Java forces you to write OO program. Which is unnecessary burden for programming on codechef.
3. No pointers? No pass by reference? Seriously this is a put off.
4. Top programmers are wicked! And C++ allows you to do wicked things. For example macros. Can you do this in Java?
5. C++ has STL, which is awesome. So argument "Java definitely has more inbuilt functionality than c++" is invalid. Whenever I see C++ beating C, I immediately understand that it has got to do with STL.
6. Taste. Yes a language is supposed to be tasty. Java syntax is rather mundane. C++ packs a lot of spicy operators.
7. Generics are not as powerful as templates. I don't know whether people use either of them on codechef, but it is a fact. With C++ templates, you can do a lot of work at compile time.
8. Also it is possible that C++ is taught before Java (as in my case). Which I think is again for a good reason.

I have omitted many points of difference between C++ and Java, because they are not relevant in Codechef programs are quite small. But 80% of time, Java losses. Which is yet another reason for programming in C++ on Codechef.
Note 1 - I am not suggesting that Java programmers should become C++ programmer. Code in the language, you are comfortable in. And both languages are good enough for all sorts of programming. This answer is merely an answer to the question.
Note 2 - Feel free to correct me, if I said anything wrong.

In addition, there is a saying "Rich gets richer, poor gets poorer", which I think is valid in this context. The problem setters and testers most of the time, test the solutions in C or C++. So the Time Limit for slower languages like Python, or the esoteric ones like Prolog, maybe unjust (even after giving them 2x to 6x time compared to C).

This post is not supposed to bash Java language, its just my true observations regarding C++ and Java.

Greatest Common Divisor (GCD) C++ Program

One of the most useful math function is Greatest Common Divisor (GCD), also known as Highest Common Factor (HCF). It takes 2 (or more) integers (positive or negative, but not zero) and returns the largest positive integer which divides the input integers without leaving remainder.

Examples-
* GCD(2, 4) = 2 because 2 divides both 2 and 4, and there is no other integer bigger than 2 which can do this.
* GCD(16, 24) = 8
* GCD(5, 6) = 1
* GCD(-2, 6) = 2

There are several ways to compute GCD as given on Wikipedia page, but we will use Euclid's algorithm, which is well suited for programming.

Note - Take care that the arguments are positive integers only. You can call GCD(abs(a), abs(b)) to ensure the negative integers are converted to positive.
The recursive version of Euclid's GCD function in C/C++

int gcd(int a, int b)
{
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}

The non-recursive version of Euclid's GCD function in C/C++

int gcd(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

Let's trace GCD(18, 88) to see how code works for recursive version-

GCD(18, 88) => GCD(88, 18) => GCD(18, 16) => GCD(16, 2) => GCD(2, 0) => 2