Day: December 17, 2011

sicily 2014. Dairy Queen 解题报告

Sun Yat-sen University ACM 2014. Dairy Queen

1. 原题中文大意;

给出一个在 [1, 300] 之间的数字N。然后给出一个集合，这个集合中有C 个数字，C在[1, 8]之间。该集合中的每个数字在[1, 200]之间。问如何用这个集合中的数字组合（数字可以重复使用），使它们的总和等于N。

2. 解这种题毫不犹豫地想到用动态规划。

3. 设一个数组 ways[301]; ways[n]表示有多少种方法可以组合成和n。假设集合中只一个数字x。那么问题就非常简单，只能取n个该数字，和的集合为{x, 2x, 3x}，即ways[x]=1，ways[2x]=1, ways[3x]=1 ….。如果集合中有m数字，假设我们已经求得了用这m个数字的组合可以得到的和的数目存到了ways数组里。即对于m个数字，已求得 ways[1] = ?, ways[2] = ?, ways[3] = ? ….. Ways[300] = ?。 那么在此基础上，再加多一个数字，即 m+1个数字的情况会是如何呢。设新加入的这个数字的值是p，则应该是 ways[q] += ways[q-p]。（q > p）

 

4. 程序注释清单.

#include <string.h>

#include <stdlib.h>

#include <stdio.h>



int main(int argc, char* argv[])

{

int N, C, coin;  // N为题意中的N，C即题意中的C. coin作临时变量用，不解释，可见下面的代码。

int ways[301] = { 0 };  // 见第三部分的分析。

ways[0] = 1;  // 没有实际意义。为了方便计算.



scanf("%d %d", &N, &C);

for ( int i = 0; i < C; i++)

{

scanf("%d", &coin);

for ( int j = coin; j <= N; j++ )

{

ways[j] += ways[j-coin];  // 见第3部分的分析.

}

}

printf("%d\n", ways[N]);



return 0;

}

 

5.时间复杂度，空间复杂度分析。

空间复杂度是确定的常数。时间复杂度是o(n). n为有多少种面值的硬币。

http://ykyi.net zausiu's blog

原题：

Description

Bessie, always in need of an income, has decided to leverage her dairy skills by taking a part-time job at the local Dairy Queen restaurant. She is running a special cash register (since she has hooves instead of fingers and thus requires special accommodation). Her job is making change for customers as they make a purchase.

As she was counting out 83 cents in change, she wondered: "How many ways can I count out 83 cents? I can use three quarters and eight pennies, seven dimes and three pennies, 83 pennies… there must be a zillion ways!"

How many different ways can one make change for N (1 ≤ N ≤ 300) cents using coins from a set of C (1 ≤ C ≤ 8) coins of supplied values C_i (1 ≤ C_i ≤ 200)? "Different" means differing counts of coins.

Thus, 8 cents can be made, in American currency, with 1 five-cent piece + 3 one-cent pieces and also with 8 one-cent pieces. Using 3 one-cent pieces + 1 five-cent piece is the same as 1 five-cent piece + 3 one-cent pieces, so one can create eight cents in just two different ways. Note that some coin systems are poor at making change and result in an answer of '0'.

Coin values in the input file are listed in descending order from largest to smallest. All coin values will be distinct.

Input

 

Line 1: Two space-separated integers: N and C
Lines 2..C+1: Line i+1 contains a single integer: C_i

 

Output

Line 1: A single line with a single integer that is the number of ways to create N cents of change using the supplied coins. The answer is guaranteed to fit into a signed 32-bit int

 

Sample Input

83 5
50
25
10
5
1

Sample Output

159

 

copyright ykyi.net

 

Related Posts

Unix网络编程.第九章笔记

# TCP 协议在1981年标准化，而SCTP协议则是在2000年由IETF组织标准化。IETF： Internet Engineering Task Force 互联网工程任务组成立于1985年。

# SCTP支持两种类型的socket. one to one(为了方便现有的tcp程序迁移到sctp) 和 one to many.

# sctp的sctp_bindx可以绑定多个地址，并且可以动态增删。但动态增删不影响已经存在的associations.不过各个unix分支不一定支持这个特性。

# sctp_getpaddrs和sctp_getladdrs分别是getpeername和gethostname的sctp版。They are designed with the concept of a multihoming aware transport protocol.

# sctp传输的报文是有边界的。sctp在传输层支持传输超大的message.

Related Posts

Is your biometric data safe

Kot教授的这个讲座在网页上写的标题是：IEEE Distinguished Lecture Talk。多么气质不凡的Distinguished啊！！！作为一个小工程硕，实在有受宠若惊之感。

