The Kattis Challenge: Link
Companion Moodle Exam: Link
For this final you will be solving problems on a Kattis challege. There are 9 problems. You only need to solve 5 of them to get a 100% on this part of the test. If you solve more I will a 5% boost on the other moodle test for each extra one you get.
You are to turn all your final code in on the Moodle exam, along with you test name. If your code passes the test, you only need. turn in your code. If it did not, you need to show your tests (more then the test in the problem descrption), and show a picture of the screen telling what happened (such as test failed, time limited reached, compilation error).
For this exam you may only look at the C++ reference site: https://en.cppreference.com/w/, the text book, and sample I gave you in class or on gethub, or other sites I reveal below in the hints. You may also look at previous repls you have worked on or I have published as part of the course. You may not look anywhere else. You may not talk to anyone but me.
Here are the instructions. Please follow carefully:
- You will create an account here: Kattis. When you create your account, you must set it to hide your username. Make sure the following boxes are not checked on the setting page. If you already sigened up, click on your name on the upper right corner, and select “profile settings”. The options below are at the bottom on the page.
- The challenge is now published, and you can join anytime. You can start Oct 15 at 8:00 am.
- You can register with a team name that does not identify you. For this midterm you MUST use a made up name (per FERPA rules). When you join the contest you will need to give a team name. This is the name that will show up on the standings page. Make sure no one knows it is you. Go here to enter your team name so I know it: Kattis Team Name
- The challenge can be found at this link.
- The challenge starts: 2024-12-16 13:00:00 and ends: 2024-12-18 13:00:00
- You can use you text, notes, and any
- You CANNOT use other people, AI, or websites that contain the complete solution
- Solve all problems in C++.
Hints:
Problem B:
For this you will need two priority queue of pairs, one for buy orders and one for sell orders. The pairs will be <price,shares>.
You will need a comparer function for he priority queues of pairs. Use this to understand how to do this:
https://www.geeksforgeeks.org/custom-comparator-in-priority_queue-in-cpp-stl
Problem D:
This is pretty simple, but if you use the built in sort you need to write a special compare function.
Problem E:
You could use a map to count the number of occurances of number. But you have to convert the map to some sort of vector to sort. I used a struct which contained the number, the number of occurances, and index of the first occurance. The index allows you to sort based on how soon you saw it. You have to sort twice (the order of occurance and the number occurances), and in doing so you need a stable sort.
Problem F:
This problems used a Depth First Search like we saw in the maze problems. You need to make a 2-dimensional array of the characters. You can use recursion or a stack to implement the search. You should also make a 2-dimensional array of “visited” to keep track of where you have been so you don’t search the same place twice (or get caught in a loop).
This problem is not too hard to solve, but it hard to solve it within the given time constraits. If you can get it to solve the at least the first 10 problems, I’ll give you a 95% on it, if you can get all but the last 100 I’ll give you 100%. If you solve it in the time givem completely, I’m give you double bonus, i.e I’ll give you 200%!
Problem G:
To solve this problem, you can use either a depth-first search (DFS) or a breadth-first search (BFS). Since there are no strict time constraints as in Problem F, both approaches are viable. Essentially, this problem can be thought of as a “fill” operation.
The method I used involves searching for cells marked with -. Once a - is found, I performed a DFS to “fill” all reachable cells (those also marked with -) using a unique star number. I started with star number 1 and incremented it for each new star cluster I encountered. At the end of the operation, the final star number represents the total number of stars (or connected components) in the grid.
Problem H:
This is something you have seen in class, and obviously involves a stack.
Problem I:
Approach:
- Sort Customers: Sort the customers based on their deposit amounts in descending order to prioritize higher deposits.
- Track Available Slots: Use a data structure to keep track of available time slots up to the maximum deadline.
- Assign Customers to Slots: Iterate through the sorted list of customers and assign each to the latest available time slot before their deadline.
Implementation:
- A common approach is to use a priority queue (max-heap) to efficiently manage and assign time slots to customers based on their deposit amounts and deadlines.
Mixing cin and getline
If you mix cin and getline you can have problems (I did on some of these problems).
If you have used cin and now you want to call getline you must purge the newline character after the last cin.
Do with with the code:
cin.ignore();