Eternal: 2015

Friday 17 July 2015

/* package whatever; // don't place package name! */

similar implimentation to java System.out.println()

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
A a=new A();
A.p.out();
}
}
class P
{
int out()
{
System.out.println("here what prints");
return 0;
}

}
class A
{

static Prin print=new Prin();

}

Wednesday 1 July 2015

telerik basic page work

<!DOCTYPE html>

<html>
<head>
<meta name="viewport" content="width=device-width, initial-scale=1">

<link rel="stylesheet" href="http://code.jquery.com/mobile/1.4.5/jquery.mobile-1.4.5.min.css">
<link rel="stylesheet" href="css/index.css" />

<script src="http://code.jquery.com/jquery-1.11.3.min.js"></script>

<script src="http://code.jquery.com/mobile/1.4.5/jquery.mobile-1.4.5.min.js"></script>

<script>

function check() {
var a = document.getElementById("text1").value;
var b = document.getElementById("password1").value;
if (a == "raj" && b == "password" || a == "RAJ" && b == "password" || a == "Raj" && b == "password") {
window.location.href = "#pagetwo";
document.getElementById("show").innerHTML = a;
}
else {
alert("wrong username/password");
}
}
</script>

</head>
<body>


<div data-role="page" id="pageone">
<div data-role="header">
<h1> Welcome To HomePAGE </h1>
</div>
<p><center><h1>login form</h1></center></p>

<div data-role="main" class="ui-content">

<table>
<tr>
<td>username</td>
<td><input type="text" id="text1" /></td>
</tr>
<tr>
<td>password</td>
<td><input type="password" id="password1" /></td>
</tr>
</table>
<center><input type="button" value="login" onclick="check()" /></center>

</div>

<div data-role="footer" data-position="fixed">
<h1> FOOTER</h1>

</div>
</div>


<div data-role="page" id="pagetwo">
<div data-role="header">
<h1> hello world </h1>

</div>

<div data-role="main" class="ui-content">
<p>Welcome</p>
<a href="#pageone">go back</a>
<div id="show">
</div>
</div>

<div data-role="footer" data-position="fixed">
<h1> FOOTER</h1>

</div>
</div>

</body>
</html>

Friday 26 June 2015

javascript

date object

var today = new date(); // return todays date

to make out own obj

we can we

var day= new Date(2011,0,1);// year month and day , month as an exception starts as 0

var daytime= new Date(2011,0,1,0,0,0);//also adds hours , mins and secs with previous

Get methods of date obj

day.getMonth();
day.getYear();
day.getTime();

Set methods

day.setMonth(5);

comparison

var date1= new Date(2001,1,1);
var date2= new Date(2001,1,1);

if(date1==date2)//false

if(date1.getTime()==date2.getTime())

CREATING NEW OBJECT

var player= new object();

now its data members will be declared as

player.name="fred";
player.age=13;
player.rank=1;

A variable inside a object is called its properties, same as data member

shorthand to create an object

var player= {name: "Fred",age:13,rank:1};

Thursday 25 June 2015

git bash

git config --global user.name "<name>"

git config --global user.email "<email>"

git init <project>
to make the folder working area for git , ie to make it project folder

git log
see changes made through commit

git status
see the staged area , new files that have come up and the files that have changed

git add .
add all the files of folder to the staged area

git add "filename"
add the particular file to the stage area

git commit -m "any comment to indicate the changes that reflect in this commit"

git diff
show the exact changes that have taken place in files (as their lines of code)
but shows only of unstaged files

git diff --cached
after we add a file to the stage area and we want to see the differences then we need to use --cached otherwise the changes wont show

shortcuts
if the log becomes to big , to come out of it we need to press ctrl+z+z or ctrl+c(checked)

git log --oneline
show all commits with just the associated message

git commit -a -m "message"
it will quickly do commit , and also add the files to the staging area (replacement as one line code)

git status -s
show modifications in shorthand

ssh-keygen -t rsa -C "email address"
generates rsa key for computer

ssh -T git@github.com
checks whether the computer is able to communicate with the gitserver or not after using rsa encryption

