### eatmore's blog

By eatmore, 7 years ago, translation,

The third round of Facebook Hacker Cup 2015 will take place exactly one week after round 2: on January 31st at 9:00 PM UTC. The round will last 3 hours. Top 25 participants will win a trip to Menlo Park to participate in the final round, which will take place at Facebook office on March 6th.

Participants will be able to enter the contest using this link, and the scoreboard will be available to everyone here.

• +114

 » 7 years ago, # |   +28 Round 3 problem statements are available on the Hacker Cup page: https://www.facebook.com/hackercup/posts/907649815933874
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 when final results going to be avaliable?
•  » » » 7 years ago, # ^ |   0 Hopefully within 30 minutes of the contest ending.
•  » » » 7 years ago, # ^ |   +32
•  » » » » 7 years ago, # ^ |   +13 :(
•  » » » » 7 years ago, # ^ |   +41 :)
 » 7 years ago, # | ← Rev. 2 →   +8 Here are my inputs and answers.UPD: they're wrong for 35 and 40 problems.
•  » » 7 years ago, # ^ |   +3 "hz" in Lunch Scheduling answers?
•  » » » 7 years ago, # ^ |   0 Whoops, I've uploaded wrong file. Fixed.
•  » » 7 years ago, # ^ |   0 I have different answers for Gentrification, anyone else?
•  » » » 7 years ago, # ^ |   +5 Can you compare with mine and sankear in comment below?
•  » » 7 years ago, # ^ |   +13 Me and sankear all differ in problem C. Our outputs: http://pastie.org/9877127Moreover, me and sankear differ only in test four, my answer is larger by 1, and your answers are larger then ours on significant number of tests.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +13 My answers coincide with sankear's.Edit: also implemented tourist's approach now, answers are the same.
•  » » » 7 years ago, # ^ |   +8 +1 to your answers... probably, I have the same bug :)
•  » » » » 7 years ago, # ^ |   0 Does it mean it coincides with my answers? Or even more +1?
•  » » » » » 7 years ago, # ^ |   +8 coincides
•  » » » » » » 7 years ago, # ^ |   +16 Probably that's because you forget to replace graph with its transitive closure. Me too =(
 » 7 years ago, # |   +19 Problem 35 was clearly Dilworth's theorem. Isn't it too classical to be in qualification round?
•  » » 7 years ago, # ^ |   +5 Well, you also have to find how to account for weights. Doesn't seem trivial to me.
•  » » » 7 years ago, # ^ |   0 Well, it is not trivial, but so standard move...
•  » » » 7 years ago, # ^ |   0 Or maybe my solution is wrong and the problem is ok)
•  » » » 7 years ago, # ^ |   +136 There is no need to find strongly connected components at all (and thus to account for weights). You can just use partial order (u < v) <=> (there is a path from u to v, but no path from v to u).
•  » » » » 7 years ago, # ^ |   +32 I didn't even read the problem but I know you said something that makes people go "Wow, that is amazing, how did you think of it?" :D
•  » » » 7 years ago, # ^ |   +24 I agree.I'm familiar with Dilworth's theorem. (E.g. I have created a task about this: SRM557 Div1-Medium) But it still took me about 30 minutes to figure out how to deal with the weights.
•  » » 7 years ago, # ^ | ← Rev. 3 →   -9 Is it really classical and wide-known theorem? If yes, then I'm totally fine with this task. Otherwise, while not denying that it's good for me that I learned a new theorem today, I personally find it rather bizarre to give 35 points on the basis of how well can one use Google. Which, apparently, I suck at.UPD: I see, so it's a well-known and pretty widely-used theorem. Have absolutely no problems with the task in this case. Thanks for the feedback!
•  » » » 7 years ago, # ^ |   +21 Believe be, I even didn't hear the name of the theorem until now, beside of the content.
•  » » » 7 years ago, # ^ |   +32 There is a similar problem at Timus Online Judge: Fat Hobbits
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +8 This theorem was given in at least a topcoder and one GCJ problem, see for instance here.I don't think it was an obvious solution, I clearly knew the theorem and couldn't solve the problem, so maybe it was okay after all...
 » 7 years ago, # |   -46 Zonk. I find it pretty bizzarre that strong redcoders don't know Dilworth's theorem xd. Here you have beatiful problem where it can be applied (or rather, need to be :P) http://main.edu.pl/en/archive/oi/9/nar
