AFAIK

Valar Morghulis

The cost for Power Ups has changed since version 0.7, so this post is no longer applicable.

\(\newcommand{\eps}{\varepsilon} \newcommand{\R}{\mathbb{R}}\) Vampire Survivors is a game released in early access near the end of 2021. It received 110k recommendations in one month, which is pretty amazing given its minimal aesthetics and seemingly low production costs. I also played it a lot back then, but I won't talk about its gameplay here. Instead, this post discusses the (old) Power Up mechanism and some of the math behind it.

The Power Up mechanism in Vampire Survivors is similar to Kingdom Rush's Upgrades, where you spend the gold earned during gameplay to make permanent gains (e.g., increase move speed by x%). As per the notes in Fandom, the cost for a Power Up is defined as: \[ Price = \text{InitialPrice} \cdot (1 + \text{Bought}) \cdot \left(1 + \frac{\text{TotalBought}}{10} \right), \] where \(\text{InitialPrice}\) is the initial price of the Power Up, \(\text{Bought}\) is the number of purchased ranks for this Power Up, and \(\text{TotalBought}\) is the total number of purchased ranks among all Power Ups. What's interesting is that the order in which you buy Power Ups actually matters!

Intuitively, we should purchase expensive Power Ups first. For example, IGN recommends maxing out Power Ups with the highest initial costs first. However, this is not optimal. Suppose we have two Power Ups, A and B. A has 5 ranks with an initial price of 1, while B has only 1 rank with an initial price of 2. If we max out A first, the total price is: \[ 1 \times 1 + 1.1 \times 2 + 1.2 \times 3 + 1.3 \times 4 + 1.4 \times 5 + 1.5 \times 2 = 22, \] and if we max out B first, the total price is: \[ 1 \times 2 + 1.1 \times 1 + 1.2 \times 2 + 1.3 \times 3 + 1.4 \times 4 + 1.5 \times 5 = 22.5. \]

So, here is our central topic today:

What is the optimal order for buying all Power Ups?

Read more »

几个星期前,我和朋友们去了趟湾区的后花园 Lake Tahoe,这里就随便写点东西记录一下。由于时间比较短,我们只过了一个周末,所以显得这篇文章尤为流水帐 23333

9.14

由于早上要赶路,我们八点钟就起床了。熟悉我的人都知道,这个时间点对我特别早,然而这天我却因为还在倒时差,早早就起床了。中午在 Sacramento 吃的桂林米粉,Top Choice Restaurant,味道挺不错的,而且这价格真是太让人感动了,放在湾区怕是要翻个倍。

下午我们搞了个 kayak,六个人分成三组,我和胡老师一组。划之前我们又在开玩笑说会不会翻船。脸哥信心满满,这次绝对不会翻船。然而天公不作美,天气预报告诉我们下午的风不小。这次我们租的是 Tahoe 特色透明小船,因为 Tahoe 的湖水特别清澈,透明小船就会有一种悬浮的感觉。我不由想到当年的图形学大作业了,我写了一个 AMCMCPPM 算法(自适应马尔可夫链蒙特卡洛渐进式光子映射,特别适合用来装逼),里面还有一张 渲染图 ,就和我在 Tahoe 看到的一样。

透明 Kayak
Lake Tahoe (from Sand Harbor)

和我们同行的还有两个导游,估计是来保护我们的。而导游的 kayak 很特别,可以用脚踩着划,所以我们就看到导游一边刷手机,一边划 kayak,而我和胡老师死命划,划的手臂累死了,却只能望其项背。不过速度不重要,重要的是,我和胡老师友谊的小船,在不断进水!一个浪打过来,船头迎浪而上,浪过以后,船头重重打到水面上,激起的浪花落入船中,而我们还没有办法把水排出去。更要命的是,这还是个正反馈,已经进的水越多,船就越沉;船越沉,就越容易进水,再这样下去,我和胡老师就要上演泰坦尼克号了……我们试图在湖中泼一下水出去,但是看起来效果不大,最后我和胡老师一致决定:离目的地不远了,赶紧在船沉之前划到目的地,然后下船排水。可喜可贺,我和胡老师终于逃离了这艘 sinking boat……

返程下船的时候岸边浪很大,胡老师在前排我在后排,导游帮我们抓着 kayak 我们就可以下船了。在这里我犯了一个致命错误,初中物理书上经常提到的,为什么水比看上去的浅?我看着挺浅的,就自信一脚踏下去,直到没过了腰才后悔莫及,甚至一个浪冲过来,我的拖鞋都差点无了……

整体而言,这次 kayak 体验挺好的,风景也不错,但是问题在于周围没啥设施,我们走出来后脚底一堆沙子,但是周围没有一个水龙头可以冲一下脚,就很难受……

划了 kayak 后,我们就去吃饭了。由于我们也不期望 Incline Village 这边有啥好吃的餐厅,我们就在 Google Map 上随便看看了。环顾一圈,我们找到了一家 炸鸡店,评分高达 4.9,堪称是 Incline Village 评分最高的餐馆。于是我们就一致决定是它了。没想到的是,这家炸鸡店做的特别慢,而我们还准备去 Cave Rock 去看日落,就只好在车上吃了。