git remote add origin "git repository ssh "
will add the remote repository from where we will push or pull the data

git push origin master
will push everything on remote repository

git branch
ti know all braches

git brach branchname
to make a new branch

git checkout branchname
to go to that branch

git clone "ssh url"
to clone a project to local

git remote add variablename "ssh " or
git push varialbe name branch name
git push something in a branch

TO merge
git merge master
this will merge the code of master with our branch

Thursday 26 March 2015

my php codes

what do we do to display the common file name that php file shares

<?php
//echo 'hello';
echo $_SERVER['SCRIPT_NAME'];// WILL TAKE THE SCRIPT NAME AND DISPLAY IT
//echo $var;
?>

vid lec - 61

first file 1.php
<?php

include 'inc.php';

if(isset($_POST['submit'])){
echo 'process 1';

}

?>

file 2.php

<?php

include 'inc.php';

if(isset($_POST['submit'])){
echo 'process 2';

}

?>

inc.php

<?php

$script_name= $_SERVER['SCRIPT_NAME'];// WILL TAKE THE SCRIPT NAME AND DISPLAY IT
echo $script_name;
?>

<form action="<?php echo $script_name; ?>" method="POST">
<input type="submit" name="submit" value="Submit">
</form>
//

will display the name of page we are in inspite of the fact that the running code of that part was included but that became independent bcz of the use of server[script_name];

to see your ip address

<?php

$ip_address= $_SERVER['REMOTE_ADDR'];
echo $ip_address;

// this isnt always a good way to get users ip address, esp when they are on a shared network
// or someone may be using proxy
?>

so what we can do is that we cant check wherether he using a proxy, or is in a shared network
there are ready made functions discussed in video lec

to print an array we use print_r();

to check whether the form has been left empty in the type POST or get,
we use function (!empty(nameofvariable))

isset()-> just checks whether the submit button has been clicked or not

when we start a session , we create a file on the server side , and that file after its created should be accessible to every page.

SIMPLE CODE FOR SETTING UP SESSION
<?php
session_start();
$_SESSION['name']="alex";
//echo $_SESSION['name'];
?>

CODE TO VIEW SESSION

<?php

session_start();
echo $_SESSION['name'];

?>

a better way to log in , and to check whether user has his session or not and ask him to log in

<?php

session_start();
if(isset($_SESSION['name'])){
echo $_SESSION['name'];
}
else
{
echo 'plz log in.. ';
}
?>

TO END SESSION

<?php
// unset a session

session_start(); // though we are unsetting a session we do need to start the session

unset($_SESSION['name']);
?>

COOKIES

setcookie('username','value',time);// time in seconds

the time here is in terms of timestamp so we save the time stamp
$time= time(); // this time() returns timestamp
and in the parameter we write $time+5 , that sets the cookie for 5 secs

now if one wants to log out , can again set the cookie with time-> $time -5

sql database connection

now, when we connect to database , if there is an improper connection it might show an error,
to avoid that display of error we write thr statement like

<?php
$mysql_host = 'localhost';
$mysql_user='alex';
$mysql_pass='';

mysql_connect($mysql_host, $mysql_user, $mysql_pass );

// instead of writing the above statement (which can display the error mesg)we can write

mysql_connect($mysql_host, $mysql_user, $mysql_pass ) or die('could not connect');

>?

we can write the above code in a file and include wherever needed

after connecting to the dbms we need to specify the dbms we need to connect to

my_sql_dbms(nameofDbms);

for any query we need to write it as a string and save that in a variable and then pass that in the function
mysql_query();

Sunday 22 February 2015

Bit-masking in DP

Bit-masking

generally uses the concept of representing number in form of bits and then performing the required operations .
(usually used for the selection process in a given set , a given element)
lets take an example

Let there be an set of 4 elements {3,5,2,1}
Now we want to all the different elements we can make by selecting some the elements out of this set ,
so what are the possible sums.
To find that out we will have to take out numbers out of sets in different combinations

how to think of selection out of sets in terms of maths and computer programming
Here comes the role of Bit masking P)

