This is the first article I have written after a one-year pause. So let's just start...

Cutting to the chase

There are articles on LCA on many sites(Topcoder, Codeforces), Youtube videos, the Wiki is quite explicative. So why do I write this? The answer is actually simple. I have no friends.

On a more serious note, I think most LCA articles don't mention the off-line and no-query cases

When someone says nobody ain't doing no thing with CF, I be like

So, haven't you met the average Joe that keep saying that "efficiency is not that important", "my [Greedy wrong sh*t] solution is certainly correct", "who's Dijkstra"? You will. Therefore, we'll be...

Cutting to the chase

And show some situations where competitive programming was particularly useful. I would really like to hear more solutions as I am myself a CF Avg. Joe.

An intro would be also be kind of mainstream, but I'll still be...

Cutting to the chase

Rotations and balancing are kind of boring, but invariants are not. The nice thing about in looking for different solutions for the same problem is that you can find elegance in each of them. Maybe more importantly, it helps you develop backups when the first solution fails.

It is just the fact that sometimes to sell and start over is the right call. Of course, starting off with a small amount of one million dollars would do(couldn't help myself, people keep saying orange is the new black (now seriously: I say Donald, you say... Knuth)

Some of you made the mistake of demanding an article on one of my favorite topics. (DP)

Note that the article might be simple for a big part of you as it is intended for the general public.

Seriously, why so serious? And why so mainstream? Competitive programming is all about fun, therefore...

Cutting to the chase

I'll talk about something that goes like that: everyone talks about it, few really know how to do it, everyone thinks everybody else knows how to do it, so everyone claims they know how to do it.Not teenage sex, but understanding data structures. In the sense of the metaphor before, I am close to a virgin but I still can give you some insight as there are some structures that are my type. I will write more on data structures, but this time we'll look at tries.

Don't get me wrong, I am talking about data structure that tend to be implemented and modeled the same way each time due to habit or even not implemented(cause STL has them).

Note that I will put more emphasis on the steps in getting the solution than on the implementation and the way the data structure works, because there are many great articles on it.

I began holding some weekly student workshop at Imperial College London and I find some of the material presented useful for Codeforces community, so I will also post it here. So, enjoy!

Quicksort

We already discussed some cool sorts such as mergesort that work in O(N log N). We want you to learn not “a sort algorithm”, but the ideas behind some of them.

A technique that works many times is finding redundancies in problems. We will illustrate this by trying to build quicksort out of insertion sort. Insertion sort takes each element and puts it in the right place. Take the next example: ( first array is the sorted one that is being constructed and the second is the remainings from the initial array )

Yeah, yeah, I know you expect from me matrix jokes. What if I told you I have no jokes on that ? So, just take the blue pill and go into serious stuff like ...

Cutting to the chase

I personally find matrix multiplication as the guy who sells stolen phones at the corner of the street. I mean, you get stuff at lower price but it can break in two days and you can get busted by the cops. Or not. I really need to find better metaphors...

Matrix multiplication is a well known method. People wrote on it before quite good articles, but I think you might get stuff simpler just by looking over some problems. For the ones who are familiar with the topic, you can skip to the last two problems.

It's sqrt decomposition. It didn't rime. Bummer...

Cutting to the chase

It has been written about sqrt decomposition many times. Still, many people see as a poor cousin of segment trees. Even though segment trees are more frequent in practice and much faster, I think both of them have their own advantages. Comparing a tank with a Ferrari might not be the best metaphor, but it's still applicable to some extent.

Sqrt decomposition is straight forward and easy to understand and yet an useful tool. Playing with data structures might come more natural if you broaden your horizon. One might fight with sticks before using a sword. Though, one might skip stick fighting for some reason and still be an excellent swordsman. Still, fighting with sticks is badass, especially if you're a monk.

Cutting to the chase

Clearly you don't need a PhD in Computing to sweep in the yard , but one might be useful in order to know linear and radial sweep algorithms. So , what's all about ? It's just what it sounds it is , sweeping linear ( up to down , for example ) or radial ( making a 360 degrees loop ).

How this can help?

Hello everyone !

I am glad to announce that the 4th MindCoding Round will take place on 25th of March 2015, 19:00 EET ! We delayed announcing the rounds on CodeForces to be sure our servers would ran smooth and we are ready for this round as our servers supported over 300 participants in the 1st round.

The Scientific Committee of the contest has the following members: Petru Trimbitas (Petru), Puscas Sergiu (Sergiu), Marius Gavrilescu (mgv), Cosmin Rusu (cr.rusucosmin), Gabriel Inelus (gabrielinelus), Onesim Robert (Robert.One), Adrian Scoup and me.

This is the first time this contest is publicly announced on CodeForces and I will talk about the site a little bit. Firstly, you can find a quick-start guide here and you also can try some of our problems from here. The contest is 1:30 hours long and there are 4 tasks for 100, 250, 500 and 1000 points. Like on Codeforces, the points decrease during the contests and you lose points for every resubmission. You will have partial or full feeback (depending on the problem; this will be specified in the statement)

There are 5 places for the Final taking place in Cluj-Napoca, Romania for non-Romanian citizens that are 18+ years old. The accomodation and food will be provided by the organisers. We had some international participants in last rounds, but there are big chances to qualify this round.

GL & HF everyone ! :D

PS : I proposed some problems in the last rounds. I would be glad if you take a look and give some feedback. :)