Cave Rock 那边不是很好停车,我们几个人先下车之后有人去停了车。Cave Rock 那里一堆大石头,坡度不小,手脚并用才好上去,幸亏这里石头很实,踩上去不会晃悠。由于就在湖边上,拍的日落还挺好看的。刚日落的时候云是灿烂的金黄色,太阳落下去后云变成了赤陶色,甚至有种不真实的模糊感。lzy 和 tjc 来的比较晚,想爬上去的时候已经比较黑了,担心安全就没上去了,特别是下山比上山还危险。

Cave Rock 上的晚霞
爬 Cave Rock

爬完 Cave Rock 后我们就去买了点东西,给明天的活动准备一下,然后租的 AirBnB 休息了。说起来这一段时间刚好 Incline Village 有山火,好像就在我们租的 AirBnB 旁边。经过 lzy 缜密分析查资料,最后决定风向应该是远离我们的方向。要是突然风向变了,睡到一半被烟薰起来就尴尬了。

9.15

胡老师起了个大早,开始给大家做早餐。昨天晚上胡老师机智地买了 bacon,这样就可以不用买油了,可以用 bacon 的油来煎鸡蛋。我也来大显身手,然后煎糊了 sausage……

今天的第一站是 Ed Z'berg Sugar Pine Point State Park。公园地上一堆松果,你说的我都懂,可是为啥松果这么大?胡老师大为震撼,决定捡一个松果给汤姐做礼物。胡老师又注意到这松果上有些粘液,还有种奇特的芬芳,然后意识到这就是传说中的松脂吗……而且这个公园叫做 Sugar Pine Point State Park,那想必这里的松树都是 Sugar Pine 咯,有没有勇士来尝尝是不是真的是甜的 2333

Sugar Pine 树上有一些小地衣

这个公园里还有一个网红景点,是一段废弃铁轨延伸进清澈的湖水里。说实话第一次看的时候感觉就这?但是拍了照之后再加几个滤镜修修图感觉还挺不错的……

铁轨,湖,与云

第二站是 Emerald Bay State Park。今天的风明显比昨天大,我在 Vikingsholm Trail Head 被风吹的不行了,但是这里的风景确实不错,从这里能看到 Fannette Island。理论上附近还有一个 Eagle Fall,到了之后实在让我大跌眼镜,就这???别说是 Fall 了,你说这是个 Creek 我都将信将疑……

Lake Tahoe (from Emerald Bay State Park)

然后我们就去了 Heavenly。这里有个大缆车,可以通往一个高处的观景台(Heaven?)。不得不说,站得高看得远,湖景能一览无余,虽然票价要 $75……但从另外一方面来说,高处不胜寒,我还穿了一件短袖,风还呜呜的吹,冻死我了。缆车的终点是一个游乐园,我们只玩了其中一个项目,就是一个可以自己控制速度的过山车。说是能自己控制速度,但是对我这种不高的人不太友好,我需要弯腰用力才能把速度加满,不然就只能慢慢游了。

Lake Tahoe (from Heavenly)

不知不觉已经到晚饭时间了。晚上我们吃的是 Edgewood Restaurant,一家 fine-dining 餐馆。这里环境挺好的,一个很大的落地窗可以看外面的湖景。说起来我一直在思考为啥湖面上有两种颜色,一种是正常的蓝色,一种是棕色,还成带状分布,最后得出结论:这带状分布的棕色是镜子反光出来的我们背后的墙上那一条棕色装饰带……

吃完饭后我们就跑路了,天黑了不好开夜路。路上我们正聊着天(@胡老师和 tjc),我突然发现外面的晚霞超好看,脸哥便拍下了这张晚霞照片,比昨天的还好看,梦幻的粉红色:

回家路上拍的晚霞

很多文件格式都是以一个 Magic number 开始,例如 Java 编译后的字节码文件就是以 CAFEBABE 开头。Wikipedia 上还有一个 ,里面放了很多好玩的 magic number,例如 DEADBEEF (还有个音乐播放器叫这个名字)和 FEE1DEAD (linux 的 reboot syscall 中用到)。于是我就心血来潮,能不能整出类似的看起来像英文词组的 magic numbers 。

首先我们要限定一下范围:

  • 字符串长度限制为恰好为 8;
  • 能被拆成一个或多个英文单词。由于英文单词也没有准确的定义,和之前一样,我这里采用 unix 自带的字典。
  • 字符集允许 0-9A-F 。这字符集有点小,但是我们可以整一些字符的 alias
    • O => o
    • I => 1
    • L => 1。由于 IL 都映射到了 1,所以我限制这两个字母不能同时出现
    • ATE => 8
    • 或许可以允许 S => 5
    • 或许可以允许 K => C
    • 或许可以允许 G => 9
  • 每个拆分的单词长度在 3-8 之间。

