ACM@USC Codeathon - GameStonk - C++
The greatest thing I learned this year, was imagine every dynamic programming question as some subproblem of knapsack. Once you think of it as knapsack, it feels magnitudes easier to solve if you know the \(O(nW)\) dynamic solution and \(W\) is sufficiently a small enough factor. K-dimensional dynamic programming has become a lot easier, but I still struggle from time to time.
I learned through my years going to ICPC that my weakness in algorithm competitions is dynamic programming. Graph algorithms almost feel trivial, divide and conquer can be difficult but do not come up often. I decided to spend the last year or so really trying to get a deep understanding and ability in dynamic programming. Today I feel very comfortable. I found a neat problem, Min Jumps, and tweaked it to be a little more difficult, and requiring an understanding of the algorithm otherwise trying to tweak the geeks for geeks solution will be futile.
This last month has also been a great opportunity to really pick up on my C++ and algorithms skills. I went ahead and brushed up quite a bit over the last few days, and have decided to try and finish all of AlgoExpert in just C++, AlgoExpert Solutions.
It begins with an array of positive integers designating how many jumps you can go forward to reach the end from each position. The target is to solve the path of jumps that give the fewest jumps. This is almost knapsack, and thinking it this way makes life a lot easier. Below is the the problem statement and solution.
2021 GameStonk
It has been shown with a high correlation that turning memes into integers, and ordering them chronologically gives you data that you can predict the value of GameStop stock with 70% confidence. Every meme gives a value indicating how many memes forward you can jump. You must move chronologically. Once you have the shortest path through all of the memes, you can use this information to put memes into google reverse image search. If there is more green than red, you invest now. If there is more red than green, you hold. If there is an equal amount of green and red, you have hit the lotto, you should sell your home and buy call options.
Description
Given all the values of memes in chronological order. Then the corresponding meme names, find the path of memes A->B->C->D such that you take the shortest path to Gamestop riches.
Input
You will receive an integer n that will correspond to the number of memes you will receive on the first line. You will then receive the meme’s value v_i space delimitted on the same line. Then you will receive the meme names. Meme names will be in the regex [A-z]* and have length less than or equal to 15 ascii characters.
n
v_1 v_2 v_3 ... v_n
m_1 m_2 m_3 ... m_n
Constraints
\[1 \leq n \leq 10000\] \[1 \leq v_i \leq 100\] \[m_i \in [A-z]*\]Output
p_1 p_2 ... p_k
Where you can legally jump from \(p_1\)->\(p_2\)->…\(p_k\), where \(p_k = m_n\).
Disclaimer
This is not a financial strategy, advice, or anything more than a problem statement for the USC Codeathon.
Solution
/* Copyright 2021
** Justin Baum
** MIT License
*/
#include <vector>
#include <iostream>
#include <string>
#include <climits>
using namespace std;
vector<string> min_number_of_jumps(vector<int> &array, vector<string> &names) {
int size = array.size();
vector<string> solution;
int steps = array[0];
int max_reach = array[0];
int max_index = 0;
solution.push_back(names[0]);
for (int i = 1; i < array.size() - 1; i++) {
int new_reach = i + array[i];
--steps;
if (new_reach > max_reach) {
max_index = i;
max_reach = new_reach;
}
if (steps == 0) {
solution.push_back(names[max_index]);
steps = max_reach - i;
}
}
return solution;
}
int main(void) {
int n;
cin >> n;
vector<int> array;
vector<string> names;
for(int _ = 0; _ < n; ++_) {
int x;
cin >> x;
array.push_back(x);
}
for(int _ = 0; _ < n; ++_) {
string x;
cin >> x;
names.push_back(x);
}
auto x = min_number_of_jumps(array, names);
//cout << x.first << endl;
for(string name : x) {
cout << name << " ";
}
cout << names[n - 1];
cout << endl;
return 0;
}
Custom Checker
/* Copyright 2021
** Justin Baum
** MIT License
** AlgoExpert Solutions
*/
// Start of BODY
/**
* TestStruct members::
* testcase_id [size_t] ID of the test-case
* testcase_input_path [string] File path to test-case input
* testcase_output_path [string] File path to test-case output generated by the problem solver
* testcase_expected_output_path [string] File path to test-case expected output to be matched with
* testcase_error_path [string] File path to test-case STDERR
* metadata_file_paths [vector<string>] File paths to Question metadata (Extra files usually used for defining traning sets)
* submission_code_path [string] File path to submission source code
* submission_language [string] Language token of submission
* testcase_result [bool] Set to true if test-case output matches test-case expected output. Matching is done line by line
* testcase_signal [size_t] Exit code of the test-case process
* testcase_time [float] Time taken by the test-case process in seconds
* testcase_memory [size_t] Peak memory of the test-case process determined in bytes
* data [string] <Future use>
*
*
* ResultStruct::
* result [bool] Assign test-case result. true determines success. false determines failure
* score [float] Assign test-case score. Normalized between 0 to 1
* message [string] Assign test-case message. This message is visible to the problem solver
**/
void run_custom_checker(const TestStruct t_obj,
ResultStruct &r_obj) {
//Don't print anything to STDOUT in this function
//Enter your custom checker scoring logic here
ifstream expected, output, input;
map<string, int> indexOfMeme;
vector<int> jumps;
vector<string> memes;
int n;
input.open(t_obj.testcase_input_path);
input >> n;
for (int i = 0; i < n; ++i) {
int x;
input >> x;
jumps.push_back(x);
}
for (int i = 0; i < n; ++i) {
string m;
input >> m;
memes.push_back(m);
indexOfMeme[m] = i;
}
expected.open(t_obj.testcase_expected_output_path);
int answer = 0;
string memethrow;
while (expected >> memethrow) {
++answer;
}
output.open(t_obj.testcase_output_path);
int index = 0;
int count = 0;
r_obj.message = "";
string last = "";
while (output >> memethrow) {
++count;
auto x = indexOfMeme.find(memethrow);
r_obj.message += memethrow;
if (x == indexOfMeme.end()) {
r_obj.result = false;
r_obj.score = 0.0;
r_obj.message += "You used an illegal meme.";
return;
}
int jumpss = jumps[x->second];
if (x->second > index + jumpss) {
r_obj.result = false;
r_obj.score = 0.0;
r_obj.message = "You made an illegal jump.";
return;
}
index = x->second + jumpss;
last = memethrow;
}
if (last != memes[n-1]) {
r_obj.result = false;
r_obj.score = 0.0;
r_obj.message = "You didn't jump land on the last meme.";
return;
}
if (count > answer) {
r_obj.result = false;
r_obj.score = 0.0;
r_obj.message = "You had too many jumps.";
return;
}
if (index < n) {
r_obj.result = false;
r_obj.score = 0.0;
r_obj.message = "Didn't make it to the end";
return;
}
if (count < answer) {
r_obj.result = false;
r_obj.score = 0.0;
r_obj.message = "IF YOU SEE THIS LET SOMEONE KNOW";
return;
}
r_obj.result = true;
r_obj.score = 1.0f;
r_obj.message = "Success";
}
// End of BODY