Translate

Monday 19 January 2015

SPOJ ANARC05B PROBLEM SOLUTION(The Double Helix) 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
HII GUYS 
this is the application of Greedy and Binary search algorithm...........
so first of all Important Thing is that U should know what are these algorithms.....

Binary search Algorithm::

let say u have an array a[]   and u want to search a item x in it then .........

int binarySearch(int a[],int x,int lower_index,int higher_index)
{
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]==item)
return mid;   //i.e index of that item will be return if it found
else
{
if(a[mid]>item)
higher_index=mid-1;
else
lower_index=mid+1;
}
}
return -1;   //any thing that u want to return it means item is not found in array a[]
}





Greedy Algorithm::


1.Greedy Algorithms are use for the optimisation problems
2.This technique can be apply only for the problem that has the property that:at every
    step we make some choice on the basis of which is best at that moment and we get the 
   optimal solution of that problem......
3.One important Thing is If any problem can be solved by Greedy as well as by 
     DP(Dynamic Programming) then try to do that by greedy bcz Greedy solution is more
     efficient Than DP in most of the cases.





I HOPE YOU GOT THE LOGIC OF BOTH ALGORITHM JUST TRY THE PROBLEM
ONCE AGAIN IF STILL U ARE NOT ABLE TO DO THAT U CAN REFER MY SOLUTION
GIVEN BELOW...........

MY AC c++ SOUTION IS::


#include<cstdio>
#include<iostream>
using namespace std;
#define max(a,b) a>b?a:b
#define mod 10005
int a[mod],b[mod],m,n;
int suma[mod],sumb[mod];
int binary(int val)
{
 int low=0,high=m-1,mid;
 while(low<=high)
 {
  mid=(low+high)/2;
  if(b[mid]==val)
  {
   return mid;
  }
  else
  {
   if(b[mid]>val)
   high=mid-1;
   else
   low=mid+1;
  }
 }
 return -1;
}
int main()
{
 scanf("%d",&n);
 do
 {
  int i,sum=0;
  for(i=0;i<n;i++)
  {
   scanf("%d",&a[i]);
   sum+=a[i];
   suma[i]=sum;
  }
  scanf("%d",&m);
  sum=0;
  for(i=0;i<m;i++)
  {
   scanf("%d",&b[i]);
   sum+=b[i];
   sumb[i]=sum;
  }
  int o1=0,o2=0,n1=0,n2=0,x,y=0;
  int s1,s2,ans=0;
  for(i=0;i<n;i++)
  {
   x=binary(a[i]);
   if(x>=0)
   {
    y++;
    n2=x;
    n1=i;
    if(y==1)
    {
     s1=suma[n1];
     s2=sumb[n2];
    }
    else
    {
     s1=suma[n1]-suma[o1];
     s2=sumb[n2]-sumb[o2];
    }
    ans+=max(s1,s2);
    o1=n1;
    o2=n2;
   }
  }
  if(y>0)
  {
  s1=suma[n-1]-suma[o1];
  s2=sumb[m-1]-sumb[o2];
    }
    else
    {
   s1=suma[n-1];
   s2=sumb[m-1];
    }
  ans+=max(s1,s2);
  printf("%d\n",ans);
  scanf("%d",&n);
 }while(n!=0);
 return 0;
}
at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Working With Java Collections