• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Google code jam 2008 QR - Saving the Universe

            Problem

            The urban legend goes that if you go to the Google homepage and search for "Google", the universe will implode. We have a secret to share... It is true! Please don't try it, or tell anyone. All right, maybe not. We are just kidding.

            The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine's name, the universe does implode!

            To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they're received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.

            Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.

            Input

            The first line of the input file contains the number of cases, N. N test cases follow.

            Each case starts with the number S -- the number of search engines. The next S lines each contain the name of a search engine. Each search engine name is no more than one hundred characters long and contains only uppercase letters, lowercase letters, spaces, and numbers. There will not be two search engines with the same name.

            The following line contains a number Q -- the number of incoming queries. The next Q lines will each contain a query. Each query will be the name of a search engine in the case.

            Output

            For each input case, you should output:

            Case #X: Y
            where X is the number of the test case and Y is the number of search engine switches. Do not count the initial choice of a search engine as a switch.

             

            Limits

            0 < N ≤ 20

            Small dataset

            2 ≤ S ≤ 10

            0 ≤ Q ≤ 100

            Large dataset

            2 ≤ S ≤ 100

            0 ≤ Q ≤ 1000

            Sample


            Input

            Output
            2
            5
            Yeehaw
            NSM
            Dont Ask
            B9
            Googol
            10
            Yeehaw
            Yeehaw
            Googol
            B9
            Googol
            NSM
            B9
            NSM
            Dont Ask
            Googol
            5
            Yeehaw
            NSM
            Dont Ask
            B9
            Googol
            7
            Googol
            Dont Ask
            NSM
            NSM
            Yeehaw
            Yeehaw
            Googol

            Case #1: 1
            Case #2: 0

            In the first case, one possible solution is to start by using Dont Ask, and switch to NSM after query number 8.
            For the second case, you can use B9, and not need to make any switches.


            Analysis

            The first task in the new Google Code Jam is about, no surprise, search engines, and also, the grandiose feat of saving the universe in a parsimonious way. However, putting all the fancies aside, the problem itself is easy.

            List all queries one by one, and break them up into segments. Each segment will be an interval where we use one search engine, and when we cross from one segment to another we will switch the search engine we use. What can you say about each segment? Well, one thing for sure is:

            Never ever ever have all S different search engines appear as queries in one segment. (*)
            Why is this? Because if all S names appeared in one segment, then any search engine used for that segment will encounter at least one query that is the same as its name, thus exploding the universe!

             

            Working in the opposite direction, (*) is all we need to achieve; as long as you can partition the list of queries into such segments, it corresponds to a plan of saving the universe. You don't even care about which engine is used for one segment; any engine not appearing as a query on that segment will do. However, you might sometimes pick the same engine for two consecutive segments, laughing at yourself when you realize it; why don't I just join the two segments into one? Because your task is to use as few segments as possible, it is obvious that you want to make each segment as long as possible.

            This leads to the greedy solution: Starting from the first query, add one query at a time to the current segment until the names of all S search engines have been encountered. Then we continue this process in a new segment until all queries are processed.

            Sample code in C++, where st is the set of queries in the current segment, q is the next query, and count is the number of switches.

            st.clear();
            count = 0;
            for (int i=0; i<Q; i++) {
            getline(cin, q);
            if (st.find(q) == st.end()) {
            if (st.size() == S-1) {
            st.clear();
            count++;
            }
            st.insert(q);
            }
            }
            
            If st is a hashset, you expect the solution run in O(n) time. Note that this solution uses the fact that each query will be a search engine name and so we can ignore the list of names provided in the input.

             

            Let us justify that the greedy approach always gives the optimal answer. Think of the procedure as Q steps, and we want to show that, for each i, there is (at least) one optimal choice which agrees with us on the first i steps. We do this inductively for i = 0, then i = 1, and so on. The proposition for i = Q when proven true will imply that our algorithm is correct.

            So, the key points in the inductive step i:

            1. If adding the next query will explode the universe, we must start a new segment. Any optimal choice agrees with us for the first (i-1) steps must also do that.
            2. If adding the next query will not explode the universe, we do not start a new segment. We know there is an optimal solution R agreed with us for (i-1) steps. Even if in R a new segment is started at step i, we can modify it a little bit. Let R' be the plan that agrees with R, but instead of starting a new segment on the i-th step, we delay this to the (i+1)st. It is clear that R' will also make the universe safe, and has no more switches than R does. So, R' is also an optimal solution, and agrees with our choice for the first i steps.

             

            The similar lines of justifications work for many greedy algorithms, including the well beloved minimum spanning trees.
             
            Another DP Solution:

            Def. Cost[k][i] as the min switches
            when k queries come and current search engine is i

            0<=i<=S
            0<=k<=Q

            1. Optimal: if i!=id[k]: Cost[k][i]=min{..., Cost[k-1][i-2]+1, Cost[k-1][i-1]+1, Cost[k-1][i], Cost[k-1][i+1]+1, Cost[k-1][i+2]+1,...}

                else: Cost[k][i]=min{..., Cost[k-1][i-2]+1, Cost[k-1][i-1]+1, Cost[k-1][i+1]+1, Cost[k-1][i+2]+1,...}

            2. Init: Cost[0][i]=0


            Source Code
            #include <hash_set>
            #include 
            <iostream>

            using namespace std;

            #define Rep(i,n) for (int i(0),_n(n); i<_n; ++i)

            int main()
            {
                
            int T;
                
            //freopen("..\\s.in","r",stdin);
                
            //freopen("..\\s.out","w",stdout);
                scanf("%d"&T);
                Rep(t, T) 
            {
                    
            int S;
                    scanf(
            "%d"&S);
                    
            string q;
                    getline(cin, q);
            //a unread '\n' in scanf
                    Rep(i, S) {
                        getline(cin, q);
                    }

                    
            int Q;
                    scanf(
            "%d"&Q);
                    getline(cin, q);

                    stdext::hash_set
            <string> st;
                    
            int count = 0;
                    Rep(i, Q) 
            {
                        getline(cin, q);
                        
            if (st.find(q) == st.end()) {
                            
            if (st.size() == S-1{
                                st.clear();
                                count
            ++;
                            }

                            st.insert(q);
                        }

                    }

                    
                    printf(
            "Case #%d: %d\n", t+1, count);
                }

            }

            posted on 2009-08-12 20:25 Chauncey 閱讀(105) 評論(0)  編輯 收藏 引用

            導航

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統計

            常用鏈接

            留言簿

            隨筆檔案(4)

            文章檔案(3)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            性欧美丰满熟妇XXXX性久久久 | 国产成人精品综合久久久| 久久精品国产99久久香蕉| 日本欧美国产精品第一页久久| 久久毛片免费看一区二区三区| 伊人久久精品无码av一区| 狠狠色丁香久久婷婷综| 久久久高清免费视频| 欧洲成人午夜精品无码区久久| AV狠狠色丁香婷婷综合久久 | 久久亚洲精品成人av无码网站| WWW婷婷AV久久久影片| 波多野结衣久久精品| 亚洲国产成人久久综合碰碰动漫3d | 久久夜色精品国产噜噜亚洲a | 久久天天躁狠狠躁夜夜网站| 国产精品成人99久久久久91gav| 精品久久久无码21p发布| 久久se精品一区二区影院| 久久久噜噜噜久久熟女AA片| 一本久久免费视频| 久久久久久国产a免费观看不卡| 精品久久久久中文字幕日本| 蜜桃麻豆WWW久久囤产精品| 久久精品人妻一区二区三区| 久久国产精品一区二区| 国产产无码乱码精品久久鸭| 久久国产欧美日韩精品| 一本久久a久久精品综合香蕉| 国产精品VIDEOSSEX久久发布| 精品一区二区久久| 99久久人妻无码精品系列蜜桃| 精品综合久久久久久98| 天天影视色香欲综合久久| 国产精品伊人久久伊人电影| 久久精品国产亚洲沈樵| 国产91色综合久久免费| 久久精品成人免费网站| 精品久久久久久亚洲| 久久WWW免费人成—看片| 欧美激情精品久久久久久久九九九|