事实上,我们可以先看一下那些单词可以在这些规则下表示出来。

跑了之后发现里面这样 unix 自带字典 /usr/share/dict/words 太大,23w 个词,太多词我不认识了……为了解决这个问题我决定按照词频排序,于是我找到了 wordfreq 这个 repo。虽然他因为 AI generated content 污染决定不更新词频统计了,但是我们还是相信它吧。于是我们把词限定在这两个交集:可以去除一些人名地名、过去分词、专有名词,还可以按照词频排序。

我先看看有那些词替换之后直接就是 8 个字符。这种词总共只有 8 个:

1
2
3
4
5
6
7
8
ACC01ADE => accolade
F01DAB1E => foldable
CA11AB1E => callable
DEADFA11 => deadfall
CAB00D1E => caboodle
D011FACE => dollface
C0C0B010 => cocobolo
C0CC1D1A => coccidia

但是如果你允许 S => 5 的话,small list 都有一些了:

1
2
3
4
5
6
7
8
BA5EBA11 => baseball
DECEA5ED => deceased
A55E55ED => assessed
C01055A1 => colossal
5E1F1E55 => selfless
D15EA5ED => diseased
BA5E1E55 => baseless
5CAFF01D => scaffold

剩下要组词的话,由于限制 8 个字符,所以只能是一个 3-5 字符的词 + 一个 5-3 字符的词。这样的词总共只有 300 个左右,列表如下:

3-5 字符的词

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
A11      => all
D1D => did
0FF => off
01D => old
FEE1 => feel
BAD => bad
CA11 => call
FACE => face
AB1E => able
10CA1 => local
F00D => food
1DEA => idea
DEA1 => deal
1EAD => lead
DEAD => dead
ADDED => added
C001 => cool
FA11 => fall
1ED => led
B100D => blood
ADD => add
C0DE => code
BED => bed
D1E => die
BA11 => ball
C01D => cold
1CE => ice
DAD => dad
CE11 => cell
FE11 => fell
A1D => aid
1EE => lee
FEED => feed
DEB8 => debate
B0B => bob
BE11 => bell
10AD => load
CAB1E => cable
FED => fed
FEE => fee
C0A1 => coal
FACED => faced
AC1D => acid
1ABE1 => label
1AB => lab
0DD => odd
B1D => bid
D0C => doc
F100D => flood
BEEF => beef
F001 => fool
B01D => bold
1EAF => leaf
B1ADE => blade
C01E => cole
ACE => ace
BABE => babe
BEE => bee
F01D => fold
D011 => doll
F1ED => fled
CA1 => cal
DEAF => deaf
DA1E => dale
CAB => cab
C01 => col
10C8 => locate
B00 => boo
1AD => lad
C0D => cod
FADE => fade
DEE => dee
D0E => doe
BA1D => bald
1ACE => lace
F1EE => flee
BE11E => belle
D1CE => dice
DEED => deed
C01A => cola
FADED => faded
B1EED => bleed
CA1F => calf
A1DE => aide
A1E => ale
DE11 => dell
F0CA1 => focal
A1EC => alec
E1F => elf
C0CA => coca
C0C0A => cocoa
BA1E => bale
B10C => bloc
AB1DE => abide
BABA => baba
BAE => bae
C1AD => clad
1EA => lea
AD0BE => adobe
A1A => ala
F0E => foe
C0C0 => coco
10AF => loaf
1CED => iced
BEAD => bead
E11E => elle
BE1 => bel
F1EA => flea
B00B => boob
CAD => cad
F1FE => fife
D0DD => dodd
0B1 => obi
D0D => dod
F00 => foo
A1BA => alba
D01E => dole
ABA => aba
DAB => dab
1AC => lac
0DE => ode
C00 => coo
10BE => lobe
100 => loo
CE110 => cello
1ACED => laced
DAE => dae
F1DE => fide
FAD => fad
DA1 => dal
DEB => deb
EE1 => eel
B1ED => bled
10C0 => loco
AD0 => ado
B0A => boa
FE1 => fei
DADE => dade
FAB1E => fable
C0E => coe
1DE => ide
AB0DE => abode
BA1 => bal
A1F => alf
BAC => bac
F0B => fob
DADA => dada
0DA => oda
A1FA => alfa
B10B => blob
A10E => aloe
D10DE => diode
B0D => bod
CABA1 => cabal
C0B => cob
EBB => ebb
B0DE => bode
B0B0 => bobo
DECA1 => decal
FECA1 => fecal

要组词的话其实挺简单的,因为这里面有足够的动词名词形容词:

  • 动词:
    1
    2
    3
    4
    5
    FEE1 => feel
    CA11 => call
    DEA1 => deal
    FA11 => fall
    FEED => feed
  • 名词
    1
    2
    3
    4
    5
    FACE => face
    FOOD => food
    1DEA => idea
    1CE => ice
    BEEF => beef
  • 形容词
    1
    2
    3
    4
    5
    A11  =>  all
    01D => old
    BAD => bad
    C001 => cool
    DEAD => dead