• https://mindcoding.ro/pb/tournament — easy
• https://mindcoding.ro/pb/kspecialists — medium
• https://mindcoding.ro/pb/bosses — hard
• https://mindcoding.ro/pb/undograph — hard

I also recommend taking a look on some of our interactive problems such as https://mindcoding.ro/pb/eggs.

UPD : The round starts in less than an hour. Don't forget to join our facebook event.

UPD2 : Before and during the round you can ask for questions on our IRC channel.

UPD3: Contest is finished. The editorial has been posted.

Congrats to the winners:

• mmaxio
• rares.buhai
• alex.velea
• VladaMG98
• george_stelian

I have been stuck between two divisions for the last 20 contests I've participated. Basicly , when I fall in div2 , I get back in div1 , but not pass the purple color. I am kind of disappointed of myself , so I decided to make a change and train harder than I ever did.

So in the next 30 days ( 30/7 — 28/8 ) I will solve 150 div1 problems. If someone is willing to take the same challenge , I've made a group.

Hi CF ! Long time , no see. I have an interesting problem for you.

Statement

N dwarfs fell into a pit with depth of D cm. For every dwarf you know the height to the shoulders ( i.e. the distance from the ground to the shoulders ) and the arms length. The dwarfs try to escape from the pit , so they climb one on each other and get out of the pit.

Every dwarfs stands on the shoulders of other. If one dwarf reaches the top of the pit , he can get out of the pit. We denote the shoulder height of the i - th dwarf with h_i and the arms length with l_i. A tower formed from k dwarfs j₁, j₂, ..., j_k has the height h_j1 + h_j2 + ... + h_jk . The dwarf h_jk can get out of the pit if h_j1 + h_j2 + ... + h_jk + l_jk ≥ D. A tower can be formed in any possible way.

Your task is to determine how many dwarfs can get out of the pit. (1 ≤ N ≤ 2000)

Solution

Let's start with a simpler problem. Supose the length of the hands does not matter. ( i.e. j_k - th dwarf can get out if h_j1 + h_j2 + ... + h_jk ≥ D ) In this case we can sort the dwarfs decrasingly by h_i and get out as many short dwarfs as possbile.

Note that a similar stategy would not work in our problem. An example would be N = 3 , D = 5 with ( h₁ = 1 , l₁ = 4 ) , ( h₂ = 2 , l₂ = 0 ) , ( h₃ = 2 , l₃ = 0 ).

With the previous strategy we would have the tower 2, 3, 1 and the dwarf 1 would be saved. But if the tower is 3, 1, 2 both 1 and 2 dwarfs can be saved.

We can conclude that a small dwarf with long hands can be placed closer to the base of the tower than other dwarfs. The order in wich the dwarfs will get out of the pit would rather be determined by the sum h_i + l_i. Also we need not to forget that a heigher dwarf ( with h_i bigger ) is more useful for the others than a small one.

Now , imagine we have already pulled out the optimum set of dwarfs. Let's now find how they came out. We can iterate through them and select the ones which we can put inside the hole and they still can get out. We will repeat that operation until all of them are in the hole.

