summaryrefslogtreecommitdiff
path: root/blog/post/2018-05-08.html
blob: b716be6b1c49ed9c37b9e755afe4a220f52dc21e (plain) (blame)
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
<html><head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<meta name="theme-color" content="#000000">
<title>Chrisoft::Blog</title>
<script type="text/javascript" src="/panel.js"></script>
<script type="text/javascript" src="/blog/footnoter.js"></script>
<script type="text/javascript" src="/blog/aes-js.js"></script>
<script type="text/javascript" src="/blog/scrypt.js"></script>
<script type="text/javascript" src="/blog/sha256.js"></script>
<script type="text/javascript" src="/blog/decryptor.js"></script>
<link rel="stylesheet" type="text/css" href="/common.css">
<link rel="stylesheet" type="text/css" href="/panel.css">
<link rel="stylesheet" type="text/css" href="/theme0a.css" id="theme0a">
<link rel="stylesheet" type="text/css" href="/theme0b.css" id="theme0b">
<link rel="stylesheet" type="text/css" href="/theme1a.css" id="theme1a">
<link rel="stylesheet" type="text/css" href="/theme1b.css" id="theme1b">
<link rel="stylesheet" type="text/css" href="/theme2a.css" id="theme2a">
<link rel="stylesheet" type="text/css" href="/theme2b.css" id="theme2b">
<link rel="stylesheet" type="text/css" href="/theme3a.css" id="theme3a">
<link rel="stylesheet" type="text/css" href="/theme3b.css" id="theme3b">
<link rel="stylesheet" type="text/css" href="/blog/blogext.css">
<script>
function ol()
{
	window.onresize=function()
	{
		if(window.innerWidth<768)
		setupevents();
		else unsetevents();
	}
	window.onresize();
	_decryptonload();
}
function loadTheme(){
	var thm=document.cookie.replace(new RegExp("(?:(?:^|.*;\\s*)thm\\s*\\=\\s*([^;]*).*$)|^.*$"),"$1");
	if(thm.length<2||'0123z'.indexOf(thm[0])==-1||'abz'.indexOf(thm[1])==-1)thm='zz';
	var ent="";
	var d=new Date();
	if(thm[0]=='z')
	{
		var m=d.getMonth()+1;
		if(m>=3&&m<6)thm='0'+thm[1];
		else if(m>=6&&m<9)thm='1'+thm[1];
		else if(m>=9&&m<12)thm='2'+thm[1];
		else thm='3'+thm[1];
	}
	if(thm[1]=='z')
	{if(d.getHours()>=18||d.getHours()<6)thm=thm[0]+'b';else thm=thm[0]+'a';}
	ent=`theme${thm}`;
	var R=new RegExp('theme[0-4][ab]');
	for(var i=0;i<document.styleSheets.length;++i)
	{
		if(R.exec(document.styleSheets[i].ownerNode.id)!==null&&document.styleSheets[i].ownerNode.id!=ent)
		document.styleSheets[i].disabled=true;
		else document.styleSheets[i].disabled=false;
	}
	var thmcolor="";
	switch(thm[0])
	{
		case '0':thmcolor=thm[1]=='a'?'#f59dda':'#2f0933';break;
		case '1':thmcolor=thm[1]=='a'?'#9df59d':'#090933';break;
		case '2':thmcolor=thm[1]=='a'?'#edb47b':'#1f1205';break;
		case '3':thmcolor=thm[1]=='a'?'#a0cdfa':'#051933';break;
	}
	document.querySelector("meta[name=theme-color]").setAttribute('content',thmcolor);
}
loadTheme();
</script>
</head>
<body onload="ol()" style="overflow-x:hidden;">
	<div id="panel" class="TText">
		<ul id="panellist">
			<li><a href="/"><h1>Chrisoft</h1></a></li>
			<li><a href="/blog"><h2>Blog</h2></a></li>
			<li><a href="#"><h3 id="title">Respecting your job</h3></a></li>
			<li><span>Tags</span>
			<ul id="tagslist">
			<li><a href="/blog/list/sophistry/">sophistry</a></li><li><a href="/blog/list/garbage/">garbage</a></li><li><a href="/blog/list/acmicpc/">acmicpc</a></li></ul>
			</li>
			<li id="tocouter">
				<span>Table of Contents</span>
				<ul id="tocroot">
				<li><a class="toctarg" href="#tocanch0">尊重别人的委托 - 关于题目</a></li><li><a class="toctarg" href="#tocanch1">正直者之死 - 关于F题</a></li><li><a class="toctarg" href="#tocanch2">做最坏的打算 - 关于F题和其他</a></li><li><a class="toctarg" href="#tocanch3">一向阴暗的未来</a></li><li><a class="toctarg" href="#tocanch4">Fun facts &amp;c.</a></li></ul>
			</li>
			<li style="margin-left:-0.5em"><a id="prevp" href="2018-05-03.html">Prev post</a></li>
			<li style="margin-left:-0.5em"><a id="nextp" href="2018-05-18.html">Next post</a></li>
		</ul>
	</div>
	<div id="content">
		<h2 id="titleh" class="TText" style="font-wight:normal;">Respecting your job</h2>
		<div id="datetags" class="TText" style="margin-bottom:1em;">2018-05-08<br>#sophistry #garbage #acmicpc</div>
		<hr><div id="article" class="TText">
