Editorial for Trại hè Đà Lạt 2020 - Thi đấu vòng tròn
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Biểu diễn quan hệ thắng thua bằng đồ thị: Mỗi đội là một đỉnh, có cung nối từ ~A~ tới ~B~ khi đội ~A~ thắng đội ~B~. Ta thấy tổng số cung vào và cung ra của mỗi đỉnh đều là ~n-1~. (do mỗi đội chỉ thi đấu ~1~ lần với ~n-1~ đội còn lại)
Nhận xét: Để cực đại số lượng TCIRCLE thì ta phải cực tiểu số chênh lệch cung vào và cung ra của mỗi đỉnh. Ta chia ~2~ trường hợp như sau:
Trường hợp 1: ~n~ lẻ
Khi đó ta có thể cho mỗi đỉnh có ~\frac{n-1}{2}~ cung vào và ~\frac{n-1}{2}~ cung ra.
Số TCIRCLE = số cách chọn ~3~ đỉnh có mối quan hệ tcircle.
Ta thấy việc tính trực tiếp quá khó, nên ta tính phần phủ định
Số TCIRCLE = số cách chọn ~3~ đỉnh bất kì - số cách chọn ~3~ đỉnh không có mối quan hệ tcircle.
Ta thấy với mọi cách chọn ~3~ đỉnh mà không có mỗi quan hệ tcircle, luôn tồn tại một đỉnh có ~2~ cung ra (và đồng thời có một đỉnh có ~2~ cung vào). Vì vậy ta sẽ tính số cách chọn ~3~ đỉnh mà trong đó có ~1~ đỉnh có ~2~ cung ra, vì mỗi đỉnh có ~\frac{n-1}{2}~ cung ra nên mỗi đỉnh có ~{\frac{n-1}{2} \choose 2}~ (tổ hợp) cách chọn
Như vậy, số TCIRCLE = ~{n \choose 3} - n \times {\frac{n-1}{2} \choose 2}~.
Trường hợp 2: ~n~ chẵn
Vì ~n~ chẵn, nên có ~\frac{n}{2}~ đỉnh có số cung ra nhiều hơn ~1~ so với số cung vào, và có ~\frac{n}{2}~ đỉnh có số cung vào nhiều hơn ~1~ so với số cung ra. Đỉnh có số cung ra nhiều hơn thì có ~{\frac{n}{2} \choose 2}~ cách chọn. Đỉnh có số cung ra ít hơn thì có ~{\frac{n-1}{2} \choose 2}~ cách chọn.
Như vậy, số TCIRCLE = ~{n \choose 3} - \frac{n}{2} \times {\frac{n-1}{2} \choose 2} - \frac{n}{2} \times {\frac{n}{2} \choose 2}~.
Code tham khảo:
#include <bits/stdc++.h>
using namespace std;
/***Crazy Macros***/
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define reu(i,a,b) for(ll i = (a); i <= (b); ++i)
#define red(i,a,b) for(ll i = (a); i >= (b); --i)
typedef int64_t ll;
typedef deque<int> di;
typedef deque<ll> dll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef tuple<ll,ll,ll> iii;
const ll inf = 2e9;
/***Common Functions***/
ll inp() {ll x; cin >> x; return x;}
string inp_str() {string x; cin >> x; return x;}
ll sqr(ll n) {return n*n;}
ll power(ll a, ll b, ll mod = inf) {
ll res = 1; a %= mod;
for(ll i = b; i > 0; i /= 2) {
if (i % 2) res = (res*a) % mod;
a = (a*a) % mod;
} return res;
}
ll gcd(ll a, ll b) {
while (b > 0) {ll tmp = a % b; a = b; b = tmp;}
return a;
}
bool is_pal(string s) {return equal(all(s), s.rbegin());}
void fast_io() {ios::sync_with_stdio(0); cin.tie(0);}
void file_io(char *in, char *out) {
freopen(in, "r", stdin);
freopen(out, "w", stdout);
}
void print_bool(bool a) {
if (a) cout << "YES\n";
else cout << "NO\n";
}
/***Main Code***/
ll n;
void Input() {
cin >> n;
}
ll nCr(ll n, ll r) {
ll ans = 1;
reu(i, n-r+1, n) ans *= i;
reu(i, 1, r) ans /= i;
return ans;
}
void Solve() {
ll ans;
if (n%2) {
ans = nCr(n, 3) - n*nCr((n-1)/2, 2);
} else {
ans = nCr(n, 3) - n/2*nCr((n-1)/2, 2) - n/2*nCr(n/2, 2);
}
cout << ans;
}
int main()
{
fast_io();
// file_io("TCIRCLE.INP", "TCIRCLE.OUT");
Input(), Solve();
return 0;
}
Comments