Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<< 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. Petr
2. lyrically
3. tomek
4. meret
5. jakubr
6. rng_58
7. Eryx
8. ACRush
9. andrewzta
10. gnurdux
11. kalinov
12. Akim
13. Zhukov_Dmitry
14. Bolek
15. dgarthur
16. bwps
17. tomekkulczynski
18. Soultaker
19. gawry
20. Xazker
21. Vintik
22. RAD.
23. embe
24. ktuan
25. Jedi_Knight
26. kmod
27. John Dethridge

Top 25 distribution:
Poland(8): tomek, meret, jakubr, Eryx, Bolek, tomekkulczynski, gawry, embe
Russian Federation(7): Petr, andrewzta, Akim, Zhukov_Dmitry, Vintik, RAD., Jedi_Knight
Japan: lyrically, rng_58
China: ACRush
United States: gnurdux
Croatia: kalinov
Canada: dgarthur
Germany: bwps
Netherlands: Soultaker
Ukraine: Xazker
Vietnam: 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 andrewzta
First 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.
<< PREV    [ 1 ... 52 53 54 55 56 57 58 ]    NEXT >

RSS