•  » » 7 years ago, # ^ |   +22 Since this comment is on top-level, I'm not 100% sure if this was meant to be a reply to my original question. It really looks like it is, so I'll go ahead and answer it, even though I don't consider myself a strong redcoder.So, you are finding pretty bizarre that there is a possibility that strong redcoder doesn't know that theorem. In fact, the theorem itself doesn't even matter. Let's consider the possible ways of how can one learn it: Was taught it in some kind of school/camp/etc. Read about it or tried solving a problem which required the knowledge of it. I believe that's pretty much is it in general terms. So let's consider what is required for these ways to occur.For the first way, not everyone have that privilege, which requires an infrastructure and coaches at schools and universities, willing to devote their valuable time on coaching. Please, do no take that for granted. Even if everything is in place, it's not guaranteed that you will learn it from this way.As for the second way, there are two scenarios around it. One is to invest a lot of time in training, which is usually expressed in solving problems from various online and onsite competitions on your own. I do not think it's bizarre that some people simply do not have enough free time to be willing to do this. For me personally, competitive programming is pretty much a hobby rather than the thing I seriously devote myself to ever since I changed university in late 2012. And I'm not alone at my University. It is ridiculously hard to organize anything regular here (I have tried, trust me, and still am), since no one has lots of free time available and pretty much everyone has his own schedule. And I'm not even talking about people having a full-time job — even less time is available there.Second scenario is to participate in competitions and encounter a problem on the topic there. Which, again, with the same reasoning of limited time available, I don't find that bizarre that for some, like me, this particular contest might have been the first time they've encountered a problem on this topic, since, again, not enough time to participate in every contest available.So, with this, the way I understand your statement is that you find bizarre that strong redcoders might not have the privilege to be coached or enough free time willing to invest in heavy training. Well, I don't. One likely needs to invest a lot of his time to become a strong redcoder, I'm not arguing with that. However one also likely needs to continuously invest even more time to continue learning new to them algorithms, data structures, approaches, types of tasks etc. And a vast majority of people after some point in life can't afford that anymore.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +8 Huh, that's a pretty exhaustive answer to my a bit stupid statement xD. I already saw problem like "You're given a grid with positive integers inside it, how many paths from lower-left to upper-right corner (going up and right) do you need in order to obtain an arrangement such that at least a[i][j] paths passes through cell (i, j)?" on ejudge and vast majority of teams got this problem accepted in a short period of time and that is a classical application of that theorem, so I assumed that among univeristy students it is widely known.Though I understand that not everybody is obliged to know all theorems on the world and that's of course understandable.
 » 7 years ago, # |   +13 My solution for problem 35: Gentrification: ls = {0,1,2,...,components-1} sol=1 do shuffle(ls) curSol=0 // from left to right, if possible, mark the component and add it's size to curSol. sol=max(sol,curSol) // same from right to left repeat for 8 seconds 
•  » » 7 years ago, # ^ |   +8 I did DP for <= 25 components. And random_shuffle for > 25.There were 5 tests > 25 (28, 161, 191, 500, 500) Half of the tests were with 1 component. (these are the components after you build the graph with edge u->v if there is a path from u to v.I suppose their tests are weak.A case that can beat the random: a -> b <- c (b = 3, a = 1, c = 1) you need to choose b.Have lots of these. Less likely you choose b over all of these.
 » 7 years ago, # |   0 In problem 40, are there precision issues with the naive solution (Gauss over each four vertices)?
