Solution for 2021.6.9 Training
Once edited 2 年，10 月前
Problem A
Solving this problem entails simulating the movement of the pebble based on each of its three possible starting points, taking whichever yields the most right answers. My code for doing this in C++ is below; it is hopefully straightforward enough that those of you who write in other languages can follow.
#include <iostream>
#include <fstream>
using namespace std;
int N, A[100], B[100], G[100];
int num_correct(int starting_shell)
{
int current_shell = starting_shell, correct = 0;
for (int i=0; i<N; i++) {
if (A[i] == current_shell) current_shell = B[i];
else if (B[i] == current_shell) current_shell = A[i];
if (current_shell == G[i]) correct++;
}
return correct;
}
int main(void)
{
ifstream fin ("shell.in");
fin >> N;
for (int i=0; i<N; i++)
fin >> A[i] >> B[i] >> G[i];
int best = 0;
for (int i=1; i<=3; i++)
best = max(best, num_correct(i));
ofstream fout ("shell.out");
fout << best << "\n";
return 0;
}
Problem B
By scanning through the stalls, we can compute a list of gaps: blocks of contiguous empty stalls. Let $l_1,\dots,l_k$ be the lengths of these gaps. For example, consider the sample input:
10001001000010
Then in this example, the gap lengths are $3$, $2$, $4$, and $1$.
If we only place a single cow, it will either go at the center of the largest gap, or in the left-most stall, or in the right-most stall. If we have two cows, then we might consider the following algorithm: for each of the three cases for the first cow, place the first cow; then try the three different cases for where the second cow might go. In total there are $9$ potentially optimal placements (actually less because some are impossible) and for each placement we can compute the length of the minimum distance between cows in that placement, by a linear scan.
However, this does not cover all cases. It’s possible that both cows are placed in the same gap (the largest gap). In this case we want to place one of the cows approximately one-third of the way through the gap, and the other cow two-thirds through. The above algorithm will never try this placement, so we need to check it also.
We can prove that the resulting $10$-case algorithm is correct. If the cows are not placed in the same gap, then each cow will be either in the center of some gap, or at the left end or right end of the whole sequence (because the two cows don’t “interact”). If either cow is at the left end or the right end, then the above algorithm covers that case. If both cows are in centers of gaps, then at least one of them will be at the center of the largest gap. This case is also covered.
See below for Brian Dean’s $O(N)$ time algorithm. Some of the cases are condensed (and some are omitted because they’re impossible), but in spirit his algorithm is as we described above.
#include <iostream>
#include <fstream>
using namespace std;
// Returns size of largest gap between two 1s and also the index where it starts
int find_largest_interior_gap(string s, int &gap_start)
{
int biggest_gap = 0, current_start = -1, N = s.length();
for (int i=0; i<N; i++)
if (s[i] == '1') {
if (current_start!=-1 && i-current_start > biggest_gap) {
biggest_gap = i-current_start;
gap_start = current_start;
}
current_start = i;
}
return biggest_gap;
}
// Returns size of smallest gap between two 1s
int find_smallest_interior_gap(string s)
{
int smallest_gap = 1000000000, current_start = -1, N = s.length();
for (int i=0; i<N; i++)
if (s[i] == '1') {
if (current_start!=-1 && i-current_start < smallest_gap) smallest_gap = i-current_start;
current_start = i;
}
return smallest_gap;
}
int try_cow_in_largest_gap(string s)
{
int gap_start, largest_gap = find_largest_interior_gap(s, gap_start);
if (largest_gap >= 2) {
s[gap_start + largest_gap / 2] = '1';
return find_smallest_interior_gap(s);
}
return -1; // no gap!
}
int main(void)
{
ifstream fin ("socdist1.in");
int N;
string s, temp_s;
fin >> N >> s;
ofstream fout ("socdist1.out");
int answer = 0;
// Possibility 1. put two cows in largest interior gap
int gap_start, largest_gap = find_largest_interior_gap(s, gap_start);
if (largest_gap >= 3) {
temp_s = s;
temp_s[gap_start + largest_gap / 3] = '1';
temp_s[gap_start + largest_gap * 2 / 3] = '1';
answer = max(answer, find_smallest_interior_gap(temp_s));
}
// Possibility 2. cows at both ends
if (s[0] == '0' && s[N-1] == '0') {
temp_s = s; temp_s[0] = temp_s[N-1] = '1';
answer = max(answer, find_smallest_interior_gap(temp_s));
}
// Possibility 3. cow at left + cow in largest interior gap
if (s[0] == '0') {
temp_s = s; temp_s[0] = '1';
answer = max(answer, try_cow_in_largest_gap(temp_s));
}
// Possibility 4. cow at right + cow in largest interior gap
if (s[N-1] == '0') {
temp_s = s; temp_s[N-1] = '1';
answer = max(answer, try_cow_in_largest_gap(temp_s));
}
// Possibility 5. cow at largest interior gap. done twice.
if (largest_gap >= 2) {
temp_s = s; temp_s[gap_start + largest_gap / 2] = '1';
answer = max(answer, try_cow_in_largest_gap(temp_s));
}
fout << answer << "\n";
return 0;
}
Problem C
Suppose that Farmer John doesn’t remove any cows from the line. Then we can simply simulate the actions of the cows in order, keeping track of which boxes of cereal are left. This yields an $O(N^2)$ solution to the original problem: for each $i$, simulate the last $N-i$ cows.
There are several ways to speed up this solution. One way is to start with $i = N$ and add cows one by one. Suppose we have solved the problem for the last $N-i$ cows: that is, if the last $N-i$ cows line up in order, we know which box each cow takes. We want to efficiently update this outcome to the outcome if instead the last $N+1-i$ cows were to line up. Thus, we need to handle the operation “add cow to front of line”.
Suppose the new cow has preferences $(f, s)$. Then the new cow will certainly get cereal $f$. If the last $N-i$ cows didn’t take cereal $f$, then nothing will change: all of those cows have the same outcomes after adding the new cow. But if some cow $j$ had taken cereal $f$, then after adding the new cow, $j$ no longer gets $f$. If $f$ is $j$’s second choice, then now $j$ gets nothing—and all other cows have the same outcomes. If $f$ is $j$’s first choice, and her second choice was taken by some cow earlier in line, then again $j$ gets nothing, and all other cows have the same outcome. But if $j$’s second choice was not taken by some cow earlier in line, then $j$ will take it. Unfortunately, this case may cause a cascade: we need to recurse on $j$ and figure out whether $j$ stole her second-choice cereal from someone later in line, and so forth.
At each step of the recursion, a cow $j$ can only “steal” from one later cow: the cow who originally took the cereal which $j$ is now taking. So the above algorithm doesn’t blow up exponentially or anything. But each addition of a new cow seems like it could cause a recursion of depth $O(N)$, which would imply an overall time complexity of $O(N^2)$!
Fortunately, this is not the case: we can show that the sum of the recursion depths is actually $O(N)$. The reason is that every time we recurse, a cow is either kicked from first-preference to second-preference or from second-preference to nothing. Moreover, as we add cows, the reverse can never happen: a cow who was getting nothing cannot suddenly get something when we add a cow to the front of the line. It follows that the total depth of all the recursion is at most $2N$.
To implement the algorithm efficiently (with a constant-time update at each recursion step) we just need to keep track of which cow currently gets each box of cereal ($occ[pos]$ stores the index of the cow that gets cereal $pos$). The final algorithm runs in time $O(N)$. See my code below:
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100001
int N,M;
int f[MAXN];
int s[MAXN];
int occ[MAXN];
int ans[MAXN];
int main()
{
cin >> N >> M;
for(int i=0;i<N;i++)
cin >> f[i] >> s[i];
int cnt = 0;
for(int i=N-1;i>=0;i--)
{
int j = i;
int pos = f[i];
while(1)
{
if(occ[pos] == 0)
{
occ[pos] = j;
cnt++;
break;
}
else if(occ[pos] < j)
break;
else
{
int k = occ[pos];
occ[pos] = j;
if(pos == s[k])
break;
j = k;
pos = s[k];
}
}
ans[i] = cnt;
}
for(int i=0;i<N;i++)
cout << ans[i] << '\n';
}
Problem D
This is a nice example of a problem where half the work goes into figuring out useful structural properties of the solution, and then the other half goes into writing code to search for a solution based on this knowledge. In this case, let $M$ be the maximum number of characteristics any two cows have in common, over all pairs of cows. We claim that $M+1$ is the answer.
Here is a simple argument. If we pick two cows (say $A$ and $B$) that have $M$ traits in common, then we can ask about just those traits, generating $M$ “yes” answers and leaving a feasible set that still contains $A$ and $B$. Hence, the maximum number of “yes” answers in a transcript could be larger than $M$. On the other hand, the number of “yes” answers in any transcript cannot be larger than $M+1$. Suppose we have a transcript involving $M+1$ yes answers after which there are still multiple cows in our feasible set. If so, those cows must have had more than $M$ traits in common, which cannot be the case! After $M+1$ “yes” answers, we therefore must have reduced the feasible set down to at most a single cow.
Now that we know all we need to do is compute $M$, the coding part isn’t too bad. My code below does this in perhaps the most straightforward way, looping over all pairs of cows and for each, checking the number of characteristics in common again with two “for” loops. The input size is small enough that this runs fast enough to pass all test cases.
As a note to those en route to silver, however, one could make the “num_common” function quite a bit faster using fancier data structures like a binary search tree (e.g., a “set” in C++) or a hash table (e.g., an “unordered_set” in C++). To compare cows $A$ and $B$, we would add all of $A$’s characteristics to the data structure, then do lookups for all of $B$’s characteristics, counting the number that succeed. Alternatively, we could have sorted every cow’s list of characteristics, and to compare $A$ with $B$ we enact the process of “merging” their sorted characteristics into one larger sorted list, a standard algorithmic procedure (e.g., part of the “merge sort” algorithm) that allows us to easily count duplicates along the way. Alternatively still, after sorting, we could run through all of $B$’s characteristics and binary search for them in $A$’s sorted list of characteristics.
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int N;
vector<string> characteristics[100];
int num_common(int i, int j)
{
int count = 0;
vector<string> &v1 = characteristics[i], &v2 = characteristics[j];
for (int i=0; i<v1.size(); i++)
for (int j=0; j<v2.size(); j++)
if (v1[i] == v2[j]) count++;
return count;
}
int main(void)
{
ifstream fin ("guess.in");
fin >> N;
string s;
for (int i=0; i<N; i++) {
int K;
fin >> s >> K;
for (int j=0; j<K; j++) {
fin >> s;
characteristics[i].push_back(s);
}
}
int largest = 0;
for (int i=0; i<N; i++)
for (int j=i+1; j<N; j++)
largest = max(largest, num_common(i,j));
ofstream fout ("guess.out");
fout << largest+1 << "\n";
return 0;
}
Problem E
Problem F
