A C++ Mistake

Consider this piece of code:

int f = 10;

int ff() {
    return f = 5;
}

int main() {
    printf("%d %d\n", ff(), f);
    return 0;
}

As I have expected it to print "5 5" (I was using Dev C++) so did I get, but I didn't know it was wrong until the judge showed me the famous and fabulous "WA". The correct output is "5 10", because, function parameters are though of to be similar as assignment operation and should be performed from right to left. Now it makes sense. But got some penalty for stupid yet adorable Dev C++. However, I've learnt this... that's the good side of it! So, you too be careful if you don't know that already.

Huffman's Code

Here is a program I have written this afternoon, for one of my old friends. Basically, it's a simple one, reads character values and their frequency and generate Huffman Coding for each character. Not going to describe here what is huffman's algorithm, but it is widely used for data compression and stuff...

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

vector< pair< string, int > > V;

class Node {
public:
    Node *left, *right;
    int weight, ch;
    Node() {}
    Node(int _w, int _c) : weight(_w), ch(_c) { left = right = NULL; }
    ~Node() {}
};

class comp {
public:
    bool operator() (const Node &a, const Node &b) {
        return a.weight > b.weight;
    }
};

void generate(const Node *a, char *code, int depth) {
    if(a->left == NULL && a->right == NULL) {
        code[depth] = 0;
        V.push_back(pair< string, int > (code, a->ch));
        return;
    }
    if(a->left != NULL) {
        code[depth] = '0';
        generate(a->left, code, depth + 1);
    }
    if(a->right != NULL) {
        code[depth] = '1';
        generate(a->right, code, depth + 1);
    }
}

int main() {
    priority_queue< Node, vector< Node >, comp > Q;
    int ch, weight;
    char code[100];

    // read ascii and frequency
    while(cin >> ch >> weight) {
        Q.push(Node(weight, ch));
    }

    // build 2-tree
    while(Q.size() > 1) {
        Node *a = new Node;
        *a = Q.top(); Q.pop();
        Node *b = new Node;
        *b = Q.top(); Q.pop();
        Node c(a->weight + b->weight, 0);
        c.left = a, c.right = b;
        Q.push(c);
    }

    // traverse tree to generate code
    generate(&Q.top(), code, 0);

    // display character and code
    for(int i = 0; i < (int)V.size(); i++) {
        cout << V[i].first << " --> " << V[i].second << endl;
    }
    return 0;
}

Writing compressor decompressor is also easy, just make sure, you use 1 bit for each '0' or '1', not 1 byte :p

Pollard's Rho in Java

This is a Pollard's Rho implementation in java. Not very fast, but works for uva online judge. The reason behind using java is the default support of the BigInteger class.

import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.*;
import java.util.*;

public class PollardRho {

    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE  = new BigInteger("1");
    private final static BigInteger TWO  = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();

    static Vector<BigInteger> v = new Vector<BigInteger>();

    public static BigInteger rho(BigInteger N) {

        BigInteger divisor;
        BigInteger c  = new BigInteger(N.bitLength(), random);
        BigInteger x  = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

        do {
            x  =  x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    public static void factor(BigInteger N) {

        if (N.compareTo(ONE) == 0) return;

        if (N.isProbablePrime(20)) {
            v.add(N);
            return;
        }

        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }

    public static void main(String[] args) throws Exception {

        String string = "";
        InputStreamReader input = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input);

        while(null != (string = reader.readLine())) {
            BigInteger N = new BigInteger(string);
            v.clear();
            factor(N);
            Collections.sort(v);
            for(int i = 0; i < v.size(); i++) System.out.println(v.get(i));
            System.out.println();
        }
    }
}

I have seen this piece of code years ago somewhere in the internet, but can't remember exactly where. So, I will be glad if anyone can comment/mail me the original source. However, for spoj, I need to write a much much better version of this in C++ :( Exam sucks life...

Java Access Modifiers

Overview:

There are 4 types of access modifiers which are applicable to the members of a class, i.e. the variables and methods. Namely:

1. Public


2. Protected


3. Default or no modifier


4. Private

However, for a class declaration, protected and private are not allowed, and in a .java file, there can be only one public class, the rest must have been declared with default access. Well, we are more concerned about the access modifiers for the members of a class, as they are quite confusing on some aspects. Each of the four types is described below:

Public

As we can guess, the public members are visible from anywhere regardless of which package or file it is in. Then can be accessible from any other class of same or another package using just a '.' {dot} operator with the class reference.

Protected

This is probably most confusing modifier of java. Protected members are similar as members having default modifier, however, the difference is, protected members can be accessible outside the package it is in through inheritance, i.e. extending the parent class.

Default or no modifier

When no modifier is specified explicitly, it becomes the default modifier. Default modifiers can be thought of as a subset of the Public modifier. As, they are essentially same as Public when they are in the same package. However, members with default modifiers are not accessible from anywhere outside the package the class is in. When we don't specify a package, still there is a default package maintained by the java environment.

Private

It is also straight-forward as public, a private member can not be accessed from anywhere out side the class it is in.

More on "protected"

There are something more notable regarding protected type. As they are often very confusing with it's two near relatives, default and public.

Say, we have a "protected int x" in "class A" in package "pack1". And we derived "class B" from "class A" in package "pack2". In this case, variable x in "class B" is known as if it is just a member of "class B". so, in "class B", we can write in a method "System.out.println(x);". But note, we can't do this: "System.out.println(new A().x);". So, if the subclass is outside the package, we can't access it's parent class' protected member by a class reference. There is another interesting thing, Say, we have another "class C" which is extending the above "class B", then in "class C", we can't use 'x' as when a derived class have some protected member, it becomes a private data in the derived class, so farther extensions can not use those variables anymore.

Summery of the above

