Hablu

Standard

My first experience of problem setting. It feels good when you see people think about your problem and come up with better solutions than yours :P
This problem is about math and primes. The link is this.

UVa Easy Problem List

Standard

UVa(University of Valladolid) has one of the best online judges to start online problem solving. Here is a list of some easy problems from UVa for newbies.

100, 119, 133, 136, 146, 272, 401, 409, 412, 440, 444, 446, 458, 468, 476, 488, 489, 490, 492, 494, 498, 499, 541, 575, 579, 583, 729, 900, 913, 10035, 10038, 10055, 10071, 10082, 10110, 10222, 10235, 10327, 10346, 10370, 10424, 10469, 10591, 10696, 10699, 10789, 10812, 10922, 10924, 10929, 10931, 10970, 11152, 11172, 11185, 11192, 11219, 11233, 11462, 11530, 11727, 11764, 11799, 11804, 11805, 11827, 11854, 11875, 11900, 11917, 11934, 11936, 11942, 11984, 11988, 11991, 11995, 12015, 12149, 12149, 12149, 12149, 12149, 12149, 12372, 12372, 12372, 12372, 12372

Kruskal’s Minimum Spanning Tree Algorithm

Standard

Kruskal’s algorithm is the best and probably fastest option if you’re urging to form a subgraph of a graph connecting all nodes. Some implementations are shown.

Minimum Spanning Tree
To form an MST(Minimum Spanning Tree) follow this procedure,

1. Begin with a connected graph G.
2. E is the set of all edges of different weights, from G.
3. Sort edges of E in the ascending order of their weights.
4. Go through each member(edge) of E and see if the nodes of that edge is already connected or not.
5. If they aren’t connected, connect them and include that member of E(edge) int MST.
6. Continue this process untill you’ve got n-1 edges(in case of n nodes).

An implementation in C++ using Disjoint Set data structure, is shown

#include <cstdio>
#include <algorithm>
#define MAX_node 100000
using namespace std;

struct edg{
	int a,b,w;
	bool operator < (const edg &b) const{
		return w<b.w;
	}
}E[MAX_node+1];

int Prev[MAX_node+1];
int parent(int a){
	if(a==Prev[a]) return a;
	return Prev[a]=parent(Prev[a]);
}

int main(){
	int node,edge;
	while(scanf("%d%d",&node,&edge)){
		
		int TOTAL=0;
			
		for(int i=1;i<=node;i++) Prev[i]=i;//*
		for(int i=0;i<edge;i++) scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].w);//**
		
		sort(E,E+edge);//***
		
		for(int i=0; i<edge; i++ ){
			int u=parent(E[i].a);//****
			int v=parent(E[i].b);
			
			if(u!=v){
				TOTAL+=E[i].w;
				Prev[u]=v;//*****
			}
		}
		
		printf("Total Cost of MST %d\n",TOTAL);
	}
	return 0;
}

/*
 * Making each node it's own parent
 ** Input edges in the format "node1 node2 weight"
 *** Sorting them in the ascending order of weight
 **** Find the current parent of a and b
 ***** If the nodes of that edge is not connected yet, Connect them.
 */

if you don't know Maximum possible number of nodes, then just use a vector(which is a bit slower) of type 'edg'.

Related Problems
MST(spoj)
Dark Roads(UVa)
Audiophobia(UVa)
Connect the Campus(UVa)
Highways(UVa)



Maximum Spanning Tree
To get a maximum spanning tree, the procedure is almost same. The only difference is that, you got to sort members of E in the descending order of their weights.

Related Problems
Heavy Cargo(UVa)



Second Best Minimum Spanning Tree
There may be some other better procedure to find the second best MST, but this is the one I've used.
1. First form an MST of graph G, and mark the edges which formes the MST.
2. Then for each member edge of the MST, Form another MST without using that particular member.
3. Thus, u need to form n-1 (in case of n nodes) 'another' MSTs and consider the minimun among them.

Related Problems
Is There A Second Way Left ?(UVa)
ACM contest and Blackout(UVa)