<article>
<p>
……所以为什么省赛总结起了一个这种奇怪的标题……
</p>
<h2 id="tocanch0" class="tvis">尊重别人的委托 - 关于题目</h2>
<blockquote>
<p>
除非完全失去了对生活的希望,
不然别人委托的工作还是至少应该抱着敬意来完成的。
</p>
</blockquote>
<p>
先不论题目质量(10题中有3题可以网络流乱搞过去),题目中明显的失误就有不少。
虽然这并不在是说北邮的出题人不尊重他们的工作。
(其实可以看出他们已经努力了,Nice try.)
</p>
<div style="text-align:center;"><a href="//filestorage.chrisoft.org/blog/img/sdacm18xa.png"><img style="width: 50%;" src="//filestorage.chrisoft.org/blog/img/ssbsthumb_1024x1024_sdacm18xa.png"></a><br><i>正式赛B题</i></div>
<p>
输出呢?经验是什么?数据范围呢???这种随便过一遍就能审阅出的明显问题,
出现在省级比赛上,真的不会让人看不起吗?
裁判组在比赛开始一刻钟有队伍提出质疑之后才(陆续)发现了此题中的各种问题。
即使是印刷了错误版本的题目,依然不能原谅吧?
</p>
<div style="text-align:center;"><a href="//filestorage.chrisoft.org/blog/img/sdacm18xd.png"><img style="width: 50%;" src="//filestorage.chrisoft.org/blog/img/sdacm18xd.png"></a><br><i>Real Contest.</i></div>
<p>
Real contest? Faux contest?
</p>
<div style="text-align:center;"><a href="//filestorage.chrisoft.org/blog/img/sdacm18xb.png"><img style="width: 50%;" src="//filestorage.chrisoft.org/blog/img/ssbsthumb_1024x1024_sdacm18xb.png"></a><br><i>用Gill Sans作正文字体?</i></div>
<p>
即使用伦敦地铁用的字体也无法改变你英语差的事实。另外,
1Il只有用游标卡尺才能量出区别的字体用在科技类文本里大概不太好吧?
</p>
<div style="text-align:center;"><a href="//filestorage.chrisoft.org/blog/img/sdacm18xc.png"><img style="width: 50%;" src="//filestorage.chrisoft.org/blog/img/ssbsthumb_1024x1024_sdacm18xc.png"></a><br><i>最好的防AK方式当然是题意杀啦</i></div>
<p>
最后是一道没有人能读懂的题。敝校公认英语最强的两位队员没有一个看懂的。
感兴趣的读者可以挑战一下。<b>要能够解释样例才行喔</b></p>
<h2 id="tocanch1" class="tvis">正直者之死 - 关于F题</h2>
<p>
于是上面写了那么多,到这里却才是本次省赛真正的亮点。
下面我就以此题最大受害者
<a id="n1" href="#note1" class="note">[1]</a>
的身份来讲述一下F题的故事……
</p>
<p>
首先来看一下题目(图片比较乱…):
</p>
<div style="text-align:center;"><a href="//filestorage.chrisoft.org/blog/img/sdacm18xe.png"><img style="width: 50%;" src="//filestorage.chrisoft.org/blog/img/sdacm18xe.png"></a><br><i>F题题面</i></div>
<p>
实际上F题是容斥里面比较常规甚至可以说是相当简单的,
题目本身也可以说是中规中矩。思路其实很明显:设条件
x<sub>1</sub>≠x<sub>2</sub>
x<sub>2</sub>≠x<sub>3</sub>
x<sub>3</sub>≠x<sub>4</sub>
x<sub>4</sub>≠x<sub>1</sub>
分别为A, B, C, D,同时也用A, B, C, D表示符合相应条件的集合。
全集为仅需满足范围限制的四元组构成的集合。
容易发现答案并不好通过A, B, C, D的集合大小求得。
正难则反。∁A, ∁B, ∁C, ∁D及它们的交的大小更容易求得,而且
∁(∁A∪∁B∪∁C∪∁D)恰好为所求的集合。多么基本的容斥……
</p>
<p>
然而事情从这里开始变得诡异了起来。作为一道容斥,
自然有把代码写成一坨屎的可能性。我的代码很不幸就写成了一坨。
写到75%的时候觉得头大,于是直接砍掉重练。这次相对来说比较顺利,
样例也是一发就通过了。然而,
以往根本不负责数学题的我<a id="n2" href="#note2" class="note">[2]</a>
对自己写的容斥持怀疑态度,决定写个暴力对拍一下。这下好。
最水(没样例水)的数据就把我的程序卡掉了。于是就开始挂机找问题。
这时比赛已经进行到了80分钟,我们队还没有瞟过一眼榜。于是找出榜一看,
F题已经被过穿了。与此同时我还注意到这题的一血是开场<b>6分钟</b>
的时候被我校一支相对较弱的挂星队拿到的。这下更好了。
虽然是基本的容斥,但是按山东选手的水平,也不能6分钟写完吧?
于是就开始想自己是不是想复杂了,然后就开始试图换思路,
就有了题面附近大量乱七八糟的草稿以及下面这张图……
</p>
<div style="text-align:center;"><a href="//filestorage.chrisoft.org/blog/img/sdacm18xf.png"><img style="width: 50%;" src="//filestorage.chrisoft.org/blog/img/sdacm18xf.png"></a><br><i>wtf???</i></div>
<p>
后来甚至想到了把整个区间分8段然后乘法原理强上的思路……
然而因为依然难写所以也被否决了。此时的我,大概已是意识模糊,不省人事,
以至于当队友跟我说「还是继续容斥吧」之后,
我甚至无法用容斥手算出正确的结果了。。。
最后我就直接宣告死在了这道题上。另外一个队友最后30分钟试图用乘法原理强搞,
不过到比赛结束也没有搞出来。
<a id="n3" href="#note3" class="note">[3]</a>
</p>
<p>
当然如果事情就这么结束了的话,也不足以让这题成为本次比赛最大的亮点。
比赛结束后我问了一下那支6分钟过此题的队伍,得知他们
<b>直接输出的四个区间长度的积</b>。当时我就立刻晕了:
莫非是花了四个小时在完全不同的一道题上?不过这题这么短应该不会读错吧?
于是我试图询问他有没有对循环不等的条件有印象,他表示不知情。我……
不得不猜测出题人rand生成的数据,
而且很不幸这10<sup>6</sup>组数据里面没有一组区间有重叠部分的。
此时我的内心十分平静,甚至想对裁判组施展白帝圣剑:
F题什么难度你们不知道吗?6分钟被人过了就不看眼他的代码吗?
<a id="n4" href="#note4" class="note">[4]</a>
</p>
<p>
当然如果这件事情只有这么简单,显然依然不足以让此题成为本次比赛最大的亮点。
闭幕式之前在山财校园中闲逛时,听到了这样的对话:
</p>
<blockquote>
——「有个队四层循环就过了。」<br>
——「那有什么,我们队连样例都没过也过了。」
</blockquote>
<p>
听到这段对话的我表面强装镇定,内心早已就地阵亡。
10<sup>42</sup>的计算量都能过,难道这题T=0?
</p>
<p>
后来通过官方渠道证实,这题在比赛过程中用于评测的数据是全空的。
还导致了最终裁判组和主办方之间意见的不一致。裁判组最后拒绝签字,
这其实是负责任的行为,
但是裁判组也可以以此把锅甩给PC^2和主办方所谓的「技术支持组」了。
首先,PC^2是一个浑身上下都是bug,设计上也存在一些问题的程序。
我们在配置17年校赛的时候,就遇到过PC^2无法保存题目名称的bug。
各种各样的连接问题也是数不胜数,Judge还会爆Java内存。但是即便如此,
裁判组仍然对此负有不可推卸的责任:如果在6分钟时就发现了问题,
完全有时间重新上传数据并进行重测,对比赛也不会造成太大影响。
而事到如今,这个6分钟通过的队伍,
让大量其他不应该如此快速「通过」此题的队伍「通过」了此题,
同时也对我们这样完全没有专攻数学题目的队伍造成了不可估量的打击,
最后还让各方闹翻。这样的疏忽……可以算是epic fail了。
至于推锅给「技术支持组」,
一个有多年出题经验的学校把锅丢给一个没几年ACM经验的学校,
可以说是非常不公了。当然由于我并不清楚这其中的分工,
所以并不好对此妄加评论。然而我认为主办学校的「技术支持组」,
本来就不应该负责太多与比赛直接相关的事务。
</p>
<p>
其实可以合理地预测,
比赛过程中没有验算而且在120分钟内通过此题的队伍,能够通过rejudge的
也许只是凤毛麟角。
</p>
<p>
至于这题对我队的影响,远没有未过一题这么简单。
已经理论掉的I题也因此驾鹤西去了。当然,经历了无数次「几乎成功」的失败之后,
我本人对此早已麻木,也就写不出×乎上那种动情的文字,
所有的心情只能汇集成一个「sigh」了。
</p>
<p>
然而以后碰到这种情况估计还是会死的。<s>人家就是如此正直,你有什么办法。</s>
不过讲道理总不能把自己成功的希望寄托在别人的失误上吧(
</p>
<h2 id="tocanch2" class="tvis">做最坏的打算 - 关于F题和其他</h2>
<p>
事已至此,任何的假设都成了虚拟语态。更应该考虑的显然是找一个合适的解决方案。
在这个问题上,即使我是「F题最大的受害者」,我仍然是十分理解裁判组的,
因为类似的事情在我们举办校赛的时候也遇到过。
所以我也没有像某些参赛者一样去「围攻」裁判组(我甚至没有加群),
因为我们都清楚被围攻的滋味并不好。从出题人在知乎上的表态看,
他们也承受着巨大的压力。
但是F题的问题实际上与出题人的关系不大——更多在于题目配置及比赛过程中的疏忽。
<a id="n5" href="#note5" class="note">[5]</a>
</p>
<p>
至于在如何处理的问题上,从自私的角度考虑,当然是删除F题对我们最有利:
<s>因为这样我们队就变成第一了</s>。其实无论是rejudge,维持原判还是直接删除,
对部分队伍来说都是不公平的。较为公平的解决方案,
无非是订正数据并延长比赛时间,甚至重赛。
但是无论是承办方还是从北京远道而来的裁判,谁能承受延时或者重赛的负担呢?
<a id="n6" href="#note6" class="note">[6]</a>
</p>
<p>
在组织程序设计竞赛的时候,
负责比赛准备的各方往往对比赛过程中可能发生的各种事故不做太多预案,
而是更多地依赖提前把问题减少到最少。然而人总是不可避免地犯错,
PC^2也没有应对这种问题的功能(甚至全部重测的功能)。是时候让PC^2退休了。
</p>
<h2 id="tocanch3" class="tvis">一向阴暗的未来</h2>
<p>
与山东其他高校不同,山大的ACM实验室似乎即将成为各路教员追逐名利的工具。
真正一心为了实验室发展的人,不是根本没有,就是完全被边缘化了。
</p>
<p>
当然,在现在各方都没有任何实际行动的前提下,并没有办法得出什么实质性的结论。
不过,未来悬而未决的感觉也不好啊(
</p>
<h2 id="tocanch4" class="tvis">Fun facts &amp;c.</h2>
<ul>
<li>苟狗写了全部AC代码。<s>难道我成功培养了新一代代码手</s></li>
<li>最后半小时队友试图抢救F题时,已经空状态的我在一边理论I题……
<div style="text-align:center;"><a href="//filestorage.chrisoft.org/blog/img/sdacm18xg.jpg"><img style="width: 50%;" src="//filestorage.chrisoft.org/blog/img/sdacm18xg.jpg"></a>
<br><i>没用尺规</i></div>
<br>
……实在惭愧
</li>
<li>山财,作为一所刚刚开始搞ACM的学校,对这场比赛准备得可以说是很充分,
也十分有诚意了。为了防止发生去年滚榜时的尴尬情形,
他们甚至还提前排练了滚榜环节。
虽然后来发生了各种不可预见的事故导致榜没有滚成,
但是这不足以彻底抹杀他们为准备这场比赛付出的努力的。
</li>
<li>至于北邮,这所已经为山东省赛命题(至少)两年的学校,
在命题这方面自然也可以说是十分有经验了。即使遇到了各种各样意料之外的事情,
也不应该完全否定他们的工作——因为出题本身就不是一个容易活啊。
</li>
<li>14级学长的自嘲:「有了我们之后就再也没捧过杯」。
<s>希望明年可以换种方式自嘲。</s></li>
</ul>
</article>
<!--
vim: syntax=html
-->
</div><br><hr>
		<div class="TText" id="notediv" style="font-size:80%;"><span class="TText"><a id="note1" href="#n1">[1]</a>: 读完这部分之后你就可以知道为什么我可以给自己冠上「最大受害者」的称号了。<br></span><span class="TText"><a id="note2" href="#n2">[2]</a>: FYI,我们队的人员出现了调整,
原来负责数学题的队友离开了<br></span><span class="TText"><a id="note3" href="#n3">[3]</a>: 尽管在302分钟时发现比赛还没有被关闭就随手交了一发,
然而那个提交并没有被评测。<br></span><span class="TText"><a id="note4" href="#n4">[4]</a>: 就连在我们校赛的评测过程中,即使会去玩PC^2 Judge里的"I'm bored",
每个题前几名AC的队伍的代码我们也是会看的。<br></span><span class="TText"><a id="note5" href="#n5">[5]</a>: 另,如果出题组和裁判组是完全不同的两队人,
他们在比赛前应该有充分的沟通。而且出事之后出题人的道歉也无法代替后者。
某种程度上我依然认为裁判组应当亲自有诚意、非匿名地正式道歉。<br></span><span class="TText"><a id="note6" href="#n6">[6]</a>: 今年我校校赛时有一位负责人在未与所有其他负责人商讨的情况下,
因在最后30分钟发现数据出现问题擅自将比赛延长,
导致实验室内部对此产生争议。<br></span></div>
		<div id="insanch" style="height:3em;"></div>
		<div id="footer" style="">
		<div id="pagesw" class="TText" style="width:100%;height:0.5em;"></div>
			<div style="text-align:center;" class="TText">
				Proudly powered by SSBS <reduced style="font-size:70%;">(the static stupid blogging system)</reduced> 2.5
				<br>
				Content licensed under CC BY-SA 4.0. <span id="purgep" style="display:none;font-size:70%;">This page has passphrase(s) stored. Click <a href="javascript:_purgep()">here</a> to purge.</span>
			</div>
		</div>
		<div id="cmdbuf" class="TText" style="transition:500ms;padding:1em;font-size:2em;color:white;position:absolute;background-color:rgba(0,0,0,0.6);left:50%;top:50%;transform:translate(-50%,-50%);pointer-events:none;opacity:0;">
		</div>
	</div>
	<div id="decryptui" style="display:none;opacity:0;color:white;z-index:1000;position:fixed;left:0;top:0;width:100%;height:100%;background-color:rgba(0,0,0,0.4);transition:opacity 0.5s;">
		<div id="decryptdlg" class="TText" style="padding:10px 20px;position:absolute;left:50%;top:50%;transform:translate(-50%,-50%);background-color:rgba(0,0,0,0.6);">
			<div id="keyhint" style="margin-bottom:8px;"></div>
			<div style="margin-bottom:8px;">Key: <input id="keyinp" type="text" style="color:#fff;"></div>
			<div style="height:2.25em;">
			<button id="btndecrypt" onclick="decryptor(decid,document.getElementById('keyinp').value);" style="position:absolute;left:20px;">Decrypt</button>
			<button onclick="hidedecryptui();" style="position:absolute;right:20px;">Cancel</button>
			</div>
		
	</div>


</div></body></html>