Inclusion Exclusion

August 22, 2010

I am sure that most of you have heard of the inclusion exclusion principle.  If not then I suggest that you either head over to Google or Wikipedia.  It is a really useful technique with many applications; even to this day I am still discovering new ways in which it can be used.

In this post I will outline a partial solution to the following problem located on SPOJ, PGCD.

The first thing you should notice is that the answer to (a,b) will be the same as the solution to (b,a).  This is because of the symmetry of the gcd(\cdot,\cdot) operation, thus suppose that a\le b.

Suppose that there are a columns in our gcd table.  We will find how many primes there are in each column.  Suppose that there are m rows, and we are looking at column n=p_1p_2\cdots p_r, where p_1,p_2,\cdots,p_r are distinct primes.  I’m not going to consider the case where a prime factor is repeated, though I have a feeling that the solution below should still work.

First we find how many multiples there are of each prime between 1\ \mbox{and}\ m.  This is just

\displaystyle\sum_{i=1}^r\left\lfloor\frac{n}{p_i}\right\rfloor

But what about the multiples of say, p_1p_2?  Well they were counted twice, and their entry in the table is not going to be a prime (you can easily convince yourself of this fact).  So we just subtract them out twice, leaving our answer as

\displaystyle\sum_{i=1}^r\left\lfloor\frac{n}{p_i}\right\rfloor-\sum_{1\le i<j\le r}2\left\lfloor\frac{n}{p_ip_j}\right\rfloor

Now what about the divisors of n with exactly 3 prime factors?  Their multiples have been removed too many times, thus we need to add them back.  If we continue this way we see that we will be using inclusion exclusion.

So to solve this we can use the following code.


#include bitset
#include vector

int answer=0;
bitset PIE;
for(int i=2 to n;++i)
{
	vector prime_factors=factor(i);
	int r=prime_factors.size();
	for(int cnt=1 to 2^r - 1;++cnt)
	{
		PIE=cnt;//express cnt in base 2 and store in PIE
		int ones=PIE.count();//the number of 1s in our bit string
		int p=1;
		for(int j=0 to prime_factors.size() -1;++j)
			if(PIE[j])
				p*=prime_factors[j];
		if(ones&1)//there are an odd number of 1s
			answer+=(ones*(m/p));
		else//there are an even number of 1s
			answer-=(ones*(m/p));
	}
}

This isn’t totally legal code because I had to paste it into HTML so the less than and greater than signs disappear and I don’t want to waste the time to fix it (even though I know how to).
For those of you that don’t know the bitset is just a string of 1s and 0s. When I did PIE=cnt I basically set it so that the bit string was equal to the base 2 representation of cnt. Using this method we can get all possible combinations of the prime factors.
The code can easily be converted to Java since I think it too has something similar to a bitset. If your language of choice doesn’t have a bit set, no need to worry. You can just get the base 2 representation on your own (it’s not that hard, trust me).
WARNING: This approach will only be feasible if each number doesn’t have too many prime factors. Not the case with the problem on SPOJ since each number can be decomposed into the product of at most 23 primes, and at most 9 distinct primes. So I’m not sure if the time limit will allow you use this method, I haven’t tried, but please let me know if you do.

Advertisements

Eclipse

July 16, 2010

I’m sure that you have heard of Eclise.  If not then all you need to know is that it is a very popular (and for a good reason) IDE mainly for Java.  However, it does also have C/C++ support, but it is mostly used with Java.

As you know, I’m not big on programming in Java.  But I recently purchased a Nexus One phone, and the IEEE SECon got me a little interested in Android application development.  I don’t plan for anything I make to be widely distributed, but rather just for personal use.  In any case, I would still need a place to create my programs.  Sure this can be done with a normal text editor and the command line but why bother with that when Eclipse and the Android SDK make it so simple?

I’m going to talk about getting and installing Eclipse onto you system (which I will assume to be Ubuntu).  Sure you could just run sudo apt-get install eclipse but this way assumes that you are using the OpenJDK version of Java and not Sun’s. So if you are using SunJava, which it seems most people do, then this how-to is for you.

First head over to the Eclipse site and download the IDE. To find the site just use Google and then do some reading and clicking, so there is no need for me to post a link. If you can’t get past this step then you probably shouldn’t be thinking about using Eclipse.