Installing Elements for Compiz Fusion

Standard

Elements is a plugin for Compiz Fusion 0.7.4 which integrates all the features of the popular Snow, Autumn, Fireflies, and Stars plugins, plus an all new feature, Bubbles. Written from the ground-up with only open source software, Elements is designed to be free, fast, and fun. It’s also fully customizable. You want flower petals falling in spring? Draw the petals and use them with the Autumn feature. Want to have toasters flying towards you at warp speed? Take a picture of your toaster and use it with the Stars feature. Feel really adventuresome? Take a look at the code and make it your own. Elements is completely free and released under the GNU General Public Licence (GPL).

Download Elements script from here

Once you downloaded you need to install this using the following command

bash ./elementsinstall.sh

This will complete the installation

Uninstall Elements Plugin

If you want to uninstall elements plugin follow this procedure

cd ~/.elements
sudo make uninstall
make clean
compiz --replace &amp

ইউটিউব কথন

Standard

টিউব সাইটগুলোর মধ্যে ইউটিউব সবসময়ই শীর্ষে ছিল। ভিডিও স্ট্রিমিংয়ের এই আসাধারন সাইটটি ব্লগারদের জন্যও অনেক গুরুত্ব বহন করে। এই পোস্টে ইউটিউব ব্যাবহারের কিছু “টিপস অ্যান্ড ট্রিকস” দেয়া হল।




ভিডিও ডাউনলোড

ইউটিউব থেকে ভিডিও ডাউনলোডের কম করে হলেও হাজারখানেক নিয়ম আছে। সবচেয়ে জনপ্রিয় হচ্ছে OK পদ্ধতি।

ধরুন আপনি http://www.youtube.com/watch?v=5baDknt6Z7w এই ভিডিওটি যদি ডাউনলোড করতে চান তাহলে এড্রেসবারে youtube কথাটির আগে OK লিখে Enter চাপলেই হবে। অর্থাৎ http://www.OKyoutube.com/watch?v=5baDknt6Z7w লিখে Enter চাপলেই দেখবেন ভিডিওটি ডাউনলোড হচ্ছে।

এরকম আরও নিয়মের মাঝে একটি হচ্ছে OK এর জায়গায় kiss লিখা। অর্থাৎ যদি http://www.youtube.com/watch?v=5baDknt6Z7w ভিডিওটা ডাউনলোড করতে হয় তবে এড্রেসবারে http://www.youtube.com/watch?v=5baDknt6Z7w লিখলেই চলবে!

আপনি যদি কোন নির্দিষ্ট ফরম্যাটের ভিডিও ডাউনলোড করতে চান, তাহলে youtube000 পদ্ধতিটি আপনার উপযোগি। এখানে, যদি লিঙ্ক হয় http://www.youtube.com/watch?v=5baDknt6Z7w তাহলে ডাউনলোডের লিঙ্ক হবে http://www.youtube.com000/watch?v=5baDknt6Z7w । এখানে flv, mp4 , 3gp তিনটা ফরম্যাট থেকে আপনাকে বেছে নিতে হবে ।

আর আপনার যদি হাইকোয়ালিটি ভিডিও(HQ/HD) প্রয়োজন হয়, তাহলে youtube এর জায়গায় keephd লিখলে অর্থাৎ http://www.youtube.com/watch?v=5baDknt6Z7w এটা ডাউনলোড করতে http://www.keepHD.com/watch?v=5baDknt6Z7w লিখলে আপনি Flash, For mobile, Mp4, HQ MP4(720p), HQ MP4(1080p) ফরমাটের ডাউনলোড লিঙ্ক পেয়ে যাবেন।

এই সুবিধাগুলো পেতে হলে অবশ্যই আপনার কম্পিউটারে জাভা থাকতে হবে। না থাকলে, সেটি পাবেন এখানে




হাই কোয়ালিটি ভিডিও দেখা