out of the set we either select the number or dont select it , that makes it a _ _ _ _ (four dashes of true or false)
we plan to represent these four dashes as 0 or 1 .(which makes it binary)
so the possible representations can be
0 0 1 0 ---> if we select only 2 that is 3rd element and sum becomes 2
0 1 0 1 ---> if we select both 5 and 1 , that sums up to 6

This binary representation is good , but now we need to help ourselves to use it more efficiently
alas we plan to convert into decimal and work upon it, and use that as binary as per when required

we will be able to use this concept whenever the number of elements in the set happens to be less equal to 64( for we can represent max of 64 bit in a computer)

any time with n elements in the set and max possible combination will be 2^n
In the above case its 2^4 that is 16
from
0 0 0 0 - - - when we select no element TO
1 1 1 1 - - - when we select all (decimal 15)

pseudo algo

int n // number of elements in a set

int tp=1<<n // 2^n total possible combination

for(int i=0;i<tp;i++)
{
for(int j=0;j<n;j++)// here we will work on whether we will select the element or not as per i
{
if((1<<j)&i) // if the particular bit of i is on , then true ,(*) explined at bottom
{
//select it
}
}

}

if i is 5 0101
loop over j (0 to 3)
0 -> 2^0 0 0 0 1 & 0 1 01 so true
1-> 2^1 0 0 1 0 & 0 1 0 1 so false
2->2^2 0 1 0 0 & 0 1 0 1 so true
3->2^3 1 0 0 0 & 0 1 0 1 so false

hence 5 and 1 are selected

question

http://community.topcoder.com/stat?c=problem_statement&pm=13166

solution

http://community.topcoder.com/stat?c=problem_solution&cr=22777422&rd=15854&pm=13166

Thursday 5 February 2015

dijkstra (using set)

shortest path spoj

http://nikhilnihal.blogspot.in/2015/01/dijkstra-list-ques-shortest-path-here.html

Saturday 24 January 2015

Suffix Arrays (learning material)

http://www.quora.com/Given-a-string-how-do-I-find-the-number-of-distinct-substrings-of-the-string
(used)

http://web.stanford.edu/class/cs97si/suffix-array.pdf

https://greasepalm.wordpress.com/2012/07/01/suffix-arrays-a-simple-tutorial/

http://www.quora.com/How-do-I-find-the-total-number-of-different-palindromes-of-length-k-in-a-given-string-using-suffix-array (used)

http://www.quora.com/If-two-strings-have-more-than-one-longest-common-subsequence-considering-length-what-is-the-algorithm-to-find-the-lexicographically-smallest-longest-common-subsequence-among-them

http://www.roman10.net/suffix-array-part-3-longest-common-substring-lcs/ (read imp)

question link

http://www.spoj.com/problems/DISUBSTR/
http://www.spoj.com/problems/SARRAY/ (this is for understanding the complexity of ur designed suffix array implimentation)

suffix array standard code( time complexity o(n log^2 n ) using bucket sort
https://gist.github.com/calmhandtitan/8119030

String hashing

can be used instead of suffix array and all (in some cases)

tutorial by lalit kundu

http://threads-iiith.quora.com/String-Hashing-for-competitive-programming

code of DISUBSTR

as per the instructions of quora (implementation of suffix array) , first link
time complexity( n^2 logn)

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
typedef long long ll;
using namespace std;
int L;

int su[1005];
char arr[1005];

int mpp(int a,int b)
{

while(arr[a]==arr[b] && a<L && b<L){a++;b++;}
if(arr[a]==NULL || arr[b]==NULL)
{
a--;b--;
}

if(arr[a]!=arr[b])
{
return arr[a]<arr[b];
}
else// the one which will be shorter all be being equal in all respect will come first
{
return a>b;
}
}

int str(int l)
{
for(int i=0;i<=l;i++)
su[i]=i;

sort(su,su+l,mpp);

}

int main()
{
int t;

// freopen("kr.in","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%s",arr);

ll l=strlen(arr);
L=l;
str(l);
ll s=l-su[0];
for(int i=0;i<l-1;i++)
{
ll p=l-su[i+1];
ll co=0;
ll a=su[i];
ll b=su[i+1];
while(arr[a]==arr[b])
{
co++;
a++;
b++;
}
s+=p-co;
}
printf("%lld\n",s);
}
}

