You are not logged in. Please login at www.codechef.com to post your questions!

×

Help with segment trees - query processing

Hello all,

I am now attempting to solve the problem FLIPCOIN in the practice section, medium difficulty level.

I am aware that a naive solution gets TLE... However, I also know that some sort of segment tree data structure can and needs to be used to process queries fast.

Below is my naive and wrong (from the execution time point of view) code, that gives me a TLE:

#include <stdio.h>

int main()
{
    int N,Q;
    int i;
    scanf("%d %d", &N, &Q);
    char* array;
    array = (char *)malloc(N*sizeof(char));
    for(i = 0; i < N; i++)
    {
        array[i] = 'T';
    }
    int q;
    for(q = 0; q < Q;q++)
    {
        int control,low,high;
        scanf("%d %d %d", &control,&low,&high);
        if(control == 0)
        {
            for(i=low;i <= high; i++)
            {
                if(array[i] == 'T')
                array[i] = 'H';
                else
                array[i] = 'T';
            }
        }
        else
        {
            int auxiliar = 0;
            for(i=low;i <= high; i++)
            {
                if(array[i] == 'H')
                auxiliar++;
            }
            printf("%d\n", auxiliar);
        }
    }
    return 0;
}

What I would like to ask, if that is possible is either a very good and explanatory reference with examples to implement segment trees for a similar problem, or, something that would be even better, if someone with more expertise could provide some sort of "editorial" and provide me with tips along the way, so that I could implement a segment tree on my own, I would be very appreciated.

The reason why I ask this is that sometimes, even after reading editorials I have some trouble implementing some new data structures and a more guided and step by step explanation would help me a lot... If I can do simple things, one at a time and end up with a segment tree implemented and understood on my own, i'd be very, very thankful :D

Thanks in advance,

Bruno

asked 27 Jan '13, 19:08

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

edited 27 Jan '13, 19:09


Hello @betlista,

Thanks for your response, but I'd actually prefer a more naive explanation (like if I was 5 y.o. really!) of this concept...

Because, like graphs, sometimes I get a bit lost in the theory behind the concepts and totally fail at implementing them...

So, several things:

  • Using trees, queries can be processed in O(logN) time;
  • They provide the only fastest way to get AC to these sort of problems;
  • They can be implemented using either arrays or heaps/binary trees (I think);
  • They depend upon the range of the queries, i.e., if it's either updating 1 element, or several;

If I want to write an efficient method to query over an array, something with a signature like:

int query(int low, int high)

where this function will return me (for this problem) the number of coins heads up between low and high, I will need a method update, like:

void update(int low, int high)

My questions are:

What auxiliary data structures do I need to use/create,besides a tree, so that I can use these methods efficiently?

How to create a tree in itself?

For example, if our input array was called simply array, we know that, initially we have:

array[N] = {'T', 'T',..., 'T'};

would this function for querying values be correct:

int query(int low, int high)
{
    int auxiliar = 0;
    for(i=low;i <= high; i++)
    {
        if(array[i] == 'H')
        auxiliar++;
        }
        return auxiliar;
   }

This is where I've come so far... Any help would be extremely useful, thanks in advance,

Bruno

link

answered 28 Jan '13, 03:05

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

edited 28 Jan '13, 03:26

no!!I dont think above query function is right!!It would take a lot time!!Instead of use Segment trees...Just subtract the no of heads coins from total no of coins below that node!!And just use some basic function on query and update!I guess this might help for reference http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

(26 Jun '13, 02:27) jaythegenius3★

You can read a very nice tutorial on segment trees here

link

answered 05 Dec '13, 02:54

kangoonie's gravatar image

2★kangoonie
56
accept rate: 25%

There very similar question to yours - http://discuss.codechef.com/questions/2068/flip-coins-solutions-arent-public . And probably the answer is exactly what you are looking for...

Especially this sample problem is the same one.

If there is still problem we can elaborate more ;-)

link

answered 28 Jan '13, 01:39

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

edited 28 Jan '13, 01:40

I really dont know much about data structs but i found my own way of solving such probs. I simply create two arrays, one for each element stored individually and other which stores result of 100 element in one block. While processing queries i use those those groups to make my program around 100 times faster to get AC :)

Here is a link to my soln.

link

answered 26 Jun '13, 11:48

abbas's gravatar image

4★abbas
4118
accept rate: 28%

I wrote a tutorial about Lazy Updates. Let me know if you have any more questions. Good luck!

link

answered 10 Dec '13, 22:35

kangoonie's gravatar image

2★kangoonie
56
accept rate: 25%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×727
×711
×116
×92

question asked: 27 Jan '13, 19:08

question was seen: 3,853 times

last updated: 10 Dec '13, 22:35