From this reverse kind of thinking you got the idea that selecting a set of dwarfs who get out is a good one. We will sort the dwarfs decreasingly after h_i ( in case of equalty after l_i ). If all the dwarfs from some set of dwarfs can get out we need to choose the last wich can get out , than he can be added to the tower.

We keep a vector in wich we will mark if some dwarf is in the set of the ones witch can get out. At each step we will try to add the dwarf with the maximum h_i into the set.

    for (int i=1;i<=N;++i)
    {
        int dwarf = oH[i]; // oH - order after height decreasingly
        if ( good(dwarf) )
        {
            mark[ rev[dwarf] ] = 1; // put the dwarf in the set
            // mark - the marking vector
            // rev - the order in the original vector
            
            h_init -= h[dwarf]; // h_init - the height of the tower
            co++; // new dwarf added
        }
        else
            mark[ rev[dwarf] ] = 0; // the dwarf is outside the set
    }

Now we have to verify is we can add a dwarf in the set. For this we design a function wich says if a set of dwarfs is good or not. The last dwarf from the set wich will get out is the one with maximum h_i + l_i. Then we can get it out of the set and repeat the process. Of course , we do not need sorting because we can precompute the vector oHL ( order after h_i + l_i decreasingly ).

bool good(int dwarf)
{
    int h_now = h_init - H[dwarf]; // h_now - acutal tower height
    l[ rev[dwarf] ] = 1; // mark the dwarf
    for (int i=N;i>=0;--i) 
        if ( l[i] == 1 )
        {
            if ( h_now + H[oHL[i]] + L[oHL[i]] >= D ) 
                h_now += H[oHL[i]]; // if the dwarf can get out we put it in the tower
            else
                return 0; // else we have the guaranty that the actual set can't get out
        }
    return 1;
}

We verify in O(N) the introduction of some dwarf and we try to add every dwarf once. The final complexity is O(N²). Here is my source.

BONUS: The problem can be also solved by DP. Take a look. ;)

Field for the Cemetery

I tried to solve this problem and I am getting WA on test 16. I would really apreciate your help.

I tried to find an upper bound of the solution.

I colored the matrix of size q x c in n colors so that every two neighbour cells have different colours and every continuous segment of sizen does not contain the same colour. For the example in the statement , I colour the matrix like that:

1 2 3 1 2
2 3 1 2 3
3 1 2 3 1
1 2 3 1 2

Now , my aproximation of the upper bound would be the minimum number of cells with some color. It is really close to the real solution and I am quite sure that it is the solution too.

Notice that for a matrix of n x c you have the same number of colors on every line. So , I got the following calculus formula: ans = ( q / n ) * c + (c / n) * (q % n) + corner where corner = (l%n) + (c%n) - n.

UPD: If the solution is equal with my upper bound , than how can you prove that the lower bound is equal with the upper bound ?

UPD2: I also tried to put the segments after some rule , but it didn't suceed. For example if you have 7 7 4 you might be tempted to place the segments something like this:

1 1 1 1 8 9 1
2 2 2 2 8 9 1
3 3 3 3 8 9 1
4 4 4 4 8 9 1
5 5 5 5 0 0 0
6 6 6 6 0 0 0
7 7 7 7 0 0 0

But they can be placed like this:

1 1 1 1 8 9 1
2 2 2 2 8 9 1
3 3 3 3 8 9 1
4 5 6 0 8 9 1
4 5 6 7 7 7 7
4 5 6 1 1 1 1
4 5 6 2 2 2 2