如果只看 wordfreq small list 里的,那更少,只有 160 个。我自己稍微组了一些词:

1
2
3
4
5
6
7
FEE1BAAD => feel bad       这个其实不太可行,因为我用的 BAAD,也可以考虑 FEE15BAD
A10EFOOD => aloe food
DEB81DEA => debate idea
BADCAB1E => bad cable
ADD1ABE1 => add label
DEADF001 => dead fool 差一点变成了 deadpool
1EAFFA11 => leaf fall 让我想起了 e.e. cummings 的诗 l(a

如果我们不允许任何 alias,只用 A-F 来组词,也是能组出一些的:

1
2
3
DEADBEEF => dead beef    经典
FEEDBABE => feed babe 张嘴,啊~
FADEDDAD => faded dad 我去买个橘子?

我挑了一些词:

部分只包含 A-F 的词

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
BAD      => bad
FACE => face
DEAD => dead
ADDED => added
ADD => add
BED => bed
DAD => dad
FEED => feed
DECADE => decade
FED => fed
FEE => fee
FACED => faced
BEEF => beef
ACE => ace
BABE => babe
BEE => bee
DEAF => deaf
CAB => cab
FADE => fade
DEED => deed
FADED => faded
BEAD => bead
FACADE => facade
DAB => dab
FAD => fad
BEADED => beaded
EBB => ebb

可以看到长度为 5 的词很少,所以 3+5 和 5+3 这种搭配不好组词,只能 4+4 的组。

代码不长我就直接放这里了:

代码

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
import wordfreq
from pathlib import Path


def transform(x):
result = x.upper()
for c in x:
if not c.isalpha():
return None
if "I" in result and "L" in result:
return None

# if result.endswith("ATE"):
# result = result[:-3] + "8"
# result = result.replace("L", "1")
# result = result.replace("O", "0")
# result = result.replace("I", "1")
# result = result.replace("S", "5")

for c in result:
if not c.isdigit() and c > "F":
return None

return result


dictionary = set(Path("/usr/share/dict/words").read_text().splitlines())


words = {}
for w in wordfreq.iter_wordlist("en", wordlist="small"):
if w not in dictionary:
continue
w2 = transform(w)
if w2 and w2 not in words and 3 <= len(w2) <= 8:
words[w2] = w

for w2, w in words.items():
print(f"{w:12} => {w2:12}")

试证明:如果一个大矩形能被有限个小矩形(大小不一定相同)平铺,且小矩形至少一条边为整数,则大矩形至少有一条变为整数。

解答

注意到积分 \[\int_{a}^b e^{2 \pi i x} \mathrm{d} x = e^{2 \pi i a} \left(e^{2 \pi i (b - a)} - 1 \right)\] 为 0 当且仅当 \(b - a \in \mathbb{Z}\)。对于平面上一个矩形区域 \(R\),我们考虑如下积分:\[I(R) = \iint_R e^{2\pi i (x + y)} \mathrm{d} x \mathrm{d} y,\] 这个积分值为 0 当且仅当 \(R\) 至少有一边长为整数。令 \(R^*\) 为大矩形,\(R_{1, \dots, n}\) 为小矩形,则有 \[I(R^*) = \sum_{i} I(R_i) = 0,\]\(R^*\) 至少有一条边长为整数。

事实上这个题还有很多种证明方法(14 种!),但我最喜欢的还是这个基于积分的证明。

参考资料:

  • Fourteen Proofs of a Result About Tiling a Rectangle, Stan Wagon.
  • Simple Proofs of a Rectangle Tiling Theorem
  • Mathematical Puzzles, Revised Edition, Chapter 24, Integral Rectangles

今年上半年,ydl 找到我,说他和 maggie 订婚了,诚邀我去 Hawaii 参加婚礼。这我怎么能不参加呢?况且我还没去过 Hawaii,自然应该趁这个机会小小旅游一下。这里就随手记一下流水帐。这次旅游之后,终于知道 Hawaii, O'ahu, Waikiki, Honolulu 之间的关系了……

后来发现一个有趣的 trivia:夏威夷的 state fish 叫做 Humuhumunukunukuapua'a,虽然看起来很长,但是读起来非常有节奏感 23333

准备

出之前自然应该先订一下酒店。看了一下 ydl 他们推荐的酒店 Hyatt Regency Waikiki Beach,价格有点小贵,于是问了一下 ydl 还有谁来吗,结果发现 zw 也来,那我们又可以愉快的做室友了 23333

去之前肯定要稍微做一下攻略,刚好公司里有一个土生土长的 Waikiki 人,于是我就愉快的向他取了取经,拿到了一份《O'ahu 旅游宝典》可以直接抄答案了。

周六

由于我在 Hawaii 只待三天,都在 O'ahu 上,我就准备特种兵一下,早去晚会,maximize 在这里的时间。为此,我订了一个早上七点钟起飞的航班,早上五点钟就得挣扎着起床……飞机上也没睡好,整个脖子疼。这里给个建议:从美西去夏威夷最好坐飞机右侧,因为来的时候是从东向西飞,机场在岛南侧,所以坐在右侧能从天上看到岛的全貌。

到了夏威夷后,九点多,打个车到酒店大概十点多,然后震惊的发现,我打的这辆车下一个乘客就是 zhy 和 ljw……不过我当时脸盲真没认出来只看着眼熟哈哈哈哈哈囧……到了酒店后前台告诉我房间还没准备好,说好了会发短信告诉我,行李箱可以先寄存在酒店里面,妙啊,这样我就可以在 Waikiki 大走特走欣赏一下美丽的城市风景了。令人尴尬的是,就在楼下的 Bell Desk 我愣是找了半天才找到,而且还是找的侧门,出了门之后一看,BELL DESK 几个字母就大大方方的写在那里。脱下飞机上穿的长裤,换上一条短裤,Waikiki 我来啦!

出门就是 Waikiki Beach,但是里面人太多了(而且我也不会游泳)。拍了几张游客照我就想跑路了。接下来我就面临人生两大问题之一:中午吃什么?这个时候自然要问问万能的 xhs 啦~xhs 告诉我,这里可以吃日料,但是一个个都需要预订,很显然,我完全没有做准备。不要慌,我还有 wp 的 O'ahu 旅游宝典。wp 推荐的第一个餐馆叫做 Gina's BBQ。可以啊,让我体验一下什么才是正宗的 Hawaiian BBQ!我准备一路走过去,只要走四五十分钟就到了哦~于是打定主意,我就走了过去。这一路上都没啥树,在大太阳下走着晒死我了,路过了几家日料店,没有位置,路过了一个 Taco Bell,有啥好吃的,路过了一个 Mango Mango,都到夏威夷了怎么能吃这种大路货!最后终于走到了 Gina's BBQ,等等,为啥店名下面一个大大的 Korean BBQ???我再看了一眼菜单,没错,就是 Korean BBQ……不知道点啥就点了个 Gina's special,里面肉挺多的,但是问题是,我去哪里吃……这个店就一个门店,没有吃饭的地方啊……不慌,我看夏威夷这么多的公园,找个公园里的桌子不成问题!于是我又原路走回,这一路上都没啥树,在大太阳下走着晒死我了,路过了几家日料店,没有位置,路过了一个 Mango Mango,都到夏威夷了怎么能吃这种……啊真香!热的时候吃冷饮太香了!我路上试图招一个空地上的长桌来吃饭,但是问题是这些桌子全在草坪里,蚂蚁苍蝇来开会,我实在吃不下去,不能再现 SIGYAO30 '22 @ LA 的三和大神荣光了,直到——我有一次路过 Taco Bell。虽然我没买东西,但是 Taco Bell 有室外的水泥餐桌凳子,看起来不赶人,重点是,还有遮阳伞!我没有丝毫犹豫,直接坐在了 Taco Bell 的凳子上开始吃饭,吃饱喝足后旁边还有个垃圾桶,一气呵成!

之后我准备往 Diamond Head 那边走走看,拍几张游客照。走到一半收到短信说房间好了可以去 check in 了。那我自然应该往酒店走了。到酒店取出之前的行李后,ydl 就过来了,打了声招呼,我就去 check in 了,zw 到了之后一起去房间。

稍微修整了一下后我们就去下面玩,因为 zw 来的时候堵车了,原因就是有一个 festival 封路。既然来都来了,不如我们就去逛逛吧。这个 festival 叫做 Kanikapila Waikiki Festival,就在我们酒店旁边,但是去了之后有点大路货……所谓的 festival 就是一堆小贩在街边支个摊子,然后卖一些有的没的的东西。有些东西还稍微有点特色,例如自称 Hawaii 本地蜂蜜,但是有些东西就毫无特色了,例如烤鱿鱼,写着名字的竹子……

回到酒店后遇到了人生两大问题的第二个问题:晚上吃什么?经过 zw 一顿搜索,我们决定吃一家日式烧烤店,叫做 Aburiya Ibushi,打电话订了今天晚上最后一个位置。味道整体还可以,小菜里的 Cold Tofu 感觉很妙,上面淋的那层肉沫味道很好,wasyugyu sirloin steak 感觉也很好,不肥,入口即化,对比起来 beef flank 就差一些,不过看价格就看得出来 2333

晚上回到宾馆后在考虑明天搞些啥活动。我提议去去爬 Diamond Head 山,毕竟这个火山坑空中看起来超帅。但是这个 trail 需要预订,我们晚上预订的时候,7am-12pm 都已经被订完了,只剩下 6am-7am 或者 12pm 以后,但是 12pm 之后有点晚了,一来太热了我怕了,二来我们明天下午两点多需要在酒店集合坐车去婚礼现场。zw 表示我们可以早起特一特,于是我们就订了 6am-7am 这个时间。

周日

昨晚订的 trail,哭着也要爬完……但是 Diamond Head Summit Trail 这个还好,主要是比较短,往返就一个小时多一点。去的路上和司机 bibi 了一下,司机上来就问我们有没有预订,然后说一半以上的游客没有预订……但是机智如我们早已在昨天晚上订好了 23333 进了公园后就开始爬山。这个 trail 不长,单程只有 30-40min,一下子就爬完了。我发现我爬楼梯超级菜,稍微一爬膝盖就软了,不太对劲。虽然一开始是因为只有 6-7am 有时间我们才订的,但是爬的时候感觉就得这个时候爬,没有特别晒,温度也不高,天气很好,我估计九十点钟就太热了。不过我觉得山顶的景色一般吧,从山顶看 Waikiki 既没有一片高楼带来的现代气息,也没有纯粹自然的风景气息。

爬 Diamond Head Summit Trail 时看到的彩虹

爬了这个 trail 后我们就去打车回去了,补 wan 补 shou 觉 ji。中午吃的 Paia Fish Market,感觉还行,zw 说鱼非常新鲜但是我不知道什么新不新鲜……

下午说好的两点十五集合,我和 zw 就两点十分下去了,到了之后发现咋没人呢……有人和我打了个招呼,随便聊了两句但是我没认出来是谁,超级尴尬。到了两点半,人来齐了,我们开车前往 Kualoa Ranch,听说这还是拍侏罗纪公园的地方,但是我也没看过侏罗纪公园……车上我对着群里的名字一个一个找,终于想起了之前和我打招呼的是谁了……

之后婚礼正式开始了。这真是一个举办婚礼的好地方。我们在去婚礼现场的路上看到海上有一个小岛,感觉挺有意思的,查了一下叫做 China Man Hat Island。但是有意思的不只是这个,如果你从一个合适的角度去看婚礼花拱,你会发现这个岛恰好就在花拱中间,位置太妙了!

China Man Hat Island
花拱与 China Man Hat Island
Kualoa Ranch

婚礼进行的时候天有点阴,要是阳光再明媚一点就好了,不过另一方面想,我们就没那么晒了是吧哈哈哈。婚礼快要结束的时候,下起了点点细雨;婚礼刚刚结束的时候,这点点细雨变成了瓢泼大雨,也是天公给足了面子。我一开始仓促跑向避雨棚,忘记带小礼品了,这怎么能忘记呢!于是我像风一样跑了回去,又像风一样跑了回来。然而,这个时候我没有注意到,摄像师正拍着 ydl 保护 yfy 从容不迫地从婚礼现场来到避雨棚。希望将来他们回顾这份温馨的录像时,忽略掉一位一闪而过挡住了镜头的风一样的男子吧……

婚礼还配置了一个 photo booth,每次可以 1-3 个人一起拍摄三张照片。photo booth 还提供了很多塑料道具可以选择。我印象最深刻的一张是我、zw 还有 ydl 三个人的一张,ydl 坐中间,我和 zw 坐两边,zw 拿着手枪指着我,我拿着菜刀砍向 zw,ydl 则在中间惊慌失措。

晚上到了宾馆之后我和 zw 再来规划明天的行程。看了一下,周围似乎没啥好玩的了,有个 aquarium 但是似乎评价不是很高。红警玩家 zw 推荐了珍珠港,因为 Arizona Memorial 在红警里出现过,那我们就去那里了。这里有个问题是 Arizona Memorial 的摆渡船需要预约,而我们没有预约上,但是 anyway 我们还是决定去那里看一下拍个队,随缘吧。说起来这边的 researvation 就很迷,只能预约要么明天的,要么两个星期之后的。预约明天的基本上都被黄牛抢了……

周一

我们本可以选择去大大大早起去 Pearl Harbor 排 Arizona Memorial 的队,但是经过前两天的特种兵旅游,我们决定躺了,吃完饭再去。卡着点 checkout 后,我们去 Sato's Seafood 吃了一个 Poke Bowl。我点了一个 spicy salmon 感觉酱调的非常不错,就是鱼有点少。这家店店内没有桌椅,就在店门口有一两个小桌子,随意配上三四把椅子,我又回忆起了前几天吃 Gina's BBQ 的场景……

吃完饭后打个车去了 Pearl Harbor。门口存了个包后我们就进去排队,幸亏这里的排队是签到制,登记了名字之后不需要排在那里,不过我对排上队不报啥希望了,一来我们吃了饭才来,里面好多人,二来我要赶飞机,如果一个小时内排不上队的话我就看不了了。之后就去里面的珍珠港事件纪念馆随便看看。正当我觉得马上到时间了看不上 Arizona Memorial 的时候,zw 突然发现排到了,哟太凑巧了。

Arizona Memorial 建立在珍珠港事件中被摧毁的 USS Arizona 残骸上,在纪念馆还能看到一些残骸。它不大,里面没有多少东西可以参观。我有时候看到水面上还有一些漂浮的五光十色的东西,zw 告诉我那是不停冒出来的机油,漂浮在水面上,不同地方油层厚度不同,在阳光下反射的光的颜色也不同,这东西还有一个名字,叫做 Tears of the Arizona。Arizona Memorial 附近还有另外一艘战舰,是退役的 USS Missouri,就是在这艘船上,日本正式投降了。将 USS Missouri 停在珍珠港内,算是给故事添上一个句号吧。

Arizona Memorial
Tears of the Arizona

听说今年这两道题比较简单,我就来蹭蹭热度了。 P1 是一个不太难的题,但是我很可能把它想复杂了;P5 是一个非常巧妙的 brainteaser 。

P1

求所有实数 \(\alpha\) 满足:对任意正整数 \(n\),整数 \(\sum\limits_{i=1}^n \lfloor i \alpha \rfloor\) 均为 \(n\) 的倍数。

解答

\(S\) 表示所有满足要求的 \(\alpha\) 构成的集合。先来个小观察:如果 \(\alpha \in S\),那么 \(2 + \alpha \in S\):对于任何 \(n \in \mathbb{N}^+\),有 \[\sum_{i=1}^n \lfloor i (\alpha + 2) \rfloor = \sum_{i=1}^n \left( \lfloor i \alpha \rfloor + 2i \right) = \sum_{i=1}^n \lfloor i \alpha \rfloor + n (n + 1)\]

于是我们就只需要研究 \([0, 2)\) 里的 \(\alpha\) 即可。

  1. 显然有 \(0 \in S\);
  2. 如果 \(0 < \alpha < 1\),考虑 \(n = \lceil \alpha^{-1} \rceil \geq 2\),有 \(\sum\limits_{i=1}^n \lfloor i \alpha \rfloor = 1\),明显不满足要求;
  3. 显然有 \(1 \not\in S\):令 \(n = 2\) 即可。
  4. 如果 \(1 < \alpha < 2\):
    1. 如果 \(\alpha \not\in \mathbb{Q}\),对于任何 \(n \in \mathbb{N}^+\)\(\sum\limits_{i=1}^n \lfloor i (2 - \alpha) \rfloor = \sum\limits_{i=1}^n (2i - 1 - \lfloor i \alpha \rfloor)\) ,故 \(2-\alpha \in S\),又有 \(0 < 2 - \alpha < 1\),矛盾。
    2. 如果 \(\alpha \in \mathbb{Q}\),不妨令 \(\alpha = p / q\)\(gcd(p, q) = 1, q > 1\)。有 \[\sum_{i=1}^{q-1} \left\lfloor i \frac{p}{q} \right \rfloor = \frac{1}{2} \sum_{i=1}^{q-1} \left( \left\lfloor i \frac{p}{q} \right \rfloor + \left\lfloor (q - i) \frac{p}{q} \right \rfloor \right) = \frac{p - 1}{2} (q - 1) \equiv 0 \pmod {q - 1}. \] 可知 \(p\) 为奇数。又考虑 \[\sum_{i=1}^q \left\lfloor i \frac{p}{q} \right \rfloor = p + \frac{1}{2} \sum_{i=1}^q \left\lfloor i \frac{p}{q} \right \rfloor = p + \frac{p - 1}{2} (q - 1) \equiv 0 \pmod{q}. \] 可得 \[\frac{p + 1}{2} \equiv 0 \pmod{q},\] 而这是不可能的,因为 \(0 < \frac{p + 1}{2} < q\).

综上所述,\([0, 2) \cap S = \{0\}\),故 \(S = \{2k: k \in \mathbb{Z}\}\).

(这个对 \(\alpha \in \mathbb{Q}\) 的讨论好丑好想优化掉……)

P5

憨豆特工在一个 2024 行 2023 列的方格表上做游戏。方格表中恰有 2022 个方格各藏有一个坏人。初始时,憨豆不知道坏人的位置,但是他知道除了第一行和最后一行之外,每行恰有一个坏人,且每列至多有一个坏人。

憨豆想从第一行移动到最后一行,并进行若干轮尝试. 在每一轮尝试中,憨豆可以在第一行中任意选取一个方格出发并不断移动,他每次可以移动到与当前所在方格有公共边的方格内。(他允许移动到之前已经到达过的方格。)若憨豆移动到一个有坏人的方格,则此轮尝试结束,并且他被传送回第一行开始新的一轮尝试。坏人在整个游戏过程中不移动,并且憨豆可以记住每个他经过的方格内是否有坏人。若憨豆到达最后一行的任意一个方格,则游戏结束。

求最小的正整数 \(n\),使得不论坏人的位置如何分布,憨豆总有策略可以确保他能够经过不超过 \(n\) 轮尝试到达最后一行。

解答

以下给出一个 \(n = 3\) 的构造。所有的图里蓝色为坏人,黄色表示可行路径。

我们先确定第二行的坏人在哪里。这一步直接扫就好了。有两种情况:

  1. Case 1:坏人不在第一列或最后一列。如图所示,A 点和 B 点同行,所以至多有一个坏人。不妨设 B 点没坏人,按照黄色路径走即可。 Case 1
  2. Case 2:坏人在第一列或最后一列。不妨设坏人在第一列,那我们便从上到下依次遍历下图的所有绿色方块,遇到第一个坏人就停止。 Case 2
    1. Case 2-1:我们没有找到任何一个坏人,那么我们可以直接走最后一列即可;
    2. Case 2-2:我们找到了一个坏人,那么按照下面的黄色路径走即可: Case 2-2 A 点左上方的点没有坏人是因为 A 点是我们从上往下扫找到的第一个坏人。

至于 \(n\) 为啥不能小于 3:我们就考虑一个 adversarial 的放坏人的方式,

  • 第一次探索时我把坏人放在你探索的第一个方块上(在第二行);
  • 第二次探索时我把坏人放在你探索的第一个位于第三行的方块上,这个方块一定和我第一次放坏人的方块不在同一列上,因为你只能从第二行的非坏人方格到第三行。

又是一年 SIGYAO30。今年 SIGYAO30 在 Chicago,一来是因为之前美东美西都举办过 SIGYAO30 了,二来去年商定举办地点的时候,刚好 Chicago 有三个人,于是我们就决定放在 Chicago 了。事实上,我对芝加哥 downtown 印象挺好的,现代的城市,干净的街道,便捷的生活,低廉的物价,丰富的娱乐,多样的美食,就是冬天有点冷,南边不安全……

七年前才毕业,到现在居然已经毕业七年了。上次在芝加哥还是上次。半年不见,如隔六月。这次来芝加哥体验了好多游客项目,我在芝加哥住了一年半,但凡我稍微出门逛逛,也不至于一点也没逛。

Read more »

这是一道来自王格斯的妙题,有一个 10s 内能说出来的解法。

一个能被 25 个半径为 1 的大圆覆盖的长方形一定能被 100 个直径为 1 的小圆覆盖吗?

Read more »

一想到上一次回国还是疫情前,我心里就直痒痒。疫情期间回国特别麻烦,严格的防疫政策,上天的机票价格,一个个让我知难而退。本想着能不能拿 combo 卡回国,结果被 EB1 突然的排期打了个措手不及。F-1 虽然还没过期,但是交了 140 了,怕是不能用了。幸亏我运气好了一次,抽上了 H1b,这才让我有机会回国喘息一下。去年年底想回国,但是由于刚开始工作不久,假也不多,就此作罢。今年本来想浩浩荡荡把整个 12 月休掉,一来我 check 一般就是这么久,二来加上去年 rollover 的假刚好有这么多,但是由于种种原因,可能更好的选择是拆成两个半个月的假,那么我就九月底先休一次了。我这种长期被 check 体质的人要去办签证了,还是得和老板说一声。今年老板龙颜大悦,直接准了。

规划回国的第一件事,也是最重要的一件事就是约美国签证。我犹豫了好久,到底是在 HK 签好还是国内签好,最后还是决定去 HK。一来我对国内的美领馆的工作人员态度印象不佳,二来感觉国内会很严,但这可能只是我的错觉,可能对于敏感专业的中国人来说,哪里都很严……三来还有一件特别 subtle 的事:我被 check 后只能去 HK 工作,而在我的计划中,我是用护照 + GEP 去 HK,这带来的问题就是,我贴签那几天必须在领馆所在地。如果我在国内签,那么那几天我就只能在国内,没法工作了……理论上是有一些方法去搞定这个这个问题,但是都挺麻烦的……

第二件事,我得有一个合法的身份能在 HK 工作。这里有两种方法,第一种方法是搞一个香港高才,但是准备材料的时候我就直接怂了,还得要我档案所在单位出示一份文件,我连我档案在哪里都记不太清楚了,而且这是和港安通行证挂钩的,我港澳通行证早就过期了,我假期就两周,还不一定能办的下港澳通行证 + 逗留签注,办不下来就 gg 了。第二种是搞一个 HK 签证,用 General Employment Policy(GEP),之后往来 HK 和内地也是用护照。但是 GEP 要求居住在海外的中国公民,还得要我最近一年的出入境记录……说起来我还得在香港办一个居民身份证,但是这怎么这么难约啊?我在芝加哥下午三点钟到它网站上约,它居然让我排!一!个!小!时!的!队!来!预!约!这可是凌晨四点钟的香港啊!(你见过凌晨四点钟的香港的?黄牛:怎么了?)排完队我我更加震惊,我八月份去预约办一个香港身份证,居然只能约到十二月了!为啥十二月还有一个 slot?因为这是刚刚放出来的……昨天放出来的 slot 全部都没了……香港人民这么热爱办居民身份证吗……

第三件事,我得遵守公司的 travel policy。具体是啥我就懒得写了,也挺麻烦的,还得找一堆人签字审批,谁叫国内是 High Risk Country 呢 →_→ 我问能不能去上海,答曰不行。能去上海就太舒服了。

第四件事,就是好好计划假期了!好久没回国了,有太多的人要见,饭局一个接一个,两个星期的假其实不够的,可能只能将将把人见完……

Read more »
0%