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
Full input link: https://drive.google.com/file/d/0ByHbOJKKpXM9dEtiSkxZdExXR00/
Full output link: https://drive.google.com/file/d/0ByHbOJKKpXM9Y1Q0dVZvUkRxanc/
B. Autocomplete
Full input link: https://drive.google.com/file/d/0ByHbOJKKpXM9eklueGpLdmh1ZEE/
Full output link: https://drive.google.com/file/d/0ByHbOJKKpXM9TWdMUVo2amJ2RUk/
C. Winning at Sports
Full input link: https://drive.google.com/file/d/0ByHbOJKKpXM9eTU0YVFRSHUyWTg/
Full output link: https://drive.google.com/file/d/0ByHbOJKKpXM9NnhpX2xfOUlJelU/
D. Corporate Gifting (this is not the output I submitted, what I submitted was wrong)
Full input link: https://drive.google.com/file/d/0ByHbOJKKpXM9elVuOVNld3pRMkE/
Full output link: https://drive.google.com/file/d/0ByHbOJKKpXM9SG43c1R3ZHlrWGc/
The above outputs are not guaranteed to be correct, I'll update the post if I found that any of them is wrong.
There is this too http://mirror.codeforces.com/blog/entry/15829#comment-207625
I agree on all outputs. Of course I have a history of making stupid mistakes on FBHC.
I have uploaded the round 1 problems to an online judge.
P1 Homework
P2 Autocomplete
P3 Winning at Sports
P4 Corporate Gifting
I 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.
I'm getting RTE on the last problem, probably due to stack size.
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.
If I am getting RTE because of exceeding the memory limit. Will the solution be discarded?
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.
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.
I'm getting Stack Overflow with Java 8 in the problem B. Can this size be increased somehow? Thanks!
It is done.
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!
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.
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 ;/.
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.
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.
The final sample requires a 3, if I'm not mistaken.
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 :(
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.
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.
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.
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 ?
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.
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.
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 .
checked !! all the outputs matched !! :) hope we do not have same bugs :D
it'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 :( :(....
I agree with the outputs here. My first 3 solutions are good, except the last one.
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
plus this comment if u have 60 pts
plus this if u have more then 60 pts
plus this comment if u have less then 60 pts
all outputs match :)
Found silly mistake in my C. A,B,D matches.
All matched, except B...
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.
Thanks. I'll try it.
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 :-)
I'm getting Stack Overflow with Java 8 in the problem B. Can this size be increased somehow? Thanks!
Thanks for posting this! My A,B,C match (and I already knew my D was wrong).
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?
Only two cases fail BTW.
Count me in :)
Is it just me or for the D problem, i found less values than your output...
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.
Stack overflow caused me 40 points T_T
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.
Is it possible for only 50pts to advance? I have made stupid error on question B and C:(
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?
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.
Got memory limit exceeded in B. Matches to output given by Ahmed Aly. UPD: Now getting Judgement Failed.