Facebook HackerCup 2020 - EDITORIAL (Unofficial)

editorial
, , ,
28

Obviously I will advance lol. I just asked, if they are done with the formalities

29

I don’t think so yet. You can confirm them by sending a mail. But whatever they do, there can’t be full fairness.

1 Like
30

Question B boiled to such a simple logic that it very easy to overthink given that it is a Hacker up question.

2 Likes
31

My solution based on loops for the problem Travel Restrictions:

Official Editorial: Solutions | Meta Hacker Cup - 2020 - Qualification Round

32

C problem can be done by dfs, just connect all components and find the longest one
For n elements 2*n nodes will be made
(pi-hi,pi)
(pi,pi+hi)
Then we will connect all the nodes whose second is equal to first of another
A disconnected tree will be generated
Then we run dfs and find the longest connected interval
Correct me if I am wrong!

3 Likes
33

I haven’t follow your code in detail but is your “maxEndingHere” variable really pretending to store the max ending there? Because if I’m not wrong that’s not the case

1 Like
34

Can we solve D1 using DiJIsktra algorithm by taking m nodes as connected for every i (except which contains 0) and then after that see if the last element of distance array for answer. @carre

35

yes some kind of dijkstra was my approach to D2 and of course D1 is a particular case of D2

36

I tried with it test cases were passing but the final verdic was WA. So is there were any edge cases?
My code

37

I don’t remember to have dealt with special cases. Anyway you can stress your solution with random generated testcases and compare your output with the output obtained from an accepted solution

1 Like
38

It seems to be right. I am storing the maximum ending at a coordinate, if all the trees are cut to the left. So tree i would fall to the left, and end at p_i - h_i. The maximum possible length would be h_i + dp_{p_i}, where dp is the maxEndingHere variable.

I removed the inner while loop, and cleaned the code a bit. The runtime has not improved, and still WA. (On the same test cases I guess).

Code 
struct Tree {
	int p, h;
	bool operator<(Tree o) {
		return p < o.p;
	}
};

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 = 0;
	unordered_map<int, int> maxEndingHereLeft, maxEndingHereRight;
	for(int i = n - 1; i >= 0; i--) {
		maxEndingHereLeft[trees[i].p - trees[i].h] = trees[i].h + maxEndingHereLeft[trees[i].p];
		best = max(best, maxEndingHereLeft[trees[i].p - trees[i].h]);
	}
	for(int i = 0; i < n; i++) {
		maxEndingHereRight[trees[i].p + trees[i].h] = maxEndingHereRight[trees[i].p] + trees[i].h;
		best = max(best, maxEndingHereRight[trees[i].p + trees[i].h]);
	}
	for(int i = 0; i < n; i++) {
		// Cut the tree i to the right and check
		best = max(best, trees[i].h + maxEndingHereLeft[trees[i].p + trees[i].h] + maxEndingHereRight[trees[i].p]);
		// Cut the tree i to the left and check
		best = max(best, trees[i].h + maxEndingHereLeft[trees[i].p] + maxEndingHereRight[trees[i].p - trees[i].h]);
	}
	cout << best << "\n";
}

There are definitely no overflows. I checked with “trapv”, and also the answer is an int.

1 Like
39

you can do first one by implementation also just using for loops

40

ya i also did the same thing…nice

41

You are right. It’s not storing the max :man_facepalming:. I feel so dumb.

1 Like
42

nope this is not mine , i m not trying as much , as only single question is enough so i solved only 2nd.

1 Like
43

nice editorial anee

but

how do you guys add math in these posts ? i know you put text in between $
but how do you add subscripts superscripts symbols like summition integrals etc.?

1 Like
44

\LaTeX

1 Like
45

\sum^n_{i = 0} \prod^m_{l = i} this is awesome… thanks.

46

Check this out. I’ve made an entire topic for that :P.

47

SecondThread has done flyod warshal :exploding_head:.
Time: @ 6:25