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




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"]

1
2
3
4
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