[my_notes]

Thesis Notes

2011-09-28T16:20:00.003+06:00

$ F_{0}=0 \\ F_{1} = 1\\ F_{n} = F_{n-1} + F_{n-2}$

2011-02-28T19:44:00.001+06:00

Useful Links

2010-12-08T02:02:00.001+06:00

PHPGraphLib is a lightweight PHP-based graphing library that creates slick PHP graphs for incorporation into a website or application. PHPGraphLib is free to use for personal use, and can be used for a small fee commercially.
You can now use the PHPGraphLib Remote API. No need to download the client library - create graphs remotely for use on your website or application. Use any language! PHP is not necessary!

http://stackoverflow.com/

Excursion Poster 2010

2010-10-16T04:08:00.000+06:00

problem set analysis

2010-08-31T22:44:00.005+06:00

problem C: reduceIt
though this was the easiest problem in the problem set, i kept the input constraints "tricky" . all is needed to pass the hidden test is to use int64 calculation. :) here goes a sample solution-

typedef unsigned __int64 ull;

ull gcd(ull A,ull B)
{
    if(B == 0) return A;
    else return gcd(B, A%B);
}

pair <ull,ull> reduce_it(ull N, ull D)
{
    return make_pair(N/gcd(N,D),D/gcd(N,D)); 
}

problem A: schoolMath

trial division is enough for this problem. only scrap's solution passed the hidden cases. other codes failed at when n itself is a prime number.

problem D:nthElement

we can do a binary search, it's fast enough when n is bigger, i think. there exist a O(1) solution. know it? share it here...

problem B

problem E:ITCityRajshahi

simple graph search problem. a simple dfs will do. here's the scrap's solution for reference.. as max N is 99
so adj matrix as in scrap's approach is enough. but if max N would 10^3 !!! matrix would be impractical.
here's a simple approach to handle that :

bool vis[LIM];
vector <int> adj[LIM]; //to represent the graph

void play(int at)
{
 queue <int> Q;
 vis[at] = true;
 Q.push(at);
 while(!Q.empty()){
  int cur = Q.front();
  Q.pop();
  int t = adj[cur].size();
  for(int j = 0; j < t; j++){
   int t = adj[cur].at(j); 
   if(!vis[t]){
    vis[t] = true;
    Q.push(t);
   }
  }
 }
}


int different_network(int N)
{
 fill(vis, vis+N+1, 0);
 int cnt = 0;
 for(int i = 1; i <= N; i++)
  if(!vis[i]){
   cnt++;
   play(i);
  }
 return cnt;          
}

problem F

problem G

contest

2009-08-16T14:39:00.016+07:00

after the contest ends, we met faruque bhai, who was the coach of the teams from brac university. it was nice to meet him there...wherever we are, when we see our familiar faces we feel a bit comfort....nitu apu, coach of HDST teams, Dinajpur...was also there..but we didn't able to meet her.
this is the front view of the campus.

aust's new permanent campus is really magnificent. it has a nice architectural design. i found their campus very attractive. anyway, but it should not be in the industrial area

inside views of the campus

these natural beauties were taken by mahdee, when we were crossing over jamuna bridge by padmaExpress. it was a nice moment to see these natural beauties.

self-referential

2009-06-19T21:54:00.002+06:00

type: number theory

problem link: DigitPrimes

use sieve to generate primes upto 1000000 then for 1 to 1000000 genarate digitprimes[]

it would be like this : digitprimes[0, 1, ....,10] = {0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4} so we can answer for the range t1 & t2 as digitprimes[t2] - digitpriems[t1-1]

self-referential

2009-06-02T06:37:00.004+06:00

type: graph search

problem link: PlayingWithWheels

we can go to 8 possible configurations of the wheels from the current configuration. a simple bfs search can do.

problem link: SwitchBulb

as the number of bulb n <= 15 so there will be at most 2^15 different bulb states. we can go to m different states from the initial bulb state, and from them we can go again m different states and so on.... a bfs search can do with keeping the depth of the each state.

self-referential

2009-05-23T00:10:00.010+06:00

type: geom

prob: PointsInFigure(similar 476, 477)

one messy thing in this problem is to handle the inputs. input can be be handled like this: char a[i]: to store what type of figure is this and at the same time x1[i] y1[i], x2[i], y2[i], x3[i], y3[i] to store the corresponding coordinates or radius. then for each input loop through a[] from i = 0 to n; if a[i] == r or t or c then check weather this point inside these r or t or c.

to check weather a point is inside a traiangle:

we can divide the original triangle to small 3 triangle (2 point from the original triangle & one is that point)

say the small triangles areas are a1 , a2 and a3 then if( a1 + a2 + a3 - Area of the original triangle A = 0 && none of the 3 area is zero) the point is inside the triangle otherwise not. ...requires tight precision arithmatic.

prob: HockeyFault

there are 2 circles, 1 rectangle, the result is the union of the points inside these three area. to check weather a point is inside a circle or a rectangle or on the boundary we know-

if (x1, y1) be LowerLeft corner and (x2 ,y2) be UpperRight corner of the rectangle. then (px,py)

is inside or on the rectangle boundary if and only if (x1 <= px && px <= x2) and (y1 <= py && py<= y2). if (cx ,cy) be circle center, r be radius, then (px, py) is inside or on the circle boundary if and only if (px - cx)^2 + (py - cy)^2 <= r^2

link

2009-05-14T19:58:00.001+06:00

http://www.mathmojo.com/abacus/abax/abaxaddition/addingwithabax1.html
http://homeschoolmath.blogspot.com/search/label/abacus

self-referential

2009-04-26T01:24:00.003+06:00

type: math

Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal expansion.

Let, n be a positive integer. Consider 1, 11, 111, 1111, ...(a list of integers consist of only 1s) where last number of the list has n + 1 1s.

Since there are n + 1 integers in the list, by Pigeonhole Principle there must be two with the same remainder when divided by n. And, We know if (a = b) (modulo m) then m |(a - b). So, the defference of these 2 integes(having same remainder) has a decimal expansion consisting completely of 0s and 1s and is divisible by n. (uva-link: 11392 :10127/diff)

self-referential

2009-04-26T01:16:00.003+06:00

Do or Die. Play it. http://online-judge.uva.es/p/v104/10409.html

self-referential

2009-04-26T01:02:00.006+06:00

“how many different squares are there in a grid of N × N squares?”

for N = 2, the answer is 5. if N = 100 ?

source:ACM ICPC2008 – South American Regionals

the begin

2008-12-02T02:03:00.004+06:00

They said 'Glory be to You!

We have no knowledge except what You have taught us.

You are the All-Knowing, the All-Wise.'

(The Qur'an, 2:32)