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 `A`

s in the string is less than the number of `B`

s.

Observe that no matter the position of `A`

, we can always combine all the `A`

s.

Some Example Strings:

`AAAABBBBB`

`ABBBABBBA`

`AABBAABBB`

`BBBAAABBB`

We can clearly extinguish all the `A`

s if the number of `A`

s is less than the number of `B`

s. Now after we extinguish all the `A`

s, 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*