Zlobober's blog

Facebook Hacker Cup 2016 Round 3
By Zlobober, history, 9 years ago, In English

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.

  • Vote: I like it
  • +124
  • Vote: I do not like it

Comments Comments (35)
| Write comment?
»
9 years ago, # |
  Vote: I like it +27 Vote: I do not like it

So many contests recently, I think I'm overloaded...

→ Reply
»
9 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Image and video hosting by TinyPic

HYPERHYPERHYPERCUBELOVER is so strong :(

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You really believe that he solve all problems in less than 1 hour? :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -44 Vote: I do not like it

      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.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    he just submitted some problems by typing ":(" in source code. :(

    → Reply
»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Suspense

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve third problem?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +26 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please provide some details on the line sweeping part?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

        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___
     \    \    \    \
        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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...

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In E can one actually fit Karatsuba into TL?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Should be possible, but jury solution was 2xFFTs with different prime modulus + CRT.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      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;
      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      My solution with fft without any modules(aka 1 module) got OK.

      UPD: Just noticed, Petr described same solution

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's clever. I used this technique in Petr's blog: http://petr-mitrichev.blogspot.com/2015/04/this-week-in-competitive-programming.html

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, it took me several minutes, but it worked.

    → Reply
»
9 years ago, # |
  Vote: I like it +128 Vote: I do not like it

My reaction after I see that I jumped to 24th from 60+:

→ Reply
»
9 years ago, # |
  Vote: I like it +37 Vote: I do not like it

l * l. Should be (long)l * l. Oh well, seems like me and Hacker Cup are just not compatible

→ Reply
»
9 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Not a single AC in D. Does anyone have ideas on how to correctly solve it?

→ Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Added the problems to the Gym: 2016 Facebook Hacker Cup, Round 3.

→ Reply
»
9 years ago, # |
  Vote: I like it +162 Vote: I do not like it

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!

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Could someone open FHC from mobile? Link: https://m.facebook.com/hackercup/round/704267919677819/

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +10 Vote: I do not like it

    Error 500, I believe they acknowleadged it and said it won't be fixed this year

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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

      1. You presumably aren't going to submit any solutions on mobile
      2. 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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +37 Vote: I do not like it

        You also want to see standings after the round

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        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...

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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.)

→ Reply