JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Round Tables External Competitions Facebook Hacker Cup << PREV    [ 1 ... 52 53 54 55 56 57 58 ]    NEXT >
 Re: Facebook Hacker Cup (response to post by FB_Tim) | Reply 1) What are you gonna do with the people who submitted after the time expired? I had a solution for problem A that I think could run in about 20 minutes but I gave up after time ran out. So I think it should be unfair to consider solutions submited after the time limit was exceeded.2) Can you organize a new round for all the people who qualified for Round 2 but did not solve any problem and name it "The T-shirt Round" where the top 150 get a T-shirt?
 Re: Facebook Hacker Cup (response to post by the_saint) | Reply Ok, if you understand how to apply the inclusion-exclusion principle at the toplevel, then you only need to figure out how to calculate in how many ways we can pick bonuses for N workers such that the lowest value is in [A:B] and the highest value is in [C:D].Suppose calc(N, X, Y) gives the number of ways to pick bonuses in [X:Y] for N people (i.e. (Y-X+1)N if X<=Y, or 0 otherwise) then we can calculate the above as calc(N, A, D) - calc(N, A, C - 1) - calc (N, B + 1, D) + calc(N, B + 1, C - 1).The way to parse this is that we start with all cases where bonuses are between A and D (regardless of what the minimum or maximum is) and then subtract the cases where the lowest value is higher than B, or the highest value is lower than C, and then we need to add the cases where all values are between B and C back in, because we have subtracted those twice. (I guess that's the inclusion-exclusion principle applied again.)
 Re: Facebook Hacker Cup (response to post by nika) | Reply nika: It looks like Petr used Karatsuba's algorithm. Jacub's program on the other hand is very small. As if he found another way. I can't quite judge it though.
 Re: Facebook Hacker Cup (response to post by Lobais) | Reply Yes, I saw some passed solution using Karatsuba.I just didn't know that there was a special feature for those with slow cpu-s: just submit after the time expires ;)
 Re: Facebook Hacker Cup (response to post by dgarthur) | Reply Did you implement the inclusion exclusion principle like you said?In my case I got the first equation F(a,d) - F(a,c-1) - F(b+1,d) + F(b+1,c-1)Then I thought about the inclusion exclusion principle as you described but failed in finding an way to implement it.Can you tell me what name have you used on facebook so I can check your code?Thank you.
 Re: Facebook Hacker Cup (response to post by nika) | Reply For the record, I have used Karatsuba's algorithm too. Took 80 sec on my computer (and I could make it run in 20 sec by using the quad core).
 Re: Facebook Hacker Cup (response to post by Soultaker) | Reply Oh well. Made a very stupid mistake in the third task - somehow, my mind assumed that the numbers are <= 10^5, not <= 10^6. Changed it, and it worked (compared to the output for 2 of the top 3 solutions). And I usually double check these things, but forgot this time. Makes it double stupid. As a result - no T-shirt. But a bonus round for 150 T-Shirts is a good idea... :)
 Re: Facebook Hacker Cup (response to post by Soultaker) | Reply Thanks, that is exactly what I needed! I was doing the calculation of all possible distributions in a different way and the chances are that I have a bug there..
 Re: Facebook Hacker Cup (response to post by the_saint) | Reply All competitors who solved at least 2 problems:1. Petr2. lyrically3. tomek4. meret5. jakubr6. rng_587. Eryx8. ACRush9. andrewzta10. gnurdux11. kalinov12. Akim13. Zhukov_Dmitry14. Bolek15. dgarthur16. bwps17. tomekkulczynski18. Soultaker19. gawry20. Xazker21. Vintik22. RAD.23. embe24. ktuan25. Jedi_Knight26. kmod27. John DethridgeTop 25 distribution:Poland(8): tomek, meret, jakubr, Eryx, Bolek, tomekkulczynski, gawry, embeRussian Federation(7): Petr, andrewzta, Akim, Zhukov_Dmitry, Vintik, RAD., Jedi_KnightJapan: lyrically, rng_58China: ACRushUnited States: gnurduxCroatia: kalinovCanada: dgarthurGermany: bwpsNetherlands: SoultakerUkraine: XazkerVietnam: ktuan
 Re: Facebook Hacker Cup (response to post by daffes) | Reply David - I came 15th.The other part is similar to a problem I wrote for TopCoder a long time ago called SquareFree. You can see Lars's editorial of it here:http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm190
 Re: Facebook Hacker Cup (response to post by dgarthur) | Reply Thank you,Its the second time I can't solve a similar problem, now it seems late =/ but I won't let it happens again.
 Re: Facebook Hacker Cup (response to post by rng_58) | Reply Andrew is andrewztaFirst Jakub is probably jakubr
 Re: Facebook Hacker Cup (response to post by dgarthur) | Reply Lars, who happens to work for Facebook =) Damn, we should have seen all editorials, problemsets, etc. made by the people working there! :D
 Re: Facebook Hacker Cup (response to post by rng_58) | Reply #18 is me, and I wouldn't be surprised if #19 is Jan_Kuipers but I can't say for sure since there is no picture.
 Re: Facebook Hacker Cup (response to post by rng_58) | Reply #30 is me.
 Forums Round Tables External Competitions Facebook Hacker Cup Previous Thread  |  Next Thread << PREV    [ 1 ... 52 53 54 55 56 57 58 ]    NEXT >