	public	protected	no modifier	private
Same class	Yes	Yes	Yes	Yes
Same package subclass	Yes	Yes	Yes	No
Same package non-subclass	Yes	Yes	Yes	No
Different package subclass	Yes	Yes	No	No
Different package non-subclass	Yes	No	No	No

I think these are the cases.

Blogger Spacing Problem

Spacing problems in blogger blogs

Blogger blogs have some serious spacing issues, especially with some specific html tags, for example, if you use a <table> tag on your post, you will see it leaves a huge blank spot before and after it. Same things might happen for your <pre> or <p> tags. This is probably because blogger treats every line breaking white space to be a <br/>. However, we can easily overcome this by adding a simple css script in the post (So, we will be using the "Edit Html" option, and in my opinion, the Rich Text Editor is shit. If you are not familiar of what we are talking about, don't be afraid, you'll see, your posts are going to be just fine).

Just add the following css in your post to create a class, and name it whatever you like, I'll call it 'nobr':

<style type="text/css">
.nobr br { display: none; }
</style>

Don't worry, it will not be visible in your actual post. Now, wrap around the elements for which you don't want to see extra line gaps before and after it using this class:

<div class="nobr">
<!-- your elements -->
</div>

Here is an example for using a <table> tag using and not using the above "nobr" class:
[Not using]

---

Name	Age
Pulok	17
Payel	20

---

[using]

---

Name	Age
Pulok	17
Payel	20

---

So, the spacing problem is significantly reduced. Hope you'll give it a try!

Story of Centipede

The centipede was very good at walking with its hundred legs. It never spent a thought on just how it could walk. Until one day, when a big black bug asked the centipede “How can you manage to walk with all those feet? Don’t you find it hard to coordinate their rhythm?” The black bug already left, when the centipede was still sitting down, pondering how it could walk, wondering, and (for the first time in his life) even worrying a little bit. From that day on, the centipede couldn’t walk anymore.

So you better not think too much if you want to achieve something.

SPOJ - POSTERS

138. Election Posters

Although this problem is actually a good data structure problem, which is meant to be solved by range tree, but as that would need a trick. We only have 40000 nodes so total of 80000 points, but actual range is huge (10^7) for range trees. So, we can map the points so that they span over the minimum range (i.e. compress them). Sounds pathetic, right? However, there are easier ways to solve this.

By using STL set, you can make the problem pretty simulation type. Lets consider a set which contains the ranges, but not as given in input. At any moment, the set will represent the wall at that time, i.e. only visible ranges (so they must be mutually exclusive).

Now, whenever we need to add a new range, we find the leftmost poster (or piece of poster still visible) which must fall under the current one (probably you already got it, it's called lower_bound) and the rightmost poster segment that must fall under it. All the segment between these two segments will be covered, so we remove them from set. Now, we just again insert new left fragment, new right fragment and the new range... that simple it is!

Finally, we can keep and index with each segment so that we can calculate the number of actual different segment at the end of the day :)
For more clarification, consider the sample case:

5
1 4
2 6
8 10
3 4
7 10

The states of the set are shown after each input:

1 4
first entry
{(1,4)}

2 6
{1,4) is leftmost and rightmost at the same time (according to above discussion)
So, we remove it and insert new ranges:
{(1,1),(2,6)}

8 10
no conflict
{(1,1),(2,6),(8,10)}

3 4
conflicts with (2,6) (left and right both)
{(1,1),(2,2),(3,4),(5,6),(8,10)}

7 10
conflicts with (8,10)
{(1,1),(2,2),(3,4),(5,6),(7,10)}

Finally, segments with different id:
(1,1), (2,2), (3,4), (7,10). Note, (2,2) and (5,6) should have same id.

It's good if you have understood what to do, and it's even better if you don't, cause you should solve your problems on your own :p

CSE 202 Pseudo Codes 2

Insert ans Delete operation on a Singly Linked List

Each Item on a Singly Linked List is formed with two fields, Info (which contains the data for the node) and Next (which is a pointer to the next Item). A pointer 'head' points the start of the linked list, and in case the linked list is empty, head has the value 'null'. Pseudo-codes for insertion and deletion at nth position is shown below:

Insert Procedure

Insert ( head, n, item )
    if n = 1 then
        temp := new Node;
        Info[temp] := item, Next[temp] = head;
        head = temp;
        return;
    ptr := head, pos := 1;
    repeat while pos + 1 < n and Next[ptr] != null
        ptr := Next[ptr], pos = pos + 1;
    temp := new Node;
    Info[temp] = item, Next[temp] = Next[ptr];
    Next[ptr] = temp;
    return;

Delete Procedure

Delete ( head, n )
    if head = null then return;
    if n = 1 then
        temp := head, head := Next[head];
        free temp;
        return;
    ptr := head, pos := 1;
    repeat while pos + 1 < n and Next[ptr] != null
        ptr := Next[ptr], pos := pos + 1;
    if Next[ptr] = null then return
    temp := Next[ptr], Next[ptr] = Next[temp];
    free temp;
    return;

Both of them handle all the possible cases on a singly linked list.