Sunday, January 23, 2011

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.

Saturday, January 22, 2011

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

Thursday, January 13, 2011

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

Thursday, January 6, 2011

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









publicprotectedno modifierprivate
Same classYesYesYesYes
Same package subclassYesYesYesNo
Same package non-subclassYesYesYesNo
Different package subclassYesYesNoNo
Different package non-subclassYesNoNoNo


I think these are the cases.

Tuesday, January 4, 2011

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]





NameAge
Pulok17
Payel20


[using]
NameAge
Pulok17
Payel20


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

Monday, January 3, 2011

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


Sunday, January 2, 2011

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.