For the continuous evaluation component involving exercise-solving during the semester, the exercises you can submit in this class are:
Submission Deadline: October 18th (submit to AED's Mooshak)
You are encouraged to talk to the professor and to your colleagues if you have difficulties. However, any more direct help you have received from other colleagues or LLMs should be acknowledged in the comments of the code you submit.
After the deadline the problems will still be available on Mooshak, but the submissions will not count towards your grade.
Each class is worth 9 per cent of the grade for this component. As there will be 12 classes with submissions, you can get full marks even if you haven't done everything.
For a problem to count, you have to get all the tests right (i.e. accepted). Even if you solve all the problems, the maximum in a single class is 100 per cent.
It is guaranted that the main exercises on each class will sum to at least 100% of the class grade.
This class includes exercises about Complexity and Asymptotic Analysis. It is therefore convenient that you know what was discussed on the lectures:
Recall that:
1. Asymptotic notation and definitions
Explain why each statement is true, using the definition of the classes \( \mathcal{O}(\cdot) \), \( \Omega(\cdot) \) and \( \Theta(\cdot) \).
2. Characterizing the complexity of concrete programs
For each of the following exercises you should characterize the asymptotic time complexity of the respective function as a function of \(n\). You should also describe what characterizes best case and worst case instances.
int remove(int x[], int n, int v) { int t = 0; for (int j=0; j<n; j++) if (x[j] <= v) x[t++] = x[j]; return t; }
bool symmetric(int x[][N], int n) { for (int i=1; i < n; i++) for(int j = 0; j < i; j++) if (x[i][j] != x[j][i]) return false; return true; }
#include <iostream> #include <vector> using namespace std; bool my_3sum(const vector<int> & x) { int n = x.size(); for (int i=0; i < n-2; i++) for(int j = i+1; j < n-1; j++) for(int k = j+1; k < n; k++) if (x[i]+x[j]+x[k] == 0) { cout << i << ' ' << j << ' ' << k << endl; return true; } return false; }
3. Summing subsequences (naive solution does not have the desired complexity)
Now that you solved some "pen and paper" exercises, let's go back to implementations and Mooshak submissions 😺
For this exercise you will be solving the problem [AED006] Bakugans.
Desired time complexity: \(\mathcal{O}(N + P)\)
Always start by carefully reading the problem statement and understand what it is asking.
There is an "obvious" algorithm: for each of the \(P\) photos, do a cycle between \(A_i\) and \(B_i\) and add up the energies of the corresponding Bakugans.
An example implementation of this idea is given in in aed006_naive.cpp (see html version). Download the file, compile and test it with the example input to verify it gives the desired output.
Now submit this code on Mooshak. You will get a Time Limit Exceeded. The problem is that the temporal complexity of this approach is \(\mathcal{O}(N \times P)\). Can you see why?
In the worst case, we can have in this problem \(N = P = 200\,000\), and \(200,000^2\) is really a big number... (the time limit for this problem on Mooshak is 1 second). We need to find a more efficient solution!
A very interesting concept is the one of "prefix sums" (also known as cumulative sums).
Imagine for instance a number array with the values [3,7,2,4,5,7,6]. The prefix sums are the total sums up to the corresponding positions. For example:
Position i: 0 1 2 3 4 5 6 7 Array Values: 3 7 2 4 5 7 6 Prefix Sum: 0 3 10 12 16 21 28 34
If we have stored the prefix sums, which can be computed in linear time, i.e. \(\mathcal{O}(N)\), finding the sum of a given interval can now be done in constant time, i.e. \(\mathcal{O}(1)\).
For example, if \(psum[]\)
stores the prefix sum, the sum between positions \(a\) and \(b\) is equal to \(psum[b] - psum[a-1]\). Can you see why?
This technique can be used to help solve many problems more efficiently, including this Bakugan problem. If the prefix sums are calculated right after reading the energies, we can answer to each photo in \(\mathcal{O}(1)\), which makes the overall temporal complexity of the programme \(\mathcal{O}(N + P)\), as we have the reading of the energies, followed by the reading of the photos, with a response in constant time for each one.
Implement this idea using as a basis de previous code, test it and submit to get your well deserved Accepted! 😎
4. Digging treasures (naive solution does not have the desired complexity)
For this exercise you will be solving the problem [AED007] Treasure Hunter.
Desired time complexity: \(\mathcal{O}(N + I)\)
A "brute force" solution that simulates all instructions can take \(I \times N\) time, since each of the \(I\) instructions can require traversing \(N\) positions in the worst case. This is not enough to pass the time limit, and we need a better solution...
This problem was originally the easiest one on the qualification phase of the National Olympiad in Informatics, an algorithmic competition for high-school students, and was solved by many students.
Try to first think about the problem and see if you can come up with a solution that avoids actually traversing one by one all the positions in each instruction. If you get stuck, the hints button will give you a spoiler on how to approach this problem.
- We can make an important observation: Sarah always covers a contiguous range of positions. If the rightmost position she reaches is position \(pos_{right}\), then Sarah had to pass through all positions from \(S\) to \(pos_{right}\), because she never 'skips' positions. Similarly, if the leftmost position she reaches is position \(pos_{left}\), then Sarah had to
pass through all positions from \(pos_{left}\) to \(S\).
Hints
- Thus, knowing \(pos_{left}\) and \(pos_{right}\), it suffices to loop only once through all positions between \(pos_{left}\) and \(pos_{right}\) and compute how many treasures there are in that interval. To calculate \(pos_{left}\) and \(pos_{right}\), simply calculate the position after following each instruction and keep the smallest and largest, respectively.
- In terms of efficiency, this corresponds to one loop to process all instructions and calculate \(pos_{left}\) and \(pos_{right}\), and a second loop to check the chests between \(pos_{left}\) and \(pos_{right}\), which corresponds to \(N + I\) operations.
- This is therefore a \(\Theta(N + I)\) solution that easily passes in all cases.
5. Saving Pipefish (naive solution does not have the desired complexity)
For this exercise you will be solving the problem [AED008] Saving Pipefish.
Desired time complexity: \(\mathcal{O}(N)\)
This is another problem from a qualification phase of the National Olympiad in Informatics
A "brute force" solution that tries all possible sections and for each of them tests all positions to see how many of them are larger than \(T\) is not enough, since it would spend \(N^2\) time (can you see why? imagine a case with \(K=N/2\)). We need a better solution...
(click to see hints; try to solve the problem first if you do not want spoilers)
- Imagine you already processed the section \([a,b]\), having obtained \(Q_a\), the amount of elements larger or equal than \(T\) in that section.
- The next section is \([a+1,b+1]\). What changes in that interval? Only the position \(a\) is removed and the position \(b+1\) is inserted. The (new) value of \(Q_{a+1}\) is therefore equal to \(Q_a\), subtracting 1 in case the depth of position \(a\) is \(\ge T\) and adding 1 in case the depth of position \(b+1\) is \(\ge T\).
- For each new interval we only need to make a constant number of operations (considering the element to remove and the element to insert).
Regarding efficiency this corresponds to an initial cycle for the first section of size \(K\) and for the remaining \(N-K\) sections we spend constant time. Another way of reasoning about this is that each position is added only once to the current section, and removed once from it. This is therefore a solution in time \(\Theta(N)\) obtaining the desired Accepted result.
- This idea of reusing the result of the previous section to compute the result of the next one is known as the sliding window technique, since we are "sliding" the windows of the current section along the input.
6. Justify the truthfulness or falsity of each statement.
7. Assume that v and w are vectors and both contain a sequence of nonnegative integers that ends with 0 (and has no other zeros). Let \(a_1, a_2,\ldots, a_m,0\) and \(b_1,b_2,\ldots, b_n,0\) be such sequences, with \(m\geq 1\) and \(n\geq 1\). The function returns an integer which is either positive, negative or 0, if the sequence given by v is lexicographically greater than, less than or equal to the sequence given by w, respectively. Recall that all \(a_i\)'s and \(b_i\)'s are positive integers.
int lex_comp(const vector<int> &v, const vector<int> &w) { int j = 0; while (w[j] == v[j] && v[j] != 0) j++; return v[j]-w[j]; }
8. Recall the problem Partition which, given a set
\(S=\{a_1,a_2,\ldots, a_n\}\) of \(n\)
positive integers, asks whether there is a set \(A\subset S\) such that
\(\sum_{x\in A} x = \sum_{x \in S\setminus A} x\).
The following function solves the problem when
we call search(x,0,n,0,0,res,nres), with nres=0,
and x and res being arrays with at least \(n\geq 2\)
elements. In addition, it returns a set \(A\) in res. It implements a brute force search algorithm.
bool search(int x[],int i, int n, int s, int r, int res[], int & nres) { if (i == n) return s == r; s += x[i]; res[nres++] = i; if (search(x,i+1,n,s,r,res,nres)) return true; s -= x[i]; nres--; r += x[i]; return search(x,i+1,n,s,r,res,nres); }
9. Maximum Subarray Problem (naive solution does not have the desired complexity)
For this exercise you will be solving the problem [AED009] Sequence Game.
Desired time complexity: \(\mathcal{O}(N)\)
Can you think on this problem on your own and try to reach a linear time solution?
- This is a classical problem that can be solved with Kadane's algorithm (see wikipedia or geeksforgeeks for an explanation)
As on the previous class, this exercise can be harder than the previous ones and does not need to simply tackle the topics of this class.
The main idea is to give you the opportunity of improving your problem solving abilities.
For this exercise you will be solving the problem [AED010] Cool Numbers.
Since this is a challenge, I will not give you any hints, but if you are stuck just contact @PedroRibeiro on Discord. Feel free to also contact @PedroRibeiro to discuss your accepted solution.
Happy coding! 😊