Facebook HackerCup 2020 - EDITORIAL (Unofficial)

editorial
, , ,
22

@akshitm16, it looks like they do not run our source code.

image
image828×268 54.2 KB

Source: https://www.facebook.com/codingcompetitions/hacker-cup/2020/round-1/faq

1 Like
23

Ya…but they check the codes for plagiarism but then someone can submit a non related (not giving the submitted output) to avoid plagiarism check. Maybe they’ll upgrade in future.

1 Like
24

Yeah that’s right. Many people in my friend list have submitted the output file for both. Hope they change the evaluation method. And waiting for the verdict till the end of the contest also sucks. Are the upcoming rounds also similar?

2 Likes
25

Yes, the upcoming rounds will have same pattern. I don’t think it will be changed for this year. Waiting for the verdict till the end is still fine. Even in Codejam there are problems where verdict is revealed at the end but I don’t like this file system of Fb

1 Like
26

Did they do the plagiarism checks for this round? As in my profile its written- “You advanced to Round 1”

27

What did you expect?

1 Like
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