算法合集之《用改进算法的思想解决规模维数增大的问题》.doc

用改进算法的思想解决规模维数增大的问题广东韶关一中 张伟达【关键字】 增大规模 改进算法 降维 分析 构造【摘要】我们常常会遇到一些特殊的问题，它们把我们能够解决的问题改了一改，增加了一维，或者增加了一个因素，从1到2或者是从2到3，本文把它们统称规模维数增大的问题。解决这类问题可以用改进算法的思想：本文第一部分先是概述这种思想；第二部分则从一道有趣的IQ题目说起，引入改进算法的基本思路和基本途径；第三部分则用多个例子解释说明如何改进算法；最后一部分是总结改进算法的思想。【目录】一、概述2二、引子：从一道IQ题说起2三、改进算法的途径3(1)直接增加算法的规模，解决问题3【例一】街道问题及其扩展。（经典问题）3(2)用枚举处理增加的规模，从而解决问题4【例二】旅行（广东省奥林匹克竞赛2001）4【例三】炮兵阵地。（NOI2001）5(3)用贪心解决增加的规模，从而解决问题5【例四】求网络的最小费用最大流。（经典问题）5(4)多种途径的综合运用6【例五】Team Selection (Balkan OI 2004 Day1)6四、总结9【感谢】9【参考文献】10【附录】11A.旅行(广东省奥林匹克竞赛2001)11B.炮兵阵地（NOI2001）12C.Team Selection (BalkanOI 2004 Day 1 Task 2)13一、概述每个学习信息学奥林匹克的选手总是要先学习一些基本的算法，然后才能把算法应用到题目当中去。但是，题目形式多种多样，这些算法往往是不能够直接套用的。有的时候我们分析到某个问题好像可以用某种方法解决，但是这个问题却与之前见过的问题有些不同，例如本文所讨论的情况：问题的规模维数比原问题大，一维的变二维的，二维的变三维的，等等。我们不妨把这类问题叫做规模维数增大的问题，解决这一类问题，往往需要观察问题的特殊性，改进原有算法，从而解决实际问题。二、引子：从一道IQ题说起【IQ题题目】在走入正题之前，还是让我们来玩一道IQ题(据说是IBM公司招聘面试用过的题目)：有两根完全相同但分布不均匀的香（提示：不妨假设是蚊香，一圈圈的那种），每根香烧完的时间是一个小时，你能用什么方法来确定一段45分钟的时间？【】（思考中）【思路】在公布答案之前，还是让我们来循序渐进地思考下去吧。要确定45分钟的时间，而每根香烧完的时间是一个小时，现在应该有三个模型让我们思考：A.不减小每根香的计时，两根香加在一起计时是45分钟；B.只用一根香，使其计时减小，直接计时45分钟；C.把两根香的计时都减小，使两根香加起来是45分钟。A模型显然是不可能成立的；B、C模型的共同点是：我们必须使一根香的计时减小。但是怎样减，能减成什么呢？显然是不能直接把它们分开的，因为香的分布不均匀。由于这里笔者已经降低了难度，根据提示，比较容易想到香是可以两头一起烧的。这样，我们就能把一根香的计时减成半个小时。方案已经更进一步了。通过这一步，B模型只用一根香，是很容易被排除的。余下的选择只有“C模型+两头烧方法”了，但是C模型不能直接应用“两头烧”，因为这样套用的话，0.5+0.5仍然等于1。我们需要对“两头烧”做进一步改进：如果一根香只烧了一头，当剩余时间为t的时候，我们把另一头也点燃那么，我们就能够计出t/2的时间了（前提是我们已知当前剩余时间t）。特别地，当t=60min时，t/2=30min。根据这一改进后的方法，我们很容易就得出正确的解法：分别点燃第一根的两头和第二根的一头，第一根烧完的时候，已经过了30分钟；第二根还剩30分钟，点燃第二根的另一头；当第二根也烧完了，即时间又过了15分钟。那么我们计出的总的时间就为45分钟了。【小结】上面这个例子中，我们从构造模型和改进算法两方面入手，一步一步地达到了优化的解法。主要流程是：1. 找出原始解法和可能改进的方向（即分析成A、B、C模型）；2. 分析算法的原理（由烧一根香计时半小时，引申为烧剩t的时候点两头就能计时）；3. 改进算法（改进的过程中，往往不是依靠算法改进算法本身，反而是利用算法的内涵、实质，结合问题，构造算法）；4. 解决问题（我们得出了正确的解法）。但是如何来改进原有的算法呢，笔者认为可以有以下途径：1. 直接增加算法的规模，解决问题2. 用枚举处理增加的规模，从而解决问题3. 用贪心解决增加的规模，从而解决问题4. 以上各个途径的综合运用围绕这一主线，笔者将用例题做进一步的阐明。三、改进算法的途径(1)直接增加算法的规模，解决问题解决简单的问题，常常可以采用直接处理的方法，但是很多时候还是需要一些技巧。【例一】街道问题及其扩展。（经典问题）【题目大意】原题在右图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。扩展在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。【问题分析】原题是一道简单而又典型的动态规划题，很显然，可以用这样的动态规划方程解题：（这里Distance表示相邻两点间的边长）但是对于扩展后的题目：再用这种简单的方法就不太好办了。如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径“不能重叠”的问题。我们来分析一下原方法的实质：按照图中的斜线来划分阶段，即阶段变量k表示走过的步数，而状态变量xk表示当前处于这一阶段上的哪一点。这时的模型实际上已经转化成了一个特殊的多段图。用决策变量uk=0表示向右走，uk=1表示向上走，则状态转移方程为：(这里的row是地图竖直方向的行数)。通过这一步观察，我们就会发现这个问题很好解决，只需要加一维状态变量就成了。即用分别表示两条路径走到阶段k时所处的位置，相应的，决策变量也增加一维，用分别表示两条路径的行走方向。状态转移时将两条路径分别考虑：【小结】从这个例子可以看出，改进的时候不能只依靠原始算法，还要分析原始算法的本质。(2)用枚举处理增加的规模，从而解决问题【例二】旅行（广东省奥林匹克竞赛2001）【题目大意】给出一个NM的数字矩阵，要求这个矩阵的一个子矩阵，并要求这个子矩阵的数字和最大。【问题分析】初一看题目，想到枚举每一个子矩阵，求出子矩阵的和，比较得出最大值。这样，时间复杂度达到O(N4)，显然不可以接受。因为它是两维的问题，我们可以尝试着把维数降低。先看一维时候的情况：在数列ai中找出和最大的一段。对于一维的子问题，可以这样来想：如果用最基本的方法，可以枚举每个子序列。但是如果纯粹三重循环，枚举头，枚举尾，枚举中间求和，显然是太浪费了。其实我们计算Si,j ()时，可以由获得。这样，动态规划的思路就明显了，Si,j与Si-1,j有直接的关系，而且我们还可以发现Si,*（表示从Si,1到Si,i-1构成的数列）只比Si-1,*多了一项。于是简单的动态规划就出来了，用fi表示以i为终点的数列的最大和，有：不过，我们得到的只是子问题的算法，如何改进算法能使它适用于矩阵的问题呢？我们需要找出矩阵和数列的关系：矩阵是若干条数列，但是它又不仅仅是简单的若干条数列，不同数列中的相同位置的数也构成了联系。我们可以尝试着构造上下、左右同时进行的动态规划，但是也许我们无能为力。对于这道题的数据规模，似乎没有必要构造O(N2)时间的算法。不难想到，枚举上下方向的数列和，在左右方向用动态规划求解，可以得到时间复杂度在O(N3)的算法。【小结】在这个例题中，我们用了最简单的方法枚举，来改进一维数列的最大子序列的解法，从而解决问题的规模的增加。但是枚举这个简单的方法，却能解决很复杂的问题。【例三】炮兵阵地。（NOI2001）【题目大意】在图中标为P的格子中放炮兵，如图灰色区域放了炮兵后，黑色区域不能放炮兵，问图中最多能放多少炮兵？【问题分析】简化的问题：若只有一列，问最多可以放多少炮兵。可以用贪心，尽量把炮兵往上放，也可以这样递推：用fi表示前i行最多能放炮兵数，ai表示第i行的地形，则边界条件：，动态规划方程：但是当问题扩展到多列的情况，就复杂了：不仅要考虑一列是否能引用上一行的函数值，而且要多列同时考虑。但是容易观察到，mn，最大只有10，又因为炮兵攻击范围很大，实际上能放炮兵的组合数很小，可以考虑枚举组合，从而得到改进的动态规划方法：以两行为一个状态，s1表示状态中上行的炮兵布置情况，s2表示下行的布置情况，（可以预先枚举所有可能的情况并给这些情况标号）当第i行能不能布置s1或第i+1行不能布置s2时，或者s1,s2在同一位置布置了炮兵时，都是不符合情况的，令此时；否则：，其中counts2表示s2的炮兵个数；s表示该s1,s2的前一行的炮兵布置情况，而且满足：不存在这样的j。这样到最后的最优解就是最终复杂度分析，时间复杂度大约O(R3n)（R是一行状态的组合数）(3)用贪心解决增加的规模，从而解决问题【例四】求网络的最小费用最大流。（经典问题）显然，求最小费用最大流可以由求最大流的算法改进。求网络的最大流，简单地说来，是每次寻找一条连接源点和汇点的可增广路径并由之扩充网络流，直到不存在这样可增广路径，则得出最大流。那么，又如何把费用也考虑进去呢？我们先来看看网络的费用的定义吧。网络的费用一般是指在每一段弧上弧的费用与弧的流量的乘积的和。（弧的费用由可能为负）所以网络的最小费用最大流是指可行流中费用最小的。不难看出，可行流每增加1，所增加的费用都应该是最小的（事实上应该是减小得最多的）。这样可以得出一个改进：每次选取一条费用最小（而且非正）的可增广路径，直到最终不存在费用非正的可增广路径。这样用贪心的策略就能解决问题了。(4)多种途径的综合运用【例五】Team Selection (Balkan OI 2004 Day1)【题目大意】IOI要来了，BP队要选择最好的选手去参加。幸运地，教练可以从N个非常棒的选手中选择队员，这些选手被标上1到N(3 N 500000)。为了选出的选手是最好的，教练组织了三次竞赛并给出每次竞赛排名。每个选手都参加了每次竞赛并且每次竞赛都没有并列的。当A在所有竞赛中名次都比B前，我们就说A是比B better。如果没有人比A better，我们就说A是excellent。求excellent选手的个数。如数据：则excellent选手是1，2，3，5。【原始思路】一拿到这一题，很容易会有以下的思路。原始算法第一眼看到这道题往往想到枚举。简单地根据better和excellent的定义，现只需要枚举每一个选手X，判断X是否excellent。这可以通过另一重循环，枚举另一选手Y，判断Y是否比X better。判断是容易的，我们只需要简单地判断X和Y的三次排名。因此这一算法的时间复杂度是O(N2)，对于这道题，不能满足要求。主要流程1：for(X从1到N)for(Y从1到N)判断Y是否比X better改进一原始算法是可以改进的。不难看出，如果让X依照第一次竞赛的名次循环，枚举Y时只需要枚举在第一次竞赛中排在X前面选手即可，因为第一次竞赛排在X后的选手一定不可能比X better。不过这样小的改进提起来只是开阔开阔思路，它对时间复杂度不会有太大影响。主要流程2：for(X从第一次竞赛的第1名到第一次竞赛的第N名)for(Y从第一次竞赛的第1名到第一次竞赛的第(X-1)名)判断Y是否比X better改进二如果我们进一步观察，我们能优化上述算法的时间复杂度。我们发现：如果Y不是excellent（因为有Z比Y better），当我们检查X是否excellent时，我们检查了Z是否比X better的话，可以不检查Y。因为如果Y比X better，那么Z一定比X better。然后可以通过简单地修改“改进一”。在判断X是否excellent的时候，我们只需要在当前的excellent选手集合中取得Y即可。主要流程3：for(X从第一次竞赛的第1名到第一次竞赛的第N名)for(Y枚举当前已知的excellent)判断Y是否比X better这样，我们能把时间复杂度减少到O(NK)（设K是excellent选手的个数）。由于这题K可能很大，算法效果仍然不是很理想。【原始思路小结】这里的原始算法是直接根据原始模型模拟出来的，改进一和改进二都单纯地根据原始算法的设计缺陷来“改进”（这个改进没有利用问题的特殊性，不是本文所要阐述的“改进”），所以最后的时间复杂度没有质的进展。【降维思路】本道题规模还是很明显的从二维扩充到三维。所以还是先用降维的思想，我们先解决选手之间只进行两次竞赛的问题。两次竞赛的问题同样可以套用改进二的普遍算法。为了方便说明，我们设第一次竞赛排名依次为Ai（表示第一次竞赛的第i名是Ai）， Ai号选手在第二次竞赛中的排名的为BAi（注意BAi与Ai的含义不同）。参考“主要流程3”：先是X=A1，显然A1是excellent；接着X=A2，只需要比较BA1与BA2大小，不妨假设BA2BA1，则A2也是excellent；接下来，X=A3，我们需要比较BA1与BA3，BA2与BA3假设A3也是excellent；X=A4时，我们需要比较BA1与BA4，BA2与BA4，BA3与BA4，假设A4也是excellent；。也许这里有心人会发现什么，对了，比较BA1与BX，BA2与BX，BA3与BAi的时候，只要有任何一个BAjBAi(ji)，Ai就不是excellent的，那么，我们只需要用min(BAj)与BAi比较！改进三（适用于两次竞赛）以上我们看到了一个特殊的例子：两次排名完全相反，但是我们可以从中提炼出可行的改进算法：对于两次竞赛的情况，当X=Ai时，设，则BAi只需要与besti比较即可。时间复杂度竟然达到O(N)。【降维思路小结】在这次分析中，我们从两次竞赛简化后的问题出发，通过简单的观察和思考，得出了改进的算法，但是优化后的算法要应用到三维的情况还有很长的路要走。【扩展思路】我们怎样把“改进三”应用到三维的情况从而解决问题呢？改进三的思路能否再明确些？改进三的本质是什么？其实，X依照第一次竞赛的名次循环，X=Ai时，因为中，ji这样就保证了Aj在第一次竞赛中名次一定比Ai前；如果bestiBAi，这样就保证了Aj在第二次竞赛中名次比X前；总之则必然有Aj比Ai better。改进四能否把改进三扩展到三次竞赛上面去呢？为了方便说明，我们还需要设第三次竞赛中Ai选手名次为CAi。我们假设这样一个过程：(1)当X=Ai，设ji，则可以保证Aj在第一次竞赛中名次比Ai前，若不存在这样的j，则Ai是excellent；(2)在符合(1)条件的所有Aj中找出能满足BAjBAi的选手，保证Aj在第二次竞赛中名次比Ai前，若不存在这样的j，则Ai是excellent；(3)在符合(1)(2)条件的所有Aj中找出min(CAj)，比较min(CAj)与CAi，若min(CAj)CAi，则保证Aj在第三次竞赛中名次比Ai前，则必有Aj比Ai better，Ai必不是excellent；反之Ai是excellent。以上三个条件即为：“Ai是excellent”等价于“不存在这样的，使”。改进五显然，如果我们仍然用枚举的方法来实现第(2)步，则最终的算法复杂度仍然是O(N2)。为什么我们却说这是改进过后的算法呢？因为我们实际上利用问题的特殊性，改进二是纯粹的枚举，进行的第(1)步以后要第二第三次竞赛同时比较，实现起来是很难优化的。但是改进四则体现了第二第三次竞赛分步选取的思路，利用这一点能否在实现中改进算法的复杂度呢？我们可以比较，改进二和改进四是不同的，在进行了第(1)步以后，改进二需要同时考虑第二第三次竞赛成绩，两次成绩同时考虑并不是严格有序的，有时候我们不能比较二元组(BAi,CAi)与(BAj,CAj)的大小（例如当BAiCAj时）。而改进四的第(2)步可以先考虑第二次竞赛的成绩，如果我们把第二次竞赛的成绩用有序数列来记录（设这个序列为Dk，即把BAj(ji)从小到大排序），我们能轻易找到符合条件的Aj。改进六由改进五可以知道，我们单单从改进第(2)步，时间复杂度仍然不理想的，能否切实把第(2)步和第(3)步结合起来？经过了改进五的改进，我们把查找到的符合BAjBAi(ji)的Aj在一个有序数列中记录下来，这样，符合条件的Aj必然在数列中是连续的，设它是从D1到DK。为了让第(3)步与第(2)步结合，我们再设另一个数列Ek，使它和Dk一一对应，即Dk与Ek分别代表同一选手在第二第三次竞赛的名次。这样，第(3)步又可以简化为在一段数列Ek中查找最小值，即找能否在最短时间内查找出这个最小值呢？我们需要一种优化的数据结构来记录Dk和Ek。该数据结构能很快处理Dk和Ek，并且需要支持两种操作。插入：加入一对数(key,value)到数据结构中。查询：查询key小于X的最小的value显然，这里的key代表Dk，value代表Ek。因为我们需要的操作与检索树擅长的操作很类似，所以对数据结构有一定理解的选手，在这里都能够想到我们可以构造一个二叉检索树。【改进六的实现：优化数据结构】我们构造检索树的目的是查询某一区间的最小value，这样，我们可以定义每个节点代表一个区间，叶子部分代表一个key，我们依次把每两个叶子指向同一个父亲节点。例如1和2的父亲是区间1,2；1,2和3,4的父亲是1,4，如此类推。我们定义每个节点表示的区间是key的区间，而节点值则记录该区间中的最小value。插入和查询具体做法如下：插入操作：当我们接到一个请求：把(a,b)加入到检索树中。那么我们只需要依次从key=a的叶子检索到根节点，比较b和途中每个节点的值大小，如果b小于该节点的值，就用b更新它。查询操作：我们要让检索树能够查询key小于a的最小value。显然我们查询1,a的最小value时，由检索树的性质，我们可以把它分成小区间并分别查询它。例如当a=14时，需要访问到区间1,8，9,12，13,13。对于这题，可以有简单的实现方法：先令min-value为0，依次从表示a,a的节点检索到根节点，如果该节点有父亲并且是父亲的右儿子，就比较它的左兄弟和min-value的值，如果左兄弟节点的值小于min-value，就用左兄弟节点的值更新它。到根节点的时候即可以返回min-value。这种数据结构能使查询和插入操作都能在O(LogN)的复杂度下完成，最终算法这样我们就能很清晰地得出优化的解法：以第一次竞赛的名次从高到低枚举X，以第二次竞赛名次为key，第三次竞赛名次为value。对于每个X，只要查询区间1,key的最小值min-value，若min-valuevalue，说明X是excellent，并把(key,value)加入检索树。由于枚举X循环需要O(N)时间，查询和插入都只需要O(LogN)，总的时间复杂度是O(NLogN)。对于所有数据都应该在很短时间内出解。【小结】在这个部分，我们分析了Team一题，过程中总结了很多算法，有的是基本算法，有的是改进不完全的算法。不过很多时候我们思考这一题并不需要这么多的改进，例如我们很容易就能跳过改进一而直接得到改进二的结论。这一题改进三得出来以后，并没有而且不能直接得出改进四，而需要很重要的一步：分析改进三的本质，从而扩展改进三。笔者之所以选取了Team这题作重点分析，不仅是因为Team一题需要灵敏的头脑，全面地观察，还因为它需要对数据结构有一定的认识，笔者当初做这道题的时候就在这里栽了跟头。四、总结这篇论文给大家解释了笔者关于规模维数增加的一类问题的看法。由于笔者水平有限，有些道理仍然未能参透，文中的算法还能有改进的地方。但本文旨在阐述在解决这类问题的过程中，应该结合算法的本质和问题的特点。算法改进的思想其实是开阔进取的思想，即不满足于现状，要开发新的算法，新的思路。人类漫长的历史不就是开阔进取的精神在支配着，没有开阔进取，又何来我们今天的发达的生产力？在OI中很多问题我们不能够说随便解决了就OK，我们还要有开阔进取的精神，不断改进算法和数据结构，才能真正意义上解决问题。算法改进的思想其实也是创新的思想，即“要创造”的思想。很多时候，信息学奥林匹克的问题并不能直接套用经典算法，而需要加入很多创新的思维，和具体的实践。事实上，任何经典的算法都是由创新的思想总结出来的。只要我们能大胆创新，说不定某一天也会有我们创造的经典算法哩。【感谢】感谢林盛华老师指导和杨溢同学的热情帮助。【参考文献】1金牌之路 高中计算机竞赛辅导/江文哉主编.西安：陕西师范大学出版社，2000.62奥赛经典 信息学奥林匹克教程 提高篇/吴耀斌，曹利国，向期中，朱全民编著.长沙：湖南师范大学出版社，2001.63算法艺术与信息学竞赛/刘汝佳，黄亮著.北京：清华大学出版社，20034 Balkan Olympiad Informatic 2004官方网站提供的原题和解题报告5广东省奥林匹克竞赛2001（GDOI2001）题目6全国奥林匹克竞赛2001（NOI2001）题目【附录】A.旅行(广东省奥林匹克竞赛2001)问题描述GDOI队员们到Z镇游玩。Z镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成个区域。Z镇的名胜位于这些区域内。从上往下数第i行，从左往右数第j列的区域记为D(i,j)。GDOI队员们预先对这个区域打分V(i,j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便集合，队员们只能在某一范围内活动。我们可以用(m1,nl)与(m2,n2)表示这样的一个范围：它是这些区域的集合：。GDOI队员们希望他们活动范围内的区域的分值总和最大。 当然，有可能队员们一个地方也不去（例如，所有区域的分值都是负数。当然，如果某范串内的分值总和为零的话，他们也会去玩）。也有可能他们游览整个Z镇。你的任务是编写一个程序，求出他们的活动范围(m1,nl),(m2,n2)。输入格式输入数据存放在当前目录下的文本文件travel.dat中。数据有m+1行。第一行有两个数m,n(m,n定义如上)。其中，。接下来的m行，每行n个整数，第i行第j个数表示分值V(I,j)。每两个数之间有一个空格。输出格式答案输出到当前目录下 travel.out中，只有一行，分两种情况:1 队员们在范围(m1,n1),(m2,n2)内活动，输出该范围内的分值。2 队员们不想去任何地方，只需输出NO。注意：不要有多余空行，行首行尾不要有多余空格。输入输出举例样例一样例二Travel.dattravel.outTravel.dattravel.out4 51 -2 3 -4 56 7 8 9 10-11 12 13 14 -1516 17 18 19 201462 3-1 -2 -1-4 -3 -6NOB.炮兵阵地（NOI2001）司令部的将军们打算在的网格地图上部署他们的炮兵部队。一个的地图由N行M列组成，地图的每一格可能是山地（用H 表示），也可能是平原（用P表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 Input第一行包含两个由空格分割开的正整数，分别表示N和M； 接下来的N行，每一行含有连续的M个字符(P或者H)，中间没有空格。按顺序表示地图中每一行的数据。N = 100；M = 10。Output仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。Sample Input5 4PHPPPPHHPPPPPHPPPHHPSample Output6C.Team Selection (BalkanOI 2004 Day 1 Task 2)The Interpeninsular Olympiad in Informatics is coming and the leaders of the Balkan Peninsula Team have to choose the best contestants on the Balkans. Fortunately, the leaders could choose the members of the team among N very good contestants, numbered from 1 to N (3 N 500000). In order to select the best contestants the leaders organized three competitions. Each of the N contestants took part in all three competitions and there were no two contestants with equal results on any of the competitions. We say that contestant is better than another contestant when is ranked before in all of the competitions. A contestant A is said to be excellent if no other contestant is better than A. The leaders of the Balkan Peninsula Team would like to know the number of excellent contestants.Write a program named TEAM, which for given N and the three competitions results, computes the number of excellent contestants.The input data are given on the standard input as four lines. The first line contains the number N. The next three lines show the rankings for the three competitions. Each of these lines contains the identification numbers of the contestants, separated by single spaces, in the order of their ranking from first to last place. The standard output should contain one line with a single number written on it: the number of the excellent.EXAMPLE 1Input3 2 3 13 1 21 2 3Output3Note: No contestant is better than any other contestant, hence all three are excellent.EXAMPLE 2Input 102 5 3 8 10 7 1 6 9 41 2 3 4 5 6 7 8 9 103 8 7 10 5 4 1 2 6 9Output4Note: The excellent contestants are those numbered with 1, 2, 3 and 5.