riadwaw's blog

Facebook Hackercup Round 3
By riadwaw, history, 8 years ago, In English

Starts in less than 3 hours

Top 200 from round 2 are allowed to participate and top 25 (aged 18+) will advance to onsite finals

Let's discuss problems here.

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

»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

https://www.facebook.com/hackercup/round

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

How to solve the third problem?

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

    Shortest path between any two cities is either shortest path around the circle or shortest path from A to the center plus shortest path from B to the center. Shortest paths to/from the center can be calculated with Dijkstra's algorithm.

    Then — bunch of binary searches. For each starting city A remaining cities are separated in three groups based on what is the best way to reach them: go right, go left, go to the center. I find three borders for each starting city: when it becomes better to go through the center than go left, similar for right, and when it becomes better to go right than to go left. Turns out that all these functions are monotonous and we can use binary search. After that — a bunch of prefix sums.

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

    First of all, run dijkstra from center and relax r_i. Now we may notice, that we either go throught center or without going to center. From vertex i, we always go clockwise to some range of vertices [i + 1, i + r], counterclockwise for some range [i — l, i + r] and otherwise throught center. Now use 2 bin.searches in each vertex

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

    Edit: I was too slow :|

    First, set R[i] = min cost from i to center (also take into consideration of going around the circle).

    For each i, find left[i] = farthest point on the left where you should go around the circle from left[i] to i.

    Find right[i] which has similar meaning but to the right.

    Array left[i] and right[i] can be calculated in O(N) using 2 pointers.

    Then for each i, there are 3 types of vertices:

    • left[i] to i
    • i to right[i]
    • the other vertices

    Each type can be calculated in O(1).

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

Damn! I copy-pasted the sample from the third problem without the last line, and obviously the answer didn't match. I wasted about 15 minutes trying to find the bug in the code — almost missed the final because of that.

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

    So there is no runtime error or anything in your code when you try and read an integer that is not there?

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

      Of course not when you're using C++.

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

        Well this is not trivially obvious to me, particularly as Al.Cash uses his own custom input parsing library, I don't think there is anything that stops him from throwing in some assert statements to check for this, although in this cases I suppose he does not.

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

          I see why you asked the question now :). I think he kept same behavior as scanf: returns number of arguments successfully read, and not throw error.

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

      Currently not, as I mimic scanf behavior. This incident suggests changing it.

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

How to solve the second problem?

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

    Let's call a pair "splitting" if the friends are in different queues. Let's find the first splitting pair (in lexicographical order). If something "crosses" it, we need to delete these two pairs, solve the problem recursively (for everything before and after it) and returned the doubled product (we can choose the order of deletion of these 2 pairs). Otherwise, we have to delete this pair alone and solve two smaller subproblems again. The base case is when there're no "splitting" pairs (the answer is some binomial coefficient).

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

    Some sketch:

    We can see that not too many different configuratons of pair is allowed. So call group in one line "good" if it's of form "aa" or "abab" — it may be processed without going to other line.

    Now, while we not finished, calculate and skip good groups. Now in the start you see one of not-so-many configuration of two-line divided groups (or answer is zero). So we can process good groups in any order (it is binomial coefficient) and multiply answer by that number and maybe by 2 if we can process "bad group" in two ways.

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

    Let's try to model the process described in the problem statement.

    Suppose, we've already processed first p1 items from the first queue and first p2 items from the second queue. We may either proceed with the operation that depends only on one of the queues or with the operation that depends on both of queues.

    Operations that depend only on one queue look as following (operations of the first type):

    • aa
    • abab

    Operations that depend on both of the queues(operations of the second type):

    1 way to perform:

    • a a

    2 ways to perform:

    • ab ba
    • aba b

    Consider, that we made c1 operations of the first type with the first queue and c2 operations of the first type with the second queue before we have to make the operation of the second type. We can arrange them in C(c1 + c2, c1) ways (C is a binomial coefficient), so we should multiply the result by this value. Then we have to perform the operation of the second type (and possibly multiply the result by 2).

    If in any step we are unable to perform any of the operations — the answer is 0

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

Ah... First task is almost same with this task I wrote about 3 years ago..

Somehow I failed on this task (by mistype 'n' into '1000') otherwise I could advance. :(

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

Providing the inverse suffix array as an input instead of a suffix array in the first problem was the evilest possible thing :(

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

    Why? You note that at a glance when you look at the first sample. Anyway, there was no reason to do so, I don't justify the authors.

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

      Well, I always have both these arrays in suffix array, so it's weird to call "usual suffix array" only one of the permutations.

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

        Still, suffix array is well-defined, so it makes sense.

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

    what's the difference considering you need both of them?

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

It seems I had small implementation bug in last task, good thing tests had not caught it

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

    Will you release screencast of your win, or are you not doing those anymore? It has been nearly a year now :(

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

      I think about some new formats for this. I do not do screencasts for now unfortunately

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

(pity post warning)

I solved A, D, and submitted for problem B. However my problem B fails due to overflow error, passes with one extra line of "ans %= MOD;"

Sad orange coder ksun48 would have qualified

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

    One of the reasons I wrote a wrapper class that handles modulus for me. It's used for example in this submission 24049890

    → Reply