Hooray! Today we've survived another DDOS attack. The round was not perfect, but it was not ruined! ×

### Zlobober's blog

By Zlobober, history, 5 years ago,

Today (January 30th) at 10:00 AM PST / 21:00 MSK there will be the last online round for FHC. Don't miss the round!

As you remember, top-25 contestants will go to the onsite round in London.

Good luck to everybody!

UPD: UP! The round is in 30 minutes.

• +124

 » 5 years ago, # |   +27 So many contests recently, I think I'm overloaded...
•  » » 5 years ago, # ^ |   +48 Greetings from Petrozavodsk camp xD
 » 5 years ago, # |   -22 cubelover is so strong :(
•  » » 5 years ago, # ^ |   +8 You really believe that he solve all problems in less than 1 hour? :)
•  » » » 5 years ago, # ^ |   -44 Even if 3 of them will be correct he passes to onsite. I think FHC organizators should really think about fairness such structure of competition, because everybody have different kind of CPU and RAM and if competitor have access to powerful machine he would be able to solve problems with less effective algorithms and logic. I believe that "fair competition" implies equal condition for all competitors.
•  » » 5 years ago, # ^ |   0 he just submitted some problems by typing ":(" in source code. :(
 » 5 years ago, # |   +12 Suspense
 » 5 years ago, # |   0 How to solve third problem?
•  » » 5 years ago, # ^ | ← Rev. 5 →   +26 On the coordinate plane (k, x) your task is to cover as many points as possible with a geometric shape that looks like a horizontal segment with two symmetrical rays flying from its ends to infinity (both up or both down).This can be done with bottom-up line sweeping + interval maximum tree to store how many points are below (or above) the current horizontal on each slope.Incidentally, this shape has quite a resemblance to an actual umbrella (and to a boomerang too!) so thumbs up to the writers for choosing this problem name and story.
•  » » » 5 years ago, # ^ |   0 Could you please provide some details on the line sweeping part?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +8 So you are searching among this kind of shapes (the other case is solved by reflection):  ___p1____p2__ / \ / \ It is safe to assume that at least one point lies on the horizontal segment (otherwise move this segment up or down) but in general no such guarantees can be made for the other two segments (see Example 5). Maximize the value left[p] + right[p] over the points p lying on the horizontal segment where left[p] is the maximum number of points that can lie on the part of shape that is to the left (and below) of p and right[p] is defined analogously. When moving from p1 to p2 (see the picture) you need to find a maximum among all the lines between these points and also add +1 for all the lines that are to the left of p1.And when moving from a horizontal to another, add this horizontal's points to all the non-horizontal lines: ___ p1___p2___p3___p4___ / / / / and ___ p1___p2___p3___p4___ \ \ \ \ 
•  » » » » » 5 years ago, # ^ |   0 Cool, thanks!
 » 5 years ago, # |   0 Well, that went terrible! At least I got a T-shirt :)In all seriousness, I think after getting A I spent too much time on getting CDE (D in particular), and only in the end realised that B was quite doable. Unfortunately I had only 10 minutes left to write it, and with a minute left to go my code printed 0 for all samples.As for D, does anyone have any good ideas on how to solve it? I first thought of sorting the (D_i, W_i) in (ascending, descending) order and picking an arbitrary element plus a prefix of the remaining sorted sequence, but this failed already on the fourth sample. I'm curious to hear what others came up with.
•  » » 5 years ago, # ^ |   +15 Same thing here, I was so sure you needed D to qualify (because it looked so simple), and it never occurred to me that it was actually the most difficult of the contest...
 » 5 years ago, # |   0 In E can one actually fit Karatsuba into TL?
