### ahmed_aly's blog

By ahmed_aly, 5 years ago, ,

Edit: Looks like the following outputs are correct, you can use them to judge your solutions (or you can submit your solutions here). Also it looks like many contestants will fail in the last problem, so I guess the cutoff will be 60 points (anyone with at least 60 points will be qualified).

Until Facebook finishes the manual judging, let's compare our solutions against each other. Here are what I think should be the correct outputs for the given inputs, please run your solutions against these inputs and write a comment here and say what your solution agrees with and what it doesn't.

A. Homework

B. Autocomplete

C. Winning at Sports

D. Corporate Gifting (this is not the output I submitted, what I submitted was wrong)

The above outputs are not guaranteed to be correct, I'll update the post if I found that any of them is wrong.

• +58

 » 5 years ago, # |   0 There is this too http://codeforces.com/blog/entry/15829#comment-207625
 » 5 years ago, # |   0 I agree on all outputs. Of course I have a history of making stupid mistakes on FBHC.
 » 5 years ago, # | ← Rev. 6 →   +52 I have uploaded the round 1 problems to an online judge.P1 HomeworkP2 AutocompleteP3 Winning at SportsP4 Corporate GiftingI used my own inputs and output as the test data. Please note that the judge is strict and requires the output to be in the exact format as the sample output (i.e. newline after every case, # signs).Also, the hard memory limit for the problems is 1GB and time limit is 1 minute, which may differ a bit from your local resources.On the judge, please do not read from file — all input/output is from/to stdin/stdout.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +14 I'm getting RTE on the last problem, probably due to stack size.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Sorry, I will try to increase the stack size and rejudge in a few minutes. Also I will raise the memory limit to 1GB for all the problems.Update: The issue is resolved.
•  » » » » 5 years ago, # ^ |   0 If I am getting RTE because of exceeding the memory limit. Will the solution be discarded?
•  » » » » » 5 years ago, # ^ |   0 If you mean on the real Facebook Hacker Cup, then no, because me putting the problems on the judge is totally unofficial. If you mean on the judge, the solution will not be deleted and you can view it at any time.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Ok, I haven't found the problem (yet), but I ran your code on the 32-bit judge. The RTE only happens on the 64-bit (and faster) ones, so we're still looking into that.Update: The "few minutes" turned into "almost an hour" but I finally fixed the issue. In case you were wondering, it's because I'm bad and forgot to recompile the C++ part of the judge. Sorry to anyone who was affected by this stack size issue! I'm in the process of rejudging all the RTE/IR.
•  » » » » 5 years ago, # ^ |   0 I'm getting Stack Overflow with Java 8 in the problem B. Can this size be increased somehow? Thanks!
•  » » » » » 5 years ago, # ^ |   0 It is done.
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Thanks! It passes the first case now but I'm still getting Stack Overflow in the second test case. Could you please increase it further? Thanks again!Edit: Thanks FatalEagle. I indeed confused it with the Gym contest. I'm sorry for the inconvenience!
•  » » » » » » » 5 years ago, # ^ |   0 Ah, maybe you are talking about Codeforces Gym. In that case, I'm sorry but I have no clue how to change the stack size. Perhaps someone more experienced than myself could offer you a solution.
•  » » 5 years ago, # ^ |   +11 Thank you very much!Though I realized that I got D wrong which makes me sad, because so many people submitted it and it looks that cutoff will be definitely higher than 60 pts ;___;. I got some little hope that given sufficient amount of luck I may be able to qualify to onsite and I failed on first round, so pathetic :(. I think that I just disregarded this round since it lasts 24h, 500 people qualify and so on ;/.
•  » » » 5 years ago, # ^ |   -8 Oh come on! I bet that 60 pts will be enough to advance — just read all the comments of people like you who submitted D but failed on it.I personally failed as well because I somehow came up with provement that 3 colors would be enough but I have no doubts that will advance — we don't need to underestimate weaknesses of other contestants.
•  » » » » 5 years ago, # ^ |   0 Hm, on the second thought it was pretty easy to came up with a wrong solution. Was bicoloring enough to pass samples? It was pretty tempting to code that :P. But there are >1300 people with submitted solutions which are worth >60 pts + don't forget about manual judgments, I guess we just need to wait.
•  » » » » » 5 years ago, # ^ |   +15 The final sample requires a 3, if I'm not mistaken.
•  » » » » » 5 years ago, # ^ |   0 I read a comment on FB hacker cup that the cutoff point will not be affected by the manual judgement(which gave me some hope). Let's hope the cut off points will just be 60 :(
•  » » » » 5 years ago, # ^ |   +5 Nice to hear that I wasn't the only one 100% certain of my "proof" that 3 colors are all you need. :) However, I'm not that confident that 60 points will be enough ... but there's still hope.
•  » » » » » 5 years ago, # ^ |   0 Well, 3 colors are not all you need. You can proof that there are cases where using 4 colors i.e using a gift of value $4 is better than only using gifts of value$1, $2,$3. If you want a proof, you can think of a tree which have the following properties: 1 root A with 1000 child that are leafs (are not manager of other people). the root also have 2 other child, lets call them B and C. Each of them have 1000 child which are leafs. B also have 3 other childs that each have 1000 childs which are leafs. C have one child exactly like B (have 1000 childs which are leafs and 3 more childs which also have 1000 leafs). In that case, the root should be 4, else the amount of money spend would be higher. You can easily prove that the 1000 leafs that each node have must be 1, else thats not an optimal solution. After proving that, you can see that now, if you only want to use 2 and 3, the root can be either 2 or 3. if the root is 2, then B and C must be 3, the 3 childs of B must be 2, the child of C must be 2, and its 3 childs would be 3. if the root is 3 then the ones that are 2 should become 3 and the ones that are 3 become 2. If you would like to try it, the input would be: 1 1010 0 1 1 2 4 4 4 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
•  » » » » 5 years ago, # ^ |   +8 I didn't assume anything about the number of colours and used a more programming-oriented solution — when doing the DP, you can just consider the best colours of sons and the 2 smallest ones that aren't the best of any son.
•  » » 5 years ago, # ^ |   0 Thanks for uploading the problems. Actually adding them to CF Gym might be better as users here are already registered and can submit the problems directly. I think Mike already did so.
 » 5 years ago, # |   0 for the last problem I constructed a directed graph for the given input , nodes — employee ID and edges — directed edge from A -> B if A is the manager of B . Then I ran a simple dfs hitting base cases filling from 1 as least for each nodes to provided least expenditure which is greater than the max value than its sub employees and saved it in a separate array and then accumulated the result which I tested for many cases and runs well for 2*10^5 big cases also and throws a seg fault all of a sudden for 5th case this approach correct ?