讲座的大概讲的Kot教授提出了如何构建一个新颖的(novel)系统来保证Biometric信息在服务端的安全。即使这部分信息泄露出去，攻击者也不能够利用它。首先什么是BIOMETRIC呢？你的指纹，你的面部，你的头发…都属于Biometric。其实Biometric对于大家都不会陌生，指纹考勤系统实在是相当之普遍啊。而且科幻或者犯罪电影里还有虹膜校验。

Kot教授提出Biometric的验证系统的不安全的方面，如果被泄露出去，Biometric信息不像普通密码一样容易被更换，一但被伪造这样就会比传统的验证方法更加麻烦。Prof. Kot简单地walk through了几个保护Biometric的解决方案，并说明Biometric信息是可以被利用被伪造的。

PPT中多次提到Minutiae的概念，一直没听明白啊！貌似是从原始的Biometric信息中提取出部分信息而作为用来验证的数据。Professor Kot论证常见的基于指纹的验证系统的弊端。论证中非常多的“valley”，"ridge"，比较变换前后的差异。不明白啊，不明白！大概的结论是目前的技术可以做到从Minutiae中reconstruct到原始的original fingerprint。后来想这时候论证的是为了支撑其后Prof. Kot提出的新的novel solution.

Kot提出的解决方案是在采集指纹信息时需要采集用户的两个不同的手指，然后综合这两个手指的信息计算出一个Minutiae。这个Minutiae与从采集单个手指得到的Minutiae几乎没有差别。因为这个Minutiae记载的是两个不同手指的信息，而且每个手指仅仅只记部分信息。这样的话，即使攻击者盗取了这个Minutiae，它就无法原始到原始的fingerprint。按我自己的理解，攻击者应该也不清楚它还原得到的指纹其实并不存在，因为Minutiae是两个指纹的信息合成的而且与由单个指纹得到的几乎一样，攻击者无法分辨。攻击者应该会沾沾自喜reconstruct到了被误导的original finger print。

Kot还指出在他提出的这个解决方案中可以嵌入信息记到Minutiae里面。在后面的提问阶段。有同学问到这个解决方案可以存入多少信息。Kot补充目前可以存一千多个Bit位信息，足够存下重要的身份认证数据了。按我自已的理解，能存多少信息应该是可以根据需要调大和缩小的呀。比如把图形转成矢量图形后，就可以不失真的放大，于是就会有更多存储空间了。不确定是不是这样。

提问阶段Kot指出这个设计没有使用token或者key因此会运行的非常迅速。而如果采用复杂的加解密算法，则会有非常大的计算开销。运行速度对于一些嵌入式的电子系统是至关重要的。

有同学提问提到做Face Recognition，问Kot教授有什么看法。Kot认为Face Recognition is very difficult, very very difficult, few advancement has been achieved nowadays. It's a very tough problem.

At last, as a conclusion for this report, I must show my great respect to Alex Kot. He is a great scientist.

/////////////////

IEEE Distinguished Lecture Talk

Title：Is your biometric data safe?

Speaker：Prof. Alex C Kot, 新加坡南洋理工大学教授、IEEE Fellow

时  间：  12月16日（本周五）下午3：00

地  点：  信息科技学院大楼二楼207讲学厅

主持人：  黄继武 教授

主办单位：信息科学与技术学院、IEEE Signal Processing Society Guangzhou Chapter, IEEE Circuits and Systems Society Guangzhou Chapter

 

Abstract

Nowadays, biometrics is widely used in authentication systems. In general, biometrics needs to be stored in a database for subsequent authentication. However, templates stored in the database are at the risk of being stolen or modified. Once the template is stolen, it is difficult to be replaced like passwords and the private user information associated with the stolen template would also be exposed. Thus, biometrics templates should be stored in the database such that both the security of the template and the privacy of the user are not compromised under various attacks.

 

 We first propose a fingerprint authentication system for the privacy protection of the fingerprint template stored in a database. The considered fingerprint data is a binary thinned fingerprint image, which will be embedded with some private user information without causing obvious abnormality in the enrollment phase. In the authentication phase, these hidden user data can be extracted from the stored template for verifying the authenticity of the person who provides the query fingerprint. A novel data hiding scheme is proposed for the thinned fingerprint template. Compared with using existing binary image data hiding techniques, the proposed method causes the least abnormality for a thinned fingerprint without compromising the performance of the fingerprint identification.

 

