NWERC 2018

J. Jinxed Betting

模拟+加速，特点大概就是数据特大，中间有一些轮次是重复的，需要找到重复的规律然后一次模拟好多轮

Prompt:

• bet between 2 teams each round, win: +1, lose: 0
• J starts in lead
• J always follows the majority from runners-up
• for how many rounds will J stay in the lead?

Constraints

• \[3 \leq n \leq 10^5\]
• \[0\leq 𝑝_𝑖 \leq10^{16}\]

Reason

• worst case for J: runners-up split evenly, and the majority loses
  • majority = \(\lceil{t/2}\rceil\)
• naive simulation: simulate the score of all betters until someone catches up with J
  • \(\Theta(r\cdot n)\), \(r\) can be as large as \(10^{16}\)
• improved simulation:
  • observation:
    • the runners-up group increases each round until it cannot be divided, i.e. the group has only one person; but in the round that this only person loses, other former-runners-up will catch up and repeat the previous pattern
    • the other groups simply increases for each round
    • after some rounds, the next group will catch up with the runners-up
    • we can simulate according to the number of people
  • suppose:
    • maxx = the score of runners-up, t = the number of runners-up
    • d = the difference between the current maxx and the second largest score other than J’s
    • \(k = \lfloor{log_2(t)}\rfloor\), which means for how many rounds the runners-up group can be divided evenly
  • in \(1 + k\) rounds, maxx increases \(k\)
  • in \(1 + k\) rounds, the other score groups increase \(1+k\)
    • -> \(d\) reduces \(1\) in every \(1 + k\) rounds
  • in \(d \cdot (1 + k)\) rounds, the second largest score group is going to catch up with the first, we should update \(t\) and \(k\)
  • we can speed up by simulating \(d \cdot (1 + k)\) rounds at a time, where max increase by \(d\cdot k\)
    • Special case: \(t\) will not increase before maxx exceeding \(J\)
      1. there is no group to be merged into runners-up
         • i.e. t == n-1
      2. runners-up take over the lead of J before the next merge happens
         • i.e. d * k + maxx >= J - max += (J - maxx) / k * (1 + k) + (J - maxx) % k

Solution

#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define LL long long

void solve() {
    int n;
    cin >> n;
    vector<LL> p(n);
    for (auto &it : p)
        cin >> it;

    sort(p.begin(), p.end(), greater<LL>());

    LL maxx = p[1], res = 0;

    for (int t = 1;; t++) {

        while (t + 1 < n && p[t + 1] == p[t])
            t++;

        int k = log2(t);
        LL delta = p[0] - maxx;
        LL d = p[t] - p[t + 1];

        if (t == n - 1 || k * d + maxx > p[0]) {
            res += (k + 1) * (delta / k) + delta % k;
            break;
        } else if (k * d + maxx <= p[0]) {
            maxx += k * d;
            res += (k + 1) * d;
        }
    }
    cout << res << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}