Re: [algogeeks] Minimal number of swaps

[tec]

It's essentially the same as kumar's algorithm.
a[n - 1] records the total number of 1's, ie. K;
a[a[n-1]-1] = a[K-1] records the number of 1's in the first K elements.
the difference K-a[K-1] is the number of 0's in the first K elements, to be
swapped for remaining 1's.

2016-04-19 16:54 GMT+08:00 ranganath g :

> Hey Sachin,
>
> What is the correctness of your code? I mean how do you say that this is
> give the right answer
>
> --
> 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.
>



-- 
__

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

Re: [algogeeks] 25 persons seated in a round table puzzle

[tec]

Another approach:

On the state [image: F=\{H_f,P_f\}], where each person holds exactly
one of [image:
H=\{25,25,24,24,\cdots,14,14,13\}], and keep passing on the rest 25
cards [image:
P=\{1,1,2,2,\cdots,12,12,13\}] to the left. Denote this as final state. In
this state, in every 25 rounds, the one holding 13 will get the other 13
once, thus having equal number on both cards.

On some state [image: S_i=\{H_i, P_i\} \ne F], there must be some [image: x
\in H_i], [image: y \in P_i] that [image: xy]. Suppose person [image: i]
holds card x, and card y is passed on to the [image: k_{th}] person(0k25)
to the right of person i.

Consider the next k-1 rounds: a) person i swaps card x for larger one to
hold; b) card x is hold by some one, no longer passing on; c) neither a nor
b happens, then person i holds card x and gets card y in [image: k_{th}]
round, thus passing on card x in the next round.

In all cases, someone swaps his holding card for larger one, and state [image:
\{H_i,P_i\}] changes with [image: \sum H_i] strictly increasing. Thus we
show that in any state other than final state F, state change must happen
within next 24 rounds.

On the other hand, the total increase in all rounds cannot exceed

[image: ((25+25+24+24+\ldots+14+14+13)-(1+1+2+2+\ldots+12+12+13)) = 312].

So there are no more than 312 state changes, each happening in at most 24
rounds after the previous change, ending with final state F, after which in
every 25 rounds one of the person gets 2 cards with number 13.

*tl;dr. After at most 312*24 rounds, the final state F is reached, when
each person holds one of [image: \{25,25,24,24,\cdots,14,14,13\}]. Then
with at most 25 extra rounds, one person get 2 cards with number 13.**
​

2015-08-19 19:43 GMT+08:00 tec technic@gmail.com:

 Consider each person holding 1 card (the larger) and passing 1 card around
 (the smaller, passing to his left).
 There are 25 cards on hold and 25 cards passing around at a time.
 When a person get a number smaller than his card on hold, he keeps the new
 card and passes on the original hold card (denoting this as a swap). In
 this case, the number on the card he holds strictly increases.
 Since the sum of the numbers on all 25 cards holding by someone cannot
 larger than 2*(25+24+...+14)+13 = 481, the number of swaps is finite in all
 possible scenario.

 Now prove by contradiction:
 Suppose at any point of time, no person will have same number on both his
 cards. then the passing on can continue infinitely.
 There must be a time point t, that no swaps occur after this point.
 Now we examine consequent 25 turns after t, the card hoding by each
 person, and the set of cards passing around, do not change in this period.
 Denoting the card hoding by i'th person as hi, and the card passing on
 from i'th person to the left at time t is pi.
 For each person i, he receives and passes on cards pi, pi+1, ..., p25, p1,
 ..., pi-1 in those turns, without swaping the card he holds.
 So hi = pj for all i,j in 1..25, i!=j. And the equality can not holds due
 to the assumption.
 ie. min{h1,h2,...,h25}  max{p1,p2,...p25}.
 But no such partition for set {1,1,2,2,...,25,25} exists. (the only
 partition that meets min{h1,h2,...,h25}  max{p1,p2,...p25} is
 {1,1,2,2,...,12,12,13} and {13,14,14,...,25,25})
 That contradicts our assumption, thus proved the original claim.



 2015-07-22 14:20 GMT+08:00 bujji jajala jajalabu...@gmail.com:

 25 persons are seated in a round table. There are two sets of cards, each
 set having 25 cards  numbered 1,2,3,, 25. Each one of them is given two
 cards from these set of cards.

 Each one will pass on card having smaller number to the one on his left.
 This happens synchronously.( All persons transfer cards at same instant ).
 Prove that at some point of time,
 some person will have same number on both his cards.

 -Thanks
 Bujji

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




 --
 __