ইউটিউবের সব ভিডিও হাই কোয়ালিটিতে থাকে না। কিন্তু আপনি ইচ্ছা করলে তা হাই কোয়ালিটিতে দেখতে পারেন। এর জন্য আপনাকে যা করতে হবে তা হচ্ছে,
url এর শেষে ‘&fmt=18′ অথবা ‘&fmt=22′ যোগ করতে হবে।

উদাহরনঃ http://www.youtube.com/watch?v=Lm3mS6rvsv তে ভিডিও টি সাধারণ কোয়ালিটিতে আছে এক্ষেত্রে আপনি http://www.youtube.com/watch?v=Lm3mS6rvsv&fmt=18 অথবা http://www.youtube.com/watch?v=VT4E_BkEx5k&fmt=22 তে হাই কোয়ালিটি ভিডিও পাবেন।




হাই-কোয়ালিটি ভিডিও এমবেড করা

এর জন্য শেষে “&ap=%26fmt=18″ অথবা “&ap=%26fmt=22″ যোগ করতে হবে।




ভিডিওর নির্দিষ্ট অংশ দেখা

ধরুন, আপনার পুরো ভিডিওটি দেখার দরকার নেই। ১ মিনিট ২২ সেকেন্ড পর থেকে দেখতে চান। সেক্ষেত্রে url এর শেষে #t=01m22s (#t=XXmYYs for XX mins and YY seconds) যোগ করুন।




ভিডিওর নির্দিষ্ট অংশ এমবেড করা

এটি ব্লগারদের জন্য খুবই গুরুত্বপুর্ন। ধরুন আপনি একটি ৩০ মিনিটের ভিডিও এমবেড করেছেন, কিন্তু সেটির শেষ ৫ মিনিট আপনার পোস্টের প্রয়োজন। এটিকে খুজে বের করতে পাঠকদের ( এমনকি আপনাকেও ) ঝামেলা পোহাতে হয়। এর ছেয়ে ঢের ভালো ভিডিওটির ২৫ মিনিট ( ২৫*৬০=১৫০০ সেকেন্ড ) পর থেকে এমবেড করুন। সেজন্য আপনার url এর শেষে ‘&start=1500′ যোগ করলেই চলবে।




এমবেডেড ভিডিও অটোপ্লে করা

কোন সাইটে কোন ভিডিও এমবেড করার পর, সাধারণত ভিডিওর উপর ক্লিক না করা পর্যন্ত শুরু হয় না। শেষে ‘&autoplay=1′ যোগ করলে পেজ লোড হবার সাথে সাথে ভিডিও প্লে হওয়া আরম্ভ করবে। আর ক্লিক করার দরকার হবে না।




এমবেডেড ভিডিও অটোমেটিক্যালি রি-প্লে করা

‘&loop=1′ যোগ করে আপনি এটা করতে পারেন। অর্থাৎ ভিডিওটি দেখা শেষ হয়ে গেলে এটি আবার শুরু হবে। আবার শেষ হলে আবার, তারপর আবার :D




রিলেটেড ভিডিও ডিজেবল করা

ইউটিউবের ভিডিও শেষ হবার পর পরই বিরক্তিকর অনেকগুল রিলেটেড ভিডিও এসে হাজির হয়। এক্ষেত্রে ‘&rel=0′ যোগ করলেই রিলেটেড ভিডিও ডিজেবল।




এমপিথ্রি ডাউনলোড

এই সাইটে গিইয়ে youtube link টি দিলেই সেখান থেকে mp3 ডাউনলোড লিঙ্ক পাওয়া যাবে।




লেখাটি পড়ার জন্য ধন্যবাদ :)।

Project Euler Problem : 48

Standard

The problem statement says

The series, 1^(1) + 2^(2) + 3^(3) + … + 10^(10) = 10405071317.

Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + … + 1000^(1000).

Though seems like it can’t be solved without using bignumber(in c/c++), The bignumber solution takes much more time than we can say moderate for a computer program(same in JAVA). Actually it needs some modular operations. You need the last ten digits and to calculate them you don’t need to calculate all the digits. See my approach

#include <stdio.h>

long long power(int a);