explaination

This is one of the problems in SPOJ (Sphere Online Judge (SPOJ))

The solution consists of constructing the suffix array and then finding the number of distinct substrings based on the Longest Common Prefixes.

One key observation here is that:

If you look through the prefixes of each suffix of a string, you have covered all substrings of that string.

Let us take an example: BANANA

Suffixes are:

0) BANANA
1) ANANA
2) NANA
3) ANA
4) NA
5) A

It would be a lot easier to go through the prefixes if we sort the above set of suffixes, as we can skip the repeated prefixes easily.

Sorted set of suffixes:

5) A
3) ANA
1) ANANA
0) BANANA
4) NA
2) NANA

From now on,

LCP = Longest Common Prefix of 2 strings.

Initialize

ans = length(first suffix) = length("A") = 1.

Now consider the consecutive pairs of suffixes, i.e, [A, ANA], [ANA, ANANA], [ANANA, BANANA], etc. from the above set of sorted suffixes.

We can see that,

LCP("A", "ANA") = "A".

All characters that are not part of the common prefix contribute to a distinct substring. In the above case, they are 'N' and 'A'. So they should be added toans.

So we have,

1 2	ans += length("ANA") - LCP("A", "ANA") ans = ans + 3 - 1 = ans + 2 = 3

Do the same for the next pair of consecutive suffixes: ["ANA", "ANANA"]

LCP("ANA", "ANANA") = "ANA".

ans += length("ANANA") - length(LCP)

=> ans = ans + 5 - 3

=> ans = 3 + 2 = 5.

Similarly, we have:

1 2	LCP("ANANA", "BANANA") = 0 ans = ans + length("BANANA") - 0 = 11

1 2	LCP("BANANA", "NA") = 0 ans = ans + length("NA") - 0 = 13

1 2	LCP("NA", "NANA") = 2 ans = ans + length("NANA") - 2 = 15

Hence the number of distinct substrings for the string "BANANA" = 15.

lcp computation for lcs (longest common string etc)

 for (i = 0; i < len1 + len2 - 1; ++i) {

        if ((ap[i] - cstr >= len1) && (ap[i+1] - cstr >= len1)) {

            //both starts with suffix of second string

            continue;

        } else if ((ap[i] - cstr < len1) && (ap[i+1] - cstr < len1)) {

            //both starts with suffix of first string

            continue;

        } else {

            lcplen = lcp(ap[i], ap[i+1]);

            if (lcplen > lcslen) {

                lcslen = lcplen;

                lcssufpos = i;

we generally merge two strings s1 and s2 and then form the suffix array and do the lcp computation ,

in then lcp computation we needed to ensure that , the consecutive suffixes that we are comparing dont belong to the same string . and then do the needful.

the above part of code explains how it is to be performed

Thursday 22 January 2015

fibosum (spoj) fibonacci

question link http://www.spoj.com/problems/FIBOSUM/

geeksfor geeks link http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

finding nth fibo number in O(log n)

imp concept for Fibonacci sum
fibosum(x)= fibonum(x+2) -1 ;

#include<stdio.h>
typedef unsigned long long ll ;
using namespace std;
ll f[2][2]={{1,1},{1,0}};
int te[2][2]={{1,1},{1,0}};
ll mo=1000000007;

int mul(int n)
{
ll t[2][2]={0,0,0,0};
if(n==1)
{
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
{
t[i][j]=(t[i][j]+f[i][k]*te[k][j])%mo;
}
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
f[i][j]=t[i][j];
}
}
}
else
{
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
{
t[i][j]=(t[i][j]+f[i][k]*f[k][j])%mo;
}
}
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
f[i][j]=t[i][j];
}
}
}

}

