0

There's a tournament. Players are ID'ed by integers, and play in a tournament style with the integer adjacent to them. So, 1 plays 2, 3 plays 4, 5 plays 6, 7 plays 8. Then, 1/2 plays 3/4, 5/6 plays 7/8, and then 1/2/3/4 plays 5/6/7/8.

Sample input:

8 5
1 2 3 4 5

First line = first number is the number of players in a tournament (always some 2^N number), second number is the number of players who withdrew before the tournament started

Second line = the IDs of the players who withdrew

If a player automatically advances to the next round because the person they would've played pulled out (call this a BYE), increment a count. Output the count in the end.

So the output for the sample input would be 2 (6 automatically advances in the first round because 6 was supposed to play 5 who withdrew, and eventually in the second-to-last round, 6/7/8 automatically advances).

I was thinking of either holding everything in a tree (but that wouldn't really be efficient would it?), or just parsing as you go, and bubbling up the BYEs. The problem with that second solution is I have no idea how to consider/store the relationships in terms of who's going to play who, and how exactly in an implementation are you to bubble something up without a structure.

J. Doe
  • 85
  • 1
  • 6

3 Answers3

1

You can get away with a simple array (of size 2^N). Encode your participants as 0 for absent and 1 for present, and simulate the tournament. In each round player at index 2*k plays agains index 2*k + 1, and the "winner" is moved to index k. A bye condition is a XOR, and the "winner" is OR. In pseudocode,

    while player_count > 1
        for k in range (player_count / 2)
            byes += arr[2*k] ^ arr[2*k + 1]
            arr[k] = arr[2*k] | arr[2*k + 1]
        player_count /= 2

Both space and time are linear in the number of players.

user58697
  • 7,808
  • 1
  • 14
  • 28
0

You can't store anything without structure, but some time structure can be implicit, for example in case of recursion we have stack which we didn't explicitly declare.

Here example of recursive solution:

public class App {
    public static void main(String[] args) {
        // I use 0 based indexing here
        Set<Integer> absent = new HashSet<>(Arrays.asList(0, 1, 2, 3, 4));

        int count = rec(absent, 8, 0);
        System.out.println("count = " + count);
    }

    private static int rec(Set<Integer> absent, int currentGroupSize, int start) {
        if (currentGroupSize == 1) {
            return absent.contains(start) ? -1 : 0;
        }

        int r1 = rec(absent, currentGroupSize / 2, start);
        int r2 = rec(absent, currentGroupSize / 2, start + currentGroupSize / 2);
        if (r1 == -1) {
            if (r2 == -1) {
                return -1;
            } else {
                return r2 + 1;
            }
        } else {
            if (r2 == -1) {
                return r1 + 1;
            } else {
                return r1 + r2;
            }
        }
    }
}
talex
  • 17,973
  • 3
  • 29
  • 66
0

Here is a solution in time O(R log R) and space O(R), where R is the number of retired (withdrawn) players. If the retired players are given in increasing order of ID, then your last insight is correct: you can just read IDs and bubble them up in O(R) time and O(1) memory. This helps when N is much larger than R (e.g. billions), because that precludes storing any array of size N.

Conceptually, retired player IDs are leaves in a tree. Here's the tree for N = 8. I subtracted 1 from all IDs because this turns out to be a bit hacking problem and bit hackers love counting from 0. :-)

           0-7
        /       \
     0-3         4-7
   /     \     /     \
 0-1    2-3   4-5    6-7
 / \    / \   / \    / \
0   1  2   3 4   5  6   7

The idea is to look at compact ranges in the input and figure out how many byes they yield. For example, the range [0-3] yields one bye: no games are played in the left bracket (subtree) and whoever reaches the final from the range [4-7] gets a bye in the final. The same goes for the range [4-7]. Basically, if one range covers one full subtree, that's one bye. Note that we look for maximal full subtrees, e.g. [0-3] and not [0-1] + [2-3] separately.

What about [0-4]? We need to split the range into [0-3] and [4-4]. Then [4-4] is a second subtree (a trivial one with just one node), meaning player 5 will also get a bye. So [0-4] counts as two byes. We determine this by counting the bits in the number 5 (the size of the range). Since 5 = 1012, we get the answer 2. This is the bit hack part, which I will gloss over, but can expand if needed.

One last issue to consider is capping the range size. Let N=1024 and consider the range [4-100]. Starting at 4, the subtree fills up at 7, at which point we should process the range [4-7] (and get 1 bye), then continue from 8 (that subtree would in turn fill at 15 and so on). Computing the right end also involves a bit hack. Consider the starting point 40=1010002. The size of the subtree is given by the least significant bit, namely 10002=8, so we should break after the range [40-47]. Again, I will gloss over the details but can expand if needed.

The C code turns out to be quite short (apologies for not writing Java, it's been a while). For brevity, it counts bits using the built-in popcount function of GCC, but there are many other methods available. Likewise, limiting the range size involves finding the rightmost set bit.

#include <stdio.h>

void startRange(unsigned p, unsigned* start, unsigned* end, unsigned* limit) {
  *start = *end = p;
  *limit = p + (p & -p) - 1;
  printf("started range %u limit %u\n", p, *limit);
}

int processRange(unsigned start, unsigned end) {
  printf("processing range [%u,%u]\n", start, end);
  return __builtin_popcount(end - start + 1);
}

int main() {
  unsigned n, r, p, result;
  unsigned start, end, limit;

  /* read from standard input */
  scanf("%d%d%d", &n, &r, &p);
  startRange(p - 1, &start, &end, &limit);
  result = 0;

  while (--r) { /* read r-1 more numbers */
    scanf("%d", &p);
    p--;

    if (p == end + 1 && p <= limit) {
      /* continue while we have consecutive numbers, but not past the limit */
      end++;
    } else {
      /* close the previous range and start a new one at p */
      result += processRange(start, end);
      startRange(p, &start, &end, &limit);
    }
  }

  /* close any outstanding range we have */
  result += processRange(start, end);
  printf("%d\n", result);

  return 0;
}
Cătălin Frâncu
  • 1,179
  • 8
  • 15