aboutsummaryrefslogtreecommitdiff
path: root/earliest_latest_rounds_players_compete.c
blob: 3784964aaa1d387a04997a4f4dfcb428d88acfa2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 1900. The Earliest and Latest Rounds Where Players Compete
#include "leetcode.h"

/*
 * there is a tournament where 'n' players are participating. the players are
 * standing a single row and are numbered from 1 to 'n' based on their initial
 * standing position. the tournament consists of multiple rounds. in each round,
 * the i'th player from the front of the row competes against the i'th player
 * from the end of the row, and the winner advances to the next round. when the
 * number of players is odd for the current round, te player is in the middle
 * automatically advances to the next round. after each round is over, the
 * winners are lined back up in the row based on the original ordering assigned
 * to them initially. the players numbered 'firstPlayer' and 'secondPlayer' are
 * the best in the tournament. they can win agsainst any other player beofre
 * they compete against each other. if any two other players compete against
 * each other, either of them might win, and thus you may choose the outcome of
 * this round.
 */

int *earliestAndLatest(int n, int firstPlayer, int secondPlayer,
                       int *returnSize) {
  *returnSize = 2;
  int *ans = (int *)malloc(*returnSize * sizeof(int));
  int first = firstPlayer, second = secondPlayer;
  if (first + second == n + 1) {
    ans[0] = ans[1] = 1;
    return ans;
  }
  if (first + second > n + 1) {
    int tmp = first;
    first = n + 1 - second;
    second = n + 1 - tmp;
  }
  int pre = 1;
  int pos = (32 - __builtin_clz(n - 1) < n + 1 - second)
                ? 32 - __builtin_clz(n - 1)
                : n + 1 - second;
  if (first + second == n) {
    if (!(first % 2))
      pre = (first + 2 < second) ? 2 : 1 + __builtin_ctz(first);
  } else if (first + 1 == second) {
    pre = 32 - __builtin_clz((n - 1) / (first + second - 1));
    pre += __builtin_ctz((n - 1) >> pre);
  } else if (first + second <= (n + 1) / 2)
    pre = 32 - __builtin_clz((n - 1) / (first + second - 1));
  ans[0] = pre + 1;
  ans[1] = pos;
  return ans;
}

int main() {
  int rs1, *eal1 = earliestAndLatest(11, 2, 4, &rs1);
  int rs2, *eal2 = earliestAndLatest(5, 1, 5, &rs2);
  for (int i = 0; i < rs1; i++)
    printf("%d ", eal1[i]); // expect: 3 4
  printf("\n");
  for (int i = 0; i < rs2; i++)
    printf("%d ", eal2[i]); // expect: 1 1
  printf("\n");
  free(eal1), free(eal2);
}