int power(ll n)
{
if(n<=1)
return 0;
// n<<2;
power(n/2);
mul(2);
if(n&1)
mul(1);

}

int fibo(ll a)
{
if(a==0)
return 0;
power(a-1);
}

int main()
{

int t;
scanf("%d",&t);
while(t--)
{
ll a,b,q,w,e;
//scanf("%llu %llu",&a,&b);
scanf("%llu %llu",&a,&b);
fibo(a+1);
q=f[0][0];
// printf("%llu\n",f[0][0]);
//printf("%d %d %d %d",te[0][0],te[1][0],te[0][1],te[1][1]);
f[0][0]=1;
f[0][1]=1;
f[1][0]=1;
f[1][1]=0;
fibo(b+2);
w=f[0][0];
// printf("%llu\n",w);
e=(w-q+mo)%mo;
printf("%llu\n",e);
f[0][0]=1;
f[0][1]=1;
f[1][0]=1;
f[1][1]=0;

}
}

Sunday 18 January 2015

Counting total number of divisor (not just prime factors)

spoj question link

solution link
http://spoj-solutions.blogspot.in/2014/10/comdiv-number-of-common-divisors.html

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
bool p[1000009];
int prime(int a)
{int pe=sqrt(a);
for(int i=2;i<=pe;i++)
{
if(!p[i])
for(int j=2;i*j<=a;j++)
p[i*j]=1;
}
}

int main()
{
//freopen("kr.in","r",stdin);
int t;

prime(1000005);
int pi[100000];
int kk=0;
pi[kk++]=2;
for(int i=3;i<1000000;i+=2)
{
if(!p[i])
pi[kk++]=i;
}
scanf("%d",&t);
while(t--)
{
int a,b,c,d=1;
scanf("%d %d",&a,&b);
c=__gcd(a,b);
/*for(int i=1;i<=c/2;i++)
{
if(c%i==0)
d++;
}*/
if(c==1)
{
printf("1\n");
continue;
}

int res=1;
//printf("gcd is %d\n",c);
for(int i=0;pi[i]<c && c;i++)
{
int co=1;
// printf("pi %d %d\n",pi[i],c);
while(c%pi[i]==0)
{
c/=pi[i];
co++;
}
res*=co;
}
if(c>1)
res*=2;
printf("%d\n",res);
}
}

imp concept

to count the total number of divisor( not just prime) using the prime number for optimization , we calculate total number of times a prime divides the number and then multiply them.

for example in case of 12

the factors are , 1 ,2, 3,4,6,12 total of 6

the prime factors are 2 ( two times ) and 3 ( one time)

if we add one with the frequency and multiply them we get the total number of factor( that are not just prime) :P

Wednesday 14 January 2015

adhoc concepts spoj

1. http://www.spoj.com/problems/STREETR/
solu- its the gcd of difference between consecutive trees

Tuesday 13 January 2015

loop in a graph

reference : geekforgeeks

Can be solved via set , or dfs and bfs.

set - looping over edges , when we encounter a edges whose any of the vertices have not been visited (are not present in set) we insert them into the set.
whereas if we encounter a edge whose both the vertices already present in set,,,We have found a loop

the major problem we face for programming this through set or dfs or bfs is for the directed graph where we encounter both visited not but one happens to be the parent of other ,
so we should use a parent array for hashing keeping who is the parent of whom in our traversal and now if we encounter both visited we check if one is a immediate parent , and if that is the case we ignore it.

Bfs and dfs

bfs - if two nodes are connected at a level difference of more that 1 then there is a loop. we keep a record of level in traversal.

dfs - if we find a already visited node during traversal in dfs and that is not immediate parent of it , then its a loop

spoj question -- is it a tree

set theory solution

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int main()
{
// freopen("kr.in","r",stdin);
/* scanf("%d",&t);
while(t--)*/
{
set<int> s;
int a,b;
int flag=0;
scanf("%d %d",&n,&m);
if(n!=m+1)
flag=1;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
if(s.find(a)!=s.end() && s.find(b)!=s.end())
{
flag=1;
}
else
{
s.insert(a);
s.insert(b);
}
}

if(flag==1)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}