Hi there! This week in Romania took place the 2014 Olympics in Informatics. I will present , as usual , the statements first and the solutions below. At final I will put links to all the problems and official solutions. There are 6 problems at my age category ( the last two highschool years ) , but I will present the solutions and the statements for my personal 3 favourites from the contest. Excuse me if you find some language/grammar mistakes. ( I try to avoid them but I'm not very good at this )

Statements

Werewolves ( day 1 )

There are 2*N villagers. Every villager has a hunch about who might be a werewolf. If you split the villagers in every possible way in two groups of N villagers , then , if there exist a suspect in both groups for every possible split , he will be the werewolf. Restrictions: 1 ≤ N ≤ 500000 , memory: 3MB. Example:

4
1 1 1 1 1 2 2 3

Solution: 1

Volume ( day 1 )

You have the heights of some portions of a field in a N * M matrix. Your task is to find the volume of water retained in the field. Restrictions: 3 ≤ N, M ≤ 752. For better understanding , let's take an example:

5 5
2 2 3 3 3
2 2 3 1 3
2 3 1 3 3
3 1 3 2 2
3 2 2 2 2

When the water is filles the field the hights will be:

2 2 3 3 3
2 2 3 3 3
2 3 3 3 3
3 2 3 2 2
3 2 2 2 2

So , the volume will be: 2 + 2 + 1 = 5

Permutation ( day 2 )

You are given a permutation of length n and m right rotations of it. There are defined two operation on every permutation of n elements : left rotation – the elements from the positions 2 to n move leftwards and the first number goes on position n — and right rotation – the same thing in the opposed sense. A right rotation of a permutation is defined as the permutation with the right rotation move applied for a certain number of times to the original permutation. Your task is to say which is the minimum number of operations to get all permutations to the same state. Restrictions: 1 ≤ n, m ≤ 100 000.

For the input data below the solution will be 5.

6 5 
3 1 4 2 6 5 
1 1 3 3 

The 5 permutation and the operation will be:

3 1 4 2 6 5 ( +1 right )
5 3 1 4 2 6 ( 0 )
5 3 1 4 2 6 ( 0 )
2 6 5 3 1 4 ( +2 left )
2 6 5 3 1 4 ( +2 left ) 

Solutions

Werewolves

During the contest I've noticed that the principle of Dirichlet can be used there. So , there need to be more than N villagers that have the same suspect. (if there are just N ,than they can be put in one group and the werewolf will not be found)

As a consequence , we have to find if there is a majoritary suspect. The majoritary vote problem is kind of a classic problem , so I will present just the optimal solution. You will abord the problem as a tournament. Every two supporters will fought and the one who remains up at the final might be the good one.

int cand = -1, k = 0;
for (int i=0;i<n;++i)
{
     int a = read();
     if (k == 0)
     {      
          cand = a;
          k = 1;
     }
     else
          if (a == cand)
               k++;
          else
               k--;
}

We will verify , after that , if the remaining suporter is the good one. Looking at the memory restriction , you will have to read the data twice ( once for finding the final candidate , once for verification ). The time complexity will be O(N) and the used memory will be O(1).

Volume

The first abordation that came to my mind during the contest was to begin either with the lowest heights or with the bigest heights.

Begining with the lowest heights we think of using sets of elements , so the best data structure used for this would be the disjoint data sets. This abordation is not very good because every time you merge two disjoint sets you will have to look for the height of the neighboring cell of the matrix. ( in the example for the cell with one you'll find the 3 as lowest neighbour ). You can continue on this abordation , but during the contest I didn't managed to get this at the good complexity. ( at complexity O(N*M*different_elements) a solution like that would have passed 70% from the tests )

Now , another abordation is to interpret the matrix as a graph. The crucial part is that the number of edges in the graph is O(N*M) ( because you have just 4 neighboring cells ). You have to find out for every cell which is the bigest element on the minimum height road from the exterior of matrix to it. In that way , you will know how much water will be in every cell. The simplest way is to use the Bellman-Ford algorithm because you have not much to think about the cost function. ( and , moreover , Bellman-Ford is very fast. ) Let's denote a[i][j] as the heights of the cells in the matrix and D[i][j] as the cost of arriving to the one matrix's cell. Here is my souce and here is how you can calculate the costs:

D[newx][newy] = min( D[newx][newy] , max( D[x][y] , a[newx][newy] ) ); ( x , y are the coordinates of the present cell , newx,newy are the coordinates of the cell where you go ).

Permutation

Even if the problem is not that complicated , I’ve enjoyed it most of all. First of all , notice that the permutation itself does not matter. You will use just the array which descriebes the states of permutations ( for the example : 0 1 1 3 3 ). Note that it would be a good idea to sort that array. Given the fact the array is a permutation you can sort it with Counting Sort:

    for (int i=1,v;i<m;++i)
    {
        F>>v;
        fr[v]++;
    }

    m = 0;
    for (int i=0;i<n;++i)
        for (int j=1;j<=fr[i];++j)
            a[++m] = i;

Let’s try to solve the problem if we have the final state of all permutations. This is very simple : you iterate through the values of the array and add to the result the minimum between the distance if you rotate the permutation just leftwards or just rightwards. Observe that you can split the array in 4 suqences ( possibly of length 0 ) for which the operations will apply :

• sequence [1,p1] – just leftwards
• sequence [p1+1,now-1] – just rightwards
• sequence [now+1,p2-1] – just leftwards
• sequence [p2,n] – just rightwards

The inequality p1 ≤ now ≤ p2 will always hold. This makes clear the fact that we have no surpassings and , therefore , the complexity can be holded at O(N). We will calculate at the first step the sequences if the center is at the first position in the array. In the following steps we’ll just look if points p1 and p2 need to be moved to the right.

    int p1 = 0;
    int p2 = 2;
    int ans = 1<<30;
    for (int i=1;i<=m;++i)
    {
        while ( p1+1 < m && a[i]-a[p1+1] > a[p1+1]+n-a[i] ) ++p1;
        while ( p2 < m && a[p2]-a[i] < n-a[p2+1]+a[i] ) ++p2;
        int now = 0;

        if ( 1 <= p1 && p1 < i )
        {
            now += sum(1,p1) + (n-a[i]) * p1;
        }
        if ( p1+1 < i )
        {
            now += ( (i-1)-(p1+1)+1 ) * a[i] - sum(p1+1,i-1);
        }

        if ( i+1 <= p2 )
        {
            now += sum(i+1,p2) - ( (p2)-(i+1)+1 ) * a[i];
        }
        if ( p2+1 <= m )
        {
            now += (a[i]+n) * (m-(p2+1)+1) - sum(p2+1,m);
        }

        ans = min(ans,now);
    }

Conclusions

From my point of view, the problems were interesting and you had something to learn from them by solving them. You can find the original statements , solutions and tests ( in Romanian ) for all age groups on this site. If you have any suggestions or different solutions for the problems please comment. I will read them next week because in this weekend I will be at the MindCoding Final. Take a look on their site. ( it's in English )

Hello ! This week I will present you some geometry problems. As the last week you'll have the statements first and the solutions below. I would also like to hear your feedback about my blog. Enjoy reading !

Statements

Hallway

This problem is from a Romanian judge. I will present the statement in English. Basically you have a hallway of size M*N. There are K columns at integer coordinates. Your task is to say the maximum size of a ball that can travese the hallway in such way that is doesn't get stuck. Restrictions: 1 ≤ M, N, K ≤ 1000 , print the result with 8 decimals rounded down.

Robot

From the same Romanian judge. You have a robot consisting of a N-polygon ( N<=10 ). Your robot position is defined as the point with the minimum y and ( in case of equality ) the minimum x. You have M ( M<=25 ) polygon obstacles with less than 251 points. Your task is to get to the final point ( fx,fy ) on the minimum length road in such way that the robot does not hit (intersect) any obstacle. You have to print the minimum length of this road. For all the polygons the points are given trigonometrically.

Solutions

Hallway

To obtain a first solution to this problem you have to think the problem "upside down". Let's assume we have already computed the radius of the ball. So you have to verify if you can traverse the hallway.

Instead of traversing the hallway with the ball , we'll shrink the ball to a point ( the red one in the picture ) and transform the obstacles into balls.

Now you can check is the point can traverse the hallway just by making the intersection graph of the balls and upper and downer sides of the hallway. We can binary search the size of the ball and we'll optain a O(K^2 log M) algorithm.

A faster solution would continue on the idea of the graph. You can associate costs in that graph : the distance between two obstacles or sides / 2. Now your problem will be reduced to calculating the minimum spanning tree in this graph until we have joined the upper and the downer sides togeather. How comes that ? When you're making the minimum spanning tree you are adding edges with ascending costs. So , if we have joined the upper and the downer side we know that the bigest edge in the road between them is our size.

Now let's analyse the complexity. We can use the Kruskal algorithm in O(K^2 log K). This is not a great improvement. On the other hand , we can use Prime in O(K^2). That's a nice solution , isn't it ?

Here is my source.

Robot

The small number of polygons suggests that the difficulty of the problem is to find a way to solve the problem as simple as possible.

If you read the post until here , you probablly expect the robot to be shrinked. You're right ! Let's take an obstacle with K points. We'll virtually move the anchor point in every point of the K and we'll obtain a new set of points. From this set we'll make a polygon just by making a convex hull in O(N*K log (N*K)). Here is some code:

void expand()
{
    sort(robot.begin(),robot.end());
    for (size_t i=0;i<obstacle.size();++i)
    {
        int size = obstacle[i].size();
        for (int j=0;j<size;++j)
            for (size_t k=0;k<robot.size();++k)
                obstacle[i].push_back( trans(obstacle[i][j],robot[0],robot[k]) );
        convex_hull( obstacle[i] );
    }
}

One right abordation in such cases ( when we deal with distances on a plane ) is to use a graph. We will consider all the points to be vertexes and we'll consider all valid edges. An edge is valid if it doesn't intersect with the interior of a polygon. We can solve that in O(K) for every polygon and pair of points.

Now our problem is how can we check if a segment intersects the interior of a polygon. This is quite a basic problem. You have to consider the following cases: at least one point is in the interior of the polygon , both points are on the edges of the polygon and the segment cuts a segment from the polygon. Checking if one point is in interior of a polygon goes like that:

int area(vector<pi> v)
{
    int out = 0;
    for (size_t i=0;i<v.size()-1;++i)
        out += cross(v[i],v[i+1]);
    out = max(out,-out);
    return out;
}
 
int tarea(pi A,pi B,pi C)
{
    int out = cross(A,B) + cross(B,C) + cross(C,A);
    out = max(out,-out);
    return out;
}
 
int parea(vector<pi> v,pi a)
{
    int out = 0;
    for (size_t i=0;i<v.size()-1;++i)
        out += tarea(v[i],v[i+1],a);
    return out;
}

bool inside(pd V,pd A)
{
    int area_v = area(V);
    int area_a = parea(V,A);
  
    if ( area_v == area_a ) return 1;
    return 0;
}

Once the graph is made , we can start a minimum road algorithm ( such as Dijkstra or Bellman-Ford ).

Here is a source.

Bonus: the shrinking trick can be used in this problem. Here is my solution.

Hi there ! I want to show you this week some interesting problems that don't necessit very much knowledge. I also think they're quite fun , so enjoy !

Firstly I will write the statements so you can try to solve them and downer will be the solutions. There will be three problems. The first problem was told me by my teacher , the second one is from a job interview and the third one is a simplified version of a problem from a Romanian judge.

Statements

Saving Dwarfs

N dwarfs have been atacked by a friendly dragon. Due to the fact the dragon is friendly he played a game with the dwarfs to decide which dwarfs he will eat. He explains the dwarfs the rules of the game and let them prepare a strategy. Then he arranges the dwarfs in a row so that the i-th dwarf can see the dwarfs with numbers i+1,i+2,..,N. Every dwarf will recieve a black hat or a white hat. The dwarfs are asked in order ( 1 to N ) what colour is their hat. If a dwarf answers the wrong colour than he will be eaten. Your task is to establish a rule to save as many dwarfs as possible.

Finding LCA

LCA is a arhiknown problem. Let’s try to solve it in O(1) memory. Formally , we have a rooted tree and two nodes x and y. Function f(x) returns the dad of the node x. Your task is to find the LCA of x and y as fast as possible.

Functions

You are given N ( 2 <= N <= 1000 ) first grade functions ( ax + b = 0 ) numberd from 1 to N. You have to respond to Q ( 1 <= Q <= 100000 ) querys q(t,p) : which is the p-th function at the moment t.

Solutions

Saving Dwarfs

Let’s start by saving at least half of the dwarfs. We will split the dwarfs in pairs of two consecutive dwarfs. The first one will tell the colour of the next dwarf so that the second one will be saved.

We’ll try to split the dwarfs in grupes of 3. The first one has to give enough information for the others to save themselves. Firstly , we know the colour of the first dwarf when he dies or survives. Therefore , the information should be : 1 – if the orther dwarfs have different colours , 0 – otherwise. Now we have saved 2/3 dwarfs.

Let’s try to generalise. The information for the anterior case goes like that:

( 0 , 0 ) -> 0 ( 1 , 0 ) -> 1 ( 1 , 0 ) -> 1 ( 1 , 1 ) -> 0

This is exactly the xor sum. Now the first dwarf will say the xor sum of the others:

x = c(2) ⊕ c(2) ⊕ … ⊕ c(n)

Now dwarf 2 knows the xor sum :

Y = c(3) ⊕… ⊕ c(n) X ⊕ Y = c(2)

So , the second dwarf will know his colour. This applies for the other dwarfs. So we have managed to save N-1 dwarfs.

Finding LCA

The obvious solution is to go upwards to the root and store the distances between the nodes( x and y ) and the root. As long as dist(x,root) < dist(y,root) , y will become f(y). When the distances are equal we are going upwards with both x and y. The complexity is O(R) , where R = max( dist(x,root) , dist(y,root) ).

A better solution comes with the observation that is you have distance L = max( dist(x,LCA) , dist(y,LCA) ) , then if you go L nodes up from the lower node ( x if dist(x,root) >dist(y,root) ,otherwise y ) and then while you are going upwards with the other node you will end up at some point being in the same place. Now you will have the distances to that common point and we will apply the same strategy as before. ( as dist(x,node) < dist(y,node) , y will become f(y) and so on )

Now if we had that distance L , the solution would run in O(L). We will do the algorithm described before with lengths l = 2^0 , 2^1 , 2^3 , … until we will have the first l = 2^k which will be larger than L.

The complexity will be: O( 1 + 2 + 4 + … + 2^k ) = O( 2^(k+1) ) = O(L).

You can observe that the complexity is good , but the constant is kind of large. We could use the idea with the powers of 2 , but in a different way. We’ll alternate when we move , we apply function f once for x , twice for y , 4 times for x and so on. We have the guarantee that the roads will overlap at some moment. So we’ve managed to reduce the constant using that trick.

Functions

Firstly we’ll try to solve a simpler problem. The querys will be which is the maximum value of the functions at some time t.

We observe that the number of changes of the highest value is maximum N-1. ( 2 in the picture ) This makes sense because two functions of the given form can intersect just a single time. Therefore , we can calculate the moment of intersections and tell which is the bigest function value at one time.

Let’s get back to the original problem. There we can apply the same principle and say that there are maximum (N-1) + (N-2) + … + 1 = (N-1) * N / 2 = O(N^2) intersections of the functions. We can calculate the moment of the intersection for every two functions and sort them.

Firstly we’ll calculate the initial order of the functions ( at the minimum_intersection_moment — 1 ). We can consider an intersection as an update operation. We will sort the querys and the updates and procces them cronologically. An update will be swaping of two values. Both querys and updates will be processed in O(1). The final complexity will be O((N^2) log N) from sorting.

The trick used in this problem is known as the convex hull trick .

Bonus

If you want to use the idea from problem functions you can try to see how it works for second grade functions. It can also be applied for the minimum spanning tree if the costs of edges are defined as functions. You also can try to solve this problem.

Thanks for reading and hope you enjoyed the problems ! :)

Hello everybody ! This is my first entry. I want to share with you my knowledge about treaps and to ask if you know any problems that use this data structure.

The treap is a combination between a heap and a BST. So , you have two values asociated with every node — the key and the priority.

The main properties are: 1. if you traverse it in inorder , your keys will be sorted 2. priority of every node is greater than the ones of the sons

Operations

Search: like in an usual BST.

Rotations: the idea behind the rotations is to keep the heap property , so if you want to swap w and z this goes like that

      z            w
     / \          / \
    w   c   <=>  a   z
   / \              / \
  a   b            b   c

Insertion: you go to the right place and insert the new node as a leaf and then when you return you balance the tree ( that means you make roations to keep the heap property )

Deletion: you search for the specified key and move it downwards ( in left or in right — you have to keep the heap property ) ; when the node becomes a leaf you delete it

Split: you can split the treap in two treaps ( one with the keys smaller than the wanted value and one with the key bigger than the wanted value ) ; you will insert a new node with priority = infinity and key = value ; your new treaps will be the left and the right sons

Join: you can join two treaps in one new treap ; you can do this by inserting a new node having the sons the two treaps and than you will delete the inserted node

Usefulness

You can keep dynamic arrays with a treap as you can search the k-th value in an array at any time in O(log n). All the operation stated before are made in O(log n) ( except rotations which are made in O(1) ).