Next we will open the package you have just downloaded and then move it to the /opt directory. To do this just run the following sequence of commands:

tar xzf <filename>
sudo mv eclipse /opt/eclipse
cd /opt
sudo chown -R root:root eclipse
sudo chmod -R +r eclipse
sudo chmod +x `sudo find eclipse -type d`

The chown command changes the owner of a file/directory, if you have been reading this blog then you should be able to figure out what the other commands do.

Next we will add eclipse executable to your path.

sudo touch /usr/bin/eclipse
sudo chmod 755 /usr/bin/eclipse
sudoedit /usr/bin/eclipse

then add this to the file

#!/bin/sh
#export MOZILLA_FIVE_HOME="/usr/lib/mozilla/"
export ECLIPSE_HOME="/opt/eclipse"

$ECLIPSE_HOME/eclipse $*

I’m not all to sure exactly what the touch command does but you can look that up yourself (either online or with man).

Finally, the “most important” part; creating a GNOME-menu icon. This is something that would normally be done when you use the apt-get method.


cd /usr/share/applications
sudo nano eclipse.desktop

And enter the following into the created file;

[Desktop Entry]
Encoding=UTF-8
Name=Eclipse
Comment=Eclipse IDE
Exec=eclipse
Icon=/opt/eclipse/icon.xpm
Terminal=false
Type=Application
Categories=GNOME;Application;Development;
StartupNotify=true

All the stuff entered into the file makes perfect sense, so if you ever wanted to make a menu item for any other program you now know how.

All of these steps can be found at http://flurdy.com/docs/eclipse/install.html.


No Upgrade For Me

September 1, 2009

Well I have finally moved into my place and have discovered 2 things.

1: My desktop is dead…well at least to a point where a Linux Live CD won’t help.

2: My Data Structures & Algorithms class will be using Java 1.5

Well #2 is more of a annoyance than a real problem (I use Java 1.6).  As for #1 I was planning to use my desktop to try and update Ubuntu.  It used to run 8.10 before it died (I’m sure it’s just some simple hardware problem).  Well at least most of my stuff from there is backed up elsewhere.  Guess it pays off to be paranoid.  Besides it is probably a good idea to do that before even attempting to upgrade you system, no matter how fool proof the process is said to be.

As things are now I will either buy another desktop around January 1, 2010 or a new laptop around that same time.  Either way, I will be putting Ubuntu on it, hopefully a 32 bit version.  The only real pain I for see is getting the wireless card to work, but other than that everything I need to change I have previously documented the process for; either on this blog or another location.

Guess in my next post I’ll talk about one of my biggest peeves of working with a functional Ubuntu installation.  The default terminal size.


See My Coffee: A C and Java tale

August 13, 2009

Anyone with half a brain can tell you that (pick one: C/C++ or Java) is vastly superior to (pick the other). The only problem is that I don’t know all that much about Java. So instead of doing the obvious thing and talking about how “C/C++ is better than Java”, I am going to talk about a few aspects of C++ that annoy the hell out of me.

Fist off why would you have a ‘long‘ data type if it is not required to be any bigger than a regular ‘int‘?  All that is specified is that both int and long must be at least 32bits. Thus if you want to get a 64bit integer you have to use ‘long long‘ (or __int64 if you are using Microsoft Visual C++).  This should really be addressed, and hopefully sometime soon. Though I suppose there are more pressing issues.

Second, I don’t know about you but no one ever told me why you it is poor C++ programming to include a class function’s definition inside the class.  It wasn’t until I was reading Thinking in C++ Vol.1 that it was made clear.  When you do this, the compiler will inline your function.  This means that everywhere you use it the compiler will reproduce the written code, instead of making a function call.  Sure, for small functions this is alright, but for larger ones it can add to code bloat, thus possibly resulting in a slower program.  The “standard” for determining if a function is small is, “does it take up more than one line of code?” If so then don’t inline.

Why are struct and classes the same?  The only difference is that the members of a class default to private, while those of a struct default to public.  Oh well, until they change this I will continue to use struct and then specify private/protected/friend when needed.

Finally, the STL is not quite as vast as the Java API.  But that can be attributed to what the languages were designed for, so I suppose I can live with this “fault”.