dfs solution

#include<stdio.h>

#include<bits/stdc++.h>

using namespace std;

// should not be an immediate parent so i need a parent array

int parent[10000000];

int flag;

bool visited[1000000];

int dfs(vector<int> g[],int a,int n)

{

stack <int > st;

st.push(a);

visited[a]=1;

while(!st.empty())

{

int k=st.top();

st.pop();

for(int i=0;i<g[k].size();i++)

{

int V=g[k][i];

if(!visited[V])

{

visited[V]=1;

parent[V]=k;

st.push(V);

}

else

{

if(parent[k]==V)

{

continue;

}

flag=1;

// printf("loop %d %d\n",k+1,V+1);

return 0;

}

int main()

{

int n,m;

//freopen("kr.in","r",stdin);

scanf("%d %d",&n,&m);

vector<int > g[n];

flag=0;

if(n-1!=m)

{

printf("NO\n");

return 0;

}

for(int i=0;i<m;i++)

{

int a,b;

scanf("%d %d",&a,&b);

a--;b--;

g[a].push_back(b);

g[b].push_back(a);

}

//printf("sending dfs\n");

dfs(g,0,n);

for(int i=0;i<n;i++)

{

if(!visited[i])

{ // printf("not visited %d\n",i+1);

flag=1;

break;

}

if(flag==1)

{

printf("NO\n");

}

else{

printf("YES\n");

}

vector stl

INCREASING THE SIZE OF 2ND DIMENSION IN 2D ARRAY

PASSING 2D VECTOR TO A FUNCTION

#include<stdio.h>
#include<vector>
using namespace std;
int check(vector < vector <int > > g)
{
for(int i=0;i<g.size();i++) /* it all becomes more easy since vector knows its size whereas array doesnt in a cpp program */
{
for(int j=0;j<g[i].size();j++)
{
printf("%d ",g[i][j]);
}
printf("\n");
}

}
int main()
{
vector< vector<int> > g;
int t;

for(int i=0;i<3;i++)
{
g.push_back(vector<int>());// increasing the size of 2nd dimension
for(int j=0;j<3;j++)
{

g[i].push_back(j);

}
//printf("\n");
}
check(g);
}

other way for these type of vector (used in graph for adjacency list)

vector<int > g[n];// declaration

int dfs(vector<int> g[],int a,int n)

vector size declaration

syntax;

vector<vector<int>> A(dimension, vector<int>(dimension));

segment tree laze propagation

reference :- spoj forum

Lazy Propagation means that you only update what you actually need to, when you need to.
For example, if we have a segment tree that covers the range 1-20.
If we update segment [1,20], we update only the value of the root node
of the tree and set a flag on it's children [1,10] and [11,20] to let them know that they
need to be updated.

Next, if we query [6,7] then when we reach a node in the traversal that
has the update flag on, we need to flag it's children and update it's value.

[1,10] is flagged for update
query [6,7]
Traversal Route:
[1,10] - push update flag to [1,5] and [6,10] and update value of [1,10]
[6,10] - push update flag to [6,8] and [9,10] and update value of [6,10]
[6.8] - push update flag to [6,7] and [8,8] and update value of [6,8]
[6,7] - push update flag to [6,6] and [7,7] and update value of [6,7]

This leaves [1,5], [6,6], [7,7], [8,8], [9,10] flagged for update.

graph notes

1. If we can somehow calculate the total sum of degree , then degree/2 = no of edges .

How to pass a 2D array as a parameter in C?

Using a single pointer
In this method, we must typecast the 2D array when passing to function.

reference geekforgeeks

#include <stdio.h>

void print(int *arr, int m, int n)

{

    int i, j;

    for (i = 0; i < m; i++)

      for (j = 0; j < n; j++)

        printf("%d ", *((arr+i*n) + j));

}

int main()

{

    int arr[][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

    int m = 3, n = 3;

    print((int *)arr, m, n);// notice (int*) here

    return 0;

}

in c a printer is a pointer in parameter so it doesnt matter whether its single or double

Eternal