#design

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]

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]

Shopkeepers often round up the change during a purchase so that the change to be given can be a single bill, making it convenient for both the shopkeeper and the customer. For example, a customer has paid a \(200\) sesterzio bill for a purchase of \(104\) sesterzi. If the customer then gives an additional \(4\) sesterzi, then the cashier will give an exact \(100\) sesterzio bill in change, instead of several bills and coins if the change is \(96\) sesterzi. [Read More]

You are given an expression in Reverse Polish Notation (RPN) and you have to evaluate it. Input Format Space separated terms of the expression to evaluate (at least one element). Constraints Each numeric element fits an int32. Any other token is either +, -, *, / The result is guaranteed not to go beyond the int32 representation Output Format The result of the expression evaluation, as a single number. Solutions The solution for this excercise would be to use a stack. [Read More]

Solutions The solutions revolve around finding the frequency of the card values. In addition, checking flush requires us to verify all the suits are equal. This check can be done in advance or while counting the frequency of each card. Afterwards, mapping the card frequency to the score is straighforward: find the maximum frequency and that will give the score: 1 is “High Card” 2 is “Pair”, 3, 4 and 5 are “Three of a Kind”). [Read More]

Solutions The naive solution involves storing each number into the buffer and calculating the product when requested: 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 28 29 30 31 32 33 34 35 36 37 38 39 class NaiveStreamingQualityAnalyzer { public: void add(int num) { stream.push_back(num); } int get(int k) { int product = 1; for (auto i = ssize(stream)-k; i < ssize(stream); ++i) { product *= stream[i]; } return product; } private: std::vector<int> stream; }; int main() { int n, i, j; cin >> n; NaiveStreamingQualityAnalyzer stream; while (n--) { cin >> i >> j; if (i == 1) { stream. [Read More]

Solutions This problem can be solved in several ways, each carrying its own pros, cons and tradeoffs. All the solutions are based on this observation: the answer is always \(max(6-n,4-d)\) where \(n\) is string length and \(d\) is the number of different type of characters that are already present in the input password. Preamble We call character family the group of characters belonging to the same requirement. The problem requires to check against 4: digits, lowercase letters, uppercase letters, special chars. [Read More]

Solutions The simplest solution to this problem involves storing a copy of the entire array every time a new version is saved. This way, to retrieve the value of an element at a specific version, we can simply access the saved array for that version. However, while easy to understand, this approach is highly inefficient for large arrays or when versions are taken frequently. If there are \(N\) calls to each function, this method would store \(N\) full copies of the array, leading to significant memory usage and poor time performance. [Read More]