In this second sub-round of Round 1, the problems ranged from parse-and-simulate to standard dynamic programming.
Contestants found Round 1B easier than 1A. The winner, Gluk, was finished 26 minutes into the contest, with yuhch123 and Gennady.Korotkevic solving all 3 problems correctly just a few minutes later.
Problem A. File Fix-it Written and prepared by David Arthur.
Problem B. Picking Up Chicks Written by Igor Naverniouk. Prepared by David Arthur and Igor Naverniouk.
Problem C. Your Rank is Pure Written by Xiaomin Chen. Prepared by Ante Derek and Xiaomin Chen.
Contest analysis presented by Xiaomin Chen and Petr Mitrichev.
Solutions and other problem preparation provided by John Dethridge, Petr Mitrichev, and Cosmin Negruseri.
On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.
A directory is uniquely identified by its name and its parent directory (the directory it is directly contained in). This is usually encoded in a path, which consists of several parts each preceded by a forward slash ('/'). The final part is the name of the directory, and everything else gives the path of its parent directory. For example, consider the path:
/home/gcj/finalsThis refers to the directory with name "finals" in the directory described by "/home/gcj", which in turn refers to the directory with name "gcj" in the directory described by the path "/home". In this path, there is only one part, which means it refers to the directory with the name "home" in the root directory.
To create a directory, you can use the mkdir command. You specify a path, and then mkdir will create the directory described by that path, but only if the parent directory already exists. For example, if you wanted to create the "/home/gcj/finals" and "/home/gcj/quals" directories from scratch, you would need four commands:
mkdir /home mkdir /home/gcj mkdir /home/gcj/finals mkdir /home/gcj/quals
Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use?
The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.
The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to list it explicitly.)
The next M lines each give the path of one directory that you want to create.
Each of the paths in the input is formatted as in the problem statement above. Specifically, a path consists of one or more lower-case alpha-numeric strings (i.e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of mkdir you need.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
No path will have more than 100 characters in it.
No path will appear twice in the list of directories already on your computer, or in the list of directories you wish to create. A path may appear once in both lists however. (See example case #2 below).
If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.
The input file will be no longer than 100,000 bytes in total.
0 ≤ N ≤ 10.
1 ≤ M ≤ 10.
0 ≤ N ≤ 100.
1 ≤ M ≤ 100.
3 0 2 /home/gcj/finals /home/gcj/quals 2 1 /chicken /chicken/egg /chicken 1 3 /a /a/b /a/c /b/b
Case #1: 4 Case #2: 0 Case #3: 4
A flock of chickens are running east along a straight, narrow road. Each one is running with its own constant speed. Whenever a chick catches up to the one in front of it, it has to slow down and follow at the speed of the other chick. You are in a mobile crane behind the flock, chasing the chicks towards the barn at the end of the road. The arm of the crane allows you to pick up any chick momentarily, let the chick behind it pass underneath and place the picked up chick back down. This operation takes no time and can only be performed on a pair of chicks that are immediately next to each other, even if 3 or more chicks are in a row, one after the other.
Given the initial locations (Xi) at time 0 and natural speeds (Vi) of the chicks, as well as the location of the barn (B), what is the minimum number of swaps you need to perform with your crane in order to have at least K of the N chicks arrive at the barn no later than time T?
You may think of the chicks as points moving along a line. Even if 3 or more chicks are at the same location, next to each other, picking up one of them will only let one of the other two pass through. Any swap is instantaneous, which means that you may perform multiple swaps at the same time, but each one will count as a separate swap.
The first line of the input gives the number of test cases, C. C test cases follow. Each test case starts with 4 integers on a line -- N, K, B and T. The next line contains the N different integers Xi, in increasing order. The line after that contains the N integers Vi. All distances are in meters; all speeds are in meters per second; all times are in seconds.
For each test case, output one line containing "Case #x: S", where x is the case number (starting from 1) and S is the smallest number of required swaps, or the word "IMPOSSIBLE".
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ C ≤ 100;
1 ≤ B ≤ 1,000,000,000;
1 ≤ T ≤ 1,000;
0 ≤ Xi < B;
1 ≤ Vi ≤ 100;
All the Xi's will be distinct and in increasing order.
1 ≤ N ≤ 10;
0 ≤ K ≤ min(3, N);
1 ≤ N ≤ 50;
0 ≤ K ≤ N;
3 5 3 10 5 0 2 5 6 7 1 1 1 1 4 5 3 10 5 0 2 3 5 7 2 1 1 1 4 5 3 10 5 0 2 3 4 7 2 1 1 1 4
Case #1: 0 Case #2: 2 Case #3: IMPOSSIBLE
Pontius: You know, I like this number 127, I don't know why.
Woland: Well, that is an object so pure. You know the prime numbers.
Pontius: Surely I do. Those are the objects possessed by our ancient masters hundreds of years ago. Oh, yes, why then? 127 is indeed a prime number as I was told.
Woland: Not... only... that. 127 is the 31st prime number; then, 31 is itself a prime, it is the 11th; and 11 is the 5th; 5 is the 3rd; 3, you know, is the second; and finally 2 is the 1st.
Pontius: Heh, that is indeed... purely prime.
The game can be played on any subset S of positive integers. A number in S is considered pure with respect to S if, starting from it, you can continue taking its rank in S, and get a number that is also in S, until in finite steps you hit the number 1, which is not in S.
When n is given, in how many ways you can pick S, a subset of {2, 3, ..., n}, so that n is pure, with respect to S? The answer might be a big number, you need to output it modulo 100003.
The first line of the input gives the number of test cases, T. T lines follow. Each contains a single integer n.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the answer as described above.
Memory limit: 1GB.
T ≤ 100.
Time limit: 30 seconds.
2 ≤ n ≤ 25.
Time limit: 60 seconds.
2 ≤ n ≤ 500.
2 5 6
Case #1: 5 Case #2: 8
This is an easy problem. Especially when efficiency is not a big issue here.
For each directory you want to create, we get all the directories you need. Those are all the ancestors of that directory. For example, if one items in the input of wanted directories is
/home/gcj/round1b/problema/inputWe need all the following
/home /home/gcj /home/gcj/round1b /home/gcj/round1b/problema /home/gcj/round1b/problema/input
Let A be the collection of all the directories we need, and B be the collection of all the directories that are already exist. Simply count how many elements are from A but not B. You need to use one mkdir for each of them.
The solution for this problem consists of several steps, each making the problem a bit easier until it becomes simple.
Suppose a chick catches another one in front of it. We have the following options:
The first observation that we need to solve this problem is that option 2 is never necessary. Intuitively: what's the point of holding the fast one if we will still do the same work on swapping them later? Formally: suppose we have a sequence of swaps that forms the solution for the problem, and that swaps chicks P and Q at time T1, while they first meet at time T0, T0<T1. Let's move this swap to time T0. Note that for each particular chick and each particular moment, the position of this chick at this moment will either stay unchanged, or move closer to the barn. Because of this, the changed solution is also valid.
Suppose that we swap two chicks that would both make it to the barn in time in the end. Then we can avoid this swap and still have both chicks arrive at the barn in time. We will need to do the same number of swaps for the fast chick during the rest of the way than we had to previously (or even fewer, since some chicks might get out of our way), so we'll save at least one swap by keeping the two chicks together until the end.
Suppose a chick can't theoretically make it to the barn in time: Xi+T*Vi<B. Then all chicks that start behind it will need to be swapped with this check or else they won't make it to the barn in time either.
Let's paint the chicks that can theoretically make it to the barn in time with red color, and the ones that can't do that with blue color.
For every red chick, the amount of swaps needed to get to the barn on time is at least the number of blue chicks that start closer to the barn. This gives us a lower bound on our answer: if we count this number for each red chick, then the answer is at least the sum of K smallest such numbers.
At the previous step, we've found some swaps that are necessary in order to solve this problem. Now we note that we don't need any more swaps. More precisely, let's take K red chicks that are closest to the barn initially, and swap them with the blue chicks as soon as they reach any. Since we took K red chicks that are closest to the barn, the number of blue chicks that will get in their way is minimum possible (remember that we never need to swap two red chicks!).
After making all of the above observations, the actual solution becomes very simple:
num_red = 0
num_blue = 0
answer = 0
for i = N - 1 .. 0:
if num_red == K:
break
if X[i] + T * V[i] < B:
num_blue += 1
else:
num_red += 1
answer += num_blue
if num_red >= K:
output answer
else
output "IMPOSSIBLE"
This is a very "mathematical" problem, and solving it required thinking in very formal terms. So please bear with a lot of formulas and little text in the below explanation.
Let's study the process described in the problem statement. Suppose the rank of number N with respect to set S is K. Since N is the largest number in S, that just means the number of elements in S is K.
Then let's consider the set S' = S ∩ {1, 2, ..., K}. From the definition of a pure number, K is now pure with respect to S'.
Does that mean that we've managed to reduce the problem for N to a smaller problem for K? Not yet: suppose we know the number of possible sets S' for which K is pure. How do we find the number of sets S that contain this set (and for which N is pure and that have K elements)?
In order to do that, we need to know how many numbers are there in S'. Suppose there are K' numbers in S'. Then the number of ways to extend this set S' back to S is the number of ways to choose K-K'-1 numbers from the set {K+1, K+2, ..., N-1}.
Let's define Count[N, K] to be the number of sets S that are subsets of {2, 3, ..., N}, have K elements, contain number N and for which number N is pure.
The above discussion proves that Count[N, K] is equal to the sum over all K' of Count[K, K'] times C[N-K-1, K-K'-1], where C[A, B] is the number of ways to choose B items out of A (so-called combination number).
We can calculate Count values in increasing order of N. That will give us O(N2) values to calculate, each requiring O(N) operations, for the total running time of O(N3). That seems to be too slow for N=500 and 100 testcases.
However, one can notice that the above algorithm calculates the answer for smaller values of N as well. That means we can run it just once for N=500, and get the answers for all testcases at once, so the total runtime will be just O(N3), which is okay.