Competitive Programming►Problems

IOI 2014 - 猜謎遊戲(game), TIOJ 1896

Link(original): http://www.ioinformatics.org/locations/ioi14/contest/day1/game/twn.pdf
Link(TIOJ): http://tioj.ck.tp.edu.tw/problems/1896

這題有三種解法，第一種大測資會TLE只能拿42分，不過我只想到第一種。

題解前，先做個定義:

  • 圖G: 由 尚未詢問過的邊 和 詢問過且回答yes的邊 構成
  • 圖H: 由 詢問過且回答yes的邊 構成

solution 1

一個很簡單的演算法: 盡量回答no，但假如這次詢問會造成G不連通，則回答yes。
實作上判斷連通需要O(N^2)，有O(N^2)次詢問，總複雜度O(N^4)
這可以用歸納法證明，不過由於這解法也不能AC這題，就不詳細說明啦XD

solution 2

我們可以發現一個性質，假如H裡面的同一個連通分量之中，有兩點間有未詢問的邊，那對方只要把那條邊留到最後，自己就必輸了；反之，如果演算法能保證那之中沒有未詢問的邊，則必勝。 (solution 1也符合這個性質)

做法是: 對於每次詢問的兩個點，它們一定位於H裡面兩個不同的連通分量，假如這兩個分量之間在G裡面只剩下一條邊了，就回答yes，否則回答no。

實作: 用一個二維陣列紀錄連通分量之間兩兩有幾條邊(初始都是1條)，當合併兩個分量時，O(N)將它們連到別的連通分量之間的邊數更新，至多更新N-1次，所以總複雜度O(N^2)。

AC code (on TIOJ)
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
#include "lib1896.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int ec[1500][1500]; //remain edges count between two components
int ds[1500]; //disjoint set
int find(int i)
{
	if(ds[i]==i) return i;
	else return ds[i]=find(ds[i]);
}
void initialize(int _n)
{
	n=_n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			ec[i][j]=1;
	for(int i=0;i<n;i++)
		ds[i]=i;
}
int hasEdge(int u,int v)
{
	u=find(u); v=find(v);
	if(ec[u][v]==1)
	{
		ds[v]=u;
		for(int i=0;i<n;i++)
			if(ds[i]==i && i!=u)
				ec[i][u]=ec[u][i]=ec[i][u]+ec[i][v];
		return true;
	}
	else
	{
		ec[u][v]--;
		ec[v][u]--;
		return false;
	}
}

solution 3

一行解: return ++c[max(u,v)]==max(u,v)
很神奇的解法，對於每個點，我們讓它連到恰好一個編號比較小的點，當只剩下一個編號較小的點時就回答yes。
我覺得這思路其實比前兩種解法都還要短啊! 不過就是沒想到要這樣構造。

AC code (on TIOJ)
1
2
3
4
5
6
7
8
9
10
11
12
13
#include "lib1896.h"
#include <algorithm>
#include <cstring>
using namespace std;
int c[1500];
void initialize(int n)
{
	memset(c,0,sizeof(c));
}
int hasEdge(int u,int v)
{
	return ++c[max(u,v)]==max(u,v);
}

參考資料:

官方題解 http://ioinformatics.org/locations/ioi14/contest/day1/game/game-solution.pdf
NOI題解(簡體中文) http://download.noi.cn/T/2014/IOI2014jietibaogao.pdf
http://gagguy.blogspot.tw/2014/07/ioi-2014-game.html
http://mathandalgs.com/?p=1042
https://betaveros.wordpress.com/2014/07/26/one-line/
http://blog.brucemerry.org.za/2014/07/ioi-2014-day-1-analysis.html
jd3 <– 很重要，因為我都看不懂詳解，找人討論後就懂了