[algogeeks] [Off topic] Call for Moderators for Algogeeks
Hi, Does anyone wants to be moderator ? We want someone who is actively participating in discussions and can frequently check the pending tasks for moderation. Shady -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] java
oh..ok thank you for replying :) On Tue, Mar 12, 2013 at 9:10 PM, manish untwal wrote: > according to my understanding the super class object have limited function > like for example > Class - animal : methods/behavior : roam() and eat() > and a sub class hippo : method/behavior : roam(),eat() and swim() > so a hippo is a animal then according to the polymorphic property of java > a reference of animal can refer to object of class hippo and animal but > still the reference can call only the behavior of class animal i.e : animal > A = new hippo() is legal but you can't call A.swim() because it refer to > the animal property of class hippo ie roam and eat...not swim. and also u > can't do this as hippo H = new animal() as this means animal should have > all the property of hippo because it is referred by a hippo reference do > H.swim() should not be a NULL.reply if you get it or not. > P.S : I tried to explain it through an example > > On Tue, Mar 12, 2013 at 8:51 PM, sulekha metta wrote: > >> what ever data members,member functions present in super class are >> applicable to subclass...subclass may contain more additional >> featuresso its obvious that size of subclass object is more than >> superclass object...now lets take an analogy of float(4 bytes) and double( >> 8 bytes) float can be implicitly converted into double( as float size is >> less when compared to double) but not vice versathen why is this not >> applicable to superclass object and subclass object(as size of superclass >> object is less when compared to subclass)? please tell if am wrong! >> >> >> On Tue, Mar 12, 2013 at 7:37 PM, subramony mahadevan > > wrote: >> >>> i think its just a logical reason take animal as superclass bird as >>> subclass ... since we are talking about inheritance it is " is a >>> relationship " ie bird is a animal not vice versa hence we cannot >>> implicitly convert to subclass >>> >>> >>> On Sat, Mar 2, 2013 at 6:18 PM, sulekha metta >>> wrote: >>> Q) why super class object can't be implicitly converted to subclass? is there any specific reason? Thanks in advance! -- sulekha metta B.E computer science osmania university -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit https://groups.google.com/groups/opt_out. >>> >>> >>> >> >> >> >> -- >> sulekha metta >> B.E computer science >> osmania university >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+unsubscr...@googlegroups.com. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > > > -- > With regards, > Manish kumar untwal > Indian Institute of Information Technology > Allahabad (2009-2013 batch) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- sulekha metta B.E computer science osmania university -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Horrible Queries on spoj
Suppose given array is a[0..N-1],
Define s[k]=a[0]+a[1]+...+a[k], k=0..N-1
The problem asks to implement 2 operations:
1) increase a[p],a[p+1]..a[q] by v
2) query a[p]+a[p+1]+..+a[q]
Define array b[0..N-1] and sb[0..N-1]:
b[0] = a[0],
b[k] = a[k] - a[k-1] for k>0,
sb[k] = b[0]+b[1]+..+b[k].
Then a[k] = b[0] + b[1] + .. + b[k]
s[k] = b[0] + (b[0]+b[1]) + .. + (b[0]+b[1]+..+b[k])
= (k+1)b[0] + k*b[1] + .. + b[k]
= (k+1)(b[0]+b[1]+..+b[k]) - (0*b[0]+1*b[1]+..+k*b[k])
Define c[k] = k * b[k] for k=0..N-1, and sc[k] = c[0]+c[1]+..+c[k].
Then s[k] = (k+1)*sb[k] - sc[k]
(b[k],sb[k]) and (c[k],sc[k]) can be maintained by 2 BITs
1) is archived by updating b[p], b[q+1], c[p] and c[q+1]
2) can be easily computed after query sb[k] and sc[k] (k=p-1,q)
2013/3/13 Aman Jain
> Here in this code given below,
> Horrible is solved using 2 BIT(binary indexed trees)
> Can Someone please explain the Logic of the program or suggest other way
> to do the same ques using BIT
> problem here coming is here range query and range updation both
> simultaneously which is difficult with BIT.
> #include
> #include
>
> using namespace std;
>
> long long bit1[12],bit2[12];
>
> void update(long long bit[], int idx, long long val){
> for(int x = idx;x <= 11;x += x & -x)
> bit[x] += val;
> }
>
> long long query(long long bit[], int idx){
> long long ret = 0;
>
> for(int x = idx;x > 0;x -= x & -x)
> ret += bit[x];
>
> return ret;
> }
>
> int main(){
> int T,N,Q;
>
> scanf("%d",&T);
>
> while(T--){
> scanf("%d %d",&N,&Q);
>
> memset(bit1,0,sizeof bit1);
> memset(bit2,0,sizeof bit2);
>
> for(int i = 0,op,l,r,v;i < Q;++i){
> scanf("%d %d %d",&op,&l,&r);
>
> if(op == 0){
> scanf("%d",&v);
>
> update(bit1,l,v); update(bit1,r + 1,-v);
> update(bit2,l,-(long long)v * (l - 1)); update(bit2,r +
> 1,(long long)v * r);
> }else{
> printf("%lld\n",query(bit1,r) * r + query(bit2,r) -
> query(bit1,l - 1) * (l - 1) - query(bit2,l - 1));
> }
> }
> }
>
> return 0;
> }
>
>
> On Tue, Feb 26, 2013 at 3:13 PM, dheeraj hasija <
> dheerajhasija1...@gmail.com> wrote:
>
>> you can have this code for better understanding
>>
>> #include
>>
>> long long v[50];
>> long long a[50];
>>
>>
>> inline long long getvalue( int index, int low, int high)
>> {
>>return a[index] + (high-low+1)*v[index];
>> }
>>
>> long long update( long long index, long long down, long long up, long
>> long low, long long high,long long value)
>> {
>> long long mid = (low+high)/2;
>>
>>
>>
>> if( down <= low && high <= up)
>> {v[index] += value;
>>
>> return 0;
>> }
>>
>> if(low> up || high < down)
>> return 0;
>>
>> v[2*index] += v[index];
>> v[2*index+1] += v[index];
>> v[index] = 0;
>>
>> update( 2*index, down,up, low,mid,value);
>> update(2*index+1 , down,up, mid+1, high,value);
>>
>>
>>
>> a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
>> mid+1,high);
>> return 0;
>>
>>
>> }
>>
>>
>>
>> long long query( long long index, long long down, long long up, long long
>> low, long long high)
>> {
>>
>> //printf("%lld %lld %lld %lld",low,high,up,down);
>>
>> long long mid;
>> mid = (low+high)/2;
>>
>>
>>
>>
>> if( down <= low && high<=up)
>> return a[index] + v[index]*( high-low+1);
>>
>> if( low > up || high < down)
>> return 0;
>>
>>
>> v[2*index] += v[index];
>> v[2*index+1] += v[index];
>>
>>
>>
>>
>> a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
>> mid+1,high);
>>
>>
>>
>> v[index] =0;
>>
>> return query( 2*index,down,up, low, mid)+query(2*index+1, down,up,
>> mid+1, high);
>>
>>
>>
>>
>> }
>>
>>
>>
>>
>> int main()
>> {
>> long long t,n,p,quer,vr,val,i,q;
>>
>>
>> scanf("%lld",&t);
>>
>> while(t--)
>> {
>> scanf("%lld%lld",&n,&quer);
>>
>> for(i=0;i<=4*n;i++)
>> a[i] =0,v[i] =0;
>>
>>
>> while(quer--)
>> {
>>// for(i=1;i<8;i++)
>> //printf("%lld ",a[i]);
>> //printf("\n");
>>
>> scanf("%lld%lld%lld",&vr,&p,&q);
>> if(!vr)
>> {scanf("%lld",&val);
>> update( 1,p,q,1,n,val);
>> }
>> else
>> printf("%lld\n",query( 1, p, q, 1, n));
>> }
>>
>> //printf("bye");
>>}
>>
>> return 0;
>> }
>>
>>
>>
>> On Tue, Feb 26, 2013 at 12:24 PM, emmy wrote:
>>
>>> Problem statement is my code. I am using segment trees +
>>> Lazy propagation. Please help me figure out
Re: [algogeeks] Horrible Queries on spoj
Here in this code given below,
Horrible is solved using 2 BIT(binary indexed trees)
Can Someone please explain the Logic of the program or suggest other way to
do the same ques using BIT
problem here coming is here range query and range updation both
simultaneously which is difficult with BIT.
#include
#include
using namespace std;
long long bit1[12],bit2[12];
void update(long long bit[], int idx, long long val){
for(int x = idx;x <= 11;x += x & -x)
bit[x] += val;
}
long long query(long long bit[], int idx){
long long ret = 0;
for(int x = idx;x > 0;x -= x & -x)
ret += bit[x];
return ret;
}
int main(){
int T,N,Q;
scanf("%d",&T);
while(T--){
scanf("%d %d",&N,&Q);
memset(bit1,0,sizeof bit1);
memset(bit2,0,sizeof bit2);
for(int i = 0,op,l,r,v;i < Q;++i){
scanf("%d %d %d",&op,&l,&r);
if(op == 0){
scanf("%d",&v);
update(bit1,l,v); update(bit1,r + 1,-v);
update(bit2,l,-(long long)v * (l - 1)); update(bit2,r +
1,(long long)v * r);
}else{
printf("%lld\n",query(bit1,r) * r + query(bit2,r) -
query(bit1,l - 1) * (l - 1) - query(bit2,l - 1));
}
}
}
return 0;
}
On Tue, Feb 26, 2013 at 3:13 PM, dheeraj hasija wrote:
> you can have this code for better understanding
>
> #include
>
> long long v[50];
> long long a[50];
>
>
> inline long long getvalue( int index, int low, int high)
> {
>return a[index] + (high-low+1)*v[index];
> }
>
> long long update( long long index, long long down, long long up, long long
> low, long long high,long long value)
> {
> long long mid = (low+high)/2;
>
>
>
> if( down <= low && high <= up)
> {v[index] += value;
>
> return 0;
> }
>
> if(low> up || high < down)
> return 0;
>
> v[2*index] += v[index];
> v[2*index+1] += v[index];
> v[index] = 0;
>
> update( 2*index, down,up, low,mid,value);
> update(2*index+1 , down,up, mid+1, high,value);
>
>
>
> a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
> mid+1,high);
> return 0;
>
>
> }
>
>
>
> long long query( long long index, long long down, long long up, long long
> low, long long high)
> {
>
> //printf("%lld %lld %lld %lld",low,high,up,down);
>
> long long mid;
> mid = (low+high)/2;
>
>
>
>
> if( down <= low && high<=up)
> return a[index] + v[index]*( high-low+1);
>
> if( low > up || high < down)
> return 0;
>
>
> v[2*index] += v[index];
> v[2*index+1] += v[index];
>
>
>
>
> a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
> mid+1,high);
>
>
>
> v[index] =0;
>
> return query( 2*index,down,up, low, mid)+query(2*index+1, down,up,
> mid+1, high);
>
>
>
>
> }
>
>
>
>
> int main()
> {
> long long t,n,p,quer,vr,val,i,q;
>
>
> scanf("%lld",&t);
>
> while(t--)
> {
> scanf("%lld%lld",&n,&quer);
>
> for(i=0;i<=4*n;i++)
> a[i] =0,v[i] =0;
>
>
> while(quer--)
> {
>// for(i=1;i<8;i++)
> //printf("%lld ",a[i]);
> //printf("\n");
>
> scanf("%lld%lld%lld",&vr,&p,&q);
> if(!vr)
> {scanf("%lld",&val);
> update( 1,p,q,1,n,val);
> }
> else
> printf("%lld\n",query( 1, p, q, 1, n));
> }
>
> //printf("bye");
>}
>
> return 0;
> }
>
>
>
> On Tue, Feb 26, 2013 at 12:24 PM, emmy wrote:
>
>> Problem statement is my code. I am using segment trees +
>> Lazy propagation. Please help me figure out my mistake.
>> I am getting a WA
>>
>> Note:
>> invariant : l <= p <=q <= r
>>
>> l and r are the limits of that node
>> p and q is the query range.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>
>
>
> --
> *Dheeraj Hasija*
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https