•  » » 5 years ago, # ^ |   0 Actually you need dynamic programming here..... maximum number of color we need to minimize the result will not be greater than log(n). dp state (i,prev) // i is the current node and prev is the color used.
•  » » 5 years ago, # ^ |   +2 The RTE is most probably due to stack overflow. If the tree is something like: 1 -> 2 -> 3 -> ... -> 200000, then your dfs will go to a depth of 2*10^5.
•  » » » 5 years ago, # ^ |   0 thanks a lot !! yes now I get it can you then clarify me on the maximum depth the recursion can hold ? and now while checking Sammarize_blog_entry I realized that keeping color 1 for all leaves would fail in a case where root has 2 children and one of these children has 1 child mine would throw 7 while I can get 6 .
 » 5 years ago, # | ← Rev. 2 →   0 checked !! all the outputs matched !! :) hope we do not have same bugs :Dit's very unfortunate for me that i could not submit my D for stupid stack overflow problem :( :(. i tried number of ways to increase stack size in 6min but failed :( :(....
 » 5 years ago, # |   +3 I agree with the outputs here. My first 3 solutions are good, except the last one.
 » 5 years ago, # | ← Rev. 2 →   0 1st & 3rd outputs are identical with yours. 2nd output is different. 4th problem hasn't been solved. you can check differences here... https://www.diffchecker.com/diff
 » 5 years ago, # |   -45 plus this comment if u have 60 pts
 » 5 years ago, # |   -40 plus this if u have more then 60 pts
 » 5 years ago, # |   -40 plus this comment if u have less then 60 pts
 » 5 years ago, # |   0 all outputs match :)
 » 5 years ago, # | ← Rev. 2 →   0 Found silly mistake in my C. A,B,D matches.
 » 5 years ago, # | ← Rev. 2 →   +10 All matched, except B... FOR(tc, 1, z) { cin >> n; nodes_num = 1; FOR(i, 0, nodes_num) nodes[i].clear(); //... 
•  » » 5 years ago, # ^ |   +5 This is why in problems with testcases you should wrap everything in struct like in following code: http://ideone.com/wenuKz . It doesn't allow you to make silly bugs in clearing data structures.
•  » » » 5 years ago, # ^ |   0 Thanks. I'll try it.
 » 5 years ago, # | ← Rev. 2 →   +61 I've added the round to the Gym: 2015 Facebook Hacker Cup, Round 1. Used inputs/outputs from ahmed_aly. Feeling glad that my solutions passed the tests :-)
•  » » 5 years ago, # ^ |   0 I'm getting Stack Overflow with Java 8 in the problem B. Can this size be increased somehow? Thanks!
 » 5 years ago, # |   +14 Thanks for posting this! My A,B,C match (and I already knew my D was wrong).
 » 5 years ago, # | ← Rev. 2 →   +35 Darn, apparently the input wasn't given as a topological sort in D (i.e. parent[i] < i). Am I the only one who thought this?
•  » » 5 years ago, # ^ |   +15 Only two cases fail BTW.
•  » » 5 years ago, # ^ |   0 Count me in :)
 » 5 years ago, # |   0 Is it just me or for the D problem, i found less values than your output...
 » 5 years ago, # | ← Rev. 2 →   0 I literally jumped when all my submission got accepted as verdict in the codeforces gym. Then I realized I didn't manage to submit problem B.
 » 5 years ago, # |   +3 Stack overflow caused me 40 points T_T
 » 5 years ago, # |   +1 Yes match for A to D ;-)I didn't notice this blog when I upload FBHC problem with my test data to SPOJ. By the way, you can compare your output with mine on SPOJ here.
 » 5 years ago, # | ← Rev. 3 →   0 Is it possible for only 50pts to advance? I have made stupid error on question B and C:(
 » 5 years ago, # |   0 I have submitted the solutions for all the problems, and I have received a tick on all of them on the scoreboard. According to the scoreboard, I have a score of 100. Is this the final score? Or is it possible that some of my solutions may be wrong?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Your solution is only judged at the end of the round, so it is not final result,BTW you can check your solution in Codeforces/Gym.
 » 5 years ago, # | ← Rev. 3 →   0 Got memory limit exceeded in B. Matches to output given by Ahmed Aly. UPD: Now getting Judgement Failed.