Facebook HackerCup 2020 - EDITORIAL (Unofficial)

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

15 Likes

Hain…1st one is graph my bad , I solved only 2nd . Btw good editorial anee :v:

2 Likes

1st one

 string a,b; // I ,O
    cin >> t;
    for(int cases=1;cases<=t;cases++){
        cout << "Case #" << cases << ":\n";
        cin >> n >> a >> b;
        bool ans[n][n];

        for(i=0;i<n;i++)
            memset(ans[i],0,sizeof(ans[i]));

        for(i=0;i<n;i++){
            ans[i][i]=true;
            for(j=i+1;j<n;j++){
                if(b[j-1]=='N' || a[j]=='N')
                    break;
                ans[i][j]=true;
            }

            for(j=i-1;j>=0;j--){
                if(b[j+1]=='N' || a[j]=='N')
                    break;
                ans[i][j]=true;
            }

        }

        for(i=0;i<n;i++){
            for(j=0;j<n;j++)
                if(ans[i][j])
                    cout << "Y";
                else
                    cout << "N";
            cout << "\n";
        }
    }

solution of l_returns

For D1 we can refer to editorial of this problem.
They are very much similar.

1 Like

Ohh nice. Anyways 1 problem is enough for qualification xD.

In C, I think I forgot to add all cut left contribution to the answer. :man_facepalming:.

1st one can be done without graph too, first mark all the cells of N*N matrix Y. then if incoming to some city i, is not allowed then mark column i ‘N’, and for all the rows j< i, mark cells >i, ‘N’ and for j>i, mark cells<i, ‘N’ and similarly for outgoing. After all this mark all the diagonal ‘Y’

1 Like

That’s right. What you have said is essentially a depth first search. As there is only one edge per node, we can just use a while loop for the dfs here.

If you write graph as pre-requisite then this ques will be not considered easy :sweat_smile:

2 Likes

Ohh my bad. I’ll change that!

My solution to 1st problem

#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define vii vector<ll> 
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int MOD = 1e9 + 7;

void solve(){
	int n;
	cin >> n;
	char I[n], O[n], ans[n][n];
	for(int i = 0; i < n; ++i)
		cin >> I[i];
	for(int i = 0; i < n; ++i)
		cin >> O[i];
	for(int i = 0; i < n; ++i){
		for(int j = i; j < n; ++j){
			if(i == j) ans[i][j] = 'Y';
			else if(O[i] == 'N' || I[j] == 'N') ans[i][j] = 'N';
			else if(O[i] == 'Y' && I[j] == 'Y' && ans[i][j-1] == 'Y' && O[j-1] == 'Y') ans[i][j] = 'Y';
			else ans[i][j] = 'N'; 
		}
	}
	for(int i = n - 1; i >= 0; --i){
		for(int j = i - 1; j >= 0; --j){
			if(O[i] == 'N' || I[j] == 'N') ans[i][j] = 'N';
			else if(O[i] == 'Y' && I[j] == 'Y' && ans[i][j+1] == 'Y' && O[j+1]== 'Y') ans[i][j] = 'Y';
			else ans[i][j] = 'N';
		}
	}
	for(int i = 0; i < n; ++i){ 
		for(int j = 0; j < n; ++j){
			cout << ans[i][j];
		}
		cout << "\n";
	}
}

int main(){
	fast;
	int t;
	cin >> t;
	for(int tt = 1; tt <= t; ++tt){
		cout << "Case #" << tt << ":" << "\n";
		solve(); 
	}
	cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
	return 0;
1 Like

For D1, I used multiset, instead of segment trees, to store the previous m values and also in set the smallest value is always in the beginning. So it made the implementation more EASIER :slight_smile:

2 Likes

That’s nice. I tend to avoid multiset, because I had a bad experience with it once. Apparently s.erase(x) erases all instances of x, which I didn’t know. To erase a single instance:

auto it = s.find(x);
s.erase(it);

The moment I realized I’m handling range updates and point queries, segment tree was my first thought.

This can also be done in \mathcal O(n) by using a deque.

2 Likes

Ah, Segment trees! I had O(n*m) approach for D1, that was easy, But I didn’t know how to optimize.

2 Likes

My method for B was different. I didn’t realize it was that easy but you can look at my submission-

Click
'''Author- Akshit Monga'''
import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')

t=int(input())
for _ in range(t):
    n=int(input())
    s=input()
    stack=[]
    ans="Y"
    for i in s:
        stack.append(i)
        if len(stack)>=3:
            a=0
            b=0
            for g in stack[-3:]:
                if g=='A':
                    a+=1
                else:
                    b+=1
            if a==0 or b==0:
                continue
            stack.pop()
            stack.pop()
            stack.pop()
            if a>b:
                stack.append('A')
            else:
                stack.append('B')
    if len(stack)>1:
        ans='N'
    print("Case #", end="")
    print(_ + 1, end="")
    print(":",ans)

Code for A-

Click
'''Author- Akshit Monga'''
import sys

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

t=int(input())
for _ in range(t):
    n=int(input())
    a=input()
    b=input()
    mat=[[-1 for x in range(n)] for y in range(n)]
    for i in range(n):
        mat[i][i]='Y'
    for i in range(n):
        if a[i]=='N':
            for j in range(n):
                if mat[j][i] == -1:
                    mat[j][i] = 'N'

    for i in range(n):
        if b[i]=='N':
            for j in range(n):
                if mat[i][j] == -1:
                    mat[i][j] = 'N'
    for i in range(n):
        boo=1
        for j in range(i+1,n):
            if boo:
                if mat[i][j]==-1:
                    mat[i][j]='Y'
                elif mat[i][j]=='N':
                    boo=0
                if b[j]=='N':
                    boo=0
            else:
                if mat[i][j]==-1:
                    mat[i][j]='N'
    for i in range(n):
        boo=1
        for j in range(i-1,-1,-1):
            if boo:
                if mat[i][j]==-1:
                    mat[i][j]='Y'
                elif mat[i][j] == 'N':
                    boo = 0
                if b[j]=='N':
                    boo=0
            else:
                if mat[i][j] == -1:
                    mat[i][j] = 'N'
    print("Case #", end="")
    print(_ + 1, end="")
    print(": ")
    for i in range(n):
        for j in range(n):
            print(mat[i][j],end="")
        print()
1 Like

Probably A silly question, but I would be glad to know that on which site Facebook hackercup is conducted and other details are published😅 @aneee004

I thought of something like this for B initialy!

Also, I assumed your language was C++ :P. So you use Python?

1 Like

Ya…I know both C++ and Python but generally use Py because I feel syntax is easier in Py.

1 Like

Lol. It’s obviously conducted by Facebook. You can click any of the problem links. It will take you to the area. The final round is on-site. (But not this year).

1 Like

C was indeed beautiful I was not able to solve it ! I overdid it Thinking it is a Hackercup question ! I am feeling stupid now that I was not able to convince myself that a combined interval will be a series of trees falling forward followed by trees falling backwards !!! Happy to upsolve C and D1 using your editorial thanks man

1 Like

That means a lot. Thanks! Do see the official editorial for D1. It has a better implementation with a deque! I’m still not able to see what’s wrong with my C though :mask:,