I'll focus on time complexity, key points, and spots where it's easy to make mistakes.
Personal Information Retention Period - LV. 1, Implementation
Coding Test Practice - Personal Information Retention Period
Explanation
This is a typical date calculation problem.
I looked at several solutions, and the one that seems easiest
is converting every date into days and comparing them.
Also, since each letter has its own Term,
store the Term in an int array indexed by
the ASCII code - 'A'.
Now just add the matching Term to each date
and judge it as required. (More on this below)
The number ranges are so small
that I don't think the time complexity needs separate analysis.
+) Since the split positions in the strings are fixed, in C++
I think it's easier to just cut them with substr
rather than writing a split function.
Easy mistakes
You need to be careful about the exact condition for putting an entry into the answer vector after adding the dates.
To make it simple, say the collection date is day n and the retention period is 1 day.
The information must still be kept through day n,
so the expiry date has to be day n+1.
So expiry date = collection date + retention period holds.
And if the expiry date is greater than or equal to Today,
the information has already expired as of today, so we put it into the answer vector.
Source code:
#include <string> #include <vector> using namespace std; int today; int term[26]; vector<int> ans; vector<int> solution(string todays, vector<string> terms, vector<string> privacies) { // change to Day today = stoi(todays.substr(0, 4))*12*28 + stoi(todays.substr(5,2))*28 + stoi(todays.substr(8)); // make Term for (string s: terms) term[s.front()-'A'] = stoi(s.substr(2))*28; // change to day and add term for (int i=1; i<= privacies.size(); i++) { string s = privacies[i-1]; int day = 0; // day: expiry date day += term[s.back()-'A']; day += stoi(s.substr(0, 4)) * 12 * 28; day += stoi(s.substr(5, 2)) * 28; day += stoi(s.substr(8, 2)); if (day <= today) ans.push_back(i); } return ans; }
Delivery and Pickup - Lv. 2, Greedy, Implementation
Coding Test Practice - Delivery and Pickup
Greedy target, explanation
You should always deliver to and pick up from the farthest house first.
To prove it roughly,
the minimum number of visits to the farthest house is fixed.
If you visit the farthest house first, you can keep the number of trips to a minimum,
but if you start with other houses and then visit the far one,
you may have to visit the far house again.
In that case the travel distance keeps growing.
First, let's deliver to the farthest house first.
Also, if there's room left to deliver, drop things off on the way.
Once all deliveries are done, the truck is empty.
Now on the way back, just pick up as much as possible starting from the farthest house.
Now let's talk about the implementation.
n is up to 100,000, so we need to finish in a small constant number of passes.
So it looks good to solve the problem by iterating from the last house to the first.
Note that the elements of deliveries and pickups are at most 50.
Even multiplying the element size by n gives about 5 million,
so it's fine to deliver and pick up cap boxes at a time at each house.
And if, at the end, fewer than cap boxes are left over,
store that in a variable, and when you move to the next house, assume they were already delivered/picked up and continue.
Time complexity
d = size of an element in deliveries
p = size of an element in pickups
Let's consider the worst case
cap = 1, d = p = 50, n = 100,000
That's 5 million, so it easily runs in time.
Source code
#include <string> #include <vector> #include <algorithm> using namespace std; typedef long long ll; // tp: boxes already picked up // td: boxes already delivered ll tp, td; ll ans; ll solution(int cap, int N, vector<int> pick, vector<int> dlv) { for (int i=N-1; i>=0; i--) { int cnt = 0; // steps int p = pick[i]; p -= tp; // boxes to pick up int d = dlv[i]; d -= td; // boxes to deliver tp = td = 0; // start delivering and picking up while (p > 0 || d > 0) { p -= cap; d -= cap; cnt += (i+1)*2; } // store what was delivered/picked up for other houses tp -= p, td -= d; // add the steps ans += cnt; } return ans; }
Emoticon Discount Event - Lv. 2, Brute force
Coding Test Practice - Emoticon Discount Event
Explanation
This problem was the easiest one for me.
Since the length of emotions is 7, you can consider every combination of 10, 20, 30, 40%.
Using 7 for loops gets too messy, so let's use a recursive function.
Then for each case, have each user buy emoticons, sign them up for the service if they exceed a certain amount, and compare.
Time complexity
e = length of emotions
u = length of users
I'm getting lazy, so calculate it yourself
Source code
#include <string> #include <vector> using namespace std; vector<vector<int>> U; vector<int> E, sales; int n, m; pair<int, int> result; void f() { pair<int, int> info = {0, 0}; for (auto v: U) { int byS = v[0], mx = v[1]; int sum = 0; for (int i=0; i<m; i++) if (byS <= sales[i]) sum += E[i]*(100-sales[i])/100; if (sum >= mx) info.first++; else info.second += sum; } result = max(result, info); } void C(int idx) { if (idx == m) { f(); return; } for (int i=10; i<=40; i+=10) { sales.push_back(i); C(idx+1); sales.pop_back(); } } vector<int> solution(vector<vector<int>> tU, vector<int> tE) { U = tU, E = tE; n = U.size(), m = E.size(); C(0); return {result.first, result.second}; }
Representable Binary Tree - Lv.3, Divide and conquer
Coding Test Practice - Representable Binary Tree
Explanation
In a perfect binary tree, all leaf nodes are on the same level. Also,
what matters is that the number of nodes in a perfect binary tree is fixed by its level.
If the tree height is H, the number of nodes is 2^H-1.
And the number of nodes is the length of the binary number.
So after converting the number to binary, add dummy nodes (0s) to the front of it to make up the missing length.
(It has to go in front because adding them anywhere else changes the number)
After adding the 0s, the tree condition fails when
a parent node is 0 but one of its children is 1.
You can check this with divide and conquer.
Time complexity
Let's use the master theorem
T(n) = T(n/2) + n, so
it's O(n).
Source code
#include <string> #include <vector> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; string tree; int n; vector<int> rtn; bool isAllZero(int lo, int hi) { for (int i=lo; i<=hi; i++) if (tree[i] != '0') return false; return true; } bool isBinaryTree(int lo, int hi) { if (lo == hi) return true; int mid = (lo+hi)>>1; if (tree[mid] == '0') { if (!isAllZero(lo, mid-1) || !isAllZero(mid+1,hi)) return false; } else { if (!isBinaryTree(lo,mid-1) || !isBinaryTree(mid+1,hi)) return false; } return true; } string toBinary(ll n) { string rtn = ""; while (n != 0) { rtn += n%2+'0', n /= 2; } ll len = 1; while (len <= rtn.size()) len *= 2; len -= 1; len -= rtn.size(); while (len--) rtn += '0'; reverse(rtn.begin(), rtn.end()); return rtn; } vector<int> solution(vector<long long> numbers) { for (ll v: numbers) { tree = toBinary(v); n = tree.size(); if (n%2 == 0 || tree[n/2]=='0') { rtn.push_back(0); continue; } rtn.push_back(isBinaryTree(0, n-1)); } return rtn; }
Table Merge - Lv.3, Disjoint set, Implementation
Coding Test Practice - Table Merge
Explanation
Use a disjoint set and every time cells are merged,
union them together.
But it turns out there was no real need for a disjoint set.
You can just keep a single array and use it like a disjoint set.
In a disjoint set, when you merge two sets,
joining one element from each
merges the two sets.
To implement this with an array,
you have to iterate over every element of one of the two sets and merge them into the other set.
Also, when splitting a set apart, if the tree gets cut in the middle of a disjoint set,
the child nodes can no longer reach the root node.
That is, the children of the cut node can no longer be split off.
So when splitting, you have to iterate over all elements, collect the set's elements separately,
and then split them all at once.
If you implement this with an array, just like merging, you iterate over all elements and split them one by one.
Time complexity
Iterating over all elements takes the longest, so
simply
O(N^2)
is the conclusion.
Source code
I solved it with a disjoint set.
#include <string> #include <vector> #include <sstream> #include <iostream> #define f first #define s second using namespace std; typedef pair<int, int> pii; struct Disjoint_set { public: pii parent[51][51]; Disjoint_set() { for (int i=1; i<=50; i++) for (int j=1; j<=50; j++) parent[i][j] = {i, j}; } pii root(pii x) { if (parent[x.f][x.s] == x) return x; return parent[x.f][x.s] = root(parent[x.f][x.s]); } void uni(pii tx, pii ty) { pii x = root(tx), y = root(ty); if (x == y) return; parent[y.f][y.s] = x; } bool isUni(pii x, pii y) { return root(x) == root(y); } }; string table[51][51]; vector<string> ans; Disjoint_set uf = Disjoint_set(); vector<string> split(string s, char c) { vector<string> rtn; stringstream ss(s); string buffer; while (getline(ss, buffer, c)) rtn.push_back(buffer); return rtn; } vector<string> solution(vector<string> commands) { for (auto s: commands) { vector<string> v = split(s, ' '); if (v[0] == "UPDATE" && v.size() == 4) { string value = v[3]; auto [r, c] = uf.root({stoi(v[1]), stoi(v[2])}); table[r][c] = value; } else if (v[0] == "UPDATE" && v.size() == 3) { string value1 = v[1], value2 = v[2]; for (int i=1; i<=50; i++) { for (int j=1; j<=50; j++) { auto [r, c] = uf.root({i, j}); if (table[r][c] == value1) table[r][c] = value2; } } } else if (v[0] == "MERGE") { int r1 = stoi(v[1]), c1 = stoi(v[2]), r2 = stoi(v[3]), c2 = stoi(v[4]); pii root1 = uf.root({r1, c1}), root2 = uf.root({r2, c2}); if (table[root1.f][root1.s].empty()) uf.uni({r2, c2}, {r1, c1}); else uf.uni({r1, c1}, {r2, c2}); } else if (v[0] == "UNMERGE") { int v1 = stoi(v[1]), v2 = stoi(v[2]); auto [r, c] = uf.root({v1, v2}); string temp = table[r][c]; vector<pii> merged; for (int i=1; i<=50; i++) for (int j=1; j<=50; j++) if (uf.isUni({r, c}, {i, j})) merged.push_back({i, j}); for (auto [f, s]: merged) { table[f][s] = ""; uf.parent[f][s] = {f, s}; } table[v1][v2] = temp; } else { auto [r, c] = uf.root({stoi(v[1]), stoi(v[2])}); ans.push_back(table[r][c].empty() ? "EMPTY" : table[r][c]); } } return ans; }
Maze Escape Command - Lv. 3, Greedy
Coding Test Practice - Maze Escape Command
Explanation
You could talk about this in all sorts of scattered ways,
but it looks like a greedy problem,
and in the end the key point is that, in the order d, l, r, u,
you must always move if a certain condition is met.
The impossible case is when the condition still isn't met even after moving all k times.
The condition is that the next coordinate doesn't leave the grid,
and that with the remaining moves you can still reach the destination by the shortest path.
Time complexity
Surprisingly, you can move to each next spot in O(1).
Since this repeats K times, the time complexity is
O(K)
overall.
Source code
#include <string> #include <vector> using namespace std; int n, m, r, c, k; int dx[] = {1, 0, 0, -1}, dy[] = {0, -1, 1, 0}; string ds = "dlru", s; bool isPsb(int x, int y) { return x > 0 && x <= n && y > 0 && y <= m && k >= abs(x-r) + abs(y-c); } string solution(int tn, int tm, int x, int y, int tr, int tc, int tk) { n = tn, m = tm, r = tr, c = tc, k = tk; while (k--) { bool isGo = false; for (int i=0; i<4; i++) { int nx = x+dx[i], ny = y+dy[i]; if (!isPsb(nx, ny)) continue; x = nx, y = ny, s += ds[i]; isGo = true; break; } if (!isGo && k == 0) return "impossible"; } return s; }
Dropping 1, 2, 3 - Lv. 4
Coding Test Practice - Dropping 1,2,3
Explanation
Cycle the path to the child nodes, moving from the one with the smallest number to the largest.
I used an adjacency list with the child nodes sorted,
and made an idx array per node, incrementing idx every time we move.
When idx reaches the end, move it back to 0.
Now look at the process of dropping into leaf nodes:
the order in which things fall into the leaf nodes is already fixed.
And since we need to minimize the numbers dropped, assume each number is 3
and drop nodes one at a time, checking whether we can produce an answer.
There are 3 cases to check while dropping numbers.
A. An answer can be produced right now.
B. An answer can't be produced yet, but it's still possible
C. There's no possibility of producing an answer at all
Looking at each case:
For A, when all numbers dropped into every node are assumed to be 3,
the node's sum is greater than target[node], and every node must satisfy this.
In this case an answer can be produced, so we move on to the next step.
B is when, for some node, even assuming all dropped numbers are 3,
there's a case where it's still less than target[node].
Here we can assign more numbers to bring it up to target[node] or above,
so there's still a chance, and we need to keep assigning numbers and observing.
C is when, for some node, even assuming all numbers dropped into it
are 1, it's still greater than target[node].
In this case there's no possibility of producing an answer.
Return {-1} and end the algorithm.
Now let's look at what happens after A.
The answer must be the lexicographically smallest one, so
starting from the first dropped number, assign values from 1 to 3,
and for each assigned value, assuming the rest are 3, the remaining count alone
just needs to satisfy at least target[node] - current number.
Once all numbers are assigned, return the answer.
Time complexity
Dropping a number can take up to O(N).
Dropping and checking whether an answer is possible is O(N).
And the possibility check and dropping can repeat up to T/3*N times.
(T: size of an element in target)
And there are at most T/3N dropped numbers, so
we check all T/3N of them while assigning numbers.
Putting it all together
O(T/3N(N+N) + T/3*N)
= O(N^2 * T)
overall.
The worst case is
N = 101, T = 100, so
it comes out to about a million and easily runs in time.
Source code
#include <string> #include <vector> #include <algorithm> #include <iostream> using namespace std; vector<int> tree[101], cnts(101), order, ans; int idx[101]; int n; void dropCnt(int node) { // is Leaf Node (base case) if (tree[node].empty()) { cnts[node]++; order.push_back(node); return; } // is Internal Node (recusion case) dropCnt(tree[node][idx[node]++]); // if child node is last node if (idx[node] == tree[node].size()) idx[node] = 0; } int isPsb(const vector<int>& target) { for (int i=1; i<=n; i++) { // Can't make answer if (cnts[i] > target[i-1]) return -1; // yet impossible if (cnts[i]*3 < target[i-1]) return 0; } // possible return 1; } vector<int> solution(vector<vector<int>> edges, vector<int> target) { // making Tree for (auto v: edges) { tree[v[0]].push_back(v[1]); n = max(n, max(v[0], v[1])); } for (auto& v: tree) sort(v.begin(), v.end()); // checking Possibility while (true) { int isPossible = isPsb(target); // Can't make answer if (isPossible == -1) return {-1}; // isPossible if (isPossible == 1) break; // yet impossible dropCnt(1); } // determine Number for (int i=0; i<order.size(); i++) { int node = order[i]; int& cnt = cnts[node]; for (int j=1; j<=3; j++) { if ((cnt-1)*3 >= target[node-1]-j) { ans.push_back(j); cnt -= 1; target[node-1] -= j; break; } } } return ans; }