Showing posts with label spoj. Show all posts
Showing posts with label spoj. Show all posts
Thursday, 5 February 2015
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);
}
}
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;
}
}
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);
}
}
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
Saturday, 10 January 2015
bfs and dfs spoj questions extra dp question list
BFS & DFS
Dijkstra, Floyd Warshall, Prim & Kruskal
• Longest Increasing Subsequence (LIS) – Classical
1. UVa 103 - Stacking Boxes (Longest Path in DAG ≈ LIS)
2. UVa 111 - History Grading (straight-forward)
3. UVa 231 - Testing the Catcher (straight-forward)
4. UVa 481 - What Goes Up? (must use O(n log k) LIS)
5. UVa 497 - Strategic Defense Initiative (solution must be printed)
6. UVa 10051 - Tower of Cubes (can be modeled as LIS)
7. UVa 10534 - Wavio Sequence (must use O(n log k) LIS twice)
8. UVa 11790 - Murcia’s Skyline (combination of classical LIS+LDS, weighted)
9. UVa 11003 - Boxes
10. UVa 11456 - Trainsorting (get max(LIS(i) + LDS(i) - 1), ∀i ∈ [0 . . . N -1])
11. LA 2815 - Tiling Up Blocks (Kaohsiung03)
• Coin Change – Classical
1. UVa 147 - Dollars (similar to UVa 357 and UVa 674)
2. UVa 166 - Making Change
3. UVa 357 - Let Me Count The Ways (a variant of the coin change problem)
4. UVa 674 - Coin Change
553.4. DYNAMIC PROGRAMMING
c Steven & Felix, NUS
5. UVa 10306 - e-Coins
6. UVa 10313 - Pay the Price
7. UVa 11137 - Ingenuous Cubrency (use long long)
8. UVa 11517 - Exact Change
• Maximum Sum
1. UVa 108 - Maximum Sum (maximum 2-D sum, elaborated in this section)
2. UVa 836 - Largest Submatrix (maximum 2-D sum)
3. UVa 10074 - Take the Land (maximum 2-D sum)
4. UVa 10667 - Largest Block (maximum 2-D sum)
5. UVa 10827 - Maximum Sum on a Torus (maximum 2-D sum)
6. UVa 507 - Jill Rides Again (maximum 1-D sum/maximum consecutive subsequence)
7. UVa 10684 - The Jackpot (maximum 1-D sum/maximum consecutive subsequence)
• 0-1 Knapsack – Classical
1. UVa 562 - Dividing Coins
2. UVa 990 - Diving For Gold
3. UVa 10130 - SuperSale
4. LA 3619 - Sum of Different Primes (Yokohama06)
• String Edit (Alignment) Distance – Classical (see Section 6.3)
• Longest Common Subsequence – Classical (see Section 6.3)
• Non Classical (medium difficulty)
1. UVa 116 - Unidirectional TSP (similar to UVa 10337)
2. UVa 473 - Raucuous Rockers
3. UVa 607 - Scheduling Lectures
4. UVa 10003 - Cutting Sticks (discussed in this book)
5. UVa 10337 - Flight Planner (DP solvable with Dijkstra)
6. UVa 10891 - Game of Sum (2 dimensional states)
7. UVa 11450 - Wedding Shopping (discussed in this book)
8. LA 3404 - Atomic Car Race (Tokyo05)
• DP + Bitmasks
1. UVa 10364 - Square (bitmask technique can be used)
2. UVa 10651 - Pebble Solitaire
3. UVa 10908 - Largest Square
4. UVa 10911 - Forming Quiz Teams (elaborated in this section)
5. LA 3136 - Fun Game (Beijing04)
6. PKU 2441 - Arrange the Bulls
• DP on ‘Graph Problem’
1. UVa 590 - Always on the Run
2. UVa 910 - TV Game (straightforward)
3. UVa 10681 - Teobaldo’s Trip
4. UVa 10702 - Traveling Salesman
5. LA 4201 - Switch Bulbs (Dhaka08)
6. SPOJ 101 - Fishmonger
563.5. CHAPTER NOTES
c Steven & Felix, NUS
• DP with non-trivial states
1. LA 4106 - ACORN (Singapore07) (DP with dimension reduction)
2. LA 4143 - Free Parentheses (Jakarta08) (Problem set by Felix Halim)
3. LA 4146 - ICPC Team Strategy (Jakarta08) (DP with 3 states)
4. LA 4336 - Palindromic paths (Amritapuri08)
5. LA 4337 - Pile it down (Amritapuri08)
6. LA 4525 - Clues (Hsinchu09)
7. LA 4526 - Inventory (Hsinchu09)
8. LA 4643 - Twenty Questions (Tokyo09)
• DP on Tree
1. UVa 10243 - Fire! Fire!! Fire!!! (Min Vertex Cover ≈ Max Independent Set on Tree)
2. UVa 11307 - Alternative Arborescence (Min Chromatic Sum, 6 colors are sufficient)
3. LA 3685 - Perfect Service (Kaohsiung06)
4. LA 3794 - Party at Hali-Bula (Tehran06)
5. LA 3797 - Bribing FIPA (Tehran06)
6. LA 3902 - Network (Seoul07)
7. LA 4141 - Disjoint Paths (Jakarta08)
which graph is tree (Is it a tree)
For checking if the graph is a tree we need to check those 3 things.
1. There are N nodes and N-1 edges. If the number of edges is different than N-1 than the graph is not a tree for sure,
2. We need to run a DFS or BFS , from any edge we want. If we meet a node which we already visited => the graph has cycles => the graph is not a tree. ( Every time we are on some node, we calculate the number of his neighbors which we already visited, the number must be less than 2 because for the cycles we shouldn't count the node which we were in our previous step. Check the source code for clarification).
3. If the previous 2 steps proved that our graph is a tree we need to check for one more thing. A tree must have only one component, there shouldn't be any other trees apart form our graph.
Friday, 2 January 2015
grid traversal (smart way ;) ) with bfs
now to move in the four direction of a grid we can use
}
| int positionsX[4]= {0,-1,0,1}; | |
| int positionsY[4]= {-1,0,1,0}; |
how to use it in the code part
| for(int i=0;i<4;i++){ | |
| int newx=top.first+positionsX[i],newy=top.second+positionsY[i]; |
we can also use a function
(validPosition(newx,newy))
and put the necessary condition in it , to make sure that the newly formed position is correct
code example
(with bfs traversal in a grid)
spoj question -> BITMAP
SOLUTION LINK
Thursday, 1 January 2015
bipartite graph (BUGS LIFE) SPOJ
http://www.spoj.com/problems/BUGLIFE/
usual mistake treated the vertices in the code starting from 0 but not modifying the input which is generally of the form where numbering starts from 1.
so that needs to taken care of in graph (ALWAYS)
#include<stdio.h>
#include<vector>
#include<queue>
int N,flag;
using namespace std;
int visited[2000+5];
vector<int> g[2000];
int bpg(int v)
{
visited[v]=1;
queue<int> q;
q.push(v);
// int flag=0;
while(!q.empty())
{
int y=q.front();
q.pop();
for(int i=0;i<g[y].size();i++)
{
int r=g[y][i];
if(!visited[r])
{ q.push(r);
if(visited[y]==1)
{
visited[r]=2;
}
else if(visited[y]==2)
visited[r]=1;
}
else
{
if(visited[r]==visited[y])
{
flag=1;
break;
}
}
}
if(flag==1)
break;
}
}
int main()
{
//freopen("kr.in","r",stdin);
int t,m,n ,i,a,b;
int ee=0;
scanf("%d",&t);
while(t--)
{ flag=0;
ee++;
scanf("%d %d",&m,&n);
//vector<int > g[m];
for( i=0;i<n;i++)
{
scanf("%d %d",&a,&b);
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
// remember if it doesnt work make it undirected
}
N=m;
for(i=0;i<2000;i++)
{
visited[i]=0;
}
for( i=0;i<m;i++)
{
if(!visited[i])
{
bpg(i);
}
}
printf("Scenario #%d:\n",ee);
if(flag==1)
printf("Suspicious bugs found!\n");
else
printf("No suspicious bugs found!\n");
for( i=0;i<2000;i++)
g[i].clear();
}
}
usual mistake treated the vertices in the code starting from 0 but not modifying the input which is generally of the form where numbering starts from 1.
so that needs to taken care of in graph (ALWAYS)
#include<stdio.h>
#include<vector>
#include<queue>
int N,flag;
using namespace std;
int visited[2000+5];
vector<int> g[2000];
int bpg(int v)
{
visited[v]=1;
queue<int> q;
q.push(v);
// int flag=0;
while(!q.empty())
{
int y=q.front();
q.pop();
for(int i=0;i<g[y].size();i++)
{
int r=g[y][i];
if(!visited[r])
{ q.push(r);
if(visited[y]==1)
{
visited[r]=2;
}
else if(visited[y]==2)
visited[r]=1;
}
else
{
if(visited[r]==visited[y])
{
flag=1;
break;
}
}
}
if(flag==1)
break;
}
}
int main()
{
//freopen("kr.in","r",stdin);
int t,m,n ,i,a,b;
int ee=0;
scanf("%d",&t);
while(t--)
{ flag=0;
ee++;
scanf("%d %d",&m,&n);
//vector<int > g[m];
for( i=0;i<n;i++)
{
scanf("%d %d",&a,&b);
a--;
b--;
g[a].push_back(b);
g[b].push_back(a);
// remember if it doesnt work make it undirected
}
N=m;
for(i=0;i<2000;i++)
{
visited[i]=0;
}
for( i=0;i<m;i++)
{
if(!visited[i])
{
bpg(i);
}
}
printf("Scenario #%d:\n",ee);
if(flag==1)
printf("Suspicious bugs found!\n");
else
printf("No suspicious bugs found!\n");
for( i=0;i<2000;i++)
g[i].clear();
}
}
Small factorial (FCTRL2) spoj
small factorial use of Big integer in java
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;
/* 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 heres
int n,m,k,l,i;
BigInteger a,x,c;
a=new BigInteger("1");
Scanner w=new Scanner(System.in);
int t= w.nextInt();
while(t>0)
{
t--;
m=1;
a=new BigInteger("1");
n=w.nextInt();
for(i=1;i<=n;i++)
{ x=new BigInteger(Integer.toString(i));
a=a.multiply(x);
}
System.out.println(a);
}
/*BigInteger a=new BigInteger(Integer.toString(t));
System.out.println(a);*/
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;
/* 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 heres
int n,m,k,l,i;
BigInteger a,x,c;
a=new BigInteger("1");
Scanner w=new Scanner(System.in);
int t= w.nextInt();
while(t>0)
{
t--;
m=1;
a=new BigInteger("1");
n=w.nextInt();
for(i=1;i<=n;i++)
{ x=new BigInteger(Integer.toString(i));
a=a.multiply(x);
}
System.out.println(a);
}
/*BigInteger a=new BigInteger(Integer.toString(t));
System.out.println(a);*/
}
}
Needle in the haysack (spoj) (solved just by using the c++ string fucntions)
link to question http://www.spoj.com/problems/NHAY/
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
int main()
{ int t;
// scan
string a,b;
int f=-1;
while(cin>>t>>a>>b)
{
do{//int k=a.length();
f=b.find(a,f+1);
if(f!=-1)
cout<<f<<endl;}while(f!=-1);
printf("\n");
}
}
The find function returns the first position where the string is found ,
The second parameter allows the substring to be found in the original string after a particular position , and since we want the next substring to be found after the found result , be initialize f with -1 and always search with f+1 ,
if the sunstring is not found , the find function returns -1 .
:)
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
int main()
{ int t;
// scan
string a,b;
int f=-1;
while(cin>>t>>a>>b)
{
do{//int k=a.length();
f=b.find(a,f+1);
if(f!=-1)
cout<<f<<endl;}while(f!=-1);
printf("\n");
}
}
The find function returns the first position where the string is found ,
The second parameter allows the substring to be found in the original string after a particular position , and since we want the next substring to be found after the found result , be initialize f with -1 and always search with f+1 ,
if the sunstring is not found , the find function returns -1 .
:)
Monday, 29 December 2014
Bridge (spoj lis)
reference : http://kaustubh-karkare.blogspot.in/2012/09/directi-selection.html
spoj link
http://www.spoj.com/problems/BRIDGE/
reference
Given the coordinates of N pairs of cities, each pair containing cities on two opposite sides of a river, we need to make bridges between the pairs. What is the maximum number of non-overlapping bridges that can be built? I had seen this question somewhere not to long ago, so I was able to give an O(nlgn) solution in which we sort according to one coordinate (X) and then perform an LIS on the other (Y). I gave the answer instantly,
spoj link
http://www.spoj.com/problems/BRIDGE/
reference
Given the coordinates of N pairs of cities, each pair containing cities on two opposite sides of a river, we need to make bridges between the pairs. What is the maximum number of non-overlapping bridges that can be built? I had seen this question somewhere not to long ago, so I was able to give an O(nlgn) solution in which we sort according to one coordinate (X) and then perform an LIS on the other (Y). I gave the answer instantly,
Monday, 22 December 2014
sorting bank accounts (map)(spoj)
Its a simple question which demands use of map and good control on string .
There is a question with good combination of both and though simple offers many things to learn.
http://www.spoj.com/problems/SBANK/
#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
using namespace std;
int main()
{
int t,p;
freopen("kr.in","r",stdin);
map <string, int> cal;
map <string, int> :: iterator it;
char st[10000];
scanf("%d",&t);
while(t--)
{
scanf("%d",&p);
char c;
scanf("%c",&c);
for(int i=0;i<p;i++){
// fflush(stdin);
gets(st);
//puts(st);
cal[st]++;}
for(it=cal.begin();it!=cal.end();it++)
{
// cout<<it->first<<" ";
printf("%s %d\n",it->first.c_str(),it->second);
}
printf("\n");
cal.clear();
}
}
There is a question with good combination of both and though simple offers many things to learn.
http://www.spoj.com/problems/SBANK/
#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
using namespace std;
int main()
{
int t,p;
freopen("kr.in","r",stdin);
map <string, int> cal;
map <string, int> :: iterator it;
char st[10000];
scanf("%d",&t);
while(t--)
{
scanf("%d",&p);
char c;
scanf("%c",&c);
for(int i=0;i<p;i++){
// fflush(stdin);
gets(st);
//puts(st);
cal[st]++;}
for(it=cal.begin();it!=cal.end();it++)
{
// cout<<it->first<<" ";
printf("%s %d\n",it->first.c_str(),it->second);
}
printf("\n");
cal.clear();
}
}
things learnt
if we use string it becomes difficult to take input via gets
anyways its imp to take a char input to remove the new line character from getting into gets
if we want to print the string which is the key via printf , we need to use it->first.c_str() ,
most importantly , we cannot take string (which is a object input through scanf or gets ) which are functions of cpp and if we use just cin we will be unable to string input with space.
Thursday, 18 December 2014
SPOJ (MIXTURES)
#include<bits/stdc++.h>
using namespace std;
long long int min_mul(long long int arr[],long long int n)
{
long long int smok,s;
long long int l,i,j,k,max_val=1000000;
long long int dp[n+1][n+1],dp_smoke[n+1][n+1];
for( i=0;i<=n;i++)
{
for( j=0;j<=n;j++)
{
dp[i][j]=0;
dp_smoke[i][j]=0;
}
}
for(i=1;i<=n;i++)
dp[i][i]=arr[i];
for(l=2;l<=n;l++)
{
for(i=1;i<=n-l+1;i++)
{
j=i+l-1;
dp[i][j]=INT_MAX;
smok=INT_MAX;
for(k=i;k<=j-1;k++)//diagonal
{
if(smok>dp[i][k]*dp[k+1][j]+dp_smoke[i][k]+dp_smoke[k+1][j])
{
smok=dp[i][k]*dp[k+1][j]+dp_smoke[i][k]+dp_smoke[k+1][j];
s=k;
}
}
dp[i][j]=(dp[i][s]+dp[s+1][j])%100;
dp_smoke[i][j]=smok;
}
}
/*
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
cout<<endl<<endl;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
cout<<dp_smoke[i][j]<<" ";
}
cout<<endl;
}
/* for(i=0;i<n;i++)
{
for(j=)
}
*/
return dp_smoke[1][n];
}
int main()
{
long long int n,i;
while(scanf("%lld",&n)==1)
{
//printf("give the no of matrices\n");
/*if()
return 0;*/
//printf("give the row column matrix\n");
long long int arr[n+1];
arr[0]=0;
for(i=1;i<=n;i++)
scanf("%lld",&arr[i]);
cout<<min_mul(arr,n)<<endl;
}
return 0;
}
using namespace std;
long long int min_mul(long long int arr[],long long int n)
{
long long int smok,s;
long long int l,i,j,k,max_val=1000000;
long long int dp[n+1][n+1],dp_smoke[n+1][n+1];
for( i=0;i<=n;i++)
{
for( j=0;j<=n;j++)
{
dp[i][j]=0;
dp_smoke[i][j]=0;
}
}
for(i=1;i<=n;i++)
dp[i][i]=arr[i];
for(l=2;l<=n;l++)
{
for(i=1;i<=n-l+1;i++)
{
j=i+l-1;
dp[i][j]=INT_MAX;
smok=INT_MAX;
for(k=i;k<=j-1;k++)//diagonal
{
if(smok>dp[i][k]*dp[k+1][j]+dp_smoke[i][k]+dp_smoke[k+1][j])
{
smok=dp[i][k]*dp[k+1][j]+dp_smoke[i][k]+dp_smoke[k+1][j];
s=k;
}
}
dp[i][j]=(dp[i][s]+dp[s+1][j])%100;
dp_smoke[i][j]=smok;
}
}
/*
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
cout<<endl<<endl;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
cout<<dp_smoke[i][j]<<" ";
}
cout<<endl;
}
/* for(i=0;i<n;i++)
{
for(j=)
}
*/
return dp_smoke[1][n];
}
int main()
{
long long int n,i;
while(scanf("%lld",&n)==1)
{
//printf("give the no of matrices\n");
/*if()
return 0;*/
//printf("give the row column matrix\n");
long long int arr[n+1];
arr[0]=0;
for(i=1;i<=n;i++)
scanf("%lld",&arr[i]);
cout<<min_mul(arr,n)<<endl;
}
return 0;
}
Tuesday, 16 December 2014
prime1 spoj
PRIME1 (SPOJ)
in the prime1 question the , the click point was that the range in which we had to print all the prime number was very small in comparison to the overall range of numbers.. So what we did was we found out all the possible prime factor within that range that(10^9) that could be a prime divisor for any number within the overall range...
Now one possibility is that we will compute all the prime numbers present within (10^9) but that is allot of work in comparison to the computing only in given ranges
so we decided to opt for the latter and computed only those prime numbers which were asked for
since the range is 10^5 and over all constraint is 10^9
it would take 10^4 test cases to beat the second method and make the 1st method more effective
Code:
#include <stdio.h>
int main()
{
unsigned long long a[31625],b[100005],d,e,f,i,j,t,m,n;
long long c;
for(i=0;i<100005;i++)
b[i]=0;
for(i=0;i<31625;++i)
a[i]=0;
for(i=2;i<179;i++)
if(!a[i])
for(j=2;j*i<31625;j++)
a[i*j]=1;
scanf("%llu",&t);
while(t--)
{
scanf("%llu",&m);
scanf("%llu",&n);
for(i=2;i<31625 && i*i<n;i++)
{ if(!a[i])
for(j=(m/i)*i;j<=n;j+=i)
{ c=j-m;
/*if(j==2 || j==3)
continue;
if(j==1)b[j]=1;*/
if(c>=0 && c<100001 && j!=i){
b[c]=1;
//printf("%lld\n",c+m);
}
}
}
for(i=0;i<=n-m;i++)
if(!b[i] && m+i!=1)
printf("%lld\n",m+i);
for(i=0;i<=n-m;i++)
b[i]=0;
}
}
in the prime1 question the , the click point was that the range in which we had to print all the prime number was very small in comparison to the overall range of numbers.. So what we did was we found out all the possible prime factor within that range that(10^9) that could be a prime divisor for any number within the overall range...
Now one possibility is that we will compute all the prime numbers present within (10^9) but that is allot of work in comparison to the computing only in given ranges
so we decided to opt for the latter and computed only those prime numbers which were asked for
since the range is 10^5 and over all constraint is 10^9
it would take 10^4 test cases to beat the second method and make the 1st method more effective
Code:
#include <stdio.h>
int main()
{
unsigned long long a[31625],b[100005],d,e,f,i,j,t,m,n;
long long c;
for(i=0;i<100005;i++)
b[i]=0;
for(i=0;i<31625;++i)
a[i]=0;
for(i=2;i<179;i++)
if(!a[i])
for(j=2;j*i<31625;j++)
a[i*j]=1;
scanf("%llu",&t);
while(t--)
{
scanf("%llu",&m);
scanf("%llu",&n);
for(i=2;i<31625 && i*i<n;i++)
{ if(!a[i])
for(j=(m/i)*i;j<=n;j+=i)
{ c=j-m;
/*if(j==2 || j==3)
continue;
if(j==1)b[j]=1;*/
if(c>=0 && c<100001 && j!=i){
b[c]=1;
//printf("%lld\n",c+m);
}
}
}
for(i=0;i<=n-m;i++)
if(!b[i] && m+i!=1)
printf("%lld\n",m+i);
for(i=0;i<=n-m;i++)
b[i]=0;
}
}
Saturday, 13 December 2014
EDIT DISTANCE AND LCS
The edit distance and lcs are very much related
and the relation is
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
but
The edit distance when only insertion and deletion is allowed (no substitution), or when the cost of the substitution is the double of the cost of an insertion or deletion, is: in terms of lcs
spoj edist soultion
#include<stdio.h>
#include<string.h>
char a[1000000],b[1000000];
int k[20001][2001];
int mi(int a,int b,int c)
{
if(a<=b && a<=c )
return a;
if(b<=a && b<=c )
return b;
if(c<=a && c<=b )
return c;
}
int main()
{
int l1,l2,t;
// printf("%d",mi(1,0,3));
scanf("%d",&t);
while(t--)
{
scanf("%s",a);
scanf("%s",b);
l1=strlen(a);
l2=strlen(b);
for(int i=0;i<=l1;i++)
k[i][0]=i;
for(int i=0;i<=l2;i++)
k[0][i]=i;
for(int i=1;i<=l1;i++)
{ int c=0;
for(int j=1;j<=l2;j++)
{
if(a[i-1]==b[j-1])
c=0;
else
c=1;
k[i][j]=mi(k[i-1][j]+1,k[i][j-1]+1,k[i-1][j-1]+c);
}
}
printf("%d\n",k[l1][l2]);
}
}
explanation
we find the minimum from all the three up, left and up-left diagonal
the up and left diagonal will always be added with one and computed where as
if a[i]==a[j] then the upleft diagonal will be added with zero (0)
else if a[i] != a[j] , then the upleft diagonal will be adder with 1 and computed .
but
The edit distance when only insertion and deletion is allowed (no substitution), or when the cost of the substitution is the double of the cost of an insertion or deletion, is: in terms of lcs
spoj edist soultion
#include<stdio.h>
#include<string.h>
char a[1000000],b[1000000];
int k[20001][2001];
int mi(int a,int b,int c)
{
if(a<=b && a<=c )
return a;
if(b<=a && b<=c )
return b;
if(c<=a && c<=b )
return c;
}
int main()
{
int l1,l2,t;
// printf("%d",mi(1,0,3));
scanf("%d",&t);
while(t--)
{
scanf("%s",a);
scanf("%s",b);
l1=strlen(a);
l2=strlen(b);
for(int i=0;i<=l1;i++)
k[i][0]=i;
for(int i=0;i<=l2;i++)
k[0][i]=i;
for(int i=1;i<=l1;i++)
{ int c=0;
for(int j=1;j<=l2;j++)
{
if(a[i-1]==b[j-1])
c=0;
else
c=1;
k[i][j]=mi(k[i-1][j]+1,k[i][j-1]+1,k[i-1][j-1]+c);
}
}
printf("%d\n",k[l1][l2]);
}
}
explanation
we find the minimum from all the three up, left and up-left diagonal
the up and left diagonal will always be added with one and computed where as
if a[i]==a[j] then the upleft diagonal will be added with zero (0)
else if a[i] != a[j] , then the upleft diagonal will be adder with 1 and computed .
Subscribe to:
Posts (Atom)