GCJ Qualification Round 2015 题解

前言

这篇日志用中文写是因为想省点时间打游戏。。。(请鄙视我吧。。。

A. Standing Ovation

题意

这是一个骗掌声的故事。

当演出结束后,观众们要站起来鼓掌。但是有些观众比较羞涩,只有在k个人站起来鼓掌后才会故障。

你的目标是在观众中安插一些卧底领掌,让所有观众都站起来鼓掌。(臭不要脸)

求最少的卧底数。

数据规模

抛开数据规模谈解题,都是TM耍流氓。 —— Wizmann

100组数据。

小数据集,观众羞涩值的范围:0 ≤ Smax ≤ 6.

大数据集,观众羞涩值的范围:0 ≤ Smax ≤ 1000.

解题

本题比较简单。有两种方法,一是暴力枚举,因为大数据集中,观众羞涩值最大只为1000,即最大安插卧底数不超过1000。(当然,二分也可以,不过对于1000的数据集,真心没啥必要。)

二是O(N)的一个遍历,在观众羞涩的不想鼓掌时,安插相应数量的卧底。

本题推荐方法一。因为个人感觉,在编程竞赛中 …

more ...

ZeroMQ启示录

ØMQ是一个消息系统

ZeroMQ是一个消息系统,也被称为“消息中间件”。它被广泛的用于经济、游戏、嵌入式等领域。

什么是消息系统

打个比方,消息系统就像我们使用的IM软件一样。首先,一方决定将消息发往何处(一对一或一对多)。然后将信息打包,点击发送按钮。之后,IM系统会帮你料理剩余的事务。

但是,它们也有很大的不同点。IM系统对于消息系统似乎太低效了一点。另外,消息系统是没有用户界面(GUI)的。在错误发生时,消息的另一端也不会有人来智能的介入处理。

所以,我们可以这样下定义。消息系统是具有高效性和容错性的消息传递解决方案。

ZeroMQ的起源和发展

ZeroMQ最先的设想是实现一个炒鸡快的用于证券交易的消息系统,所以在设计初期的关注点就是在极致的优化上。

第一年的工作重点,在于发明性能测试的方法,和设计高效架构。

之后,大约在第二年,工作重点转移到实现一个通用的消息系统,以应用于分布式系统,使其可以利用不同的编程语言,使用不同方式,来传递各种模式的信息。

启示1:独立应用 vs. 程序库 …

more ...

Codeforces Round #290 (Div. 2) Tutorial

A. Fox And Snake

Implementation

(n, m) = map(int, raw_input().split())

res = []

for i in xrange(n):
    if i % 2 == 0:
        res.append('#' * m)
    elif (i / 2) % 2 == 0:
        res.append('.' * (m - 1) + '#')
    else:
        res.append('#' + '.' * (m - 1))

for line in res:
    print line

B. Fox And Two Dots

DFS …

more ...

Codeforces Round #289 (Div. 2) Tutorial

A. Maximum in Table

Simulation.

n = int(raw_input())
g = [[1 for i in xrange(n)] for j in xrange(n)]

for i in xrange(1, n):
    for j in xrange(1, n):
        g[i][j] = g[i - 1][j] + g[i][j - 1]

print g[n - 1][n - 1]

B …

more ...

Codeforces Round #288 (Div. 2)

A. Pasha and Pixels

Brute force.

There are multiple ways to form a 2*2 square at one single step.

Alt text

So at every step, we have to check the neighbours of pixel that is colored black.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define …
more ...

Sequence Median

Description

Given a sequence of integer numbers, try to find the median of the sequence.

Extending

  • Make sure your code can get the right answer in any conditions
  • Make sure your code work effectively on some special kinds of sequence. For example, ordered sequence or a nearly ordered one, a …
more ...

类型-长度-值(TLV)协议

在数据通信协议中,可选的信息或字段通常使用type-length-value(a.k.a TLV)元素来进行编码。

  • Type - 类型

用来标示字段类型的值,通常是一个二进制值或简单的字母

  • Length - 长度

字段长度,单位通常为Byte

  • Value - 值

一个变长的比特数组用来存储这个字段的值

优势

  • TLV序列方便遍历查找
  • 新的字段可以无痛的加入现有的协议中。解析的时候,对于未知的字段,可以轻松的跳过。这点与XML类似
  • TLV元素的顺序可以是随意的
  • TLV元素通常使用二进制存储,可以使解析速度加快并且使数据更小
  • TLV可以与XML数据相互转换,易于人类阅读

例子

在这里,我们以protobuf的可选和变长字段为例。

field_number ++ wire_type

每一个protobuf的字段在传输时,都会加上field_numberwire_type这两个值,这两个值组成这个字段的key。

key = (field_number << 3) | wire_type

field_number标明了字段的编号,方便协议向前向后的兼容。而 …

more ...

Reasons They Recruit

From Ace of Programming Interview, Cpt1 - Hiring Programmers: The Inside Story

Establish a Rapport

For an interviewee, one the the most efficient way to build a rapport is to try to see things in from the interviewer's perspective.

  • understand the motivation of the interviewer
  • establishing a common ground
  • adapting your …
more ...


The Checklist of Steve Yegge

Hey man, I don't know that stuff

Stevey's talking aboooooout

If my boss thinks it's important

I'm gonna get fiiiiiiiiiired

Oooh yeah baaaby baaaay-beeeeee....

非技术部分

热身

好好读一本讲数据结构和算法的书

熟悉一些“术语”,可以强化分辨问题的能力。

Yegge推荐了 Steven S. Skiena 的《算法设计手册》,而我推荐的是 Udi Manber 的《算法引论》

每一本书都有它的长处短处。找一本评价不错的书,认真读完,肯定会有收获。

找个朋友来面试你,尝试白板编程

在白纸/白板上编程的体验和在计算机上大有不同。没有条件的情况下 …

more ...