•  » » 7 years ago, # ^ |   0 I haven't found any. I've tried double, long double and eps from 1e-8 to 1e-15 and all solutions gave same answers.
•  » » » 7 years ago, # ^ |   0 When I tested your solution against mine, I noticed that you output 1.0 probability in some cases when b is much less than a. While correct answers seems to be 0. So I guess the issue you had is not precision but an edge case.
•  » » » » 7 years ago, # ^ |   0 Exactly: I haven't added this check: if (floor(a/4) > floor(b/4)) return 0;
•  » » 7 years ago, # ^ |   +12 I think so. Or at least their checker is wrong. I tested Gleb's accepted solution against mine on my testcase, and there were 41 differences, where each was 1e-6 differences of the two numbers in the output. So if his solution was correct I assumed mine would be also. But it failed.I also checked yours on my test case, and it gave exactly the same result as Gleb's. But yours failed as well. So I think there is something fishy with the way they tested this problem.
•  » » » 7 years ago, # ^ |   +6 Oh my, I know what happened here. I didn't wait until your timer was up before judging, and I ended up judging your second submission (which was WA), but then you submitted a third time afterwards and I missed it. Your last submission is definitely AC.I'm double-checking all submissions now to make sure nobody else was affected.
•  » » » » 7 years ago, # ^ |   +3 Awesome! Thanks Wesley for figuring this out!
•  » » » 7 years ago, # ^ |   0 Everything else looks OK. I'll update the scoreboard.
•  » » » » 7 years ago, # ^ |   +16 So is Jakub (dj3500) going to miss the onsite now? I recall yesterday he was in 25th place, and now he is in 26th place. Is that not unfair to him, to make him think he was going and then find out that this is not the case?
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 These are the sorts of reasons (along with things like detecting cheaters) why we don't send official advancement emails until a few days after the end of each round. You could say we could withhold the whole scoreboard until then, but that would probably be a bit overkill.I've talked to Jakub, and there's always the possibility that somebody is unable to make the onsites, in which case there'll be a spot for him.I wouldn't say the situation is "unfair" in the sense that Jakub is not really in the top 25. However the emotional whiplash is certainly unpleasant, and that's my fault. I'm going to be working on better judging infrastructure for next year to reduce the potential for human error in a bunch of places.
•  » » » » » » 7 years ago, # ^ |   +3 possibility that somebody is unable to make the onsites
•  » » » » » » » 7 years ago, # ^ |   +3 Yes, indeed. This isn't reflected on the official scoreboard because the submission wasn't uploaded through the contest system.
•  » » » » » » 7 years ago, # ^ |   +43 Well, I would say the unfairness is in saying that "in 30 minutes the scoreboard will be finalized", then posting the scoreboard and claiming that top25 now advance. All of this, while not being an official email, does look like an official announcement (which then gets retracted/amended). Unfortunately I happen to have shared my joy in a Facebook post (I waited 12 hours for good measure — should have waited for the email), which now is making me look kind of stupid (unless someone drops out, I suppose).Speaking of which: any statistics on drop-outs in the last years? ;)
•  » » » » » » » 7 years ago, # ^ |   -11 JoeyWheeler: "But unfortunately I am still 17 (I hadn't realised they were unaware of this) and so cannot attend this year D:"
•  » » » » » » » » 7 years ago, # ^ |   +3 Yes, but he's out of the top25 in the current scoreboard.
•  » » » » » » » 7 years ago, # ^ |   +13 I agree that "finalized" sounds pretty final. We could probably pick a better word.Sharing the later-determined-to-be-incorrect results is hardly your fault.I think we actually had 3 people who didn't show up last year. I don't know if this was because of visa issues or other obligations. We've invited the top 25, and they have until Feb. 5 to confirm that they're coming.
•  » » » » » » » » 7 years ago, # ^ |   +7 Could you share any information about how many top 25 participants have confirmed/refused their participation?I don't expect something like official answer, just want estimate the probability of me on 29-th place being invited.
•  » » » » » » » » » 7 years ago, # ^ |   +8 I don't know of any other contestants that have decided not to come, but I'm not in charge of the travel/visa arrangements.
•  » » » » » » » » » 7 years ago, # ^ |   +8 I believe we have 25 confirmed finalists now, so the finals are set :)
•  » » » » » » » » » 7 years ago, # ^ |   +8 Thanks for the info, hope one year I will be able to be among these 25 people :)
•  » » » » » » » » » 7 years ago, # ^ |   +8 See you next year!
•  » » » » » » » 7 years ago, # ^ |   +85 I'm not going, so enjoy your trip Jakub! And make it count :)
•  » » » » » » » » 7 years ago, # ^ |   +36 Awesome (I mean, I'm sorry to hear that you're not going, but... ;) ), and thanks!
•  » » 6 years ago, # ^ |   -8 I don't know why this problem's TL is 30s, I think 0.5s is enough, there is n*log(n) solution.But there are many details to deal with when find matirx (E-A)^(-1).
 » 7 years ago, # |   +18 Now available in gym: 2015 Facebook Hacker Cup, Round 3. Used my test data and GlebsHP's solutions to generate answers.