The minutiae is another type of data stored in a fingerprint template. We investigate to what extreme a reconstructed fingerprint can be similar to the original fingerprint. A new scheme is proposed to reconstruct a full fingerprint image from the minutiae points.  Experimental results show that the successful match rate between our reconstructed fingerprint and the original fingerprint is over 99% at FAR=10-4. When matched against the different impressions of the original fingerprint, our reconstructed fingerprint has over 86% successful match rate at FAR=10-4. We consider the privacy issues of the fingerprint reconstruction. The analysis shows that our proposed technique is useful for protecting the fingerprint ridge frequency.

 

 As a reconstructed fingerprint can be so similar to the original fingerprint, it is also very important to protect the privacy of the minutiae template stored in a database. We propose a novel system for protecting the privacy of the fingerprint minutiae without using a token or key. In the enrollment, two fingerprints are captured from two different fingers of the same person. A combined minutiae template containing only a partial minutiae feature of each of the two fingerprints will be generated and stored in a database. In the authentication, the user needs to provide two query fingerprints from the same two fingers which are used in the enrollment. By storing the combined minutiae template, the complete minutiae feature of a single fingerprint will not be compromised when the database is stolen. Furthermore, because of the similarity in topology, it is also difficult for the attacker to distinguish our template from the minutiae of an original fingerprint. The experimental results show that our system can achieve a very low error rate.

Biography

Dr Kot has been with the Nanyang Technological University, Singapore since 1991. He headed the Division of Information Engineering at the School of Electrical and Electronic Engineering for eight years until 2005. The Division’s research focuses are on signal processing for image, video, speech and audio. He started serving as Vice-Dean (Research) for the School of EEE in 2005 and became Associate Dean for the College of Engineering in 2008. He is currently a Professor at the School of EEE and Associate Dean for the College of Engineering. He has published extensively with over 200 technical papers and 3 patents in the areas of signal processing for communication, biometrics recognition, data-hiding, authentication and media forensics. 

 

Dr. Kot served as Associate Editor for the IEEE Trans. on Signal Processing, IEEE Trans. on Multimedia, IEEE Trans. on Circuits and Systems for Video Technology; and IEEE Trans. on Circuits and Systems Part II as well as Part I. He also served as Guest Editor for the Special Issues for the IEEE Trans/ on CSVT and JASP. He is currently Associate Editor for the IEEE Trans. on Information, Forensics and Security, IEEE Trans. on Image Processing and IEEE Signal Processing Letter. He is also Editor for the EURASIP Journal of Advanced Signal Processing, the IEEE Signal Processing Magazine and the IEEE Journal of the Special Topics in Signal Processing. He is an Editorial Board member of the Journal of Fundamental and Theory in Signal Processing. He serves in the IEEE CAS Visual Signal Processing and Communication, the IEEE SPS Image and Video Multi-dimensional Signal Processing and IEEE SPS Information Forensic and Security technical committees. He has served the IEEE Society in various capacities such as the General Co-Chair for the 2004 IEEE International Conference on Image Processing (ICIP) and Chair of the worldwide SPS Chapter Chairs and the Distinguished Lecturer program. He serves as IEEE Fellow Evaluation Committee. He received the Best Teacher of the Year Award and is a co-author for several Best Paper Awards including ICPR, WIFS and IWDW. He was the IEEE Distinguished Lecturer in 2005 and 2006 and is a Fellow of IEEE and IES.

 

Related Posts

Distributed Framework for Iterative Computations on Massive Datasets

I must confess I've only got a few words and a vague skeleton of what the Professer Lixin Gao said due to the language barrier, during the whole speech Ms Gao spoke English, and the topic is so pedantic which is full of the complicated mathematic formulation.Personally，我未有涉及过海量数据并行计算以至云计算相关的任何技术，基本上对于海量数据的所有技术都让我觉得非常地cutting-edge。带着学习开拓眼界拓展知识面的良好愿望参加了Ms. Gao的学术讲座。Ms. Gao讲PPT时全是英文啊。我努力地听，努力地听！！！适当地记些笔记。其实还是很喜欢听英语的。 

讲座先列举了一些大型互联网公司的数据显示集群计算的规模。比如谷歌在数据中心有一百万台服务器！！！Holy gosh，1,000,000 servers！！！

然后谈到了很多大规模数据的计算对时间的要求非常地严格。于是谈到了目前流行的算法：MapReduce。MapReduce是google提倡的一种编程模型，用于大规模数据集（大于1TB）的并行运算。“Map”和 “Reduce”，和他们的主要思想，都是从函数式编程语言里继承来的，还有从矢量编程语言里借来的特性。他极大地方便了编程人员在不会分布式并行 编程的情况下，将自己的程序运行在分布式系统上。我自己的理解是：map索引整个海量数据，生成key-value pair which is used to facilitate the quick query and computing。而reduce则是用来分析和统筹基于键值对的中间计算结果，使中间结果迅速向最终的正确结果收敛。