•  » » 5 years ago, # ^ |   0 Should be possible, but jury solution was 2xFFTs with different prime modulus + CRT.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +8 A doubles FFT is fine, if you multiply a vector of distances between adjacent points by a reversed self.EDIT: entire solution (without FFT and other helper functions) below  long[] seg = new long[n]; for (int i = 0; i + 1 < n; ++i) { seg[i] = pos[i + 1] - pos[i]; } seg[n - 1] = pos[0] + l - pos[n - 1]; long[] rseg = new long[n]; for (int i = 0; i < n; ++i) { rseg[i] = seg[n - 1 - i]; } long[] prod = FastFourierTransform.mul(seg, rseg); long[] total = new long[n]; for (int i = 0; i < prod.length; ++i) { total[(i + 1) % n] = (total[(i + 1) % n] + prod[i]) % MODULO; } res = 0; for (int i = 0; i <= k; ++i) { long pr = comb(n - i, k - i) * invcomb(n, k) % MODULO; if (i != 0) { pr = pr * 2 % MODULO; } res = (res + total[i] * pr) % MODULO; } res = res * invs[4] % MODULO; res = res * invs[l] % MODULO; 
•  » » » 5 years ago, # ^ |   +30 I know a similar idea: using a doubles FFT with an integer FFT — doubles FFT may get precision error, and you can use the mod result of integer FFT to correct it.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 My solution with fft without any modules(aka 1 module) got OK.UPD: Just noticed, Petr described same solution
•  » » 5 years ago, # ^ |   0 That's clever. I used this technique in Petr's blog: http://petr-mitrichev.blogspot.com/2015/04/this-week-in-competitive-programming.html
•  » » 5 years ago, # ^ |   0 Yes, it took me several minutes, but it worked.
 » 5 years ago, # |   +128 My reaction after I see that I jumped to 24th from 60+:
•  » » 5 years ago, # ^ |   +28 Congrats :D
•  » » 5 years ago, # ^ | ← Rev. 2 →   +41 Same reaction when i realized that tourist and Egor are not going to the onsite finals .
•  » » 5 years ago, # ^ |   -10 Congrats yeputons:)
 » 5 years ago, # |   +37 l * l. Should be (long)l * l. Oh well, seems like me and Hacker Cup are just not compatible
 » 5 years ago, # |   +34 Not a single AC in D. Does anyone have ideas on how to correctly solve it?
 » 5 years ago, # |   +11 Added the problems to the Gym: 2016 Facebook Hacker Cup, Round 3.
 » 5 years ago, # |   +162 Let me tell you my story.It was 3 minutes till the end of the contest when I finally figured out how exactly to apply FFT in the last problem. Everything else was ready and FFT code was already copy-pasted. I enter those last formulas, and suddenly they pass pretests on the first try!One minute left... My heart is beating and my hands are shaking, but I'm still hitting the right button to download the input and to upload the solution. And it passes!!! I can't believe it!
 » 5 years ago, # |   +5 Could someone open FHC from mobile? Link: https://m.facebook.com/hackercup/round/704267919677819/
•  » » 5 years ago, # ^ | ← Rev. 4 →   +10 Error 500, I believe they acknowleadged it and said it won't be fixed this year
•  » » » 5 years ago, # ^ |   +12 Yeah, it's certainly something for next year though. I was surprised by the amount of people that wanted to view the rounds on mobile because You presumably aren't going to submit any solutions on mobile I don't think I heard of anybody wanting to use mobile last year But in retrospect, the use cases are pretty obvious. In untimed rounds you might want to read the problems on the bus or something before you're at a computer and ready to code. In any round you might want to use a mobile device as a separate screen to show the problems while you're coding on a main screen. Etc.So certainly we'll work on this for next year.
•  » » » » 5 years ago, # ^ |   +37 You also want to see standings after the round
•  » » » » 5 years ago, # ^ |   +36 Well a pretty common use case is that you go for lunch after finishing a round, and want to check the scoreboard while waiting for your food...
 » 4 years ago, # |   -30 looking for a good hacker who can help you do your job. Email , facebook , paypal , WU , Phone ETC contact : greenfr1007@gmail.com or skype : satish.anchan4 **** Good work
 » 2 months ago, # | ← Rev. 2 →   +20 Anyone know the solution to D? The link provided in the solutions doesn't work and the solution in Gym doesn't seem to be correct. (It outputs 3 12 when $L=12$ and $W=[1,2,3], D=[1,4,6]$ but I think it should be 2 7).(EDIT: Solution was added.)