Re: [algogeeks] How to Solve This
@anshu- your code works fine.but can you plz explain how you concluded
this codei mean what's the logic behind to check myset.size() psize
?? ...as you are assuming that it will be increase string and check
until this condition satisfies ??
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99
On Wed, Oct 12, 2011 at 10:29 AM, shady sinv...@gmail.com wrote:
thanks a lot for replying to the post... but try posting algorithm rather
than actual code...
On Mon, Oct 10, 2011 at 2:17 PM, anshu mishra
anshumishra6...@gmail.comwrote:
string all1Multiple(int x)
{
string s;
setint mySet;
mySet.push(0);
int psize, r=1;
do
{
psize = mySet.size();
s += '1';
r = r % x;
mySet.push(r);
r = r * 10 + 1;
} while(mySet.size() psize);
if (r != 1) return not Possible;
return s;
}
--
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.
Re: [algogeeks] How to Solve This
@amol
I was not sure that for every number that has 3 in its unit place has one
multiple which has all one. So I used that is if the remainder is coming
that already appeared stop there coz it will make stuck in a loop.
for ex. remainders are
1 3 19 23 37 1 3 19 that will repeat.
but it in this case u can remove the set. Code will look more simpler.
string all1Multiple(int x)
{
string s;
int r=1;
do
{
s += '1';
r = r % x;
r = r * 10 + 1;
} while(r != 1);
return s;
}
--
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] Re: Find the later version
WE CAN USE RADIX SORT TO FIND THE MAX VERSION :TRAVERSING FROM LEFT TO RIGHT
(RADIX WILL BE NUMBERS BETWEEN THE POINTS).
It will reduce the search space too.
On Tue, Oct 11, 2011 at 1:58 AM, sumit kumar pathak
sumitkp1...@gmail.comwrote:
*
*regards
- Sumit Kumar Pathak
(Sumit/ Pathak/ SKP ...)
*Smile is only good contagious thing.*
*Spread it*!
On Tue, Oct 11, 2011 at 11:22 AM, DIPANKAR DUTTA
dutta.dipanka...@gmail.com wrote:
what's happen if the versions are not in same length..
For example
v1: 1.1.1.133.2
v2: 1.2
v3: 1.2.3.4..333
v4: 1.2.3.4.5554.222
v5: 1.3.2.2.2.2.2.2.2.2.2.2.2.2
It implies we must be scan from left side one by one ...
In general the we make a some sort of lexical comparison where each
character is a number and separated by number ..
the problem definition is as :
let V1,V2,V3 ...Vn be the n version
let S={1,2,3...n} ,index=0
Latest[S,index]= return Vi if { Max(ALL Vi[k] where i belongs to S )}
is a singleton, else
= return Latest[ set of all index belongs to { Max(ALL
Vi[k] where i belongs to S )}, index+1 ]
On 10/11/11, Dave dave_and_da...@juno.com wrote:
@Karen: It is more complicated than scanning character by character.
E.g., 1.10.3 is older than 1.9.7. I think
snip
you need to parse the
numbers between the dots and compare them
/snip
simple, easier and correct way.
points:
- compare left to right (ofcourse) each version being vector of numbers
- for diffrent size, assume extra ones to be zero while comapring (no
need to store trailing zeros)
one by one. Thus, in the
above example, 1 compares equal to 1, so you keep scanning. Then 10
compares greater than 9 so the first string is number of the newer
version. I did this many years ago in a csh install script for a unix
product.
Dave
On Oct 10, 9:52 pm, bagaria.ka...@gmail.com
bagaria.ka...@gmail.com wrote:
Given two strings describing the version of a particular software need
to
find the later version.
For eg.
1st string = 1.2.4.5
2nd string=1.2.3.5
1st string is the later one.
Can be done using traversing the string and comparing each character
one
after the another. Looking for a better solution with lesser
complexity.
--
Thanks and Regards
*Karan Bagaria*
*MCA Final Year*
Training and Placement Representative
*NIT Durgapur*
--
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.
--
Thanks and Regards,
--
**DIPANKAR DUTTA
Software Development Engineer
Xen Server - OpenStack Development Team (DataCenter and Cloud)
Citrix RD India Pvt Ltd
69/3, Millers Road, Bangalore – 560052
Phone: +91 8147830733
Office: Extn: 16429
Email: dipankar.du...@citrix.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.
--
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.
--
*MOHIT VERMA*
--
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: Algo for Search in a 2D Matrix
@Shiva, not necessarily in upper half take the transpose of example put by Dave and see by yourself There are few observations for this question: 1. kth smallest will always lie in first k*k matrix 2. it wont be part of sqrt(k)*sqrt(k) matrix Thus rest all need to be searched recursively to find the element Any suggestions ? On Oct 10, 10:55 am, shiva@Algo shiv.jays...@gmail.com wrote: id we see the pattern then we can easily find that the kth smallest element lie on the upper half of the k*k submatrix(on the upperleft corner ) we can do search on (k*k)/2 elements to find that On Mon, Oct 10, 2011 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Shubham: So if the matrix is 1 2 3 4 and you want the 2nd smallest, are you saying that it is 4? Dave On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote: im assuming it be a square matrix then kth smallest element will be in a first k*k sub matrix. jst look for smallest element in the diagonal of this matrix. it will give the kth smallest element . On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
i dont think k*k submatrix approach works at all what if k =n size of submatrix will be n*n, which is matrix itself heap seems to be a good approach with a coloring scheme that helps in avoiding duplicates in heap ?? On Wed, Oct 12, 2011 at 7:18 PM, vikas vikas.rastogi2...@gmail.com wrote: @Shiva, not necessarily in upper half take the transpose of example put by Dave and see by yourself There are few observations for this question: 1. kth smallest will always lie in first k*k matrix 2. it wont be part of sqrt(k)*sqrt(k) matrix Thus rest all need to be searched recursively to find the element Any suggestions ? On Oct 10, 10:55 am, shiva@Algo shiv.jays...@gmail.com wrote: id we see the pattern then we can easily find that the kth smallest element lie on the upper half of the k*k submatrix(on the upperleft corner ) we can do search on (k*k)/2 elements to find that On Mon, Oct 10, 2011 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Shubham: So if the matrix is 1 2 3 4 and you want the 2nd smallest, are you saying that it is 4? Dave On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote: im assuming it be a square matrix then kth smallest element will be in a first k*k sub matrix. jst look for smallest element in the diagonal of this matrix. it will give the kth smallest element . On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com wrote: Given a 2D matrix which is both row wise and column wise sorted. Propose an algorithm for finding the kth smallest element in it in least time complexity A General Max Heap can be used with k space and n+klogk complexity Any other solution or even a way by which we dont scan the whole matrix to find the solution ? I -- 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Re: Algo for Search in a 2D Matrix
Here is a solution based on the fact that the matrix is quiet similar to a
min heap. each cell is smaller than its down and right neighbor.
Note :- This solution modifies the original matrix.
Algo -
repeat k-1 times
set a[0][0] = INFINITY
minHeapify the Matrix (see implementation below). This will create
holes in the matrix that can be filled with INFINITY.
return a[0][0];
- Complexity O(k*(m+n)) for a m x n matrix.
- Here is a java implementation of the same.
public static int kthSmallest(int[][] a, int k)
{
final int INF = Integer.MAX_VALUE;
int rows = a.length;
int cols = a[0].length;
if (k rows*cols)
{
System.out.println(Matrix has less than + k + elements.);
return INF;
}
while(--k 0)
{
a[0][0] = INF; int i=0, j=0;
// MinHeapify the matrix again.
while(true)
{
int down = INF; int right = INF;
if(i rows-1) down = a[i+1][j];
if(j cols-1)right = a[i][j+1];
if((down == INF) (right == INF))
break;
if(down right)
{
int temp = a[i][j];
a[i][j] = down;
a[i+1][j] = temp;
i++;
}
else
{
int temp = a[i][j];
a[i][j] = right;
a[i][j+1] = temp;
j++;
}
}
}
return a[0][0];
}
Feedback welcome :-)
- Ravindra
On Wed, Oct 12, 2011 at 8:18 PM, sunny agrawal sunny816.i...@gmail.comwrote:
i dont think k*k submatrix approach works at all
what if k =n size of submatrix will be n*n, which is matrix itself
heap seems to be a good approach with a coloring scheme that helps in
avoiding duplicates in heap ??
On Wed, Oct 12, 2011 at 7:18 PM, vikas vikas.rastogi2...@gmail.comwrote:
@Shiva, not necessarily in upper half
take the transpose of example put by Dave and see by yourself
There are few observations for this question:
1. kth smallest will always lie in first k*k matrix
2. it wont be part of sqrt(k)*sqrt(k) matrix
Thus rest all need to be searched recursively to find the element
Any suggestions ?
On Oct 10, 10:55 am, shiva@Algo shiv.jays...@gmail.com wrote:
id we see the pattern then we can easily find that the kth smallest
element
lie on the upper half of the k*k submatrix(on the upperleft corner )
we can do search on (k*k)/2 elements to find that
On Mon, Oct 10, 2011 at 10:36 AM, Dave dave_and_da...@juno.com wrote:
@Shubham: So if the matrix is
1 2
3 4
and you want the 2nd smallest, are you saying that it is 4?
Dave
On Oct 9, 7:40 pm, shubham goyal shubhamgoyal.n...@gmail.com wrote:
im assuming it be a square matrix
then kth smallest element will be in a first k*k sub matrix.
jst look for smallest element in the diagonal of this matrix.
it will give the kth smallest element .
On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg ankurga...@gmail.com
wrote:
Given a 2D matrix which is both row wise and column wise sorted.
Propose an
algorithm for finding the kth smallest element in it in least time
complexity
A General Max Heap can be used with k space and n+klogk complexity
Any other solution or even a way by which we dont scan the whole
matrix to
find the solution ?
I
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re: How to Solve This
well , I tried to solve it from Maths
though half way through only :(
N = number required i.e. (10^k -1)/9
given n = 10x + 3
by eq
(10x + 3) * m = N= (10^k - 1)/9
implies
k = 2log 3 + log m + log(10x + 3)
i.e.
k 1 + log n
This gives the lowerbound on minimum number of 1 to be start with, but
seeing the logarithmic eq, this simply seems not to add much value.
can any one figure out for upper bound ?
On Oct 12, 5:18 pm, anshu mishra anshumishra6...@gmail.com wrote:
@amol
I was not sure that for every number that has 3 in its unit place has one
multiple which has all one. So I used that is if the remainder is coming
that already appeared stop there coz it will make stuck in a loop.
for ex. remainders are
1 3 19 23 37 1 3 19 that will repeat.
but it in this case u can remove the set. Code will look more simpler.
string all1Multiple(int x)
{
string s;
int r=1;
do
{
s += '1';
r = r % x;
r = r * 10 + 1;
} while(r != 1);
return s;
}
--
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: Find the later version
As others have said, you have not completely specified the problem.
If you always have exactly 4 base 10 numbers separated by dots, and
you are working in C or C++ then you can use sscanf to get the numbers
and compare them:
// Return:
// positive if version s1 is an earlier version than s2,
// negative if s2 is earlier than s1
// zero if they're the same version
#define VERSION_CMP_ERROR INT_MAX
int version_cmp(char *s1, char *s2)
{
int i, v1[4], v2[4];
if (sscanf(s1, %u.%u.%u.%u, v1+0, v1+1, v1+2, v1+3) != 4 ||
sscanf(s2, %u.%u.%u.%u, v2+0, v2+1, v2+2, v2+3) != 4)
return VERSION_CMP_ERROR;
for (i = 0; i 4; i++)
if (v1[i] != v2[i])
return v2[i] - v1[i];
return 0;
}
On Oct 11, 4:52 am, bagaria.ka...@gmail.com
bagaria.ka...@gmail.com wrote:
Given two strings describing the version of a particular software need to
find the later version.
For eg.
1st string = 1.2.4.5
2nd string=1.2.3.5
1st string is the later one.
Can be done using traversing the string and comparing each character one
after the another. Looking for a better solution with lesser complexity.
--
Thanks and Regards
*Karan Bagaria*
*MCA Final Year*
Training and Placement Representative
*NIT Durgapur*
--
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: How to Solve This
First note:
0 * 3 = 0
7 * 3 = 21
4 * 3 = 12
1 * 3 = 3
8 * 3 = 24
5 * 3 = 15
2 * 3 = 6
9 * 3 = 27
6 * 3 = 18
3 * 3 = 9
Important is that the final digits of each line count 0 to 9.
Now you can build an answer right to left.
Example: 123.
Check the table to get the rightmost 1.
7 * 123 = 861
Now you need to add ...50 to make the 10's digit a 1. So
50 * 123 = 6150 + 861 = 7011
And now add 100 to get the third 1...
700 * 123 = 86,100 + 7011 = 93,111
Following this pattern:
6000 * 123 = 738,000 + 93,111 = 831,111
6 * 123 = 7,380,000 + 831,111 = 8,211,111
30 * 123 = 36,900,000 + 8,211,111 = 45,111,111
Okay. That's enough. We stop when the carry digits finally turn out
to be all 1's.
In a program once we've arranged for a rightmost 1 we can shift it out
of the calculation by dividing everything by 10. At the same time we
can shift out the trailing zeros in the multiplicands.
So here's a quick implementation. Sorry in advance for mistakes, but
it seems to be working okay:
#include stdio.h
// If x is all 1's (including zero of them), return
// how many there are. Otherwise return ~0u.
unsigned all_ones(unsigned x)
{
unsigned n = 0;
while (x) {
if (x % 10 != 1)
return ~0u;
x /= 10;
++n;
}
return n;
}
// A table s.t. (x + 3 * mul[x % 10]) ends in 1.
unsigned mul[] = {7,0,3,6,9,2,5,8,1,4};
// Return n s.t. x divides sum_{i=0 to n-1} 10^i .
// x must be congruent to 3 mod 10.
unsigned ones(unsigned x)
{
unsigned n, carry = x;
for (n = 0; all_ones(carry) == ~0u; n++) {
carry = (carry + mul[carry % 10] * x) / 10;
// printf(%d\n, carry);
}
return n + all_ones(carry);
}
int main(void)
{
unsigned x;
if (scanf(%u, x) == 1 x % 10 == 3)
printf(%u divides %u 1's\n, x, ones(x));
return 0;
}
On Oct 10, 9:20 am, VIHARRI viharri@gmail.com wrote:
For every number that has 3 in its units place has one multiple which
has all one's i.e. 111 is
such multiple and 13 has a multiple 11. Write a program to find
such multiple for any
number that has 3 at its units place.
--
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: Memorization
This is true when memoization is being used to merely improve
asymptotic efficiency of a single computation. (As you say, it's a
nice technique for DP, when you can often just remember one or a few
previous rows of results.)
However this is not the only use. General memoization maintains
values persistently. In this case memoized fib(n) will cost O(n) for
the first call. Afterward any call for fib(i), i = n will run in
constant time. If there are many similar-valued calls to fib, this is
a big deal.
On Oct 11, 7:15 pm, Vandana Bachani vandana@gmail.com wrote:
Hi Arvind,
For the fibonacci series, we need to memoize only the the last 2 fibonacci
numbers.
We can even avoid recursion... So our regular fibonacci algorithm is the
simplest example of a dynamic programming algorithm with memoization.
To find nth fibonacci number:
int p = 0, q = 1, f;
for (int i = 1; i = n; i++)
{
f = p + q;
p = q;
q = f;
}
But as gene mentioned, in complex programs involving dynamic programming we
might need to access more than 1 or 2 previously obtained values. To reduce
the burden of recalculating old values, we preserve them in a
hash/table/array, as the case might be and access them directly from there.
One of the most important properties of dynamic programming is that the
solutions to sub-problems are reused, which can be achieved with
memoization.
-Vandana
On Tue, Oct 11, 2011 at 3:17 AM, arvind kumar arvindk...@gmail.com wrote:
ya ya,realy sorry..typo!its MEMOIZATION.
On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg ankurga...@gmail.com wrote:
Memoization ?
On Mon, Oct 10, 2011 at 6:34 PM, arvind kumar arvindk...@gmail.comwrote:
Can anyone tell me how to go about with the memorization technique to
retrieve values from already stored values,in case of eveluating
sequences(fibonacci series,etc).?
--
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.- Hide quoted text -
- Show quoted text -
--
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] Stone Game
In the problem Stone Game http://www.spoj.pl/problems/RESN04/ , I did the
following algorithm that was accepted by spoj:
#includestdio.h
int main(){
int n,t,i,j,cont;
scanf(%d,t);
while(t--){
scanf(%d,n);
cont=0;
for(i=1;i=n;i++)
{
scanf(%d,j);
if(j=i){
cont+=j/i;
}
}
if(cont%2==0)
printf(BOB\n);
else
printf(ALICE\n);
}
return 0;
}
A friend of mine made the following code, which was also accepted by spoj:
#include stdio.h
#include iostream
#include stack
#include queue
#include algorithm
#include iostream
using namespace std;
int main(){
int n;
cin n;
while(n--)
cout ALICE endl;
return 0;
}
I could not prove because Alice always wins. Does anyone know how to prove
this fact?
Wladimir Araujo Tavares
*Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
Homepage http://lia.ufc.br/%7Ewladimir/ |
Maratonahttps://sites.google.com/site/quixadamaratona/|
*
--
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] Stone Game
being accepted doesn't imply in being correct
maybe I'm wrong but given this Test Case I think BOB wins:
3
1 3 2
didn't he (bob!)?
On Wed, Oct 12, 2011 at 6:53 PM, Wladimir Tavares wladimir...@gmail.com wrote:
In the problem Stone Game , I did the following algorithm that was accepted
by spoj:
#includestdio.h
int main(){
int n,t,i,j,cont;
scanf(%d,t);
while(t--){
scanf(%d,n);
cont=0;
for(i=1;i=n;i++)
{
scanf(%d,j);
if(j=i){
cont+=j/i;
}
}
if(cont%2==0)
printf(BOB\n);
else
printf(ALICE\n);
}
return 0;
}
A friend of mine made the following code, which was also accepted by spoj:
#include stdio.h
#include iostream
#include stack
#include queue
#include algorithm
#include iostream
using namespace std;
int main(){
int n;
cin n;
while(n--)
cout ALICE endl;
return 0;
}
I could not prove because Alice always wins. Does anyone know how to prove
this fact?
Wladimir Araujo Tavares
Federal University of Ceará
Homepage | Maratona |
--
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.
--
Hatta
--
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] Stone Game
your solution seems to be the right one... testcases may be faulty
try submitting here http://www.codechef.com/problems/RESN04/ both the
codes
On Thu, Oct 13, 2011 at 5:44 AM, Hatta tmd...@gmail.com wrote:
being accepted doesn't imply in being correct
maybe I'm wrong but given this Test Case I think BOB wins:
3
1 3 2
didn't he (bob!)?
On Wed, Oct 12, 2011 at 6:53 PM, Wladimir Tavares wladimir...@gmail.com
wrote:
In the problem Stone Game , I did the following algorithm that was
accepted
by spoj:
#includestdio.h
int main(){
int n,t,i,j,cont;
scanf(%d,t);
while(t--){
scanf(%d,n);
cont=0;
for(i=1;i=n;i++)
{
scanf(%d,j);
if(j=i){
cont+=j/i;
}
}
if(cont%2==0)
printf(BOB\n);
else
printf(ALICE\n);
}
return 0;
}
A friend of mine made the following code, which was also accepted by
spoj:
#include stdio.h
#include iostream
#include stack
#include queue
#include algorithm
#include iostream
using namespace std;
int main(){
int n;
cin n;
while(n--)
cout ALICE endl;
return 0;
}
I could not prove because Alice always wins. Does anyone know how to
prove
this fact?
Wladimir Araujo Tavares
Federal University of Ceará
Homepage | Maratona |
--
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.
--
Hatta
--
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.
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re: Find the later version
scan the numbers as string if both strings dont have equal numbers of dots then add trailing 0's with dots to the string with less number of dots now divide both the string into 2 equal halves compare the left half .if unequal then divide recursively and again compare left of the divided string.if equal the compare the right half and divide and compare it recursivelythis will reduce the complexity to logn. -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99 On Thu, Oct 13, 2011 at 2:21 AM, sravanreddy001 sravanreddy...@gmail.comwrote: it is expected that the version is given as string, in that case, atoi() has be used to convert string to int -- 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.
