[algogeeks] Spoj AMR10D

[emmy]

http://www.spoj.com/problems/AMR10D/

A number is a multiple of 11, when its digits are given alternate signs 
(starting with positive from right) and added w.r.t the signs gives a 
number modulo 11.

The question is asking to partition the given numbers into two groups say 
S1 and S2 such that the difference between their cardinalities is minimum 
and
(sum of all elements in S1) - (sum of all elements in S2) is divisible by 
11.

The question looks like dp. 

d( i , c, s') = 1 if there exists a subset S of {a1,a2,...ai} such that 
elements of S sum to s' and S has cardinality c.

A state like this will increase the running time.

Please help.

-- 
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.

[algogeeks] Spoj FARIDA

[emmy]

problem : http://www.spoj.com/problems/FARIDA/

what is wrong with this code? The algorithm is pretty straight forward

#includestdio.h
#includestdlib.h
int main(void)
{
int t,n,i;
scanf(%d,t);
long long int s1,s2,s=0,a,temp;
int c=1;
while(t--)
{
  scanf(%d,n);
  if(n==0)
  { printf(Case %d: 0\n,c);
c++;
continue;
  }
  scanf(%lld,s1);
  
  if(n==1)
  { printf(Case %d: %lld\n,c,s1);
c++;
continue;
  }
  scanf(%lld,s2);
  
  for(i=2;in;i++)
   { scanf(%lld,a);
 temp=s2;
 s2=s1+as2?s1+a:s2;
 s1=temp;
   }
   s=s1s2?s1:s2;
   
   printf(Case %d: %lld\n,c,s);
   c++;
} 
   // scanf(%d,i);
return 0;
}


-- 
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.

[algogeeks] Re: Horrible Queries on spoj

[emmy]

I saw other solutions which were accepted with long long int. So apart from 
the constraints is the algorithm correct?

On Tuesday, February 26, 2013 12:24:44 PM UTC+5:30, emmy wrote:

 Problem statement http://www.spoj.com/problems/HORRIBLE/

 Here http://ideone.com/NhDuYo 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.

[algogeeks] Re: Horrible Queries on spoj

[emmy]

Thank you very much! that helped.

On Tuesday, February 26, 2013 12:24:44 PM UTC+5:30, emmy wrote:

 Problem statement http://www.spoj.com/problems/HORRIBLE/

 Here http://ideone.com/NhDuYo 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.

[algogeeks] Re: Horrible Queries on spoj

[emmy]

please help

On Tuesday, February 26, 2013 12:24:44 PM UTC+5:30, emmy wrote:

 Problem statement http://www.spoj.com/problems/HORRIBLE/

 Here http://ideone.com/NhDuYo 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.

[algogeeks] Horrible Queries on spoj

[emmy]

Problem statement http://www.spoj.com/problems/HORRIBLE/

Here http://ideone.com/NhDuYo 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.

[algogeeks] DP equation for interval problem

[emmy]

please help me with the following problem:
http://www.spoj.com/problems/JUICE/

bit mask will require very large memory.
If I sort the intervals in decreasing order of their start time.. I still 
cant make it to a dp
If I sort the intervals in decreasing order of their finish times I am 
still not getting a recurrence for dp that is valid
If I convert this to an interval graph, I have to find the maximum number 
of vertices that can be included in some clique of size =3. But this also 
seems like a brute force approach. 

Which approach to try?? please help!!

--