Cavity Map

Solutions

We can check each element against its neighbors’ depth and mark it with ‘X’ if the cavity condition is satisfied.

Here is a C++ Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

size_t n;
cin >> n;
vector<vector<char>> data; data.reserve(n);
for (auto i=0u; i<n; ++i)
{
    data.emplace_back(n);
    copy_n(istream_iterator<char>(cin), n, begin(data[i]));
}

for (auto i=1u; i<n-1; ++i)
{
    for (auto j=1u; j<n-1; ++j)
    {
        auto cavity = data[i][j]-'0';
        if (cavity > (data[i][j+1]-'0') && 
            cavity > (data[i][j-1]-'0') &&
            cavity > (data[i-1][j]-'0') &&
            cavity > (data[i+1][j]-'0'))
            data[i][j] = 'X';
    }    
}

for (const auto& row : data)
{
    copy(begin(row), end(row), ostream_iterator<char>(cout));
    cout << endl;
}
ad hoc 

Check Sudoku

Solutions We need to check if any row, columns or sub-grid contains duplicates. We can use an array of booleans (or a frequency array) for each type of component to check. Here is the idea: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int main() { bool row[9][9]{}, column[9][9]{}, grid[3][3][9]{}; int N, r, c, v; cin >> N; for (int i = 0; i < N; ++i) { cin >> r >> c >> v; r--; c--; v--; if (row[r][v] || column[c][v] || grid[r / 3][c / 3][v]) { cout << "WRONG INPUT"; return 0; } row[r][v] = column[c][v] = grid[r / 3][c / 3][v] = true; } cout << "OK"; } Basically, we read a coordinate and we check if it has been already allocated in any of the component. [Read More]
ad hoc  frequency table  design 

Day of the Programmer

Solutions This problem seems convoluted but it can be solved very easily if decomposed in terms of simple predicates: if the year is 1918, we can directly return the day 26.09.1918 otherwise we can check if the year is leap. In this case we return 12.09 and the year if the year is not leap, we just return 13.09 and the year To determine if a year is leap, we have to apply either the Julian - if the year is less than 1918 - or the Gregorian rule - otherwise. [Read More]
design  ad-hoc 

Fair Rations

You are the benevolent ruler of Rankhacker Castle, and today you’re distributing bread. Your subjects are in a line, and some of them already have some loaves. Times are hard and your castle’s food stocks are dwindling, so you must distribute as few loaves as possible according to the following rules: Every time you give a loaf of bread to some person , you must also give a loaf of bread to the person immediately in front of or behind them in the line (i. [Read More]
math  ad hoc 

Fixed Adjacent Values

Given an array of integers where each element is obtained by adding either +1 or -1 to the previous element you need to find an element index with the minimum number of comparisons. If the element is present multiple times then print the smallest index. If the element is not present print -1. Input Format int N, denoting the number of elements. int T, denoting the number of queries. N space separated elements, denoting the array to search. [Read More]
ad hoc 

Hotel Coverage

Solutions This problem falls into the greedy category. A hotel can accomodate all customers in a distance of \(-k\) and \(+k\). We should find the smallest amount of intervals of length \(2k\) that cover all the positions of the customers. First of all, we sort the positions of the customers. We iterate over all the sorted positions and, at each step, we calculate the difference between adjacent positions. We keep track of the interval by incrementing a running sum of the such differences. [Read More]
sort  ad hoc  greedy 

Minimum Index Distance

Given two arrays, A and B, of size N that both contain permutations of the same set of unique integers, find and print the number having the absolute minimum index difference between the two arrays. In the event of a tie, choose the smallest number. Input Format The first line contains an integer, N, denoting the size of the array. The second line contains N space-separated integers describing array A (a0, a1, …). [Read More]
ad hoc 

New Year Chaos

Solutions We can see, intuitively, that the number of people a person \(p\) has bribed corresponds to the number of people on her right with value less than \(p\). For instance: 1 1 2 3 5 4 In this case, \(5\) has bribed \(4\) and took her position. Another example: 1 2 1 5 3 4 We have three bribes: \(2\) has bribed \(1\) \(5\) has bribed \(4\) \(5\) has bribed \(3\) This problem is equivalent to calculating the number of inversions of the array, that is the number of elements that are out of the natural order of a sequence. [Read More]
ad hoc  sorted sequence  constrained 

One Swap

Bob has an array \( a \) with \( n \) positive integer elements. Bob likes order, so he wants his array to be sorted in non-decreasing order. He decides to swap two elements in the array to make his array sorted. (A swap is defined as switching two elements at distinct locations in the array.) Your task is to determine if this can be done. If he can’t sort the array with one swap, print \( -1 \). [Read More]
patterns  ad-hoc 

Spiral line

A bunch of villains are waiting in line for being accepted on board of the Queen Anne’s Revenge, docked somewhere in Nassau, to become part of the crew. Every rascal is represented by a number corresponding to the “pieces of eight” they have stolen so far. However, the pirates of the Queen Anne’s Revenge are as crazy as the captain and arrange that line in a spiral: Rascals that make it wrong will walk the plank! [Read More]
matrices  ad-hoc