Problem Statement:
TopCoder SRM 371 Div. 1 Medium - ChessMatchup
Solution:
Just learnt Kuhn-Munkres algorithm, and tried a related problem. The problem is a straight forward modification of maximum weight perfect matching. Here is an implementation:
Showing posts with label TopCoder. Show all posts
Showing posts with label TopCoder. Show all posts
Sunday, December 28, 2014
Saturday, December 13, 2014
TopCoder SRM 640 Div.1 550 - MaximumBipartiteMatchingProblem
Problem Statement:
SRM 640 Div.1 550 - MaximumBipartiteMatchingProblem
Solution:
A very mathematical problem I guess, we will get to optimise a quadratic function. Firstly, take ans vertices from both n1 and n2, and match them like this:
That means we have (n1-ans) unmatched vertices from the first set F, and (n2-ans) unmatched vertices from the second set S. We cannot match any of these unmatched vertices amongst themselves, because it will immediately increase the number of bipartite matching. So we can only match them with those ans paired vertices
SRM 640 Div.1 550 - MaximumBipartiteMatchingProblem
Solution:
A very mathematical problem I guess, we will get to optimise a quadratic function. Firstly, take ans vertices from both n1 and n2, and match them like this:
ans pairs of vertices: o o o o o -> upper-end | | | | | o o o o o -> lower-end
That means we have (n1-ans) unmatched vertices from the first set F, and (n2-ans) unmatched vertices from the second set S. We cannot match any of these unmatched vertices amongst themselves, because it will immediately increase the number of bipartite matching. So we can only match them with those ans paired vertices
TopCoder SRM 641 Div. 1 250 - TrianglesContainOrigin
Problem Statement:
SRM 641 Div. 1 250 - TrianglesContainOrigin
Solution:
A pretty error prone computational geometry problem. The idea is actually quite simple, but the implementation can be quite tedious. Since no three points can form a collinear line, we can draw a line to each point P from the origin O and deterministically define that point by the angle defined by the line and the x-axis (that means the vector OP and the unit normal vector i of x-axis). Once we have converted every points as these angles and sort them, we can make use of another observation: if we choose two points with corresponding angles alpha and beta, then to form a triangle that contains the origin, we need to choose those points with angles between (alpha + 180, beta + 180). Otherwise, any triangle formed using points beyond these region will not contain the origin. This means that we can use binary search to find the number of points lying in the desired region. Overall we will have a \(O(N^2 \lg{N})\) running time complexity.
SRM 641 Div. 1 250 - TrianglesContainOrigin
Solution:
A pretty error prone computational geometry problem. The idea is actually quite simple, but the implementation can be quite tedious. Since no three points can form a collinear line, we can draw a line to each point P from the origin O and deterministically define that point by the angle defined by the line and the x-axis (that means the vector OP and the unit normal vector i of x-axis). Once we have converted every points as these angles and sort them, we can make use of another observation: if we choose two points with corresponding angles alpha and beta, then to form a triangle that contains the origin, we need to choose those points with angles between (alpha + 180, beta + 180). Otherwise, any triangle formed using points beyond these region will not contain the origin. This means that we can use binary search to find the number of points lying in the desired region. Overall we will have a \(O(N^2 \lg{N})\) running time complexity.
Friday, December 12, 2014
Topcoder SRM 640 Div. 1 250 - ChristmasTreeDecoration
Problem Statement:
SRM 640 Div. 1 250 - ChristmasTreeDecoration
Solution:
We can employ a greedy scheme:
1. For each possible remaining edge, choose the one that connects two vertices with different colors and that does not result in a loop.
2. If it is not possible anymore to do that, the remaining edges needed to form the tree will all need to connect vertices of the same color.
SRM 640 Div. 1 250 - ChristmasTreeDecoration
Solution:
We can employ a greedy scheme:
1. For each possible remaining edge, choose the one that connects two vertices with different colors and that does not result in a loop.
2. If it is not possible anymore to do that, the remaining edges needed to form the tree will all need to connect vertices of the same color.
Topcoder SRM 633 Div. 1 600 - DoubleTree
Problem Statement:
SRM 633 Div. 1 600 - DoubleTree
Solution:
It is interesting to know that this problem is actually a Maximum Flow problem. When we fix a node as the root of both of the trees, we reduce the problem to maximum weight connected sub graph problem. Let's say we have chosen a root R. R will be inside the subset S in question. We run a depth first search on both tree starting at R, forming two trees A and B. Then we build a graph G such that:
1. for each node v, we connect v with its parent u in A and B each with an edge with infinite capacity. This means that if we pick node v, then we have to also pick u, so we ensure that v and R is connected.
2. introduce two new nodes, source s and sink t. For each v in G, if v has a positive score m, add an edge between s to v with capacity m. Otherwise, m is negative, then we connect v with t using an edge with capacity -m.
SRM 633 Div. 1 600 - DoubleTree
Solution:
It is interesting to know that this problem is actually a Maximum Flow problem. When we fix a node as the root of both of the trees, we reduce the problem to maximum weight connected sub graph problem. Let's say we have chosen a root R. R will be inside the subset S in question. We run a depth first search on both tree starting at R, forming two trees A and B. Then we build a graph G such that:
1. for each node v, we connect v with its parent u in A and B each with an edge with infinite capacity. This means that if we pick node v, then we have to also pick u, so we ensure that v and R is connected.
2. introduce two new nodes, source s and sink t. For each v in G, if v has a positive score m, add an edge between s to v with capacity m. Otherwise, m is negative, then we connect v with t using an edge with capacity -m.
Sunday, November 30, 2014
TopCoder SRM 639
SRM 639 Div. 1
First Problem:
250 - AliceGame
Solution:
The problem is very mathematical in a sense. First observation: there will always be one winner and one loser in a round. So if we sum up the scores obtained by the two players, we will get the total number of scores accumulated from round 0 to round N consecutively. Hence if the sum of the players score is in the form of \( 2 \sum_{i=0}^{N} {i} - N = N^2 \), for some integer N, then the players have played N rounds, otherwise it is impossible to obtain those scores.
First Problem:
250 - AliceGame
Solution:
The problem is very mathematical in a sense. First observation: there will always be one winner and one loser in a round. So if we sum up the scores obtained by the two players, we will get the total number of scores accumulated from round 0 to round N consecutively. Hence if the sum of the players score is in the form of \( 2 \sum_{i=0}^{N} {i} - N = N^2 \), for some integer N, then the players have played N rounds, otherwise it is impossible to obtain those scores.
Saturday, November 15, 2014
Topcoder SRM 638 Div. 1 Hard - CandleTimer
Follow up to this post
Problem Statement:
Topcoder SRM 638 Div. 1 HARD - CandleTimer
Solution:
Just solved this problem, and I must say that this problem is very challenging (at least for me) in a sense that there are quite a lot of stuff going on. The way the candles are burnt rings some bells to the intuition behind Dijkstra algorithm, and indeed the way to solve this problem is through some modification of Dijkstra.
Problem Statement:
Topcoder SRM 638 Div. 1 HARD - CandleTimer
Solution:
Just solved this problem, and I must say that this problem is very challenging (at least for me) in a sense that there are quite a lot of stuff going on. The way the candles are burnt rings some bells to the intuition behind Dijkstra algorithm, and indeed the way to solve this problem is through some modification of Dijkstra.
Monday, November 3, 2014
Topcoder: SRM 638 (Div. 1)
First Problem
Div 1. (300) - ShadowSculpture
Summary:
You are given a 3D array describing a 3D figure. Then a shadow is casted from the 3D figure to XY, YZ, and ZX planes (or in other words, XY, YZ and ZX contains the projection of the 3D object). Given the projections, output whether there is a possible 3D object satisfying the required projections, given that the object must be 6-connected (which means if two cubes are a part of the 3D object, then they must share a face).
Div 1. (300) - ShadowSculpture
Summary:
You are given a 3D array describing a 3D figure. Then a shadow is casted from the 3D figure to XY, YZ, and ZX planes (or in other words, XY, YZ and ZX contains the projection of the 3D object). Given the projections, output whether there is a possible 3D object satisfying the required projections, given that the object must be 6-connected (which means if two cubes are a part of the 3D object, then they must share a face).
Friday, October 24, 2014
TopCoder SRM 637
Division 1
Problem 250:
SRM 637 Div1 (250) - GreaterGame
Solution:
To find the expectation, first sort the cards on each hand. Then for each of the known Sothe's card, we can determine whether we want to top the card with the lowest possible card on our hand, or just lose with the lowest possible card. Each of the card that we topped will contribute to the expectation by 1, and those we lose contribute 0. Then we will end up with the cards that Sothe did not reveal, and the cards that we do not used yet. For each card on our hand, we find the probability of our card winning given the knowledge of Sothe's remaining cards. Each of the probability contributes to our expectation. Hence we just sum up all the probabilities with the number of the cards that we won earlier on.
Problem 250:
SRM 637 Div1 (250) - GreaterGame
Solution:
To find the expectation, first sort the cards on each hand. Then for each of the known Sothe's card, we can determine whether we want to top the card with the lowest possible card on our hand, or just lose with the lowest possible card. Each of the card that we topped will contribute to the expectation by 1, and those we lose contribute 0. Then we will end up with the cards that Sothe did not reveal, and the cards that we do not used yet. For each card on our hand, we find the probability of our card winning given the knowledge of Sothe's remaining cards. Each of the probability contributes to our expectation. Hence we just sum up all the probabilities with the number of the cards that we won earlier on.
Wednesday, October 15, 2014
a bit of topcoder: SRM 636 Div. 1
Problem Statement:
TopCoder SRM 636 Div. 1 500
Summary:
Given an array called board of dimension MxN ( \(M, N\leq 20\) ). Each cell board[i][j] contains either '#' or '.', indicating 'full' or 'empty' respectively. We are to choose r cells out of the empty cells. Between 2 cells, we define distance of board[i][j] and board[m][n] is \(\sqrt{(i-m)^2+(j-n)^2}\). For each board[i][j], an edge is drawn between that cell and another cell with the smallest distance. If there is a tie, draw the edge to the one with lower row index, and if there is still a tie, choose the one with lower column index. The resulting undirected graphs have a number of connected components. Find the expected number of connected components.
One of the most important observation that makes solving this problem possible: If two cells have double edges (each of them have edge pointing to one another), then they contribute to one connected component.
We need some background on probability though, especially on Expectation and Indicator Function:
1. X is the random variable representing the number of connected components in a graph. Equivalently, from our observation, that X is equal to the number of pairs of double edges.
2. \(E(X) = \sum {xP(X=x)} \)
3. \(I\) is indicator function, \(I(A) = 1\) if event A occurs, 0 if it does not. If we define a random variable \(X_A = I(A)\), then \(E(X_A) = P(A)\).
4. Let \(A_{(c,d)}\) be an event that there is a double edge between two cells c and d. Furthermore, we define \(X_{(c,d)} = I(A_{(c,d)}) \). We have \(X = \sum_{c,d \in \text{board cells}, c\neq d} X_{(c,d)} \).
5. Hence E(X) = E( \( \sum_{c,d \in \text{board cells}, c\neq d} X_{(c,d)} \) ), which is equal to the sum of all probabilities of each \(A_{(c,d)}\).
Here is the implementation:
TopCoder SRM 636 Div. 1 500
Summary:
Given an array called board of dimension MxN ( \(M, N\leq 20\) ). Each cell board[i][j] contains either '#' or '.', indicating 'full' or 'empty' respectively. We are to choose r cells out of the empty cells. Between 2 cells, we define distance of board[i][j] and board[m][n] is \(\sqrt{(i-m)^2+(j-n)^2}\). For each board[i][j], an edge is drawn between that cell and another cell with the smallest distance. If there is a tie, draw the edge to the one with lower row index, and if there is still a tie, choose the one with lower column index. The resulting undirected graphs have a number of connected components. Find the expected number of connected components.
One of the most important observation that makes solving this problem possible: If two cells have double edges (each of them have edge pointing to one another), then they contribute to one connected component.
We need some background on probability though, especially on Expectation and Indicator Function:
1. X is the random variable representing the number of connected components in a graph. Equivalently, from our observation, that X is equal to the number of pairs of double edges.
2. \(E(X) = \sum {xP(X=x)} \)
3. \(I\) is indicator function, \(I(A) = 1\) if event A occurs, 0 if it does not. If we define a random variable \(X_A = I(A)\), then \(E(X_A) = P(A)\).
4. Let \(A_{(c,d)}\) be an event that there is a double edge between two cells c and d. Furthermore, we define \(X_{(c,d)} = I(A_{(c,d)}) \). We have \(X = \sum_{c,d \in \text{board cells}, c\neq d} X_{(c,d)} \).
5. Hence E(X) = E( \( \sum_{c,d \in \text{board cells}, c\neq d} X_{(c,d)} \) ), which is equal to the sum of all probabilities of each \(A_{(c,d)}\).
Here is the implementation:
/* X = number of double edges E[X] = sum xP(X=x) P(i-j has double edge) Given P(X=1), can I get P(X=k) k>1? Seems terribly inefficient. Let's use Indicator function instead Let I(edge i-j) = 1 if i-j has double edge if we sort all edges into one sequence X(i) = I(i-th edge)
E[X] = E[X(i)] = sum {i=1 to |E|} E(X(i)) And E(X(i)) = P(ith-edge) since expectation of an indicator is its prability Now the problem reduces to finding probability of each edges from happening. Complexity: O(N^2) to perform check for each edge. total O(N^3) */ class ClosestRabbit{ public: vector<string> board; double ncr[403][403]; int M, N, R; int emp; int dist(int ia, int ja, int ib, int jb){ return (ia-ib)*(ia-ib) + (ja-jb)*(ja-jb); } int countAvailable(int ia, int ja, int ib, int jb){ int ret = 0; int mindist = dist(ia, ja, ib, jb); for(int i=0;i<M;++i){ for(int j=0;j<N;++j){ if(i == ia && j == ja) continue; if(i == ib && j == jb) continue; if(board[i][j] == '#' || mindist > dist(i,j,ia,ja) || mindist > dist(i,j,ib,jb)){ continue; } if(mindist == dist(i,j,ia,ja)){ if(i < ib) continue; if(i == ib && j < jb) continue; } if(mindist == dist(i,j,ib,jb)){ if(i < ia) continue; if(i == ia && j < ja) continue; } ++ret; } } return ret; } double prob(int ia, int ja, int ib, int jb){ if(board[ia][ja] == '#' || board[ib][jb] == '#') return 0; int avail = countAvailable(ia,ja,ib,jb); return ncr[avail][R-2]; } double getExpected(vector<string> board, int r){ this->board = board; M = board.size(); N = board[0].size(); R = r; emp = 0; for(int i=0;i<M;++i){ for(int j=0;j<N;++j){ if(board[i][j] == '.') ++emp; } } for(int i=0;i<=emp;++i){ ncr[i][0] = 1; if(i>0) ncr[i-1][i] = 0; } for(int i=1;i<=emp;++i){ for(int j=i;j>=1;--j){ ncr[i][j] = ncr[i-1][j] + ncr[i-1][j-1]; } } double ans = 0; for(int ia=0;ia<M;++ia){ for(int ja=0;ja<N;++ja){ for(int ib=0;ib<M;++ib){ for(int jb=0;jb<N;++jb){ if(ib == ia && jb == ja) continue; ans += prob(ia, ja, ib, jb); } } } } return ans/ncr[emp][r]/2.0; } };
Thursday, September 18, 2014
a bit of topcoder: SRM 633 Div. 1
(My first Div 1, OMG damn difficult)
First Problem (250 pts)
Problem Statement
633 Div. 1 250 - PeriodicJumping
Summary:
Can u build a polygon with a periodic sequence of segments \(a_1,a_2,a_3,\ldots,a_t\) by using the segments sequentially? If so, what is the minimum segments needed?
Solution:
Firstly it is always possible to build a polygon using these segments. Secondly, to solve this problem we need to know the "Polygon Inequality", which is a generalization of Triangle Inequality:
Triangle Ineq: \(a\leq b\leq c\) are the sides of a triangle if and only if \(c \leq a+b\)
Extended to polygons (by Induction I suppose)
Polygon Ineq: \(a_1,a_2,\ldots, a_n\) are sides of polygons iff the max side is \(\leq\) the sum of the rest of the sides.
So to build the polygon, we have to iterate through the segments one by one until we manage to fulfill the inequality. The idea sounds simple but whenever it is computational geometry, there are corner cases that must be taken care of..
First Problem (250 pts)
Problem Statement
633 Div. 1 250 - PeriodicJumping
Summary:
Can u build a polygon with a periodic sequence of segments \(a_1,a_2,a_3,\ldots,a_t\) by using the segments sequentially? If so, what is the minimum segments needed?
Solution:
Firstly it is always possible to build a polygon using these segments. Secondly, to solve this problem we need to know the "Polygon Inequality", which is a generalization of Triangle Inequality:
Triangle Ineq: \(a\leq b\leq c\) are the sides of a triangle if and only if \(c \leq a+b\)
Extended to polygons (by Induction I suppose)
Polygon Ineq: \(a_1,a_2,\ldots, a_n\) are sides of polygons iff the max side is \(\leq\) the sum of the rest of the sides.
So to build the polygon, we have to iterate through the segments one by one until we manage to fulfill the inequality. The idea sounds simple but whenever it is computational geometry, there are corner cases that must be taken care of..
Saturday, September 6, 2014
a bit of topcoder: SRM 632 Div 2 Medium
Problem Statement:
Given d[i] array of trailing zeroes in in the representation of a[i] (where a[i] can be any satisfying integer), determine whether a consecutive sequence a[i], a[i+1], ..., a[j] can form a geometric sequence.
Solution:
I think this is a good problem :D The important observation is that a[i], ..., a[j] can form a geometric sequence if and only if d[i], ..., d[j] forms an arithmetic sequence. This is because for a[i] to have a change in d[i] to d[i+1], it has to be multiplied with a constant \(r = r_0(2^k)\) where \(k\) is the difference between d[i] and d[i+1]. Furthermore, \(r_0\) must be odd, otherwise if we factor out \(2\) from \(r_0\) it will contribute to \(k\) leading to a contradiction. Now if d[i], ..., d[j] does not form an arithmetic sequence, there is some point where the \(k\) in \(r\) changes value, which contradicts the fact that \(r\) is constant. Finally, setting \(r_0=1\) or any other odd valued integer will give us the desired geometric sequence.
Given d[i] array of trailing zeroes in in the representation of a[i] (where a[i] can be any satisfying integer), determine whether a consecutive sequence a[i], a[i+1], ..., a[j] can form a geometric sequence.
Solution:
I think this is a good problem :D The important observation is that a[i], ..., a[j] can form a geometric sequence if and only if d[i], ..., d[j] forms an arithmetic sequence. This is because for a[i] to have a change in d[i] to d[i+1], it has to be multiplied with a constant \(r = r_0(2^k)\) where \(k\) is the difference between d[i] and d[i+1]. Furthermore, \(r_0\) must be odd, otherwise if we factor out \(2\) from \(r_0\) it will contribute to \(k\) leading to a contradiction. Now if d[i], ..., d[j] does not form an arithmetic sequence, there is some point where the \(k\) in \(r\) changes value, which contradicts the fact that \(r\) is constant. Finally, setting \(r_0=1\) or any other odd valued integer will give us the desired geometric sequence.
Sunday, August 31, 2014
a bit of topcoder: SRM 631
TOPCODER SRM 631
Div 2 - 500
Problem Statement:
On a one dimensional array, at position[i] there are count[i] cats. In a unit time, each cat can stay on its position, move 1 block to the left, or move 1 block to the right. Given time \(t\), check whether it is possible for all cats to occupy different cells at time \(t\).
Solution:
Firstly sort the pairs (position[i], count[i]) and starting from lowest position[i]:
The cats can occupy any position in \([ \text{position[i] - time}, \text{position[i] + time} ] \).
We greedily place the cats to the left-most orientation so as to leave more spaces for the remaining cats.
If this is not possible, return "Impossible".
/* Did not manage to think about sorting during the match... :( haha oh well! */
Div 2 - 950
Problem Statement:
Given a number N, find the number of ways to represent N in "binary" representation such that each "bit" is made up of 0, 1, or 2.
Solution:
First, represent N in terms of its normal binary representation in an array/vector<int> called rep. Then establish the following recursion:
The function count counts the number of ways of equivalent representation of rep using the first n+1 bits. It returns early when rep[n] is bigger than 3, since any equivalent representation of such will have at least one of its bits to be more than 2. Furthermore, we use a map to cache the result from calculations, which is important to bring down the exponential time of this algorithm to a polynomial one. :D
/* of course I did not think about this during the contest either but pretty happy I can solve it now :D */
Div 1 - 250
Problem Statement:
Given an NxN board with 'B' and 'W', you can either paint a whole row 'B' or 'W' in each turn. Find the minimum number of turns such that there is no more than \(N/2\) consecutive cells with the same color in every column.
This problem is all about bruteforce, but it needs one important observation: You only need at most 2 painting to eliminate consecutive cells with the same colors in any column into parts of length less than \(N/2\). As such, the problem can be "easily" (yeah in a sense that you don't have to think too much, just implement) solved by trying to paint the board once ('W' or 'B') or twice (one 'W' one 'B'). Don't forget to check the case where we don't even need to paint anything though.
Div 2 - 500
Problem Statement:
On a one dimensional array, at position[i] there are count[i] cats. In a unit time, each cat can stay on its position, move 1 block to the left, or move 1 block to the right. Given time \(t\), check whether it is possible for all cats to occupy different cells at time \(t\).
Solution:
Firstly sort the pairs (position[i], count[i]) and starting from lowest position[i]:
The cats can occupy any position in \([ \text{position[i] - time}, \text{position[i] + time} ] \).
We greedily place the cats to the left-most orientation so as to leave more spaces for the remaining cats.
If this is not possible, return "Impossible".
/* Did not manage to think about sorting during the match... :( haha oh well! */
Div 2 - 950
Problem Statement:
Given a number N, find the number of ways to represent N in "binary" representation such that each "bit" is made up of 0, 1, or 2.
Solution:
First, represent N in terms of its normal binary representation in an array/vector<int> called rep. Then establish the following recursion:
typedef long long Long; map<vector<int>, Long> dp; Long count(vector<int> rep, int n){ rep.resize(n+1); vector<int> cur = rep; if(dp.find(cur) != dp.end()) { // printf("called\n"); return dp[cur]; } if(n == 0){ if(rep[0] <= 2) return 1; else return 0; } if(rep[n] > 3) return 0; Long ret = 0; while(rep[n]>=0){ if(rep[n] <= 2){ ret += count(rep, n-1); } rep[n-1] += 2; --rep[n]; } dp[cur] = ret; return dp[cur]; }
The function count counts the number of ways of equivalent representation of rep using the first n+1 bits. It returns early when rep[n] is bigger than 3, since any equivalent representation of such will have at least one of its bits to be more than 2. Furthermore, we use a map to cache the result from calculations, which is important to bring down the exponential time of this algorithm to a polynomial one. :D
/* of course I did not think about this during the contest either but pretty happy I can solve it now :D */
Div 1 - 250
Problem Statement:
Given an NxN board with 'B' and 'W', you can either paint a whole row 'B' or 'W' in each turn. Find the minimum number of turns such that there is no more than \(N/2\) consecutive cells with the same color in every column.
This problem is all about bruteforce, but it needs one important observation: You only need at most 2 painting to eliminate consecutive cells with the same colors in any column into parts of length less than \(N/2\). As such, the problem can be "easily" (yeah in a sense that you don't have to think too much, just implement) solved by trying to paint the board once ('W' or 'B') or twice (one 'W' one 'B'). Don't forget to check the case where we don't even need to paint anything though.
Wednesday, August 13, 2014
a bit of srm: Minimizing Absolute Values - SRM 629 Div II 550
Problem Statement:
Given \( M = \sum^{n}_{i=1} |a_ix - b_i| \), find \(x\) that minimizes \(M\).
The solution to the problem hinges on the following lemma:
Lemma 1:
If \(x\) minimizes M, then \(x \in \{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \} \).
Proof:
The proof comes from an observation that the curve for M is made up of segments of straight lines with sharp turns on each \(x \in \{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \} \). Why? Let's assume without losing generality that \(\{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \}\) is sorted in increasing order. Each \( (\frac{b_k}{a_k}, \frac{b_{k+1}}{a_{k+1}}) \) forms a segment on the real number line, and \(x\) can only be one of the segment at any point of time. In any segment, each \(a_ix - b_i\) will be either positive or negative and the parity will not change as long as \(x\) stays in the same segment. This means that in each segment, \(M = Ax - B\), which is a straight line. From here it is clear that if \(x\) minimizes M, it cannot be in the middle of the line segment, since moving along the downward slope will gives us even smaller M. Hence \(x\) must be on the segment ends, and hence leads to Lemma 1.
From here, we can perform a \(O(N^2)\) complete search to find \(x\).
Friday, June 20, 2014
a bit of topcoder: SRM 625 Div II 500
Problem Statement:
Incrementing Sequence
Summary:
Given a set of numbers \(S\) of size \(N\), and an integer \(k\), determine whether we can transform \(S\) to set containing integer \(1\) to \(N\) by adding multiples of \(k\) to element of \(S\).
I've just figured out how to solve this problem (and it is really just too late) but well, practice makes perfect :D
The idea is that if we sort \(S\), we need to check the following conditions hold:
1. The last element of \(S\) (which is the maximum element) must not exceed \(N\)
2. If \(S\) can be transformed into \({1,2,\ldots,N}\), that means there is an element \(a_i\) in \(N\) such that addition of \(k\) to \(a_i\) equals to \(N\). In other words, \(a_i \equiv N \bmod{k}\).
A greedy algorithm which picks the largest element in \(S\) which satisfies the above conditions allows us to carry out such transformation:
This algorithm takes roughly \(O(N^2)\) depending on the data structure used.
Incrementing Sequence
Summary:
Given a set of numbers \(S\) of size \(N\), and an integer \(k\), determine whether we can transform \(S\) to set containing integer \(1\) to \(N\) by adding multiples of \(k\) to element of \(S\).
I've just figured out how to solve this problem (and it is really just too late) but well, practice makes perfect :D
The idea is that if we sort \(S\), we need to check the following conditions hold:
1. The last element of \(S\) (which is the maximum element) must not exceed \(N\)
2. If \(S\) can be transformed into \({1,2,\ldots,N}\), that means there is an element \(a_i\) in \(N\) such that addition of \(k\) to \(a_i\) equals to \(N\). In other words, \(a_i \equiv N \bmod{k}\).
A greedy algorithm which picks the largest element in \(S\) which satisfies the above conditions allows us to carry out such transformation:
string canItBeDone(int k, vector<int> A) {
sort(A.begin(),A.end());
while(!A.empty()){
int N=A.size();
if(A[N-1]>N)return "IMPOSSIBLE";
int j=N-1;
while((A[j]-N)%k!=0) {
--j;
if (j==-1) return "IMPOSSIBLE";
}
A.erase(A.begin()+j);
}
return "POSSIBLE";
}
This algorithm takes roughly \(O(N^2)\) depending on the data structure used.
Subscribe to:
Posts (Atom)