int main()
{
	int i;
	long long ans=0;
	
	for(i=1; i<=1000; i++)
	{
		ans=(ans+power(i))%10000000000000;
	}
	
	ans=(ans%10000000000);
	
	printf("%lld\n",ans);
	
	return 0;
}

long long power(int a)
{
	int i;
	long long ans=1;
	
	for(i=1; i<=a; i++)
	{
		ans*=a;
		ans=ans%10000000000000;
	}
	
	return ans;
}

Fractals

Standard





Fractal? What’s That?

A point has dimension 0, a line has dimension 1, and a plane has dimension 2. But did you know that some objects can be regarded to have “fractional” dimension?

You can think of dimension of an object X as the amount of information necessary to specify the position of a point in X. For instance, a block of wood is 3-dimensional because you need three coordinates to specify any point inside.

Fractal

The Fractal ( Cantor set ) has fractional dimension! Why? Well it is at most 1-dimensional, because one coordinate would certainly specify where a point is. However, you can get away with “less”, because the object is self-similar.

In Mathworld Fractals are defined as

an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales.
This is a fancy way of saying that a fractal is a geometrical figure that has fractional dimension (non integer) including the same pattern, scaled down and rotated, and repeated over and over.
If you still can’t visualize the aspect ( just like almost every first timers ) just peek here.

Fractal

Fractals are said to have a unique property named self similarity. We see the same image again when we “zoom” in and examine a portion of the original.





How Everything Started

Gaston Julia(1893-1978) was a French mathematician who published a book on the iteration of rational functions in 1918. Before computers, he had to draw the sets of functions by hand. These types of fractals are now called Julia sets. His masterpiece on these sets was published in 1918. His interest apparently was piqued by the 1879 paper by Sir Arthur Cayley called The Newton-Fourier Imaginary Problem.

Broccoli fractal

Benoit Mandelbrot (1924- ) is an emeritus professor at Yale University. He used a computer to explore Julia’s iterated functions, and found a simpler equation that included all the Julia sets. Mandelbrot set is named after him.

Waclaw Sierpinski (1882-1969) was a Polish mathematician. His work predated Mandelbrot’s discovery

of fractals. He is known for the Sierpinski triangle, but there are many other Sierpinski-style fractals.

Coastline fractal

In 1918, Bertrand Russell had recognised a “supreme beauty” within the mathematics of fractals that was then emerging. The idea of self-similar curves was taken further by Paul Pierre Levy, who, in his 1938 paper Plane or Space Curves and Surfaces Consisting of Parts Similar to the Whole described a new fractal curve, the Levy C curve. Georg Cantor also gave examples of subsets of the real line with unusual properties – these Cantor sets are also now recognized as fractals.





Properties of Fractals

The essential and most fascinating property of any fractal is its non integer dimension and complexity. The rule for

Snow flake fractal

creating one is essentially simple – A-Level mathematics no more. But the resulting picture has suprising depth. If you zoom in on any part of a fractal, you find the same amount of detail as before. It does not simplify. You find echoes of larger shapes appearing within smaller parts of the shape.

If you zoom in further, the same thing happens. You never seem to get down to the skeleton of the picture, just detail upon detail. Look here or here for illustrations of this. There are many computer programs available for you to do this yourself.
Fractint is probably the best. It is freely available here.





Fractals in Life, Nature or may be beyond that

Coastline fractal in midwest USA

Nature is full of fractals. From a tiny Broccoli, crystals, peacock tail to clouds, snow flakes and blood vessels, approximate fractals are easily found in nature.

Butterfly Effect


Sea shell, urchin,thunder ightnings are also fractals. The Coastline fractal in midwest USA is a surprising example of them as well.

The Butterfly Effect is most succesfully explained by Fractals.

Even the internet (world wide web) is fractal leading us to great links having medium sized links and furthur.
Learn more about fractal nature of internet here.

Butterfly Effect

According to this the universe isformed in a fractal structure, and our cosmos might be a particle, too.
We might be living in a particle. Such particles as the cosmos may exist innumerably.
And there might be a gigantic universe, and it is not the end of all there is. In fact, it might be another particle in another greater universe.