Re: [algogeeks] Min Edges to be added to DAG to make it Strongly connected?
This is the linkhttp://apps.topcoder.com/forums/?module=ThreadthreadID=764182start=0mc=4#1614862to the answer given by misof.. and it worked!! On Sunday, 7 October 2012 00:41:48 UTC+5:30, kailash wrote: @atul: No,it's not the correct answer. Let's take an example of star like DAG:- A --B--C | V D This DAG contains only one cut vertex(B) but we need to add two edges to make it strongly connected. On Sat, Oct 6, 2012 at 7:37 PM, atul anand atul.8...@gmail.comjavascript: wrote: find no. of cut vertex in the DAGthat will be the ans. On 6 Oct 2012 19:33, KK kunalka...@gmail.com javascript: wrote: Given a DAG(Directed Acyclic Graph). How to find out the minimum number of edges that needs to be added so that the given graph becomes Strongly Connected? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ. To post to this group, send email to algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 algo...@googlegroups.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- ‘Kailash Bagaria’ B-tech 4th year Computer Science Engineering Indian Institute of Technology, Roorkee Roorkee, India (247667) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/O5kS0uhrsr4J. 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: Help me find my Recursive algo complexity
Hi Vicky.. Its O(n^K) as u are iterating over all the elements of array for
each of the k element subset!!
On Monday, 8 October 2012 23:53:15 UTC+5:30, ((** VICKY **)) wrote:
Hi, I wrote code for generating all possible sets of length k in a array
of length n. I did using recursion, but i'm not able to calc the
complexity systematically [image: :-/] Kindly help me.
11:39 PM
i.p {1,2,3,4,5} k =2
o.p
Vector has : 1 2 3 4 5
1 1 2
2 1 3
3 1 4
4 1 5
5 2 3
6 2 4
7 2 5
8 3 4
9 3 5
10 4 5
Approach:
Assume I have a selected and remaining set, now initially all will be
remaining set and selected set= {}.
In first step pick 1 and grow recursion with it as root and pick 2,3,4,5
(n-1) as possible picks. Now print those sets since k=2(base case) is
reached.
Now grow recursion with 2 as root and 3,4,5 (n-2) as possible
picks(childs) print them. Repeat till i reach 5 where i have no children
possible as rem set is empty.
void print_all(vectorintsel,vectorintrem, int n){
if(sel.size() == n)
{
static int cnt = 1;
coutcnt++ ;
for(int i = 0; i n; i++)
coutsel[i] ;
coutendl;
return;
sel.erase(sel.begin(),sel.end());
}
for(int i = 0; i rem.size(); i++)
{
vectorintnow,curr_sel;
//for(int j = 0; j i; j++)
// now.push_back(rem[j]);
for(int j = i+1; jrem.size(); j++)
now.push_back(rem[j]);
// coutnow has : ;
//for(int i = 0; i now.size(); i++)
// coutnow[i] ;
//coutendl;
for(int i = 0; i sel.size(); i++)
curr_sel.push_back(sel[i]);
curr_sel.push_back(rem[i]);
print_all(curr_sel,now,n);
}}
--
Cheers,
Vicky
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/GTlxcHY8JDYJ.
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] Min Edges to be added to DAG to make it Strongly connected?
Given a DAG(Directed Acyclic Graph). How to find out the minimum number of edges that needs to be added so that the given graph becomes Strongly Connected? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/T6idnKJ0It0J. 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] Min Edges to be added to DAG to make it Strongly connected?
Given a DAG(Directed Acyclic Graph). How to find out the minimum number of edges that needs to be added so that the given graph becomes Strongly Connected? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/PbR3j9S5OXUJ. 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] 4Sum
@Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.comwrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/9jCCN5iHDB8J. 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: Permutations of a string
Thanks Gene :D
On Tuesday, 8 May 2012 07:24:01 UTC+5:30, Gene wrote:
You just need to make sure that the same character is never swapped to
the same position twice. Here is one way to do it.
#include stdio.h
#include string.h
void swap(char *s, int i, int j)
{
char t = s[i];
s[i] = s[j];
s[j] = t;
}
void permute(char *s, int n)
{
if (s[n]) {
int i;
unsigned char done[256] = { 0 };
for (i = n; s[i]; i++) {
if (!done[s[i]]) {
swap(s, n, i);
permute(s, n + 1);
swap(s, n, i);
done[s[i]] = 1;
}
}
}
else printf(%s\n, s);
}
int main(int argc, char *argv[])
{
char buf[10 * 1024];
if (argc 1) {
strcpy(buf, argv[1]);
permute(buf, 0);
}
return 0;
}
On May 7, 6:23 am, Sairam ravu...@gmail.com wrote:
Thanks for ur clean Code!! But you haven't considered the case of
repeating
characters in a string
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PjyaYiTqYxQJ.
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: problem
This problem is of ACM-ICPC kanpur online round 2012. you can find the solution herehttp://www.codechef.com/ACMKAN11/problems/ARTHMNCY . On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0tnSKnC7YRYJ. 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] Matrix Minimum Path Sum
The problem u are referencing is different one.. here u can move in all 4 directions! On Wednesday, 6 June 2012 18:43:15 UTC+5:30, Dheeraj wrote: http://www.geeksforgeeks.org/archives/14943 On Mon, Jun 4, 2012 at 7:57 PM, Decipher ankurseth...@gmail.com wrote: @Victor - Someone had asked this question from me !! He told me its from Project Euler Q-83. @Hassan - I think you are right. This question can be solved by Dijikstra's algo, if we consider the matrix elements as weights. On Monday, 4 June 2012 16:28:31 UTC+5:30, Hassan Monfared wrote: moving must be done in A* style On Mon, Jun 4, 2012 at 1:17 PM, atul anand atul.87fri...@gmail.comwrote: i dont think so dijistra will worh here..bcozz we cannot move diagonally ...but according to matrix this path can be considered. On Mon, Jun 4, 2012 at 1:39 PM, Hassan Monfared hmonfa...@gmail.comwrote: for non-negative values Dijkstra will solve the problem in ( O(N^2) ) and Floyd-Warshal is the solution for negative cells. ( O(N^3) ) On Mon, Jun 4, 2012 at 11:20 AM, atul anand atul.87fri...@gmail.comwrote: this recurrence wont work..ignore On Mon, Jun 4, 2012 at 8:55 AM, atul anand atul.87fri...@gmail.comwrote: find cumulative sum row[0] find cumulative sum of col[0] after this following recurrence will solve the problem. start from mat[1][1] mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] ) On Sun, Jun 3, 2012 at 7:30 PM, Decipher ankurseth...@gmail.comwrote: Q) In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297. *131* 673 *234* *103* *18* *201* *96* *342* 965 *150* 630 803 746 *422* *111* 537 699 497 *121* 956 805 732 524 *37* *331* Write an algorithm to find the same. Also, write an algorithm if the same matrix contains negative numbers (maybe negative cycle) and compare the space and time complexity of both. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/3JeyGNqWbs8Jhttps://groups.google.com/d/msg/algogeeks/-/3JeyGNqWbs8J . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@* *googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/l9UCuzmoZRMJ. 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. On Wednesday, 6 June 2012 18:43:15 UTC+5:30, Dheeraj wrote: http://www.geeksforgeeks.org/archives/14943 On Mon, Jun 4, 2012 at 7:57 PM, Decipher ankurseth...@gmail.com wrote: @Victor - Someone had asked this question from me !! He told me its from Project Euler Q-83. @Hassan - I think you are right. This question can be solved by Dijikstra's algo, if we consider the matrix elements as weights. On Monday, 4 June 2012 16:28:31 UTC+5:30, Hassan Monfared wrote: moving must
[algogeeks] Re: SPOJ TLE
Try wid BFS.. thats the only alternative i can think off!! I got acc
wid that!!
On Dec 6, 12:29 pm, varma C.S.P verma@gmail.com wrote:
I am getting a lot of tle's for this problem.
https://www.spoj.pl/problems/BUGLIFE/
Here is my code
#includeiostream
#includecstdio
#includecstring
using namespace std;
int g[2001][2001];
int color[2001];
short stack[5001];
int bugs, rel;
int inline complement(int n);
bool inline dfs();
int v1, v2;
int main()
{
int cases;
scanf(%d, cases);
for(int i=1; i=cases; i++)
{
scanf(%d %d, bugs, rel);
memset(g, 0x00, sizeof g);
int relq = rel;
while(relq--)
{
scanf(%d %d, v1, v2);
g[v1][++g[v1][0]]=v2;
g[v2][++g[v2][0]]=v1;
}
printf(Scenario #%d:\n, i);
if(dfs())
{
printf(No suspicious bugs found!\n);
}
else
{
printf(Suspicious bugs found!\n);
}
}
return 0;}
int inline complement(int n)
{
if(n==1)
return 2;
if(n==2)
return 1;
}
bool inline dfs() //iterative DFS
{
int node, no, in;
memset(color, 0x00, (bugs+1)*sizeof(int));
stack[0]=0;
for(int it = 1; it=bugs; it++)
{
if(color[(it)]==0 g[(it)][0]!=0)
{
stack[++stack[0]]=(it);
color[(it)] = 1;
while(stack[0] (rel0)) //if stack is not empty
{
in = stack[stack[0]--];
no = g[in][0];
for(int j=1; j=no; j++)
{
node = g[in][j];
if(color[node]!=0)
{
if(color[node] == color[in])
{
return false;
}
}
else
{
color[node] = complement(color[in]);
stack[++stack[0]]=node;
rel--;
}
}
}
}
}
return true;
}
Please help me.
Ashok
--
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: Can Any1 provide a proper implementation of a Hashtable(Seperation Chaining) in C,C++
#includeiostream
#includevector
#includelist
#define TR(a,it)for(typeof((a).begin()) it = (a).begin(); it !=
(a).end(); ++it)
using namespace std;
void Insert(int key, int m, vector listint v);
listint::iterator Search(int key, int m, vector listint v);
void Delete(int key, int m, vector listint v);
int main()
{
int m,choice,key;
vector listint v;
cout Enter the no of slots endl;
cin m;
v.resize(m);
while(1)
{
cout 1. Insert\n2. Search \n3. Delete \n4. Exit\n;
cin choice;
switch(choice)
{
case 1:
cout Enter the key\n;
cin key;
Insert(key, m, v);
break;
case 2:
cout Enter the key\n;
cin key;
Search(key, m, v);
break;
case 3:
cout Enter the key\n;
cin key;
Delete(key, m, v);
break;
case 4:
exit(0);
}
}
}
int h(int key, int m)
{
return key % m;
}
void Insert(int key, int m, vector listint v)
{
int slot = h(key,m);
if(Search(key,m,v) == NULL)
{
cout Inserting...\n;
v[slot].push_back(key);
cout Insertion Completed!!\n;
}
}
listint::iterator Search(int key, int m, vector listint v)
{
int slot = h(key, m);
cout Searching...;
TR(v[slot], it)
{
if(*it == key)
{
cout Key found!!\n;
return it;
}
}
cout key not found!!\n;
return NULL; //we can use like this also:
(listint iterator::i)NULL
}
void Delete(int key, int m, vector listint v)
{
int slot = h(key, m);
listint::iterator i;
i = Search(key, m, v);
if(i != NULL)
{
v[slot].erase(i);
cout Deletion Completed!!\n;
}
}
This is not a tested code... it may contain bugs!!
--
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] SPOJ PIE
http://www.spoj.pl/problems/PIE/
I solved this using Binary Search its similar to shake shake shaky of
spoj... but still get WA :(
Plzz help...
#includeiostream
#includealgorithm
using namespace std;
bool solve(int *pie, int n, int mid,int f)
{
int sum = 0;
for (int i=0; in; i++)
sum += pie[i] / mid;
if (sum = f)
return true;
else
return false;
}
int binary_search(int *pie, int n, int f)
{
int low = 0, high = pie[n-1], mid;
while (low high)
{
mid = low + (high - low + 1)/2;
if (solve(pie, n, mid, f))
low = mid;
else
high = mid - 1;
}
return low;
}
int main()
{
//freopen(input.txt, r, stdin);
//freopen(output.txt, w, stdout);
const double pi = 3.14159265358979323846264338327950;
int T;
cin T;
while (T--)
{
int n, f, pie[10001];
cin n f;
for (int i=0; in; i++)
{
cin pie[i];
pie[i] *= pie[i];
}
f++;
sort(pie, pie + n);
int largest = binary_search(pie, n, f);
//cout largest is largest endl;
double ans = largest * pi;
printf(%.4lf\n, ans);
}
return 0;
}
--
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: MS test cases type Questions
U must mention all the boundary cases, very large input cases, -ve nos and must throw appropriate exception while coding during interviews... Questions are not too hard in MS... just they dont want buggy code... even if u allocate memory.. u should take an if condition i.e. if (p ! = NULL)...and avoid such other silly mistakes... -- 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: MICROSOFT in VJTI mumbai
@Bharatkumar bagana : that is a standard Qs which uses line sweep algo and has O(n lgn) soln other than the trivial O(n^2) soln... google that Qs... @tej bala: out of 10.. 5-6 were output type obj Q... then 1 was what's full form of GCC... its gnu compiler collection.. i made mistake in this Q.. @dilip : Thanks :)) They din asked me any dbms, networks, or OS Q as i applied as an intern but they do ask Qs from these subjects as well... -- 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: Implementing a grep
grep is actually implemented using a suffix tree -- 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: MICROSOFT in VJTI mumbai
MS visited out col with 2 profiles... written test: 3 different papers: 1 one all objectives 2nd 2 subjective problems... 1 ws to find the closest pair of points... and other was to find the bugs and provide the test cases for the already provided string copying code... then it was followed by 4 coding PI. I dont remember all the Qs but few of them are... LCA generating mnemonics of a phone keypad a DFS or BFS ques removing all the repeated character of string in O(1) space given all would be [A-Z a-z] given an ip address store it const space... i stored it in integer and he was satisfied... Inorder Successor the above Qs were for intern... although they followed the same process for final year people... Finally I made it through :)) -- 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] Euler Phi Function
This is the code for the Euler phi function:
int phi (int n) {
int result = n;
for (int i=2; i*i=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i; // M NOT GETTING THIS...
}
if (n 1)
result -= result / n;
return result;
}
why is it subtracting result/i from result if i is a factor of n??
plzzz explain...
--
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: C code scanf problem
Using getchar() after the first scanf ll be much better...!! -- 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: logic???????????
Check this out
//But this and fails for input such as: 101 ie all nos
must be unique..
int search_element_in_rotated_array(int *a, int low, int high, int
key)
{
while(low = high)
{
int mid = low + (high - low)/2;
if(a[mid] == key)
return mid;
if(a[mid] = a[low]) // the top part is sorted
{
if(a[low] = key key a[mid])
high = mid - 1;
else
low = mid + 1;
}
else
{
if(key = a[high] key a[mid])
low = mid + 1;
else
high = mid - 1;
}
}
return -1;
}
On Aug 12, 8:38 pm, sagar pareek sagarpar...@gmail.com wrote:
oh common shashank...its not that easy u told.
just do codingthen u will find the error in ur logic
On Fri, Aug 12, 2011 at 6:25 PM, WgpShashank
shashank7andr...@gmail.comwrote:
Hi Guys Here is the algorithm for doing same in O(logn)
Hint : Find the pivot point, divide the array in two sub-arrays and call
binary search. Thats It :)
Algorithm
1. A Pivot Point is point around which array is rotated so 1st we need to
find out its location/index. lets say it pivot.
a. to find pivot point we use same idea of binary search check if
arr[mid]a[mid+1] if true then return pivot=mid.
b else if arr[low]a[mid] search for pivot in left
c. else search for pivot in right half of array.
Time Complexity O(logn)
2. Once we have found index of pivot point check if desired element is
same value at pivot index or not e.g.
a. ( if a[pivot]==value we are searching for ) the simply return true
or 1 .
Now call binary search for one of the two sub-arrays.
(ab) *If *element is greater than 0th element then search in
left array
(ac) *Else* Search in right array *
(ad) If *element is found in selected sub-array then return
index
*Else *return -1.
Again Time Complexity O(logn)
Hope You Can Make it in Running Code , Do Noify me if You Need More
Explanation or if missed Something??
*Regards
Shashank Mani Computer Science Is Awesome So Why I Write Code
Computer Science
Birla institute of Technology Mesra
*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/QPCzNLNf_sEJ.
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.
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT 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: Plz tell wat questions are asked by MICROSOFT IDC and IT both...Plz Reply fast.....anyone...!!
Go through the last 50-100 posts... a lot of Qs have already been posted!! -- 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: amazon test question!!!
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.
[algogeeks] Re: Directi question-centre of the tree
Codechef Ques(Initiative of Directi) use DFS, BFS or Floyd Warshall... :) -- 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: Microsoft :)
@Harshal: Thanx -- 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: Microsoft :)
Hey Congrats!! :) I got intern dere :) -- 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] Facebook Intern F2F Interview
bool foo(int x)
// Implement this function where 0 = x = 100
It should return true x% of times n false otherwise
first i told him to have a static int s then increment it each time
the func is called...
and if s % (100 - x ) == 0 then true else false.
then he told me to have some different approach..
I told him like this:
bool foo(int x)
{
// checking if x is btw 0 100
if(x == 0)
return false;
if(x == 100)
return true;
srand(time(0));
int rno = rand();
if(rno % (100 - x) == 0)
return True;
else
return False;
}
He was like okk but i think he was not completely satisfied
Any other Approach...
--
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: Facebook Intern F2F Interview
@Nikhil: ya true but i dont know wht else was he expecting. @sunny and Muthu: like suppose u pass 20 then func should return true with 20% probabily and false otherwise... -- 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: Facebook Intern F2F Interview
No i was not able to come up with a soln dere.. my bad :( This was my 1st interview hope the upcoming interviews would be nice!! -- 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
@shady: if ur not interested dont post ur comment, but let others do it.. @viswamath: WA -- 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
@piyush: even if r = di and c = dj then whats the prob?? -- 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] SPOJ
www.spoj.pl/problems/SHOP
Its a pretty easy Q... But m not able to figure out any silly mistake
in my prog.. plzz help
#includeiostream
#includevector
#includemap
#includequeue
using namespace std;
char a[26][26];
int si, sj, di, dj, rows, cols;
void BFS(vector vectorint v, int si, int sj, int rows, int
cols);
int safe(vector vectorint v, int r, int c, int current, int
rows, int cols);
int main()
{
freopen(input.txt, r, stdin);
freopen(output.txt, w, stdout);
int si, sj;
while(1)
{
cin cols rows;
if(rows == 0 cols == 0)
break;
vectorint row(26, INT_MAX);
vector vectorint final(26, row);
for(int i=0; irows; i++)
for(int j=0; jcols; j++)
{
cin a[i][j];
if(a[i][j] == 'S')
{
si = i; sj = j;
}
else if(a[i][j] == 'D')
{
di = i; dj = j;
a[i][j] = '0';
}
}
BFS(final, si, sj, rows, cols);
cout final[di][dj] endl;
/*
for(int i=0; irows; i++)
{
for(int j=0; jcols; j++)
cout final[i][j] ;
cout endl;
}
cout endl;
*/
}
return 0;
}
void BFS(vector vectorint v, int si, int sj, int rows, int cols)
{
pairint, int p;
queue pairint, int q;
q.push(make_pair(si, sj));
v[si][sj] = 0;
while(!q.empty())
{
p = q.front(); q.pop();
int current = v[p.first][p.second];
if(safe(v, p.first+1, p.second, current, rows, cols))
q.push(make_pair(p.first+1, p.second));
if(safe(v, p.first-1, p.second, current, rows, cols))
q.push(make_pair(p.first-1, p.second));
if(safe(v, p.first, p.second+1, current, rows, cols))
q.push(make_pair(p.first, p.second+1));
if(safe(v, p.first, p.second-1, current, rows, cols))
q.push(make_pair(p.first, p.second-1));
}
}
int safe(vector vectorint v, int r, int c, int current, int
rows, int cols)
{
if(r = 0 r rows c = 0 c cols a[r][c] != 'X')
{
if(v[r][c] current + a[r][c] - '0')
{
v[r][c] = current + a[r][c] - '0';
return 1;
}
}
return 0;
}
--
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: DP or DFS
Can u elaborate something on implementation.?? -- 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: Help!!
Hey anyone Pl help... its clearly written code and algo u know vry
well so it wont take much time :)
On Jul 5, 8:43 pm, KK kunalkapadi...@gmail.com wrote:
This is the solution to the MST problem
m getting WA again n again... cant figure out where's the mistake...
so plzzz help!!!https://www.spoj.pl/problems/BLINNET/
#includeiostream
#includestring
#includevector
#includelist
#includequeue
#define MAXINT (int)9e9
#define TR(a,it) for(typeof((a).begin()) it=(a).begin(); it!
=(a).end(); ++it)
using namespace std;
struct node
{
long int data;
string name;
long int cost;
long int distance;
long int parent;
friend bool operator(const node a, const node b);
};
long int prims(vector listnode adjlist, int n);
int main()
{
freopen(input.txt, r, stdin);
freopen(output.txt, w, stdout);
long int n, t, no_neigh;
cin t;
while(t--)
{
vector listnode adjlist;
node temp;
getchar();
cin n;
adjlist.resize(n + 1);
for(int i=1; i=n; i++)
{
cin temp.name;
//temp.data = i;
//adjlist[i].push_back(temp);
cin no_neigh;
for(int j=1; j=no_neigh; j++)
{
cin temp.data temp.cost;
adjlist[i].push_back(temp);
}
}
/*for(int i=1; i=n; i++)
{
cout i : endl;
TR(adjlist[i], it)
cout it-data it-cost endl;
}*/
cout prims(adjlist, n) endl;
}
}
bool operator(const node a, const node b)
{
return a.distance b.distance;
}
long int prims(vector listnode adjlist, int n)
{
priority_queuenode, vectornode, greaternode pq;
node heap[n+1];
for(long int i=1; i=n; i++)
{
heap[i].data = i;
heap[i].distance = MAXINT;
heap[i].parent = -1;
}
long int start = 1;
heap[start].distance = 0;
pq.push(heap[start]);
while(!pq.empty())
{
node top = pq.top(); pq.pop();
//cout popped : top.data endl;
if(top.distance = heap[top.data].distance)
{
//cout Traversed endl;
TR(adjlist[top.data], it)
{
if(heap[it-data].distance it-cost)
{
heap[it-data].distance = it-cost;
heap[it-data].parent = top.data;
//cout Pushed it-data endl;
pq.push(heap[it-data]);
}
}
}
}
long int sum = 0;
for(int i=1; i=n; i++)
sum += heap[i].distance;
return sum;
}
--
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: Some adobe interview questions.
for Q5 change the expr into postfix and then build expression tree... but is expression tree same as parse tree?? correct me if i m wrong!! -- 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] DP or DFS
https://www.spoj.pl/problems/SHOP/ Anybody plzz post a solution to the above problem... i tried with dp but it failed... How to implement with DFS or if possible with DP??? -- 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] Help!!
This is the solution to the MST problem
m getting WA again n again... cant figure out where's the mistake...
so plzzz help!!!
https://www.spoj.pl/problems/BLINNET/
#includeiostream
#includestring
#includevector
#includelist
#includequeue
#define MAXINT (int)9e9
#define TR(a,it)for(typeof((a).begin()) it=(a).begin(); it!
=(a).end(); ++it)
using namespace std;
struct node
{
long int data;
string name;
long int cost;
long int distance;
long int parent;
friend bool operator(const node a, const node b);
};
long int prims(vector listnode adjlist, int n);
int main()
{
freopen(input.txt, r, stdin);
freopen(output.txt, w, stdout);
long int n, t, no_neigh;
cin t;
while(t--)
{
vector listnode adjlist;
node temp;
getchar();
cin n;
adjlist.resize(n + 1);
for(int i=1; i=n; i++)
{
cin temp.name;
//temp.data = i;
//adjlist[i].push_back(temp);
cin no_neigh;
for(int j=1; j=no_neigh; j++)
{
cin temp.data temp.cost;
adjlist[i].push_back(temp);
}
}
/*for(int i=1; i=n; i++)
{
cout i : endl;
TR(adjlist[i], it)
cout it-data it-cost endl;
}*/
cout prims(adjlist, n) endl;
}
}
bool operator(const node a, const node b)
{
return a.distance b.distance;
}
long int prims(vector listnode adjlist, int n)
{
priority_queuenode, vectornode, greaternode pq;
node heap[n+1];
for(long int i=1; i=n; i++)
{
heap[i].data = i;
heap[i].distance = MAXINT;
heap[i].parent = -1;
}
long int start = 1;
heap[start].distance = 0;
pq.push(heap[start]);
while(!pq.empty())
{
node top = pq.top(); pq.pop();
//cout popped : top.data endl;
if(top.distance = heap[top.data].distance)
{
//cout Traversed endl;
TR(adjlist[top.data], it)
{
if(heap[it-data].distance it-cost)
{
heap[it-data].distance = it-cost;
heap[it-data].parent = top.data;
//cout Pushed it-data endl;
pq.push(heap[it-data]);
}
}
}
}
long int sum = 0;
for(int i=1; i=n; i++)
sum += heap[i].distance;
return sum;
}
--
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] GATE 2011 C Ques
10. What does the following fragment of C-program print? char c[] = GATE2011; char *p =c; printf(%s, p + p[3] - p[1]); (A) GATE2011 (B) E2011 (C) 2011 (D) 011 Answer: - (C) why is p[3] - p[1] returning 4 -- 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: GATE 2011 C Ques
got it dont bother!!! anyway thanx abhijith!!! -- 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] Recurrence Relation
3. Consider the following recurrence: T(n) = 2T(n ^ (1/2)) + 1 Which one of the following is true? (A) T(n) = (loglogn) (B) T(n) = (logn) (C) T(n) = (sqrt(n)) (D) T(n) = (n) Can we solve this using master theorem??? any other way??? -- 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: Recurrence Relation
Answer (B) Let n = 2^m, T(n) = T(2^m) Let T(2^m) = S(m) From the above two, T(n) = S(m) S(m) = 2S(m/2) + C1 Above expression is a binary tree traversal recursion whose time complexity is (m). You can also prove using Master theorem. S(m) = (m) = (logn) /* Since n = 2^m */ Now, let us go back to the original recursive function T(n) T(n) = S(m) = (Logn) I din understand this its GATE 2006 Q... -- 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: STL MAP HELP
but in a set elements are not in any order...and also set cannot be indexed... if u want to sort in the basis of key use vector with pair... Correct me if m wrong -- 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: Tic Tac Toe
@sunny: This test: if(! ( (countx == counto + 1) || (countx == counto) ) ) cout no endl; prints no if countx counto and this one if(o x) cout no endl; else cout yes endl; prints no if both have won or else yes correct me if m wrong... -- 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: Tic Tac Toe
@sunny: why the answer for the case u mentioned is no.. those are possible set of moves according to me and hence my program outputs yes -- 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] Fiddling with Bits
To remove all digits left of the rightmost digit one in the binary
representation of some integer what we need to do is this:
ans = no -no
and this is what is exactly asked in this problem of SPOJ:
www.spoj.pl/problems/MZVRK/
#includeiostream
using namespace std;
int main()
{
unsigned long long int a, b, sum;
while(scanf(%lld%lld, a, b) != EOF)
{
sum = 0;
while(a != (b+1))
{
sum += (a -a);
a++;
}
printf(%lld\n, sum);
}
return 0;
}
Its giving TLE on some 10th case...
--
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: Tic Tac Toe
oops !! :) i'll look into that.. thx -- 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] Minimum Rotations
http://www.spoj.pl/problems/MINMOVE/ This code is showing TLE after some 20th test case what else can be optimized??? try: import psyco psyco.full() except ImportError: pass string = input() minlen = string length = len(string) string += string[:] #print(string) index = 0 for i in range(1, length): if string[i : i+length] minlen: minlen = string[i : i+length] index = i print(index) -- 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] MST (BLINNET) problem on SPOJ
www.spoj.pl/problems/BLINNET/
Here is the code for the same... Its not getting AC in SPOJ
m not able to figure out wheres the hole in this... plzz help
#includeiostream
#includestring
#includevector
#includelist
#includequeue
#define MAXINT (int)9e9
#define TR(a,it)for(typeof((a).begin()) it=(a).begin(); it!
=(a).end(); ++it)
using namespace std;
struct node
{
long int data;
string name;
long int cost;
long int distance;
long int parent;
friend bool operator(const node a, const node b);
};
long int prims(vector listnode adjlist, int n);
int main()
{
freopen(input.txt, r, stdin);
freopen(output.txt, w, stdout);
long int n, t, no_neigh;
cin t;
while(t--)
{
vector listnode adjlist;
node temp;
getchar();
cin n;
adjlist.resize(n + 1);
for(long int i=1; i=n; i++)
{
cin temp.name;
//temp.data = i;
//adjlist[i].push_back(temp);
cin no_neigh;
for(long int j=1; j=no_neigh; j++)
{
cin temp.data temp.cost;
adjlist[i].push_back(temp);
}
}
/*for(int i=1; i=n; i++)
{
cout i : endl;
TR(adjlist[i], it)
cout it-data it-cost endl;
}*/
cout prims(adjlist, n) endl;
}
}
bool operator(const node a, const node b)
{
return a.distance b.distance;
}
long int prims(vector listnode adjlist, int n)
{
priority_queuenode, vectornode, greaternode pq;
node heap[n+1];
for(long int i=1; i=n; i++)
{
heap[i].data = i;
heap[i].distance = MAXINT;
heap[i].parent = -1;
}
long int start = 1;
heap[start].distance = 0;
pq.push(heap[start]);
while(!pq.empty())
{
node top = pq.top(); pq.pop();
//cout popped : top.data endl;
if(top.distance = heap[top.data].distance)
{
//cout Traversed endl;
TR(adjlist[top.data], it)
{
if(heap[it-data].distance it-cost)
{
heap[it-data].distance = it-cost;
heap[it-data].parent = top.data;
pq.push(heap[it-data]);
}
}
}
}
long int sum = 0;
for(int i=1; i=n; i++)
sum += heap[i].distance;
return sum;
}
/*
Input:
2
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
3
ixowo
2
2 1
3 3
iyekowo
2
1 1
3 7
zetowo
2
1 3
2 7
Output:
3
4
*/
--
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: Finding total number of inversions in an array in O(nlogn) complexity .
This code is not getting AC on spoj.. m not able to point out the
error plzzz help.
Here is the link to this problem at spoj : http://www.spoj.pl/problems/INVCNT/
#includeiostream
#includevector
#includestring
#includealgorithm
using namespace std;
void MergeSort(vectorint v, int p, int r);
void Merge(vectorint v, int p, int q, int r);
void PrintArray(vectorint v);
int count;
int main()
{
extern int count;
int n, i, t;
vectorint v;
//freopen(input.txt,r,stdin);
//freopen(output.txt,w,stdout);
cin t;
while(t--)
{
getchar();
count = 0;
scanf(%d,n);
v.resize(n);
for(i=0; in; i++)
scanf(%d,v[i]);
//cout The Input array is: endl;
//PrintArray(v);
MergeSort(v,0,n-1);
//cout The Sorted array is: endl;
//PrintArray(v);
cout count endl;
}
return 0;
}
void MergeSort(vectorint v, int p, int r)
{
if(p r)
{
int q = (p+r)/2;
MergeSort(v,p,q);
MergeSort(v,q+1,r);
Merge(v,p,q,r);
}
}
void Merge(vectorint v, int p, int q, int r)
{
extern int count;
int i, j, k;
vectorint v1, v2;
v1.resize(q-p+1);
v2.resize(r-q);
k=0;
for(i=p; i=q; i++)
v1[k++] = v[i];
k=0;
for(i=q+1; i=r; i++)
v2[k++] = v[i];
v1.push_back(INT_MAX);
v2.push_back(INT_MAX);
i=0; j=0;
for(k=p; k=r ;k++)
{
if(v1[i] v2[j])
{
v[k] = v1[i++];
count += j; // when taking element from 1st array
Incrementing count by no of elements already taken from 2nd array
}
else
v[k] = v2[j++];
}
}
void PrintArray(vectorint v)
{
int i,n = v.size();
for(i=0; in; i++)
printf(%d ,v[i]);
printf(\n);
}
--
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: HASHIT
Thanks dude!! -- 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: Finding total number of inversions in an array in O(nlogn) complexity .
Thanks Harshal!! Actually changing juzz count from int to long long suffices -- 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 NKTM
This q increased my score by directly 3 points... and thats a huge one.. :D @ kartik - Do it by priorty queue for better efficiency.. -- 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: Swapping two variables without using a temporary variable
@kunal
Actually its not same value its the same variable and it arises only
if u code the given way(and some people do it this way)
void swap(int a, int b)
{
a ^= b ^= a ^= b;
}
now we have
int a = 10;
swap(a, a)
This will set a's value to 0...and this happens while sorting arrays
when u pass the same index values...
Conclusion: Either code as given in above Q or use the temporary
var...
--
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: Swapping two variables without using a temporary variable
It wont give correct answer when u pass same values of a and b and such conditions arises in sorting -- *** Kunal Kapadia Computer Science and Engineering B.Tech 2nd yr NIT Trichy *** -- 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: FOR ALL INDIANS PLZ READ IT
It works!! Shame on u Umer Farooq u cant even give a call a no for ur nation whereas other are on hunger strike... even if this is algo group so whats the problem???... m sorry to say this... -- 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] HASHIT
This is the link to the SPOJ problem HASHIT :
http://www.spoj.pl/problems/HASHIT/
i donno whts the mistake... i keep getting wrong answer even though
the Q is Straightforward :(
#includeiostream
#includestring
using namespace std;
int hash(string str)
{
int sum = 0;
int len = str.size();
for(int i=0; ilen; i++)
sum = (sum + (i+1)*str[i]) % 101;
sum = (sum * 19) % 101;
return sum;
}
void add(string *array, string str, int count)
{
//cout string received: str endl;
int key = hash(str), pos;
for(int j=0; j=19; j++)
{
pos = (key + j*j + 23*j) % 101;
if(array[pos] == )
{
//cout Added endl;
array[pos] = str;
count++;
return;
}
else if(array[pos] == str)
return;
}
}
void d(string *array, string str, int count)
{
//cout string received: str endl;
int key = hash(str), pos;
for(int j=0; j=19; j++)
{
pos = (key + j*j + 23*j) % 101;
if(array[pos] == str)
{
//cout Deleted endl;
array[pos] = ;
count--;
return;
}
}
}
int main()
{
freopen(input.txt, r, stdin);
freopen(output.txt, w, stdout);
int t;
cin t;
while(t--)
{
int n, count = 0;
string array[101], temp;
for(int i=0; i101; i++)
array[i] = ;
cin n;
while(n--)
{
cin temp;
string opr = temp.substr(0, 3);
if(opr == ADD)
add(array, temp.substr(4, temp.size() - 4), count);
else
d(array, temp.substr(4, temp.size() - 4), count);
}
cout count endl;
for(int i=0; i101; i++)
{
if(array[i] != )
cout i : array[i] endl;
}
}
//system(pause);
return 0;
}
--
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 THRBL
Search Topcoder Tutorial Range Minimum Query @ Google... By few intuitive changes u can implement Range Maximum Query as well... -- 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] Python
I have juz started python and finished A Byte of Python Now to which book should i switch too??? Also recommend Python books to master 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: Need help on fenwick trees
Search Topcoder Tutorial on Google.. On Apr 17, 9:06 pm, naga vinod kumar vinodkumark...@gmail.com wrote: Hi Guys , Can any one give link for tutorial or videos about segment trees. I am unable to understand the basic idea behind it . Regards, vinod -- 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: Link for sartaj sahni video lectures
Hey it seems to be a fake link... It directs to some site which shorten URLs -- 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: Cracking the IT interview: jump start your career with confidence
But i think here's no one to forward :p Kunal Kapadia Computer Science and Enggneering 2nd yr NIT Trichy -- 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: Sartaj Sahni ebook
@ Carl Barton: I also know that site... i want a shared link u stupid... -- 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: Flipping Coins
Hey guys n gals WAKE UP No reply on this topic??? Do any knows here about segment tree?? -- 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] Sartaj Sahni ebook
Please give link to: Data Structures,Algorithms and Applications by Sartaj Sahni... or directly mail to me. -- 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] Ebooks Sites
Hello people please share sites from where good programming ebooks can be downloaded... i use library.nu and 4shared.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.
[algogeeks] Flipping Coins
Pls have a look at this Question on codechef
http://www.codechef.com/problems/FLIPCOIN/
i tried this using Segment tree...
i implemented segment updating properly
but dont know how to do segment Querying in this particular Question
although point Querying is easy..
and please suggest links and ebooks for topics such as segment tree.
Interval tree , Binary Indexed tree , Suffix trees(Other than Topcoder
Tutorials)
This is how i implemented Segment updating:
void update(int beg,int end,int ind)//segment updating
{
if(begB || endA) return;
if(beg=A end=B) m[ind]+=k;
else
{
update(beg,((beg+end)1),(ind1));
update(1+((beg+end)1),end,1+(ind1));
}
}
may be u need to change for Querying
--
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: [brain teaser] Sequence Puzzle 13april
@vaibhav shukla: 3 1 2 2 1 1 is ok but how 1 3 1 1 2 2 2 1 came Thanks On Apr 13, 2:57 pm, vaibhav shukla vaibhav200...@gmail.com wrote: On Wed, Apr 13, 2011 at 1:02 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: * Sequence Puzzle * * * *The below is a number puzzle. It should be read left to right, top to bottom. Question 1 What is the next two rows of numbers. Question 2 How was this reached. 1 1 2 1 1 2 1 1 1 1 1 2 2 1* next two rows: *3 1 2 2 1 1 1 3 1 1 2 2 2 1 * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/sequence-puzzle-13april 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. -- best wishes!! Vaibhav Shukla DU-MCA -- 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: [brain teaser] Sequence Puzzle 13april
Dont worry got it!!! On Apr 13, 2:57 pm, vaibhav shukla vaibhav200...@gmail.com wrote: On Wed, Apr 13, 2011 at 1:02 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: * Sequence Puzzle * * * *The below is a number puzzle. It should be read left to right, top to bottom. Question 1 What is the next two rows of numbers. Question 2 How was this reached. 1 1 2 1 1 2 1 1 1 1 1 2 2 1* next two rows: *3 1 2 2 1 1 1 3 1 1 2 2 2 1 * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/sequence-puzzle-13april 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. -- best wishes!! Vaibhav Shukla DU-MCA -- 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: If any one have algorithms for interviews by adnan aziz ebook... Please mail ...
Hey can u mail it to me plzzz?? On Mar 23, 7:55 am, Anand anandut2...@gmail.com wrote: Thanks!! On Tue, Mar 22, 2011 at 7:11 PM, D.N.Vishwakarma@IITR deok...@gmail.comwrote: thanx... On 3/22/11, Himanshu Neema potential.himansh...@gmail.com wrote: -- Forwarded message -- From: Himanshu Neema potential.himansh...@gmail.com Date: Tue, Mar 22, 2011 at 11:13 PM Subject: Re: [algogeeks] If any one have algorithms for interviews by adnan aziz ebook... Please mail ... To: Abhishek Goswami zeal.gosw...@gmail.com Its a 15.4MB pdf so would take time to download if you have slow internet connection , otherwise i checked the link its working. But I have also uploaded it on Google docs as Abhishek suggested here : https://docs.google.com/viewer?a=vpid=explorerchrome=truesrcid=0B-... On Tue, Mar 22, 2011 at 11:01 PM, Abhishek Goswami zeal.gosw...@gmail.comwrote: can you upload this file into google docs or attach this file. i tried to download this file but did not get any success for open this file Thanks Abhishek On Tue, Mar 22, 2011 at 10:41 PM, Himanshu Neema potential.himansh...@gmail.com wrote: Turns out that I cant send file larger than 4 MB , please download it from here , let me know if you're still unable to download: http://dl.dropbox.com/u/2681370/Algorithms%2Bfor%2BInterviews%2B%28sc... have fun ! On Tue, Mar 22, 2011 at 10:21 PM, Himanshu Neema potential.himansh...@gmail.com wrote: Enjoy :) On Tue, Mar 22, 2011 at 10:09 PM, Saravanan T mail2sarava...@gmail.comwrote: ++ On Tue, Mar 22, 2011 at 9:51 PM, Anurag atri anu.anurag@gmail.comwrote: and me too :) On Tue, Mar 22, 2011 at 9:28 PM, Nikhil Mishra mishra00...@gmail.comwrote: count me too On Tue, Mar 22, 2011 at 11:16 AM, kunal srivastav kunal.shrivas...@gmail.com wrote: plz send it to me too On Tue, Mar 22, 2011 at 11:14 AM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: -- *With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department * -- 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. -- thezeitgeistmovement.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. -- Regards Anurag Atri -- 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. -- 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. -- *With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to
[algogeeks] Re: If any one have algorithms for interviews by adnan aziz ebook... Please mail ...
Hey plzz mail me too.. On Apr 14, 9:29 am, Rajeev Kumar rajeevprasa...@gmail.com wrote: check this link:https://docs.google.com/viewer?a=vpid=explorerchrome=truesrcid=1B5... If you have any problem in access,please inform me On Thu, Apr 14, 2011 at 1:04 AM, Abhishek Goswami zeal.gosw...@gmail.comwrote: Hi, I tried to open this book in google docs and got message that file is not avaliable. does this file not available in google docs if yes , can anybody share this book again On Tue, Mar 22, 2011 at 10:41 PM, Himanshu Neema potential.himansh...@gmail.com wrote: Turns out that I cant send file larger than 4 MB , please download it from here , let me know if you're still unable to download: http://dl.dropbox.com/u/2681370/Algorithms%2Bfor%2BInterviews%2B%28sc... have fun ! On Tue, Mar 22, 2011 at 10:21 PM, Himanshu Neema potential.himansh...@gmail.com wrote: Enjoy :) On Tue, Mar 22, 2011 at 10:09 PM, Saravanan T mail2sarava...@gmail.comwrote: ++ On Tue, Mar 22, 2011 at 9:51 PM, Anurag atri anu.anurag@gmail.comwrote: and me too :) On Tue, Mar 22, 2011 at 9:28 PM, Nikhil Mishra mishra00...@gmail.comwrote: count me too On Tue, Mar 22, 2011 at 11:16 AM, kunal srivastav kunal.shrivas...@gmail.com wrote: plz send it to me too On Tue, Mar 22, 2011 at 11:14 AM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: -- *With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department * -- 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. -- thezeitgeistmovement.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. -- Regards Anurag Atri -- 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. -- 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. -- Thank You Rajeev Kumar -- 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
i m getting TLE for this soln and m not getting the concept used in
the above soln can anyone help??
#includeiostream
using namespace std;
int main()
{
int t,n,k,no,flag;
scanf(%d,t);
while(t--)
{
scanf(%d,n);
k = n;
int a[100] = {0};
flag = 0;
while(k--)
{
scanf(%d,no);
a[no + 1000]++;
if(a[no + 1000] n/2)
{
printf(YES %d\n,no);
flag = 1;
break;
}
}
if(flag == 0)
printf(NO\n);
}
return 0;
}
On Mar 16, 12:13 am, UTKARSH SRIVASTAV usrivastav...@gmail.com
wrote:
tahnks balaji i have got ac in this problem my prog is same only in
the end i have taken a loop and
@ akshata the link for the prob ishttps://www.spoj.pl/problems/MAJOR/
MY CODE IS
#includestdio.h
main()
{
long long int n,t,r[100],count,major,i;
scanf(%lld,t);
while(t--)
{
scanf(%lld,n);
scanf(%lld,r[0]);
major=r[0];
count=1;
for(i=1;in;i++)
{
scanf(%lld,r[i]);
if(r[i]!=major)
{
count--;
if(count0)
{ count=1;
major=r[i];
}
}
else
{
count++;
}
}
/*if(count=0)
printf(NO\n);
else
printf(YES%lld\n,major);*/
count=0;
for(i=0;in;i++)
{
if(r[i]==major)
count++;
}
if(countn/2)
printf(YES %lld\n,major);
else
printf(NO\n);}
scanf(%lld,r[0]);
return 0;
}
On Tue, Mar 15, 2011 at 10:34 AM, Balaji Ramani
rbalaji.psgt...@gmail.comwrote:
http://www.spoj.pl/problems/MAJOR/
http://www.spoj.pl/problems/MAJOR/Thanks,
Balaji.
On Tue, Mar 15, 2011 at 11:00 PM, Akshata Sharma
akshatasharm...@gmail.com wrote:
hey link to the problem??
On Tue, Mar 15, 2011 at 10:50 PM, Balaji Ramani
rbalaji.psgt...@gmail.com wrote:
It fails for input 1,2,3. I think there needs to be one more iteration to
check if the candidate is actually a majority element or not.
Thanks,
Balaji.
On Tue, Mar 15, 2011 at 9:50 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.com wrote:
CAN ANYONE PLEASE TELL ME WHY MY CODE IS GIVING WRONG ANSWER OR SOMEONE
WHO HAS GOT AC IN THIS PROBLEM MAY POST HIS SOLUTION
#includestdio.h
main()
{
long long int n,t,r,count,major,i;
scanf(%lld,t);
while(t--)
{
scanf(%lld,n);
scanf(%lld,r);
major=r;
count=1;
for(i=1;in;i++)
{
scanf(%lld,r);
if(r!=major)
{
count--;
if(count0)
{ count=1;
major=r;
}
}
else
{
count++;
}
}
if(count=0)
printf(NO\n);
else
printf(YES%lld\n,major);
}
return 0;
}
--
*UTKARSH SRIVATAV*
*CSE-3
B-Tech 2nd Year
@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.
--
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.
--
*UTKARSH SRIVATAV*
*CSE-3
B-Tech 2nd Year
@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
[algogeeks] Re: What would be the output of the following program..?
the rule governs that in exprns on both the side gets evaluated
only if first exprns gives TRUE if 1st one gives FALSE then whatever
be 2nd exprn answer be FALSE
and in || 2nd side is not evaluated if 1st side replies with TRUE..
On Dec 13, 9:10 pm, siva viknesh sivavikne...@gmail.com wrote:
int main()
{
int k = 5;
if (++k 5 k++/5 || ++k = 8);
printf(%d\n, k);
return 0;
}
for the above code output is '7' and not '8'...why??
int main()
{
int k = 5;
if (++k 5 k++/5 );
printf(%d\n, k);
return 0;
}
similarly for the above code output is '6' and not '7'...why??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: What would be the output of the following program..?
ya all the exprn is evaluated and left expr is assigned ..
On Dec 13, 9:21 pm, siva viknesh sivavikne...@gmail.com wrote:
#includestdio.h
int main()
{
int a=1,b=2,c=3;
c=--a,b++ - c;
printf(%d %d %d,a,b,c);
return 0;
}
the above code is perfectly valid and prints 0 3 0 ...
but how comma is evaluated and the value assigned to variable 'c' is the
expression evaluated on the RHS of commais there any such rules in C ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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 problem efficiently?
On Sep 5, 11:07 am, jliang [EMAIL PROTECTED] wrote: how about a doubled linked list where you can remove item at any index. the removing is O(1). you can also keep track of the current removing from a doubled linked list is O(1)? How? size S so if you are borrowing book at index greater than S/2, you traverse the list from the end, if index S/2, you traverse from the beginning. every time a book is removed, S becomes 1 smaller, so the traversal time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 you can also put them in a binary tree, so every operation is O(lgN) putting the original array in binary tree takes O(M lgM) time, and you will lose the original indices. So it's of no use. so the total will be O(lgN M) I dont think so. correct me if I am wrong. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