Ms. Gao 提出MapReduce虽然是工业界非常popular的解决方案，但是不可以以迭代的方式计算。而Ms. Gao所做的工作即是使MapReduce支持迭代的功能。（A framework that support iterative computing in the cloud.）从事情一般规律的哲学高度看待这个问题，对于规模相当大或者最终结果是相当不明确的问题，似乎都可以用到'迭代'的思想。例如，迭代的软件开发模式则是当今互联网应用的主要开发模式。每一次迭代都使产品向理想中最perfect的状态接近。Ms. Gao用迭代的思想处理海量数据应该也是同样的道理罢！

Ms. Gao的解释说改进后支持迭代的iMapReduce可以使map后的数据支撑reduce,reduce的数据亦转而支撑map，形成一个迭代反复的过程，其中在map阶段加入static data。较之原始的MapReduce，新的算法使得static data的规模显著地减少。Ms. Gao展示了几个图表证明改进后增加了迭代功能的MapReduce(称之为 iMapReduce )的速度优于原始的MapReduce.图表中有展示用iMapReduce计算PageRank的值。PageRank？是不是判断网站权重的那个东东啊？哥的网站http://ykyi.net的PageRank才0啊！！！才0啊~~用什么算法可以算成9啊！

PPT转到计算图的指定两点最短路径的Dijkstra算法。泪流满面，终于有一个我懂的算法了啊！Ms. Gao说先找到两个结点间的最短路径，于是赋于这个最短路径经过的结点最高的权重，其它的路径就赋于相对低的权重。提出了PriorityQueue的数据结构。把权重引入到iMapReduce算法，称之为pMapReduce算法。引入权重后的pMapReduce算法比iMapReduce算法的速度更快。生活中我们做事情也要优先处理最重要的事情，道理是一样的啊！世间万事万物，无论多么复杂，抽象出来的一般规律其实都是相当地一致。易经中说：形而下者谓之器，形而上者谓之道！Oops, The ancient Tao philosophy is full Of Wisdom.

最后阶段，再次展示了一个图表，Ms. Gao完成的建立在Apache的Hadoop上的pMapReduce要明显的优于原始的Hadoop。并且也优先其它多种解决方案，其它的名字我都没听过啊！在提问阶段，尽管温武少老师积极鼓励同学提问但没有同学提出问题，大概大家都不懂吧！朝红阳老师和另一位研究海量数据的老师谈了一点点。他们提到iterative的算法在他们的实际应用中效果并不是太明显，不如memory-based的解决方案。Ms. Gao调出一张图表，解释说某种memory-based的解决方案没有迭代的算法快。

作为众多打酱油的同学中的一员，我最后的心得体会是：学术真是太高深了啊！我还是做工程吧！！！车，我有得拣咩？

/////////////////////////

Topic

Distributed Framework for Iterative Computations on Massive Datasets
 
Speaker
Prof. Lixin Gao
 
Abstract
Iterative algorithms are pervasive in many applications such as search engine algorithms,machine learning, and recommendation systems. These applications typically involve a dataset of massive scale. Fast iterative computations of the massive datasets are essential for these applications. This is particular important for on-line query such as keyword based search query. In this talk, we present an overview of MapReduce framework, and propose two frameworks, iMapReduce and pMapReduce, that enable fast iterative computations. By providing the support of iterative computations and prioritized execution, we can ensure faster convergence of the iterative process. Both iMapReduce and pMapReduce preserve the MapReduce distributed computing framework and is particularly efficient for online queries such as top-k queries. We implement iMapReduce and pMapReduce based on Apache Hadoop and evaluate its performance. Our evaluation results show that pMapReduce can reduce the computation time by two orders of magnitude comparing to that achieved with MapReduce. At the end of the talk, I will provide an overview of on-going projects in my research group.
 
Bio
Lixin Gao is a professor of Electrical and Computer Engineering at the University of Massachusetts at Amherst. She received her Ph.D. degree in computer science from the University of Massachusetts at Amherst in 1996. Her research interests include social networks, and Internet routing, network virtualization and cloud computing. Between May 1999 and January 2000, she was a visiting researcher at AT&T Research Labs and DIMACS. She was an Alfred P. Sloan Fellow between 2003-2005 and received an NSF CAREER Award in 1999. She won the best paper award from IEEE INFOCOM 2010 and her paper in ACM Cloud Computing 2011 was honored with “Paper of Distinction”. She received the Chancellor’s Award for Outstanding Accomplishment in Research and Creative Activity in 2010, and is a fellow of IEEE.

 
 

 

Date and Venue
Dec.16（Friday）13:30pm-14:30pm
Lecture Theater A101, School of Software, Sun Yat-sen University