Weekly Training Solutions: Algorithmic Schemas

Problem A (by @RobeZH)

This problem is a kinda brute-force problem. You can each configuration of the board for which each row has one queen and each column has one queen. The number of such configurations is $8! = 40320$ which easily fits into the time limit.

Then you can define a dfs function in which you keep putting queen on each possible column in a row, and then go on the next row.

The function is something like below:

void dfs(int i){
    if(i == 8){
        record_answer();
        return ;
    }
    //Enumerating columns
    for(int j = 0; j < 8; j++){
        if(isvalid(i, j)){
            record_this_row();
            dfs(next row);
            unrecord_this_row();
        }
    }
}

Problem B (by @Zeyuan He)

Idea

This problem can be solved by a greedy approach, and does not require repetitively iterating through the array.
We should be aware that the number of bag sets is always equal to the maximum number of bags with the same dimension (for the sample: 1 1 2 2 2 3, the answer is 3 because dimension 2 appears the 3 times).
To output a valid solution, simply (max_dim: maximum number of bags with the same dimension)

for(int i = 0; i < max_dim; i++) {
    for(int j = i; j < n; j+=max_dim)
        [output the j-th number in the array]
    [start a new line]
}

This code will not output the same dimension of the same line because a[j] and a[j + max_dim] cannot be the same according to out definition.

Problem C (by @LER0ever)

Idea

So the TLDR of Helping Fill Bates is basically finding whether a given sequence is a (possibly discontinuous) subsequence of the input.
The basic idea is to contruct a index record (of where the char is in the original input string) for each character in the input a[52], and start to match the query string char by char. In the matching process, we find the char’s earlist position in the index record, and record the resulting index and set that as the temporary ending index ed. For the first match, set a var st to be ed. If no matches found, then we directly return. And after all the chars in the query has been matched, the result is just the first matched index st as starting index, and the temporary ending index ed as ending index.
The matching process is done by using C++'s builtin upper_bound functions which runs pretty much the same as a binary search in $log_2(n)$ time.

Complexity

Suppose the input size is $N < 1000000$ and the query string size is $n$.
The index record construction takes linear time $O(N)$;
The matching phase, using upper_bound, takes $O(log_2(n))$ per match, with n of them, adding up to $O(n log_2(n)$.
So the overall time complexity of a single query is $O(n log_2(n))$

Code

string s; int q; vi a[60];
cin >> s >> q;
rep(i, sz(s)) a[s[i]].PB(i);
rep(i, q)
{
    string n;
    bool ok = true;
    int s=1, ed=-1;
    cin >> n;
    rep(j, sz(n))
    {
        int c = (int)n[j];
        vi::iterator up = upper_bound(all(a[c]), ed);
        if (up == a[c].end()) {
            ok = false; break;
        }
        int p = up - a[c].begin();
        ed = a[c][p];
        if (j == 0) st = a[c][p];
    }
    if (ok) cout << "Matched " << st << " " << ed << endl;
    else cout << "Not matched" <<endl;
}

Problem D (by @Lteins)

Idea

First, a letter can appear in a column only if it appears in both keyboard config. Based on that, we can construct 6 arrays, each containing the possible letters for the column they represent in ascending order. Next, assume we generate our password from the leftmost column to the rightmost, let us denote the number of password options left after the letter for the ith column is already chosen as opt[i]. Obviously, opt[6] = 1 (when the last column is fixed). Then, opt[i] = opt[i+1] * num_of_letter[i+1] (Number of letters available for the i+1 column). To choose the kth possible combinations, we choose the x = ceil(k/opt[i])-1 letter in the candidate array (after chooseing one letter, we update k to k - x*opt[i]).

Problem E (by @chinsengi)

Idea

Since all the numbers are non-negative, it’s obvious that in order to achieve max summation, we just need to select all numbers except zeroes. Pay attention to one special case when all the numbers are zero, the output in this case should be one zero alone.

Problem F

idea (@bud)

Bulletin: divide and conquer. keep track of thr minimal distances form each half. combining rule: search a strip of the splitting line to see if there are closer points between left and right. ending condition: a narrow strip.

Divide the plane into two sections by the $x$-coordinate; call the middle point $x_1$
We can solve the problem for the left and right half using divide and conquer, and get two minimum distance $ans_L$ and $ans_R$. Let $ans$ be the smaller one.
But the closest pair may exists in between two sections.
Consider the the narrow strip along the middle line $(x_1-ans, x_1+ans)$. We can define a bound for any point in the. In the worest case, we need to check at most 8? points.

Since the points are sorted by the $y$-coordinate…

Total time complexity: $O(n\log^2{n})$

improvement (@RobeZH)

How to sort the points according y-coordinate? In the algorithm bud described for finding closest pair, we first solve the left part and the right part, and then put them together. Does the structure sound familiar? It’s merge sort! Right? After calculating the closest pair in each recursion, we simply merge the two parts together in $O(n)$ time! Then we can achieve a overall complexity of $O(n\log{n})$.

Conclusion

If you have further question, be free to check other’s code in the practice.