Append and Delete

Solutions The challenging part of this exercise is how to handle operations in excess. If a string is empty, we can consume as many operations we want (as the problem specifies). So, the easy case is when we have a number of operations that is greater than the sum of length of both strings. In this case the solution is “Yes” because we can just remove all the characters from one, consume excess operations by repeatedly performing the second operation from the empty string, and finally appending the other characters. [Read More]

Bus Trip

Solutions Checking if a certain value \(x\) is suitable takes linear time. Intuitively, we have to verify if the array can be splitted into contiguous groups of sum \(x\), without remainder (empty space on the bus is not allowed). This operation consists in iteratively checking the prefix sum of the array against a cumulative value of \(x\). For example: 1 1 2 1 1 1 2 1 3 Suppose we want to the check if 3 works. [Read More]

Circular Array Rotation

Solutions You can actually rotate the array: in Javascript (by Alessia Bragagnolo) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 function circularArrayRotation(a, k, queries) { let result = []; while (k > 0) { let tmp = a.pop(); a.unshift(tmp); k--; } for (let i = 0; i < queries.length; i++) { result.push(a[queries[i]]); } return result; } But… we don’t really need to rotate the array: [Read More]
math 

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 

Herb and Bjarne

Herb puts Bjarne’s birthday present in a cuboid box. The dimensions of its edges are positive integers and the sum of its length, height, and width is N. Input Format A single integer, N (the sum of the box’s length, height, and width). Constraints \(3 \leq N \leq 10^3\) Output Format Print the maximum possible volume of the box. Solutions The product of edge lengths is maximized when the lenghts are as long as possible. [Read More]
math 

Maximum Perimeter Triangle

Solutions This problem simulates the situation when you need some additional “domain knowledge” to find a solution. In this case the domain is “geometry” and you have to find (or recall) the Triangle inequality: for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side In other terms, for any three sticks \(a, b, c\), the following must be true: [Read More]
greedy  math 

Most Distant

Solutions Since every point has either \( x \) or \( y \) to 0, only 4 points can contribute to the final solution: the rightmost point - max \( x \) the leftmost point - min \( x \) the highest point - max \( y \) the lowest point - min \( y \) Basically, we can ignore all the internal points. Then, it’s just the matter of calculating the max distance among such points (the total number of pair-wise combinations is 6). [Read More]
math 

Product of Array Except Self

Given an array of \( n \) integers where \( n > 1 \), \( nums \), print an array \( output \) such that \( output[i] \) is equal to the product of all the elements of \( nums \) except \( nums[i] \).

Solve the problem in \( O(N) \) without using division.

[Read More]

Restaurant

Solutions We have to cut a rectangular bread having size \(l * b\) into squares of equal dimension such that no piece of original bread is left over. So we have to make cuts only vertically or horizontally. Hence we can conclude that if the length of a side of the square is \(a\), both \(l\) and \(b\) has to be divisible by \(a\). In addition, \(a\) has to be as large as possible. [Read More]
math 

Secret repetition

Solutions This problem is very easy but, as we’ll see in a minute, it can be solved in a very clever way. The easiest approach uses extra space, a frequency table. The core of the algorithm in C++: 1 2 3 4 5 6 7 8 9 10 11 12 13 int N; cin >> N; vector<int> A(2*N); copy_n(istream_iterator<int>(cin), 2*N, begin(A)); vector<int> freq(1'000'000 + 1); for (auto i : A) { freq[i]++; if (freq[i] > 1) { cout << i; break; } } This solution is linear. [Read More]