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.
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.
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 ! :)
").appendTo( e.find(".right") ); e.find(".comment-content").hide(); e.find(".show-bad-comment-link").click(function () { e.find(".comment-content").show(); e.find(".bad-comment-replacement").hide(); return false; }); }); });
