I will go through the solutions for the Problems A to D1, and my approach/implementation for them.
These are the list of my macros and typedefines, that you might find in code. I have tried to remove most of them, but if I haven’t this is for your reference.
Headers
#include<bits/stdc++.h>
#pragma GCC optimize "trapv"
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define REP(n) for(int i = 0; i < n; i++)
#define all(p) p.begin(), p.end()
#define count_1(p) __builtin_popcountll(p)
#define count_0(p) __builtin_ctzll(p)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
template<class X=int>inline X min(X a,X b,X c){return min(min(a,b),c);}
template<class X=int>inline X min(X a,X b,X c,X d){return min(min(a,b,c),d);}
template<class X=int>inline X max(X a,X b,X c){return max(max(a,b),c);}
template<class X=int>inline X max(X a,X b,X c,X d){return max(max(a,b,c),d);}
template<class X=int>inline X mid(X s,X e){return (s+(e-s)/2);}
template<class X=int>inline X len(X s,X e){return (e-s+1);}
const int MOD = 1e9 + 7;
const int INF = 987654321;
const bool TESTCASES = 1;
const bool CODEJAM = 1;
void solve() {
}
signed main() {
clock_t start = clock();
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int T = 1;
if(TESTCASES) cin >> T;
for(int t = 1; t <= T; t++) {
if(CODEJAM) cout << "Case #" << t << ": ";
solve();
}
cerr << (double)(clock() - start)/CLOCKS_PER_SEC << "\n";
return 0;
}
Travel Restrictions:
Problem
Prerequisites: DFS (for my implementation)
This can also be done with just a couple of loops. Refer the official editorial.
The problem is pretty straight forward and implementation based.
Let n be the number of cities.
Prepare an adjacency matrix bool G[n][n]
G[i][j] is true if and only if I[i] is true and O[j] is true. Remember that we are constructing a directed graph, and G[i][j] is true, if there exists a directed edge from i to j.
Now that the graph is prepared, loop through all the cities and run a DFS to see what other cities are reachable from here and store it in result[i], for the city i.
Code
vector<vector<bool>> adj;
vector<vector<bool>> reach;
void dfs(int r, int u) {
reach[r][u] = 1;
for(int v = 0; v < adj.size(); v++) if(adj[u][v] and not reach[r][v])
dfs(r, v);
}
void solve() {
cout << "\n";
int n;
cin >> n;
string I, O;
cin >> I >> O;
adj.assign(n, vector<bool>(n));
reach.assign(n, vector<bool>(n));
adj[0][1] = O[0] == 'Y' and I[1] == 'Y';
for(int i = 1; i < n - 1; i++) {
adj[i][i + 1] = O[i] == 'Y' and I[i + 1] == 'Y';
adj[i][i - 1] = O[i] == 'Y' and I[i - 1] == 'Y';
}
adj[n - 1][n - 2] = O[n - 1] == 'Y' and I[n - 2] == 'Y';
for(int i = 0; i < n; i++) {
dfs(i, i);
}
for(auto &v : reach) {
for(bool x : v)
cout << (x ? 'Y' : 'N');
cout << "\n";
}
}
Alechemy:
Problem
Prerequisites: Ad-Hoc, Observations.
WLOG, let us assume the number of As in the string is less than the number of Bs.
Observe that no matter the position of A, we can always combine all the As.
Some Example Strings:
AAAABBBBB
ABBBABBBA
AABBAABBB
BBBAAABBB
We can clearly extinguish all the As if the number of As is less than the number of Bs. Now after we extinguish all the As, if we end up with more than 1 B, there is no way these can be combined into a single stone. From this, we can clearly see that, if abs(s.count('A') - s.count('B') == 1, then the answer is YES, else it is NO.
Code
void solve() {
int n;
cin >> n;
int cnt[2] = {};
for(int i = 0; i < n; i++) {
char x;
cin >> x;
cnt[x - 'A']++;
}
cout << (abs(cnt[0] - cnt[1]) == 1 ? "Y\n" : "N\n");
}
Timber:
Problem
Prerequisites: Arrays, DP.
Not surprising, but I got a WA verdict for this. I will anyways write down my implementation, if you find a flaw do let me know
Okay. So my approach to this problem is very very rusty. The runtime was 15 seconds. I will go through my approach anyways, but I’m pretty sure there is waaaayyy better solution.
Disclaimer: This is not a very clean approach.
Claim: The contiguous portion that we cut must be:
- All cut right
- All cut left
- First portion cut right, and the next portion cut left
This is true because, once we make a left cut there is no way of extending this block with a right cut on the subsequent trees.
Implementation:
Sort the array based on increasing p.
First, we will pre-compute the maximum possible cut, ending at a given coordinate.
See the code for the transision and implementation.
Next, we try to cut down a tree to the right, and see where it lands. I will call this coordinate end which is p_i + h_i. To this we add the maximum possible left-cut block that is ending at the coordinate end, and append it to the answer. Now, if there is a tree at coordinate end, we can cut this tree to the right, update end, and continue the same process. So as long as we see a tree at end, we update the answer for this state, and cut the tree that is at end to the right and continue.
Reverse the given array and call the same function for all left cuts.
I have hashed the coordinate of a tree (p_i) to it’s index in my array (i).
Code
struct Tree {
int p, h;
bool operator<(Tree o) {
return p < o.p;
}
};
int getmax(vector<Tree> &trees) {
int n = trees.size();
int best = 0;
vector<bool> vis(n);
unordered_map<int, int> indexOf;
unordered_map<int, int> maxEndingHere;
for(int i = 0; i < n; i++) indexOf[trees[i].p] = i;
for(int i = n; i--;) {
maxEndingHere[trees[i].p - trees[i].h] = trees[i].h
+ maxEndingHere[trees[i].p];
}
for(int i = 0; i < n; i++) {
if(vis[i]) continue;
int startsAt = trees[i].p, endsAt = trees[i].p + trees[i].h;
vis[i] = 1;
while(indexOf.find(endsAt) != indexOf.end()) {
auto it = indexOf.find(endsAt);
best = max(best, endsAt - startsAt + maxEndingHere[endsAt]);
endsAt += trees[it->second].h;
vis[it->second] = 1;
}
best = max(best, endsAt - startsAt + maxEndingHere[endsAt]);
}
return best;
}
void solve() {
int n;
cin >> n;
vector<Tree> trees(n);
for(int i = 0; i < n; i++) cin >> trees[i].p >> trees[i].h;
sort(all(trees));
int best = getmax(trees);
reverse(all(trees));
cout << max(best, getmax(trees)) << "\n";
}
Running on Fumes - Chapter 1
(Does sound like a good movie title, which has a sequel planned)
Problem
Prerequisites: Segment Trees (for my implementation).
My solution is pretty simple. Let’s have an auxiliary array B, where B_i stores the minimum cost to reach index i, initialized with \infty (meaning it’s not reachable).
Obviously B_1 = 0. (1-based indexing).
Now, we can also say that any index B_j for 1 < j \leq m + 1 can be reached with 0 cost.
So we update B[2 ... m+1] = 0.
Process the array from left to right. (Skip the first position, as we just processed it).
If C_i = 0, there is nothing to do here, just continue.
Otherwise, we can refuel at this position for a cost C_i. This means, we can reach the position i with B_i cost, and pay an extra C_i for a refuel . After the refuel, we can reach indices i < j \le i + m + 1 with a cost B_i + C_i.
Update B_j = \text{min}(B_j, B_i + C_i)
Note that if j was already reachable for a cheaper cost, this update at j has no effect.
Cool. This sounds legit, but when we look at the complexity, it’s \mathcal O(mn), and that’s definitely not going to run under 6 minutes. To handle the range updates and point queries efficiently, I used a segment tree. This boils the complexity down to a sweet \mathcal O(n \log n).
Code
Segment Tree Class
class SG {
vector<ll> T;
int n;
public:
SG(int n) {
this->n = n;
T.assign(2*n, INF);
}
void update(int l, int r, ll v) {
for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) T[l] = min(T[l], v), l++;
if(r & 1) T[--r] = min(T[r], v);
}
}
}
ll get(int p) {
ll ret = INF;
for(p += n; p > 0; p >>= 1) ret = min(ret, T[p]);
return ret;
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<int> C(n);
for(int i = 0; i < n; i++) cin >> C[i];
SG sg(n);
sg.update(0, m, 0);
for(int i = 1; i < n; i++) {
if(C[i] == 0) continue;
sg.update(i + 1, min(i + m, n - 1), sg.get(i) + C[i]);
}
cout << (sg.get(n - 1) == INF ? -1 : sg.get(n - 1)) << "\n";
}
Running on Fumes - Chapter 2
Not attempted
.
,