Re: [algogeeks] Re: MS
What is the problem with sunny's solution ??
On Mon, Jun 20, 2011 at 9:31 AM, RAJAT kumar singh
wrote:
> #include
> #include
> char
> s[]={'a','x','x','b','a','b','x','x','x','x','x','a','b','a','x','x','b',};
>
>
> int minimum(char,char,int );
> int main()
> {
>
> int i=minimum('a','b',17);
> printf("%d",i);
> }
>
>
> int minimum(char a ,char b,int n)
> {
> int i=0;
> int lindex=-1,rindex=-1,min;
>
> min=n;
> while(i {
>
>
>
>
> if(s[i]==a)
> {
> lindex=i;
> if(rindex!=-1)
> {
> min=mini(min,abs(lindex-rindex));
> }
> }
>
> else if(s[i]==b)
> {
> rindex=i;
> if(lindex!=-1)
> {
> min=mini(min,abs(lindex-rindex));
> }
>
>
>
> }
>
>
> i++;
> }
>
> return min;
> }
>
>
> int mini(int a,int b)
> {
>
> if(a>b)
> return b;
> else
> return a;
>
>
> }
>
> --
> 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 ,
Gaurav Saxena
--
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: Topcoder Escape problem
Ok bfs cannot be used in this. I thought that as the graph is un weighted I could use bfs. Thanks for your advice. Thanks for that idea. Actually for dijkstra I need to have a node list. Could you tell me what should I consider as node. I think I should take node as each (x,y) pair ? On Mon, Jun 13, 2011 at 5:19 PM, Divye Kapoor wrote: > You could also use a priority queue based search (A*) where you explore all > vertices with cost 0 before exploring all vertices with cost 1 etc. > Essentially, that is the same as Dijkstra's in this case. > > -- > DK > > -- > 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/-/5Po4JF4ZD_YJ. > > 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 , Gaurav Saxena -- 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] Topcoder Escape problem
Please suggest me a way to solve this problem http://www.topcoder.com/stat?c=problem_statement&pm=1170&rd=4371 Problem statement pasted below You are playing a video game that involves escaping from a dangerous area. Within the area there are DEADLY regions you can't enter, HARMFUL regions that take 1 life for every step you make in them, and NORMAL regions that don't affect you in any way. You will start from (0,0) and have to make it to (500,500) using only Up, Left, Right, and Down steps. The map will be given as a String[] deadly listing the DEADLY regions and a String[] harmful listing the HARMFUL regions. The elements in each of these parameters will be formatted as follows: Input format(quotes for clarity): "X1 Y1 X2 Y2" where (X1,Y1) is one corner of the region and (X2,Y2) is the other corner of the region The corners of the region are inclusive bounds (i.e. (4,1) and (2,2) include x-values between 4 and 2 inclusive and y-values between 1 and 2 inclusive). All unspecified regions are considered NORMAL. If regions overlap for a particular square, then whichever region is worst takes effect (e.g. DEADLY+HARMFUL = DEADLY, HARMFUL+NORMAL = HARMFUL, HARMFUL+HARMFUL = HARMFUL, DEADLY+NORMAL=DEADLY). Damage taken at each step occurs based on the destination square and not on the starting square (e.g. if the square (500,500) is HARMFUL you WILL take a point of damage stepping onto it; if the square (0,0) is HARMFUL you WON'T take a point of damage stepping off of it; this works analogously for DEADLY squares). Return the least amount of life you will have to lose in order to reach the destination. Return -1 if there is no path to the destination. Your character is not allowed to leave the map (i.e. have X or Y less than 0 or greater than 500). If two harmful regions overlap, the area where they overlap is exactly the same as non-overlapping harmful regions (i.e. the effect is NOT cumulative, and the overlapping region still takes exactly 1 life) I am not getting how to solve this problem . I know that bfs will be used but could you suggest in what way?. Thanks in advance :). -- Thanks and Regards , Gaurav Saxena -- 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] C++ problem..
Actually
A(int *m=0*)
> {
> a=m;
> }
> not
> A*(int m*) {
>a = m;
> }
>
means m has a default value of 0 ie this value will be used if no parameter
is given . So when you pass it a parameter default value is simply ignored.
On Wed, May 25, 2011 at 12:15 PM, Balaji S wrote:
> ya.. thanks :) it works. but.. we are initializing m to 0 in everycall
> ryt.. ? then how does 1,2,3,is initialized??
>
> --
> 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 ,
Gaurav Saxena
--
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] Compiler Design Help
Please mail me also. On Sat, Apr 16, 2011 at 10:02 PM, Arvinth Deenadayalan wrote: > Please cc me also. Tia. > > On 4/16/11, rgap wrote: > > Send me links too, please > > > > On Apr 10, 3:14 am, rahul rai wrote: > >> None has been published . If you want i can give you a two links to > >> video courses , and some set of solved questions . Which will be good > >> for "compiler design help" > >> > >> On 4/10/11, Harshal wrote: > >> > >> > >> > >> > someone please share the solution manual of compiler design by Aho > (aka > >> > dragon book)... I would be very grateful. Thanks.. > >> > >> > -- > >> > Harshal. > >> > >> > -- > >> > 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. > >> > >> -- > >> Rahul > > > > -- > > 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. > > > > > > -- > Sent from my mobile device > > Arvinth KumarDD > > -- > 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 , Gaurav Saxena -- 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] If any one have algorithms for interviews by adnan aziz ebook... Please mail ...
nsubscribe 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@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. > -- Thanks and Regards , Gaurav Saxena -- 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] CODECHEF FLIP COIN problem
Yes actually I could not figure out how to implement that lazy propagation
in the array . Yes please help me in doing that.
On Wed, Feb 9, 2011 at 10:56 PM, Arpit Sood wrote:
> you are not actually using the concept of lazy propagation in the code, you
> are doing update in O(n). if you want the solution then reply back.
>
>
> On Wed, Feb 9, 2011 at 6:22 PM, Gaurav Saxena wrote:
>
>> @arpit : could you please tell me what is the problem with the update
>> function ??
>>
>> On Wed, Feb 9, 2011 at 3:32 PM, Arpit Sood wrote:
>>
>>> there is problem with the update function...
>>>
>>> On Tue, Feb 8, 2011 at 8:14 PM, Gaurav Saxena wrote:
>>>
>>>> Hey thanks for your help
>>>> I have written a code using range trees but I am still getting TLE [?][?]
>>>> [?]
>>>> Please suggest me something
>>>>
>>>>
>>>> Here is my code
>>>>
>>>> /*
>>>> * File: main1.c
>>>> * Author: gs
>>>> *
>>>> * Created on 8 February, 2011, 7:46 PM
>>>> */
>>>>
>>>> #include
>>>> #include
>>>>
>>>>
>>>> #define MAX 30
>>>> #define loop0(i,j) for(int i=0;i>>> #define loop1(i,j) for(int i=1;i>>> # define true 1
>>>> # define false 0
>>>>
>>>>
>>>> _Bool flag[MAX];
>>>> int value[MAX];
>>>>
>>>> /*void initialize(int node, int b, int e)
>>>> {
>>>> if (b == e)
>>>> {
>>>> flag[node] = false;
>>>> value[node] = 0;
>>>> }
>>>> else
>>>> {
>>>> initialize(2 * node, b, (b + e) / 2);
>>>> initialize(2 * node + 1, (b + e) / 2 + 1, e);
>>>> value[node] = 0;
>>>> flag[node] = false;
>>>> }
>>>> }*/
>>>>
>>>> int update(int node, int b, int e, int i, int j)
>>>> {
>>>> int p1, p2;
>>>> if (i > e || j < b)
>>>> return 0;
>>>> if(b==e)
>>>> {
>>>> if(flag[node] == true)
>>>> return 1;
>>>> else
>>>> return 0;
>>>> }
>>>> if (b >= i && e <= j)
>>>> {
>>>> if(flag[node] == true)
>>>> {
>>>> flag[node] = false;
>>>> flag[2*node] = !flag[2*node];
>>>> flag[2*node+1] = !flag[2*node+1];
>>>> p1 = update(2 * node, b, (b + e) / 2, i, j);
>>>> p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
>>>> return (value[node] = p1 + p2);
>>>> }
>>>> else
>>>> return value[node];
>>>> }
>>>> else
>>>> {
>>>> if(flag[node]==true)
>>>> {
>>>> flag[node]=false;
>>>> flag[2*node]=!flag[2*node];
>>>> flag[2*node+1]=!flag[2*node+1];
>>>> }
>>>> p1 = update(2 * node, b, (b + e) / 2, i, j);
>>>> p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
>>>> return value[node] = p1 + p2;
>>>> }
>>>> }
>>>>
>>>> int query(int node, int b, int e, int i, int j)
>>>> {
>>>> int p1, p2;
>>>> if (i > e || j < b)
>>>> return 0;
>>>> if (b >= i && e <= j)
>>>> {
>>>> flag[node] = !flag[node];
>>>> return value[node] = e - b + 1 - value[node];
>>>> }
>>>> else
>>>> {
>>>> if(flag[node]==true)
>>>> {
>>>> flag[node]=false;
>>>> flag[2*node]=!flag[2*node];
>>>> flag[2*node+1]=!flag[2*node+1];
>>>> }
>>>> p1 = query(2 * node, b, (b + e) / 2, i, j);
>>>> p2 = query(2 * node + 1, (b + e) / 2 + 1, e, i, j);
>>>> if(p1==-1)
>>>> p1=0;
>>>> if(p2==-1)
>>>> p2=0;
>>>> return (value[node] = p1 + p2);
>>>> }
>>>
Re: [algogeeks] CODECHEF FLIP COIN problem
@arpit : could you please tell me what is the problem with the update
function ??
On Wed, Feb 9, 2011 at 3:32 PM, Arpit Sood wrote:
> there is problem with the update function...
>
> On Tue, Feb 8, 2011 at 8:14 PM, Gaurav Saxena wrote:
>
>> Hey thanks for your help
>> I have written a code using range trees but I am still getting TLE [?][?][?]
>> Please suggest me something
>>
>>
>> Here is my code
>>
>> /*
>> * File: main1.c
>> * Author: gs
>> *
>> * Created on 8 February, 2011, 7:46 PM
>> */
>>
>> #include
>> #include
>>
>>
>> #define MAX 30
>> #define loop0(i,j) for(int i=0;i> #define loop1(i,j) for(int i=1;i> # define true 1
>> # define false 0
>>
>>
>> _Bool flag[MAX];
>> int value[MAX];
>>
>> /*void initialize(int node, int b, int e)
>> {
>> if (b == e)
>> {
>> flag[node] = false;
>> value[node] = 0;
>> }
>> else
>> {
>> initialize(2 * node, b, (b + e) / 2);
>> initialize(2 * node + 1, (b + e) / 2 + 1, e);
>> value[node] = 0;
>> flag[node] = false;
>> }
>> }*/
>>
>> int update(int node, int b, int e, int i, int j)
>> {
>> int p1, p2;
>> if (i > e || j < b)
>> return 0;
>> if(b==e)
>> {
>> if(flag[node] == true)
>> return 1;
>> else
>> return 0;
>> }
>> if (b >= i && e <= j)
>> {
>> if(flag[node] == true)
>> {
>> flag[node] = false;
>> flag[2*node] = !flag[2*node];
>> flag[2*node+1] = !flag[2*node+1];
>> p1 = update(2 * node, b, (b + e) / 2, i, j);
>> p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
>> return (value[node] = p1 + p2);
>> }
>> else
>> return value[node];
>> }
>> else
>> {
>> if(flag[node]==true)
>> {
>> flag[node]=false;
>> flag[2*node]=!flag[2*node];
>> flag[2*node+1]=!flag[2*node+1];
>> }
>> p1 = update(2 * node, b, (b + e) / 2, i, j);
>> p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
>> return value[node] = p1 + p2;
>> }
>> }
>>
>> int query(int node, int b, int e, int i, int j)
>> {
>> int p1, p2;
>> if (i > e || j < b)
>> return 0;
>> if (b >= i && e <= j)
>> {
>> flag[node] = !flag[node];
>> return value[node] = e - b + 1 - value[node];
>> }
>> else
>> {
>> if(flag[node]==true)
>> {
>> flag[node]=false;
>> flag[2*node]=!flag[2*node];
>> flag[2*node+1]=!flag[2*node+1];
>> }
>> p1 = query(2 * node, b, (b + e) / 2, i, j);
>> p2 = query(2 * node + 1, (b + e) / 2 + 1, e, i, j);
>> if(p1==-1)
>> p1=0;
>> if(p2==-1)
>> p2=0;
>> return (value[node] = p1 + p2);
>> }
>> }
>>
>> int main()
>> {
>>int i, n, q,ret;
>>int cmd, a, b, z;
>>scanf("%d %d",&n,&q);
>>//initialize(1, 0, tests-1);
>>for(i=0;i< q;i++)
>>{
>>scanf("%d %d %d",&cmd,&a,&b);
>>if(cmd==0)
>>value[1] = query(1,0,n-1,a,b);
>>else
>>printf("%d\n",update(1,0,n-1,a,b));
>>}
>>return 0;
>>
>> }
>>
>>
>>
>>
>> On Tue, Feb 8, 2011 at 3:41 PM, sunny agrawal wrote:
>>
>>> make a tree where each node have the following structure
>>>
>>> 1. rangeLow
>>> 2. rangeHigh
>>> 3. headCount of its complete subTree
>>> 4. boolean variable change, if true means all nodes of that subtree need
>>> to be flipped but we are not flipping in the hope if again a flip occur we
>>> can reset the flag and we can save some time
>>> 5.isHead
>>>
>>> initialise range tree as for root range 0->MAX
>>> leftSubTree 0->MAX/2 rightSubTree MAX/2+1 -> MAX
>>> all headCount initially 0
>>> all changes to false
>>>
>>> as a query comes, i
Re: [algogeeks] CODECHEF FLIP COIN problem
Hey thanks for your help
I have written a code using range trees but I am still getting TLE [?][?][?]
Please suggest me something
Here is my code
/*
* File: main1.c
* Author: gs
*
* Created on 8 February, 2011, 7:46 PM
*/
#include
#include
#define MAX 30
#define loop0(i,j) for(int i=0;i e || j < b)
return 0;
if(b==e)
{
if(flag[node] == true)
return 1;
else
return 0;
}
if (b >= i && e <= j)
{
if(flag[node] == true)
{
flag[node] = false;
flag[2*node] = !flag[2*node];
flag[2*node+1] = !flag[2*node+1];
p1 = update(2 * node, b, (b + e) / 2, i, j);
p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
return (value[node] = p1 + p2);
}
else
return value[node];
}
else
{
if(flag[node]==true)
{
flag[node]=false;
flag[2*node]=!flag[2*node];
flag[2*node+1]=!flag[2*node+1];
}
p1 = update(2 * node, b, (b + e) / 2, i, j);
p2 = update(2 * node + 1, (b + e) / 2 + 1, e, i, j);
return value[node] = p1 + p2;
}
}
int query(int node, int b, int e, int i, int j)
{
int p1, p2;
if (i > e || j < b)
return 0;
if (b >= i && e <= j)
{
flag[node] = !flag[node];
return value[node] = e - b + 1 - value[node];
}
else
{
if(flag[node]==true)
{
flag[node]=false;
flag[2*node]=!flag[2*node];
flag[2*node+1]=!flag[2*node+1];
}
p1 = query(2 * node, b, (b + e) / 2, i, j);
p2 = query(2 * node + 1, (b + e) / 2 + 1, e, i, j);
if(p1==-1)
p1=0;
if(p2==-1)
p2=0;
return (value[node] = p1 + p2);
}
}
int main()
{
int i, n, q,ret;
int cmd, a, b, z;
scanf("%d %d",&n,&q);
//initialize(1, 0, tests-1);
for(i=0;i< q;i++)
{
scanf("%d %d %d",&cmd,&a,&b);
if(cmd==0)
value[1] = query(1,0,n-1,a,b);
else
printf("%d\n",update(1,0,n-1,a,b));
}
return 0;
}
On Tue, Feb 8, 2011 at 3:41 PM, sunny agrawal wrote:
> make a tree where each node have the following structure
>
> 1. rangeLow
> 2. rangeHigh
> 3. headCount of its complete subTree
> 4. boolean variable change, if true means all nodes of that subtree need to
> be flipped but we are not flipping in the hope if again a flip occur we can
> reset the flag and we can save some time
> 5.isHead
>
> initialise range tree as for root range 0->MAX
> leftSubTree 0->MAX/2 rightSubTree MAX/2+1 -> MAX
> all headCount initially 0
> all changes to false
>
> as a query comes, if it matches with range of some node we can stop
> propagating at that level and making change true so no need to go till leaf
> nodes
> new head count at that node will be (total nodes in its range - prev
> headCount)
>
>
> if you are still not able to get it you should read a range tree tutorial,
> that will really help
>
> On Tue, Feb 8, 2011 at 2:28 PM, Gaurav Saxena wrote:
>
>> Actually I could not figure out any good way of doing this . [?][?]
>> Could you please suggest me something or give some idea .
>> Thanks for helping
>>
>> On Tue, Feb 8, 2011 at 1:51 PM, sunny agrawal wrote:
>>
>>> i think time complexity of the O(nlgn) for an avg case will suffice
>>>
>>> no it will not be inefficient if we keep sufficient information at each
>>> node
>>> each node will keep information of all its childs(headCount) and using
>>> some optimizations such as if two flips on same range occur simultaneously,
>>> then after all there will be no effect at all so there was no need of doing
>>> anything.
>>>
>>> On Tue, Feb 8, 2011 at 1:27 PM, Gaurav Saxena wrote:
>>>
>>>> If we make segments of the range of coins which are heads then in some
>>>> case the result will become alternate which could be more inefficient. Any
>>>> idea what time complexity will suffice ?
>>>> Could you please elaborate your reply .
>>>>
>>>>
>>>> On Tue, Feb 8, 2011 at 1:08 PM, sunny agrawal
>>>> wrote:
>>>>
>>>>> i think your solution will be O(n) for each query
>>>>> so it will be O(Q*N), that will surely timeout
>>>>> read about Range Trees, segment trees from wiki or CLRS
>>>>>
>>>>> On Tue, Feb 8, 2011 at 1:01 PM, Gaurav Saxena
>>>>> wrote:
>>>>>
>>>>>>
Re: [algogeeks] CODECHEF FLIP COIN problem
Actually I could not figure out any good way of doing this . [?][?] Could you please suggest me something or give some idea . Thanks for helping On Tue, Feb 8, 2011 at 1:51 PM, sunny agrawal wrote: > i think time complexity of the O(nlgn) for an avg case will suffice > > no it will not be inefficient if we keep sufficient information at each > node > each node will keep information of all its childs(headCount) and using some > optimizations such as if two flips on same range occur simultaneously, then > after all there will be no effect at all so there was no need of doing > anything. > > On Tue, Feb 8, 2011 at 1:27 PM, Gaurav Saxena wrote: > >> If we make segments of the range of coins which are heads then in some >> case the result will become alternate which could be more inefficient. Any >> idea what time complexity will suffice ? >> Could you please elaborate your reply . >> >> >> On Tue, Feb 8, 2011 at 1:08 PM, sunny agrawal wrote: >> >>> i think your solution will be O(n) for each query >>> so it will be O(Q*N), that will surely timeout >>> read about Range Trees, segment trees from wiki or CLRS >>> >>> On Tue, Feb 8, 2011 at 1:01 PM, Gaurav Saxena wrote: >>> >>>> I need help regarding the codechef flip coin problem . >>>> I am trying a code with O(n) time and it is giving TLE . >>>> Couldn't figure out a better solution. >>>> http://www.codechef.com/problems/FLIPCOIN/ >>>> >>>> Thanks for help . >>>> >>>> -- >>>> Thanks and Regards , >>>> Gaurav Saxena >>>> >>>> -- >>>> 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 IV 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. >>> >> >> >> >> -- >> Thanks and Regards , >> Gaurav Saxena >> >> -- >> 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 IV 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. > -- Thanks and Regards , Gaurav Saxena -- 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. <<344.gif>><<33F.gif>>
Re: [algogeeks] CODECHEF FLIP COIN problem
If we make segments of the range of coins which are heads then in some case the result will become alternate which could be more inefficient. Any idea what time complexity will suffice ? Could you please elaborate your reply . On Tue, Feb 8, 2011 at 1:08 PM, sunny agrawal wrote: > i think your solution will be O(n) for each query > so it will be O(Q*N), that will surely timeout > read about Range Trees, segment trees from wiki or CLRS > > On Tue, Feb 8, 2011 at 1:01 PM, Gaurav Saxena wrote: > >> I need help regarding the codechef flip coin problem . >> I am trying a code with O(n) time and it is giving TLE . >> Couldn't figure out a better solution. >> http://www.codechef.com/problems/FLIPCOIN/ >> >> Thanks for help . >> >> -- >> Thanks and Regards , >> Gaurav Saxena >> >> -- >> 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 IV 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. > -- Thanks and Regards , Gaurav Saxena -- 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] CODECHEF FLIP COIN problem
I need help regarding the codechef flip coin problem . I am trying a code with O(n) time and it is giving TLE . Couldn't figure out a better solution. http://www.codechef.com/problems/FLIPCOIN/ Thanks for help . -- Thanks and Regards , Gaurav Saxena -- 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.