-- 
__

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

Re: [algogeeks] 25 persons seated in a round table puzzle

[tec]

Consider each person holding 1 card (the larger) and passing 1 card around
(the smaller, passing to his left).
There are 25 cards on hold and 25 cards passing around at a time.
When a person get a number smaller than his card on hold, he keeps the new
card and passes on the original hold card (denoting this as a swap). In
this case, the number on the card he holds strictly increases.
Since the sum of the numbers on all 25 cards holding by someone cannot
larger than 2*(25+24+...+14)+13 = 481, the number of swaps is finite in all
possible scenario.

Now prove by contradiction:
Suppose at any point of time, no person will have same number on both his
cards. then the passing on can continue infinitely.
There must be a time point t, that no swaps occur after this point.
Now we examine consequent 25 turns after t, the card hoding by each person,
and the set of cards passing around, do not change in this period.
Denoting the card hoding by i'th person as hi, and the card passing on from
i'th person to the left at time t is pi.
For each person i, he receives and passes on cards pi, pi+1, ..., p25, p1,
..., pi-1 in those turns, without swaping the card he holds.
So hi = pj for all i,j in 1..25, i!=j. And the equality can not holds due
to the assumption.
ie. min{h1,h2,...,h25}  max{p1,p2,...p25}.
But no such partition for set {1,1,2,2,...,25,25} exists. (the only
partition that meets min{h1,h2,...,h25}  max{p1,p2,...p25} is
{1,1,2,2,...,12,12,13} and {13,14,14,...,25,25})
That contradicts our assumption, thus proved the original claim.



2015-07-22 14:20 GMT+08:00 bujji jajala jajalabu...@gmail.com:

 25 persons are seated in a round table. There are two sets of cards, each
 set having 25 cards  numbered 1,2,3,, 25. Each one of them is given two
 cards from these set of cards.

 Each one will pass on card having smaller number to the one on his left.
 This happens synchronously.( All persons transfer cards at same instant ).
 Prove that at some point of time,
 some person will have same number on both his cards.

 -Thanks
 Bujji

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




-- 
__

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

Re: [algogeeks] Code for construction of HAFT

[tec]

To construct a HAFT of with N leaves:
a) if N=2^K for some K=0, then construct a complete tree with N leaves.
b) otherwise, suppose 2^K  N  2^(K+1), then
1) construct root node R.
2) construct a complete binary tree with 2^K leaves as the left child of R.
3) construct a HAFT with (N-2^K) leaves recursively as the right child of R.

To add a leaf node to the HAFT: (incremental construction)
a) if current tree is empty tree. Create a tree of single node.
b) if current tree is a complete binary tree, then:
   1. create a root node R;
   2. make old complete binary tree the left child of R;
   3. create a leaf node as right child of R.
c) otherwise, add a leaf to the right child of HAFT recursively.



2013/3/15 Megha Agrawal megha1...@iiitd.ac.in


 Hello,

 HAFT is a rooted binary tree in which every non-leaf node v has following
 properties:
 i. v has exactly two childrens.
 ii. the left child of v is root of complete binary subtree, containing
 half or more of v's descendants.

 Some examples of HAFT are given in attached image.

 Can anybody provide algo/code for construction of HAFT?

 --
 Regards,
 Megha Agrawal


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

Re: [algogeeks] Re: Horrible Queries on spoj

[tec]

Overflow can happen in intermediate calculations.

For example: sums[i]+=(q-p+1)*v;
q,p,v are of type long int, so the multiplication is performed in long int,
then convert the result to long long int and added to sum[i].

2013/2/27 emmy foramlakh...@gmail.com

 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.






-- 
__

-- 
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] Proof Dutch national flag problem

[tec]

What do you want proof for? Correctness? Complexity?

For the correctness, you can easily prove the invariant mentioned using
mathematical induction.

The complexity is obviously O(N). Hi-Mid=N-1 at beginning, and decreased by
1 on each step.


