riadwaw's blog

Facebook HackerCup Round 1
By riadwaw, history, 9 years ago, translation, In English

Round 1 starts in 10 hours

Note, that rules were changed:
To advance to Round 2 you need to score 30 points or more.

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

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

Is it possible to go to arbitrary place in standings? Wanna solve problems like "find number of participants who got more than x points" faster than in O(answer)

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

    Lack of possibility to go back is unfortunate to after you accidentally click "go to first/last page" :(

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

How do you code D fast? I had a solution but it took me hours to code it.

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

    First of all forget about queue and understand that it's normal playoff tree, after that get all pairs (player, mask_of_player_of_size_2^i) so that player can win in some subtree. Then iterate over pairs of all such pairs and get answer for 2^{i+1}.

    It'll give you how big subtree one can win, it gives one of places (1,2,3,5 or 9) for best. The worst place is always 1 if can win all players or "lose in first round"

    It worked 3min for me, because I didn't bother to optimize

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

    I solved with dp for every i with state: set(mask) of 2j players, winner of this set, score distribution on this set, score of ith player. We should merge such states and update values. My solution was a bit slow, so I needed to do parallelization.

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

    I computed, for each set of size 2j, the set of possible winners if only players in this set participate. To compute this, I iterated over all the ways to split it into two subsets of size 2j - 1. Player's best place can be determined by the size of the largest set where he can still win. To find the worst place: if there is a player who beats everyone, his worst place is 1, and everyone else's worst place is n / 2 + 1. Otherwise, everyone's worst place is n / 2 + 1 (because each player could possibly lose the first match).

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

    My approach is a little bit simpler and fast enough.

    As riadwaw said, forget about the queue, is easy to see than the problem can be modeled as a game tree where each player will fight at least 1 time and upto logN times, in each tree level half players are deleted.

    for each player p we can find what is the max possible number of matches he can win, this allow us to compute the maximum rank.

    So the idea is canWin[p][sz] = the list of sets of having sz players (p included) where p-th player can get in the top place, sz is 2, 4, 8, 16.

    canWin[p][2] = (1<<p)|(1<<q) if p can beat q for every pair (p, q), the set is represented using bitmasks.

    At this point you know all possible sets of size 2 where p can win, this allows us to compute sets of size 4, a set of 4 players is divided in two sets of 2, so we can find all pairs (p, q) p beating q, and find all success outcomes for p (r, s) where r is in canWin[p][2] and s in canWin[q][2], (r, s) is good if they doesn't share any value (disjoint players), in this case p beats in his tournament of size 2, q beats in his tournament of size 2 and p beats q, so p can win one match more.

    The same idea applies for tournaments of size 8 and 16.

    The list of canWin[p][16] can be huge, there is a trick to optimize this, finding only one possible set where p can win is enough, this speed up my solution 10x.

    An approximation for the complexity is O(log(N) * N^2 * (15C7)^2), the above trick avoids to perform worst case scenario.

    My code solved the input in less than 10s, here is my code: http://ideone.com/9bkbmw

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

    My solution was practically brute-force, it works under 10 seconds.

    Idea is that with 16 participants (largest possible input) there is only:

    16! / 8! / 2^8 = 2,027,025 possible pairings. So brute force all of them. Result of these pairings is at most 16! / 8! / 8! = 12,870 different answers, in most cases it will be less then that. For each of these answers you have to check only 105 potential pairing, which is even faster.

    So I end up with bitmasks showing all possible passing candidates for every level of the tournament pyramid. After that I scan through that pyramid k times and calculate highest pyramid level and lowest pyramid level for each contestant.

    Submission

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

    2n * poly(n)

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

I've just watched last-competitor-with-100-points's (she's called "Tanya") submissions. All of her submissions have the same code not related to any of the problems...

Here comes the question: what for are the source submissions then?

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

    I guess its a rules violation and she will be kicked out.

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

I find it a bit disappointing that the score distribution did not satisfy the constraints described in Problem A :(

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

Feeling awkward having failed only Problem A. What can possible go wrong there? I solved it (almost) using DP (maybe an overkill but I wanted to be sure). Idea is going backward from the end for every item check if it can be start of 1, 2, 3, 4 sequence. Each time take minimal amount of 4 options. Number for head is the answer. Sumbission

`

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

    I did something similar and it worked without problems. Did you assume that the "head" must always be the 4th element in its set (or the 1st, whatever, it's not clear to me how you're counting them) ? If yes, then this is probably the mistake.

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

      Yes, I assumed that it is always first. Still not sure why is it a mistake? Do you mean that I'm missing some opportunity to insert more elements before the first element?

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

        muguerlionut, thank for pointing me in right direction.

        I found my mistake — I don't really make any checks between quadruples of numbers, so based on problem description they also must be different by no more that 10. Studip mistake. Funny part of it is that thousands random test I used to check and recheck my solution also did not take this into account :). At least I have another chance in Round 2 (and would still have it even if they didn't change rules)

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

          Do you mean "b — a ≤ 10, c — b ≤ 10, d — c ≤ 10" this one? If so, how could you skip that if its checked in the sample tests? (15 20 25 40)

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

            I was creating my test cases in the following way:

            1. Create quadruples of numbers in accordance with the rules (b-a <= 10 as well).
            2. Put them together.
            3. Remove x random items from the list.

            Correct answers is most likely x or sometimes less then x.

            Condition I didn't enforce in my tests — and the reason for failure — is that while going from one quadruple of numbers to another there should be no difference of more then 10.

            UPDATE — Very wrong logic above. My only mistake was putting '=' instead of '+=' in the following line:

            		needtoadd = (diff - 1) / 10;

            And my tests didn't catch it because I didn't see a problem in my program producing result smaller then expected...

            → Reply