• <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)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产成人久久AV免费| 久久国产精品77777| 精品乱码久久久久久夜夜嗨| 国产91久久综合| 国产精品久久久久久五月尺| 国产成人精品综合久久久| 国产精品久久久久无码av| 久久99久久无码毛片一区二区| 四虎亚洲国产成人久久精品| 国产精品久久久久久久久软件| 欧美久久久久久精选9999| 久久精品一区二区三区中文字幕| 久久久久人妻一区二区三区| 久久ww精品w免费人成| 久久精品一区二区影院| 国产精品一久久香蕉国产线看观看 | 久久性生大片免费观看性| 日韩av无码久久精品免费| 久久久精品久久久久特色影视| 无码人妻久久一区二区三区蜜桃| 久久99国产精品久久| 久久精品aⅴ无码中文字字幕不卡| 国产精品久久久久久久 | 久久精品亚洲AV久久久无码| 久久99精品久久久久久hb无码 | 精品人妻伦九区久久AAA片69| 伊人伊成久久人综合网777| 国产精品久久久久久福利69堂| 久久精品一区二区三区AV| 久久久国产精品网站| 久久丫精品国产亚洲av不卡 | 亚洲国产天堂久久综合网站| 久久久久亚洲av综合波多野结衣 | 色综合合久久天天给综看| 久久国产精品成人影院| 色综合久久久久无码专区| 久久亚洲国产成人影院| 国产精品久久久久蜜芽| 99久久99久久精品国产片果冻| 久久久无码精品亚洲日韩京东传媒 | 亚洲国产成人精品91久久久|