2013/2/27 shady sinv...@gmail.com

 Any proof for this ?
 http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/

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

Re: [algogeeks] Re: Horrible Queries on spoj

[tec]

One possible issue is overflow.
Noting that each number can be as large as 1*10^7,
and the total sum can reach 10^17.

2013/2/27 emmy foramlakh...@gmail.com

 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.






-- 
__

-- 
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: MAX number of ones

[tec]

int max_ones(int mat[N][N])
{
int r = 0, c = 0;
while(r  N) {
  if(c  N  mat[r][c] == '1')
  ++c;
  else
  ++r;
}
return c;
}


On Dec 27, 3:24 am, jyoti saini jyotisaini1...@gmail.com wrote:
 A NxN matrix is given containing only 1’s and 0’s. Every row is sorted in
 descending order. Find the row containing maximum no. of ones.
 time complexity-O(n);
 --

 Jyoti Saini.
 B.Tech-Final year.
 Information Technology.
 National Institute of Technology,Kurukshetra.
 Alt Email jsa...@yahoo-inc.com email-jsa...@yahoo-inc.com
 +91-9813799528,+91-8030776217, 0172-4635398.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: ACM-ICPC Kanpur 2011 LCM Extreme

[tec]

the required sum is:
F(n) = sum({lcm(x,y)|1=xy=n})
 = sum({lcm(x,y)|1=x=n, 1=y=n, x#y})/2
 =(sum({lcm(x,y)|1=x=n, 1=y=n}) - n(n+1)/2)/2
 =(sum({sum({lcm(x,y)|1=x=n, 1=y=n, gcd(x,y)=d}) | 1=d=n}) -
n(n+1)/2)/2

let f(n) = sum({lcm(x,y)|x=n, y=n, gcd(x,y)=1})
for gcd(x,y)=d, let x'= x/d, y' = y/d, then (x',y') = 1
sum({lcm(x,y)|x=n, y=n, lcm(x,y)=d})
 = sum({lcm(x'd,y'd)|x'd=n, y'd=n, lcm(x'd,y'd)=d})
 = d*sum({lcm(x',y')|x'=[n/d], y'=[n/d], lcm(x',y')=1})
 = d*f([n/d])
so F(n) = (sum({d*f([n/d]) | 1=d=n}) - n(n+1)/2)/2

f(n) = sum({lcm(x,y)|1=x=n, 1=y=n, gcd(x,y)=1}) = sum({xy|1=x=n,
1=y=n, gcd(x,y)=1})
let G(n) = sum({xy|1=x=n, 1=y=n})
then G(n) = sum({sum({xy|1=x=n, 1=y=n, gcd(x,y)=d})|1=d=n})
again for gcd(x,y)=d let x'= x/d, y' = y/d, then (x',y') = 1
sum({xy|1=x=n, 1=y=n, gcd(x,y)=d})
 = sum({x'd*y'd|1=x'd=n, 1=y'd=n, gcd(x'd,y'd)=d})
 = d^2*sum({x'y'|1=x'=[n/d], 1=y'=[n/d], gcd(x',y')=1})
 = d^2*f([n/d])
so G(n) = sum({d^2*f([n/d])|1=d=n})

as G(n) = sum({xy|1=x=n, 1=y=n}) = (1+2+...+n)*(1+2+...+n) = n^2*(n
+1)^2/4
f(n) = G(n) - sum({d^2*f([n/d])|2=d=n})
 = n^2*(n+1)^2/4 - sum({d^2*f([n/d])|2=d=n})

Using this sieve to calculate f(n), then use f(n) to calculate F(n).
The direct implementation is O(n^2) time and O(n) space, and can be
optimized to O(n^1.5) time.
(break the interval by n^(1/2) into 2 parts, and use different method
in each interval)


On Dec 18, 8:04 pm, arun kumar kumar0...@gmail.com wrote:
 long long function( int n ) {
     long long res = 0;
     for( int i = 1; i = n; i++ )
         for( int j = i+1; j = n; j++ )
                   res+=lcm(i,j);
     return res;

 }

 N=5*10^6 and TestCases=25000.. TimeLimit=5s
 Can anyone give hints to solve this ?
 Thanks in advance !

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Question --

[tec]

mask = (1(j+1))-(1i);
n = (n(~mask)) | m;


On Sep 20, 3:43 pm, abhinav gupta guptaabhinav...@gmail.com wrote:
 You can also solve the problem by using bit operators. by using| !
 .
 Need sm thinking in dat..No time rite nw!

 On Tue, Sep 20, 2011 at 1:12 PM, abhinav gupta 
 guptaabhinav...@gmail.comwrote:









  Its because o/p should look like dat.Bt dats simple you can do it
  by multiplying bits to power(2, i) and
  adding all expressions.Simple!
  On Tue, Sep 20, 2011 at 1:09 PM, abhinav gupta 
  guptaabhinav...@gmail.comwrote

   In the first loop bits are added into the array N and M .I have taken two
  integers n and m .
  Caution :
  declare

  int N[31]={0};
  int M[31]={0};
  int n,m,i,j;

    On Tue, Sep 20, 2011 at 1:02 PM, Ishan Aggarwal 
  ishan.aggarwal.1...@gmail.com wrote:

  What are u doing in the first loop running for k=31 to k =0?

  On Tue, Sep 20, 2011 at 12:50 PM, abhinav gupta 
  guptaabhinav...@gmail.com wrote:

  U can use single walker (from 0 till 31) to convert integers N and M
  into array of bits, then
  another walker from i to j to replace values.

  for(k=31;k=0;k++)
  {
  N[k]=n  01;
  M[k]=m 01;
  n=1;
  m=1;
  }

  for(k=i;k=j;k++)
  N[k]=M[k];

    On Tue, Sep 20, 2011 at 12:44 PM, abhinav gupta 
  guptaabhinav...@gmail.com wrote:

  I can tell you the logic.Take two arrays N and M, put their bits in
  the array.
  Now using i and j index replace the value of N[j] to n[i] by M[j] to
  M[i].
    On Tue, Sep 20, 2011 at 12:33 PM, Ishan Aggarwal 
  ishan.aggarwal.1...@gmail.com wrote:

  You are given two 32-bit numbers, N and M, and two bit positions, i
  and j.Write a method to set all bits between i and j in N equal to M 
  (e.g.,
  M becomes a substring of N located at i and starting at j).

  EXAMPLE:

  Input: N = 100, M = 10101, i = 2, j = 6

  Output: N = 10001010100

  --
  Kind Regards
  Ishan Aggarwal
  [image: Aricent Group]
  Presidency Tower-A, M.G.Road,Sector-14
  Gurgaon,Haryana.122015 INDIA
  Phone : +91-9654602663
  ishan2.aggar...@aricent.com puneet.ar...@aricent.com

  --
  You received this message because you are subscribed to the Google
  Groups Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

  --
  @ |3  # ! /\/ @ \./

  --
  @ |3  # ! /\/ @ \./

  --
  You received this message because you are subscribed to the Google
  Groups Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

  --
  Kind Regards
  Ishan Aggarwal
  [image: Aricent Group]
  Presidency Tower-A, M.G.Road,Sector-14
  Gurgaon,Haryana.122015 INDIA
  Phone : +91-9654602663
  ishan2.aggar...@aricent.com puneet.ar...@aricent.com

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

  --
  @ |3  # ! /\/ @ \./

  --
  @ |3  # ! /\/ @ \./

 --
 @ |3  # ! /\/ @ \./

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Spoj Problem Help

[tec]

The final sequence should be (0,0),(1,1),(2,3),(3,5),(5,8)...

 (0,0) and (0,1) both finishes in 0 iteration.
 (1,2)-(0,1) and (1,1)-(0,1) both finishes in 1 iteration.
So (0,1) and (1,2) is discarded.

For the rest: (0,1) - (1,2) - (2,3) - (3,5) - (5,8) - ...
finishes in:   2   3  4
 ... iterations respectively.

2011/5/23 Akshata Sharma akshatasharm...@gmail.com:
 @tec: the sequence should be like (0,1),(1,1),(1,2),(2,3),(3,5),(5,8)... or
 m i wrong?

 On Mon, May 23, 2011 at 11:08 AM, Aakash Johari aakashj@gmail.com
 wrote:

 Matrix exponentiation can help i think

 On Sun, May 22, 2011 at 10:36 PM, Akshata Sharma
 akshatasharm...@gmail.com wrote:

 It appers that the problem is just to find the (N+3)th fibonacci number
 for given N. Since N is very large, how to find nth fibonaci number for such
 a large n??

 On Mon, May 23, 2011 at 7:51 AM, tec technic@gmail.com wrote:

 Try thinking backwards.
 (0,1),(1,2),(2,3),(3,5),(5,8),(8,13),...

 2011/5/22 shady sinv...@gmail.com:
  Hey,
  Can anyone tell how to solve this problem in Spoj ? I went through
  some material but there all they were discussing was on complexity and
  not on actual number of iterations.
  http://www.spoj.pl/problems/MAIN74/
 
  Thanks.
 
  --
  You received this message because you are subscribed to the Google
  Groups Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
  http://groups.google.com/group/algogeeks?hl=en.
 
 



 --
 __

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



 --
 -Aakash Johari
 (IIIT Allahabad)




 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
__

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Another SPOJ Problem -SIGSEGV -- Need Help

[tec]

Just try it yourself.
Start with arbitrary  5-byte code you can think of,
then fix the compiling/linking error, taking the hints in compiler
error message.
You will get it in the end.

On May 24, 2:12 am, Dumanshu duman...@gmail.com wrote:
 I want to discuss the solution in C language. I want to test my file
 using gcc compiler. For C the best solution is 5 chars. Any ideas
 about that??

 On May 23, 7:23 pm, saurabh singh saurab...@gmail.com wrote:







  Using the asm construct of c..
  Though i did this problem in native asm and my solution is 3 char ;)...
  The point is you  have to know if not proficient with NASM(Net Assembler
  used by SPOJ)...
  If you need the solution mail me.

  --
  Saurabh Singh
  B.Tech (Computer Science)
  MNNIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Spoj Problem Help

[tec]

Try thinking backwards.
(0,1),(1,2),(2,3),(3,5),(5,8),(8,13),...

2011/5/22 shady sinv...@gmail.com:
 Hey,
 Can anyone tell how to solve this problem in Spoj ? I went through
 some material but there all they were discussing was on complexity and
 not on actual number of iterations.
 http://www.spoj.pl/problems/MAIN74/

 Thanks.

 --
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to 
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at 
 http://groups.google.com/group/algogeeks?hl=en.





-- 
__

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: sequence number puzzle 18april

[tec]

Sort by English:
Eight
Five
Four
Nine
One
Seven
Six
Ten
Three
Two
Zero


On Apr 18, 4:28 pm, Lavesh Rawat lavesh.ra...@gmail.com wrote:
 * sequence number puzzle

 What is special about the following sequence of numbers?
 8 5 4 9 1 7 6 10 3 2 0
 *
 *Update Your Answers at* : Click
 Herehttp://dailybrainteaser.blogspot.com/2011/04/sequence-number-puzzle-1...

 Solution:
 Will be updated after 1 day

 --

                     Never explain yourself. Your friends don’t need it and
 your enemies won’t believe it .

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: sequence number puzzle 18april

[tec]

Sort by English:
Eight
Five
Four
Nine
One
Seven
Six
Ten
Three
Two
Zero


On Apr 18, 4:28 pm, Lavesh Rawat lavesh.ra...@gmail.com wrote:
 * sequence number puzzle

 What is special about the following sequence of numbers?
 8 5 4 9 1 7 6 10 3 2 0
 *
 *Update Your Answers at* : Click
 Herehttp://dailybrainteaser.blogspot.com/2011/04/sequence-number-puzzle-1...

 Solution:
 Will be updated after 1 day

 --

                     Never explain yourself. Your friends don’t need it and
 your enemies won’t believe it .

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: An Interesting Question Calculate nth Power of Integer

[tec]

For big number mathematics, the multiplication time complexity is not
O(1).
And the programming complexity is to be considered as well.

On Mar 24, 3:36 pm, radha krishnan radhakrishnance...@gmail.com
wrote:
 You can do it in (log n) assuming multiplication is O(1)
 suppose u are going to calculate 8 power 33
 u compute 8 power 16 and multiply with the same to get 8 power 32
 then multiply with 8 to get the result







 On Thu, Mar 24, 2011 at 1:04 PM, AAMIR KHAN ak4u2...@gmail.com wrote:
  Try this...
  #include iostream
  #include cmath
  using namespace std;
  #define DIGITS 10001
  void mult(int N,int pro[],int len) {
     int carry = 0;
     for(int i=0;ilen;i++) {
        int temp = pro[i]*N + carry;
        pro[i] = temp%10;
        carry = temp/10;
     }

     if(carry0) {
        pro[len] = carry;
        len++;
     }

  }
  int main() {
     int t,N,E;

     scanf(%d,t);
     while(t--) {
        int pro[DIGITS];
        scanf(%d %d,N,E);
        if(N==1) {
        printf(1 1\n);
        continue;
        }
        pro[0] = 1; int len = 1;
        for(int i=0;iE;i++) {
             mult(N,pro,len);
        }

        for(int i=len-1;i=0;i--) {
           printf(%d,pro[i]);
       }
        printf(\n);

     }
     return 0;
  }

  Here t stands for number of testcases...
  N = the number for which power is to be calculated..
  E = the exponent..
  On Thu, Mar 24, 2011 at 12:22 PM, bittu shashank7andr...@gmail.com wrote:

  How you will print the 100th power of a single digit( which is of type
  int). How do you maintain that big number in memory?

  Lets C The Approach

  Thank  Regards
  Shashank

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Regular exp in Python

[tec]

re.findall(r'a([^a]*)a','000aaaaa')

On Mar 24, 3:40 pm, DD dutta.dipanka...@gmail.com wrote:
  re.findall(r'a(.*)a','000aaaaa') return

 ['aaa']

 what is the regular expression such that it should return
 ['','','','']

 ?

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: SPOJ problem

[tec]

Try precomputing the results for all possible a using mathematical
method, which should be O(N) (N=10^6) in total.
Then answer each query in O(1)  (there can be 10 queries).

On Mar 26, 12:20 pm, saurabh singh saurab...@gmail.com wrote:
 I am very sorry but i dont think i got your point.You suggesting
 interpolation or some other technique?
 Kindly suggest some reference for good precomputation techniques..
 Thanks in advance

 --
 Saurabh Singh
 B.Tech (Computer Science)
 MNNIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: multiply by 2 and subtract by 1

[tec]

2009/8/26 umesh kewat umesh1...@gmail.com:
 hi
 i have one doubt if negative by 1 in a row if any element got zero and again
 doing same operation to get another element to be zero so 1st element is
 negative so could u please tell me the matrix automatically do the positive
 value else as it. if it is negative then ans is No, we will not get O
 matrix(one with all zeroes in it.) else there have some solution to get O
 matrix.
In the problem statement, Now they all have positive integers.
Negative number should be avoid in the solution.

 On Wed, Aug 26, 2009 at 12:13 AM, ankur aggarwal ankur.mast@gmail.com
 wrote:

 I've always wanted to feel the excitement in these interviews. I got a
 chance, and I liked it.

 Here is the question:

 You are given a matrix: r rows, c cols. r x c matrix.

 Now they all have positive integers. Assume that the computer has no
 overflow, it can store all possible integer values.

 Now there are only two operations you can perform on the matrix:

 a. Multiply one whole column (of size r elements) by 2 aij = aij * 2
 b. Decrement a whole row (of size c elements) by 1. aij = aij - 1

 Now you are required to find out if it's possible with these operations to
 convert this matrix into the O matrix. (one with all zeroes in it.)

 If so, how do you solve it? Or when do you decide to terminate?

 give the algo..
 not the code.





 --
 Thanks  Regards

 Umesh kewat

 IIIT-Hyderabad




 




-- 
__

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: Determining if an n-ary tree is balanced or not.

[tec]

I think you are in the right direction. Using DFS, the complexity is
O(m+n) = O(n). No better complexity I think.

2009/6/26 cgirl dmitche...@twmi.rr.com:

 I am trying to determine if an n-ary tree is balanced or not, I have
 been stuck trying several approaches and am getting nowhere. My new
 thought is that i will have to step through each node of the tree, and
 compare the lengths of the roots of the children, making sure there is
 not a difference greater than one in the values for all of the
 children. Am i thinking in the right direction, or is there a simpler
 solution?

 thanks,
 kim

 




-- 
__

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---