riadwaw's blog

Facebook Hacker Cup. Round 1
By riadwaw, 11 years ago, In English

Round 1 will last 24 hours and start December 7, 2013 at 10:00 AM PT.

The top 500 people will advance to the Round 2. In addition, anyone that scores the same number of points as the person in 500th place will also advance to Round 2

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

»
11 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

Where is the announcement? Like it was in qualification

UPD It was boring to debug "Labelmaker", until I got output PKUPERCUPTEAM

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why I can't get access to tasks round 1?

This link don't work.

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

    It should work, so sorry for the silly question: have you solved at least one problem in qualification round about 2 weeks ago?

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

      No, I don't know, sorry.

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

Can anyone explain me third case in "Coins Game". Of course if it isn't illegal.

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

    I believe any discussion is illegal. Solution on specific test case can help you to solve problem.

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

    Considering it's a small case, you can solve it yourself, manually. Just write the possible arrangements and strategies on them on a paper, and try to see which is the best one.

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

      Yeah you are right. I thought a little bit , then i found optimal arrangement.

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Что должно выдавать в D(40) на тесте N = 20, K = 1, A[i] = 50 (для всех i = {0, ..., 19})? А еще спешу огорчить тех, у кого в B(20), на тесте 3 7 7, выдает 9:(

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it -16 Vote: I do not like it

    У меня 647.

    О, а как тогда B решать?

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

      У меня 643. Мне это уже не нравится)

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

        Вот теперь это уже не нравится мне :D

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

        А, фух, не ту задачу посмотрел, 643, всё ок.

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

      Case #1: 643

      51 53 58 59 61 65 67 71 73 77 79 83 89 97 101 103 107 109 113 127

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

    643.

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

When will results be announced ?

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

Can someone explain their solution to the 40pt question?

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

    I tried dynamic programming with a state of dp[N]{set of primes used} = minimum cost.

    On its own that wasn't fast enough, but it was possible to prune the search significantly by calculating an upper bound on the answer with a simple greedy algorithm and rejecting anything which would lead to a cost greater than that.

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

      How many primes do you need in the worst case to generate the answer?

      It seems that very stupid upper bound is 36 (number of primes greater than 50) but then the number of states is huge.

      Did you use map for memoization?

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

        I tried all coefficients up to 500 and, yes, used a map<vector,int>. eduardische's comment looks like a better way to keep track of state, assuming it works.

        Code here (guaranteed to not be correct).

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

          20 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2

          answer = 19, cause you cant left 0, cause gcd(0,2) = 2 :)

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

            Should not this case be caught by the last example?

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

              Yeap, seems like, but i checked my test on hex539 solution, and he has 18.

              But may be no, cause on last sample you have to keep one zero, but in this case you have to remove all of them.

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

                It's 18, because you need just 18 ones, one zero and one 2.

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

                  Yeap, but gcd(0,2) = 2, and 2 > 1.

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

                  Oh... whoops. Well, I wouldn't have points for that problem anyway, I just did a simple backtrack (I've got nothing to lose by trying :D).

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

                Ah I see, the last example is only there to ensure that noone misses the edge case (0, K, ..., K) and that is different from your test

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

            Thanks, I've updated my comment.

            Looks like there are several nasty edge cases. This solution could probably get around them by having an extra bit of state, [used_zero].

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

              The whole case "any number is zero" can be gotten rid of quite simply. If there's any zero in the solution, all other numbers must be K; otherwise, just increase all zeroes to ones.

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

      We can notice that it is only worth using primes >50 on its own, so we can have dp[N][mask][order of first unused prime >50]. This adds an extra dimension of N size but reduces the amount of primes to 15.

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

        If you sort the ages and process them in the non-descending order then once you have used a big prime you won't stop and will use only big primes hence. So your last dimension seems redundant.

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

          Not true. Maybe we can get somthing smaller than the first unused prime >50 later with combination of first 15 primes.

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

            If it will help later then it will help "right now" as well so we can switch them: remember that the ages are non-descending.

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

      I just implemented a brute force search with pruning and it was efficient enough. However, I didn't consider some special cases with zeros. :/

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

    What I did was quite simple.

    Initially I hardcoded the first 64 primes and pre-calculated the bitmasks representing which primes were used in each of the possible numbers' prime factorisations. (overkill, I know)

    Afterwards I dealt with the simple case of all A[i] <= K (in this case, we make all members of the new array to be K, except for if there are any zeroes, one of them can become a zero). If this does not hold, I initially bounded the solution with using only K * P[i] as my new array, where P is an array of only primes.

    Now I performed a simple brute-force recursion. It takes parameters of the current sum, index, bitmask and number used). It starts a for loop from max(previousNumber + 1, A[i]/K). If the current number in the loop doesn't violate the bit mask already there, it is placed in the i-th position and we move on. I disable recursing into impossible solutions by enforcing that the elements of the new array must be in increasing order; hence, if I have just added the number X to my array and I have Y numbers left to place, then the sum is bounded below by prevSum + Y*X + Y*(Y+1)/2 (the case where the following numbers are: X+1, X+2, ..., X+Y). If this lower bound is greater than the already found minimum, we can safely stop recursing.

    This turned out to execute quite quickly on my machine (the time spent on a file with 1000 random test cases with N = 20 was negligible).

    Here's my code.

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

      Hmm, did you consider cases like 4 1, 1 1 2 3, where you might need to select a 1 twice? The answer will be 0 for this case.

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

        Yeah. I handle the array members that are less than or equal to K separately from the others (as you can see from my code).

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

    Here is my solution based on backtracking, it corrected after considering the case 12.

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

А что с Preventing Alzheimer's делать? Кроме перебора, что-то ничего не придумалось (( Но это долго...

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

Scoreboard updated. Lots of B failed. (Mine too). Can anyone give a brief description of algorithm?

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

    If you can assign q = ceil(c / n) coins to each bucket, then you just do that and the answer is c. If you cannot, assign q to as many buckets as you can (to floor(k / q)), and distribute the remaining part (k % q) among the remaining buckets in any way. Then the strategy is to try to get q coins from each bucket. In the worst case you will try n — k / q buckets that don't have q coins first, so the answer is c + n — k / q.

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

      Why is this construction optimal?

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

Results are up. Everyone with 40p get through although it was close — the first 40p is only 492th.

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

    Does 40p going further?

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

      Yes. People with 40 points advance. :D

      Total 935 people advance.

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

    Hope they have the same scoring system in the next round.

    Let's agree we will all solve problem A only.

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

      This suggestion does not go well with your avatar :P

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

What is the answer for "4 5 5" in B and why?

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

    7 is enough and the distribution is 2 2 1 0 Now I get why those simple solutions work

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could anybody whose 40-pt is OK post the answer for this input: http://pastie.org/8538734 ?

UPD. Oops, I forgot that the sources are available.

→ Reply