Member Single Round Match 468
Tuesday, April 20th, 2010
Match summary
This match was a debut for keshav_57 as a writer. All problems were devoted to a king of some abstract kingdom.
In Div-I, the relatively straightforward 250-pointer focused on implementation and quite approachable DP 500-pointer were followed with a pretty unusual 1000-pointer. Usually we check upper bounds in constraints carefully to make sure that our solution has an appropriate time/space complexity, but in this 1000-pointer it was even more important to check lower bounds. The match was successfull for Japanese coders - 3 out of Top-5 positions in Div-I were occupied by coders from this country. No wonder, both Top-2 positions were taken by people from Japan as well. The match victory goes to wata, the author of the fastest correct solution for 1000-pointer. The second place is taken by lyrically and the third position is occupied by Russia's SergeiRogulenko.
In Div-II the problems were quite hard, with only 90 solutions on 500-pointer (which was the same as 250-pointer in Div-I) and only 1 correct solution on 1000-pointer. The only one coder to solve the 1000-pointer, rgt0820 won the match (even despite the failed 500-pointer). The 2nd and 3rd positions go to misl4av and denusu, respectively.
With K flights or less, the king wants to minimize the total time for his journey. Taking flighti instead of walking between cityi and cityi+1 spares him roadTime[i] - flightTime[i]. So, it is better for the king to take the K flights that spare him the most time, enabling him to arrive as early as possible. The king might take less than K flights if there are no K flights that spare him time (in such case, taking the road consumes less time than the flight). A C++ implementation of the idea follows:
int minTime(int N, vector<int> roadTime, vector<int> flightTime, int K) {
vector<int> sparedTime(N);
for (int i = 0; i < N; ++i)
sparedTime[i] = roadTime[i] - flightTime[i];
int result = 0;
for (int i = 0; i < N; ++i)
result += roadTime[i];
sort(sparedTime.rbegin(), sparedTime.rend()); // sort them reversed
for (int i = 0; i < K; ++i)
result -= max(sparedTime[i], 0);
return result;
}
Rizvanov_de_xXx for 230.55 points (8 mins 23 secs)
Average Score
150.97 (for 495 correct submissions)
This problem needs a careful implementation of any reasonable idea of translating the key presses into text. One approach to solve the problem is explained below.
First of all, sort the dictionary words.
Make a table of characters, containing the digit key needed to be pressed for inputing each of the 26 alphabet characters. This table is named as toPress in the code below, constructed from part.
Construct the keys needed to be pressed for each of the dictionary words. This table is named as dictN in the code. It is constructed in two steps. First step is to construct the digits needed to be pressed (without the key '#') for each word. The second step is to add the appropriate number of '#' presses to each of the words in dictN.
Construct a map from strings to strings, mapping each word of dict into its corresponding key presses in dictN. This map is called dictR. dictR resembles the string of keys needed to be pressed for inputing each dictionary word, and an empty string for inputing an empty string (in case of inputing two consecutive spaces).
All what remains is to loop over the string of input keys pressed, keystr, consider each '*' as five occurrences of '#'-symbols, and accumulate these input characters, and use that accumulated string when encountering a press of '0', corresponding to a space letter. In the code, constructing the string text is done from accumulating symbol by symbol into the string acc, and using dictR once a '0' is encountered.
The code for this idea follows:
string message(vector<string> part, vector <string> dict, vector<string> keystr) {
sort(dict.begin(), dict.end());
// Construct toPress
char toPress[26];
for (int i = 0; i < part.size(); ++i)
for (int j = 0; j < part[i].size(); ++j)
toPress[part[i][j]-'a'] = '1' + i;
// Construct dictN
vector<string> dictN(dict.size());
for (int i = 0; i < dict.size(); ++i)
for (int j = 0; j < dict[i].size(); ++j)
dictN[i] += toPress[dict[i][j]-'a'];
// Add the needed #'s
for (int i = 0; i < dictN.size(); ++i)
for (int j = i+1; j < dictN.size(); ++j)
if (dictN[i] == dictN[j]) dictN[j] += "#";
// Construct dictR
map<string, string> dictR;
for (int i = 0; i < dictN.size(); ++i)
dictR[dictN[i]] = dict[i];
// Construct the resulting text
string text, acc;
for (int i = 0; i < keystr.size(); ++i)
for (int j = 0; j < keystr[i].size(); ++j)
if (keystr[i][j] == '0') {
text += " " + dictR[acc];
acc = "";
}
elseif (keystr[i][j] == '*') acc += "#####";
else acc += keystr[i][j];
text += " " + dictR[acc];
return text.substr(1);
}
This is a dynamic programming problem. The small restriction on the maximum number of gifts (16) suggests that we can include all possible subsets of gifts into the state. Therefore let's define the function minTime that takes two input parameters:
giftsTaken -- this is a bitmask that defines which gifts we have gathered. If the i-th bit is set, it means the i-th gift was taken, otherwise it is still available for collecting. (We assume that gifts are numbered from 0 to N-1 in arbitrary order, where N is the total number of gifts.)
lastGift -- this is the last gift that has been collected. Obviously, the lastGift-th bit in giftsTaken must be set.
The return of minTime(giftsTaken, lastGift) is the minimum time required to collect exactly the gifts from giftsTaken in such way that the last taken gift is lastGift. If it is not possible to collect the gifts from giftsTaken (because walls block the path to some of them), we can return some large integer (starting from T + 1) to indicate this.
In order to calculate minTime, it is useful to known the shortest distances between each pair of important places on the grid, that is king's position, queen's position and gifts' locations. The meaning of "distance" is the smallest amount of king's moves required to move from one place to another, i.e. we ignore that moves can take different time (depending on the number of gifts that king is carrying) and assume that each move takes just 1 second. Similarly to minTime, we can use some large integer to indicate that there's no path between some pair of important places. Let's denote the distance as follows:
kingDist(i) -- the distance between king's position and the i-th gift.
queenDist(i) -- the distance between queen's position and the i-th gift.
dist(i, j) -- the distance between i-th and j-th gifts.
As we consider that each move requires the same time of 1 second, breadth first search can be used to calculate these distances. We can start a separate breadth first search from each important place and obtain the distances from this place to all other places. The time required is O(grid_width * grid_height * num_important_places), so this will work very fast.
After having all these distances calculated, let's return to our main function minTime. The basic case for this function is when exactly one bit (i.e. the lastGift-th bit) is set in giftsTaken. In this case the king has only one option -- to go from his initial position directly to the lastGift-th bit. Therefore, in this case minTime(giftsTaken, lastGift) = kingDist(lastGift).
Let's proceed to general case, when the number of set bits is at least 2. Let a0, ..., aK-1 be the numbers of set bits in giftsTaken. Before collecting the lastGift-th gift, the king must have collected all gifts from giftsTaken' = giftsTaken ^ 2lastGift (note that mask ^ 2i unsets the i-th bit in mask if it was initially set). There could be many ways for the king to collect the gifts from giftsTaken'. However, once we fix lastGift' -- the last gift collected from those gifts from giftsTaken', it only makes sense to collect the gifts in the fastest possible way and this way takes exactly minTime(giftsTaken', lastGift') seconds. We're now close to getting the working formula for minTime. There are two more things left to note. First thing -- in order to move from lastGift' to lastGift, the king needs to spent time equal to K * dist(lastGift', lastGift) (as the king needs to carry K - 1 gifts at this point), therefore the total time spent will be minTime(giftsTaken', lastGift') + K * dist(lastGift', lastGift). Second thing - each value of ai ≠ lastGift can serve as a possible value for lastGift' and among possible values we need to choose such that the total time spent is minimum possible. Overall, we get the following formula for minTime:
minTime(giftsTaken, lastGift) = min{ai, 0 ≤ i < K, ai ≠ lastGift | minTime(giftsTaken ^ 2lastGift, ai) + K * dist(ai, lastGift)}
There are about 2N * N states and the calculation for each state takes O(N) operations, so the overall complexity is O(2N * N2). This is acceptable for N ≤ 16.
Once the minTime is calculated for all states, we're ready to get the final answer. For each state (giftsTaken, lastGift), the time required to collect all gifts from giftsTaken with last gift being lastGift and then to reach the queen's cell is totalTime(giftsTaken, lastGift) = minTime(giftsTaken, lastGift) + (K + 1) * queenDist(lastGift), where K is the number of set bits in giftsTaken. In order to find the maximum number of gifts that we can collect and then reach the queen within T time units, we check all states (giftsTaken, lastGift) such that totalTime(giftsTaken, lastGift) ≤ T and choose the one with the maximum number of set bits among them. If there are no such states at all, it means that we can't collect a positive number of gifts, so the answer is 0.
The only one correct solution on this problem by rgt0820 uses a very similar approach. There are two relatively major differences: Dijkstra's algorithm is used instead of Breadth First Search (in this case it's much slower, but still works within time bounds) and DP values are calculated in another way (given giftsTaken and lastGift, we can check all possible values of the next gift to be collected and update the value for minTime(giftsTaken ^ 2nextGift, nextGift) accordingly).
The problem is solvable by a dynamic programming approach. It relies on the idea that the least time to reach from cityi to cityN is computable using a recurrence with three parameters: i, number of allowed takeoffs left (k), and a boolean flag indicating whether the king is already on a flight passing cityi or not (flying). The recurrence is correct because it assumes that the king is going to take off at any city using one takeoff, going for any number of consecutive flights to any city j, where j > i.
minTime(i, k, flying):=
infinity for k < 0
0 for i = N
min(flightTime[i] + minTime(i+1, k, true),
roadTime[i] + minTime(i+1, k, false)) if flying
min(roadTime[i] + minTime(i+1, k, false),
flightTime[i] + minTime(i+1, k-1, true)) if not flying
The size of the DP table is in the order of N*K*2, which is much bigger than the 64MB memory limit. However, the calculation of cityi depends only on cityi+1. Thus, instead of storing the whole table, the dimension representing cities can be discarded from being stored while the whole table is being computed. The fastest solution for jbernadas is a clear way of implementing the solution.
Although most of the solutions were based on dynamic programming, a greedy approach works for this problem as well. To get the maximum contiguous sum in a sequence of integers is a problem known as the maximum subarray problem. The limits allow finding that maximum sum for K times. However, getting the best flight for K times, one by one, does not allow the king to reach the queen in the earliest time. The reason is that a maximal flight with a high sparedTime (check the RoadAndFlightEasy writeup for the definition of sparedTime) might better to be split into two flights rather than be taken as a single long one. The crux point of this solution is to notice that a pair of flights can be represented as either:
A pair of disjoint flights.
One flight, extending maximally, and another subarray extending maximally with maximum sum, representing a gap inside that long flight.
This gap insertion can be done as much as required to get any number of flights represented as a flight with maximal gaps inside. To search for gaps in sparedTime, sparedTime is negated in the interval where a maximal flight is chosen. An implementation for this approach follows:
longlong minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod,
int flightFirst, int flightProd, int flightAdd, int flightMod, int K) {
vector<longlong> roadTime(N), flightTime(N), sparedTime(N);
roadTime[0] = roadFirst % roadMod;
flightTime[0] = flightFirst % flightMod;
for (int i = 1; i < N; ++i) {
roadTime[i] = (roadTime[i-1]*roadProd + roadAdd) % roadMod;
flightTime[i] = (flightTime[i-1]*flightProd + flightAdd) % flightMod;
}
longlong result = 0;
for (int i = 0; i < N; ++i) {
sparedTime[i] = roadTime[i] - flightTime[i];
result += roadTime[i];
}
for (int c = 0; c < K; ++c) {
longlong bestFlight = 0, currentSum = 0;
int start = -1, end = -1, currentStart = 0;
for (int i = 0; i < N; i++) {
currentSum += sparedTime[i];
if (currentSum <= 0) {
currentSum = 0;
currentStart = i+1;
} elseif (currentSum > bestFlight) {
bestFlight = currentSum;
start = currentStart;
end = i;
}
}
if (bestFlight <= 0) break;
for (int i = start; i <= end; i++) {
result -= sparedTime[i];
sparedTime[i] = -sparedTime[i];
}
}
return result;
}
For notational convenience, we use '#' to represent the term 'number of'. For example, #vertices should be read as 'number of vertices'. Also, |S| will denote the size of (cardinality) the set S.
For the rest of the solution we refer to stations as vertices and to escalators (and super-escalators) as edges. The stations on which guards are placed will be referred to as selected vertices. The problem asks us to find the maximum number of vertices that can be selected such that there is no edge both of whose end vertices are selected. Well, that is just |maximum independent set|.
Finding the size of a maximum independent set (MIS) is NP Hard. However, the graph given in the problem is not a general graph. The vertices are divided into N sets numbered 1 to N, and we have edges only between adjacent sets (where adjacency is defined in a cyclic way, i.e. 1 is adjacent to N). To solve the problem we will be using the structure of the graph (obviously!), and a pretty well known property of bipartite graphs: |maximum independent set| in a bipartite graph = #vertices - |maximum matching|. Also, we will assume that you know how to find maximum matching in a bipartite graph. If you do not, have a look at this tutorial on maxflow, and proceed to matching on this page.
The solution is pretty simply to see when N is even. You have a bipartite graph given to you on a platter. The vertices on the 'left' are the vertices belonging to the even-numbered sets (or floors), and the vertices on the 'right' are the vertices belonging to the odd-numbered sets. Since we have edges between adjacent sets only and since 1 and N are of different parity all edges will have one end point on the left and the other end point on the right. So, return |V| - |maximum_matching|.
For odd N, the given graph is not bipartite. But then, lets see if we can make it bipartite! Now, we will make use of the weird constraint "N will be between 10 and 50, inclusive". N ≥ 10 (That's weird!). We have at most 100 vertices which are divided into N sets. N ≥ 10 implies that there is atleast one set which has at most 10 vertices. To make the rest of the explaination easier to state, we name the set which has ≤ 10 vertices as the Nth set, and we rename the sets in a way to maintain that there are edges between sets if there numbers differ by 1, or if the sets are numbered 1 and N. We can then brute force on which vertices of set N belong to the maximum independent set and which do not. If a particular vertex belongs to the maximum independent set, then none of its neighbours can belong to the maximum independent set and hence we delete the vertex along with its neighbours, else we delete only that particular vertex (since we know it is not a part of the maximum independent set). Clearly, every vertex in the Nth set gets deleted and hence the remainder of the graph is bipartite. We can find the |maximum independent set| for this bipartite graph and add to that the #vertices we chose from the Nth set as a part of the maximum independent set.
For even N we simply so matching on a bipartite graph once. For odd N, we do matching on a bipartite graph 2|smallest_set| times. Hence, the complexity of the solution is O(VE) for even N and O(2|smallest_set|VE) for odd N, which is only about 210*100*400 in the worst case, i.e. 4*107.
Java code for the above algorithm is given below:-
// Assume that we have a function Matching.maxMatch(int numbOfVert, boolean edge[][], int[][] adjList, int source, int sink)
// which returns the size of the maximum matching
public class MallSecurity {
int v; int n;
int[][] list;
int[] cumulative;
boolean[][] edge;
private void removeEdge(int index)
{
if (index == 0 || index == v-1) return;
for (int i = 0; i < list[index].length; i++)
edge[index][list[index][i]] = edge[list[index][i]][index] = false;
}
// Deletes the edges and vertices as per the vertices which are part of maximum independent set due to brute force
privateint modifyEdge(int bit, int size)
{
int ret = 0; boolean[] mark = newboolean[v];
for (int i = 0; i < size; i++)
{
if (!mark[cumulative[n-1]+i])
{
mark[cumulative[n-1]+i] = true; ret++;
removeEdge(cumulative[n-1]+i);
}
if (((1<<i)&bit) != 0)
for (int j = 0; j < list[cumulative[n-1]+i].length; j++)
if (!mark[list[cumulative[n-1]+i][j]])
{
mark[list[cumulative[n-1]+i][j]] = true;
if (list[cumulative[n-1]+i][j] != 0 && list[cumulative[n-1]+i][j] != v-1) ret++;
removeEdge(list[cumulative[n-1]+i][j]);
}
} return ret;
}
publicint maxGuards(int N, String[] escDescription)
{
// Initialization
v = 0; n = N;
int[] floor = newint[N]; cumulative = newint[N+1];
edge = newboolean[500][500];
// Concatenate the elements of escDescription
String req = "";
for (int i = 0; i < escDescription.length; i++) req += escDescription[i];
int lreq = req.length();
// Get the number of stations on each floor
String[] escBreak = req.split(",");
int[][] numb = newint[escBreak.length][3];
for (int i = 0; i < escBreak.length; i++)
{
String[] current = escBreak[i].split(" ");
// -1 makes it 0-based. Everything is 1-based in the problem.
// So in this code, the (N-1)th set will be deleted, not the Nth set (if N is odd)
for (int j = 0; j < 3; j++) numb[i][j] = Integer.parseInt(current[j])-1;
floor[numb[i][2]] = Math.max(floor[numb[i][2]], numb[i][0]+1);
floor[(numb[i][2]+1)%N] = Math.max(floor[(numb[i][2]+1)%N], numb[i][1]+1);
}
// If N is odd, rename the sets so that set N-1 has the minimum number of vertices
if (N%2==1)
{
// The edges
int least = 450; int crit = -1;
for (int i = 0; i < N; i++) if (floor[i]+1 < least) { least = floor[i]; crit = i; }
for (int i = 0; i < numb.length; i++) numb[i][2] = (numb[i][2]+N-crit-1)%N;
// The number of stations in each floor
int[] temp = newint[N];
for (int i = 0; i < N; i++) temp[(i+N-crit-1)%N] = floor[i];
for (int i = 0; i < N; i++) floor[i] = temp[i];
}
cumulative[0] = 1;
for (int i = 1; i <= N; i++) cumulative[i] = cumulative[i-1] + floor[i-1];
v = cumulative[N]+1; // Total number of vertices including source and sink
// Get the edges
for (int i = 0; i < numb.length; i++)
{
if (numb[i][2]%2==0) edge[cumulative[numb[i][2]] + numb[i][0]][cumulative[(numb[i][2]+1)%N] + numb[i][1]] = true;
else edge[cumulative[(numb[i][2]+1)%N] + numb[i][1]][cumulative[numb[i][2]] + numb[i][0]] = true;
}
// Connect to source and sink
for (int i = 0; i < N; i++)
for (int j = cumulative[i]; j < cumulative[i+1]; j++)
if (i%2==0) edge[0][j] = true;
else edge[j][v-1] = true;
// Compute the adjacency list
list = AdjList.undirected(v, edge);
// For even N
if (N%2==0)
{
return (v - 2 - Matching.maxMatch(v, edge, list, 0, v-1));
// -2 takes care of the source and the sink.
}
else
{
int size = floor[N-1];
int bestAns = 0;
boolean[][] backUp = newboolean[500][500];
for (int i = 0; i < v; i++) for (int j = 0; j < list[i].length; j++)
{ backUp[i][list[i][j]] = edge[i][list[i][j]]; }
// For every possible subset of vertices of the (N-1)th floor
// Do matching and take max
for (int bit = 0; bit < (1<<size); bit++)
{
// Get original graph
for (int i = 0; i < v; i++) for (int j = 0; j < list[i].length; j++)
{ edge[i][list[i][j]] = backUp[i][list[i][j]]; }
// Delete vertices (by destroying all edges that lead to it)
int numbDeletedVertices = modifyEdge(bit, size);
// Find matching in the remaining graph
int thisAns = Matching.maxMatch(v, edge, list, 0, v-1);
// Number of remaining vertices == v - 2 - numbDeletedVertices
// Size of matching == thisAns
// Number of vertices chosen earlier == Integer.bitCount(bit)
bestAns = Math.max(bestAns, v - 2 - numbDeletedVertices - thisAns + Integer.bitCount(bit));
}
return bestAns;
}
}
}
