V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zzy8200
V2EX  ›  程序员

Google Foobar 通关

  •  1
     
  •   zzy8200 ·
    zeruniverse · 2017-10-31 11:40:27 +08:00 · 5735 次点击
    这是一个创建于 2340 天前的主题,其中的信息可能已经有所发展或是发生改变。

    上周五被带进坑,三天时间断断续续通关了 Google Foobar Challenge。不得不说题目还是很有意思的。总共有 5 关,每关分别是 1 题,2 题,3 题,2 题,1 题。前三关比较正常,后面就开始变态了。做完第三关可以给 Google HR 留联系方式。

    顺便贴一下丧心病狂的最后一题

    Disorderly Escape
    =================
    
    Oh no! You've managed to free the bunny prisoners and escape Commander Lambdas
    exploding space station, but her team of elite starfighters has flanked your
    ship. If you don't jump to hyperspace, and fast, you'll be shot out of the sky!
    
    Problem is, to avoid detection by galactic law enforcement, Commander Lambda
    planted her space station in the middle of a quasar quantum flux field. In order
    to make the jump to hyperspace, you need to know the configuration of celestial
    bodies in the quadrant you plan to jump through. In order to do *that*, you need
    to figure out how many configurations each quadrant could possibly have, so that
    you can pick the optimal quadrant through which you'll make your jump. 
    
    There's something important to note about quasar quantum flux fields'
    configurations: when drawn on a star grid, configurations are considered
    equivalent by grouping rather than by order. That is, for a given set of
    configurations, if you exchange the position of any two columns or any two rows
    some number of times, you'll find that all of those configurations are equivalent
    in that way - in grouping, rather than order.
    
    Write a function answer(w, h, s) that takes 3 integers and returns the number of
    unique, non-equivalent configurations that can be found on a star grid w blocks
    wide and h blocks tall where each celestial body has s possible states.
    Equivalency is defined as above: any two star grids with each celestial body in
    the same state where the actual order of the rows and columns do not matter (and
    can thus be freely swapped around). Star grid standardization means that the
    width and height of the grid will always be between 1 and 12, inclusive. And
    while there are a variety of celestial bodies in each grid, the number of states
    of those bodies is between 2 and 20, inclusive. The answer can be over 20 digits
    long, so return it as a decimal string.  The intermediate values can also be
    large, so you will likely need to use at least 64-bit integers.
    
    For example, consider w=2, h=2, s=2. We have a 2x2 grid where each celestial
    body is either in state 0 (for instance, silent) or state 1 (for instance,
    noisy).  We can examine which grids are equivalent by swapping rows and
    columns.
    
    00
    00
    
    In the above configuration, all celestial bodies are "silent" - that is, they
    have a state of 0 - so any swap of row or column would keep it in the same
    state.
    
    00 00 01 10
    01 10 00 00
    
    1 celestial body is emitting noise - that is, has a state of 1 - so swapping
    rows and columns can put it in any of the 4 positions.  All four of the above
    configurations are equivalent.
    
    00 11
    11 00
    
    2 celestial bodies are emitting noise side-by-side.  Swapping columns leaves
    them unchanged, and swapping rows simply moves them between the top and bottom. 
    In both, the *groupings* are the same: one row with two bodies in state 0, one
    row with two bodies in state 1, and two columns with one of each state.
    
    01 10
    01 10
    
    2 noisy celestial bodies adjacent vertically. This is symmetric to the
    side-by-side case, but it is different because there's no way to transpose the
    grid.
    
    01 10
    10 01
    
    2 noisy celestial bodies diagonally.  Both have 2 rows and 2 columns that have
    one of each state, so they are equivalent to each other.
    
    01 10 11 11
    11 11 01 10
    
    3 noisy celestial bodies, similar to the case where only one of four is noisy.
    
    11
    11
    
    4 noisy celestial bodies.
    
    There are 7 distinct, non-equivalent grids in total, so answer(2, 2, 2) would
    return 7.
    
    Languages
    =========
    
    To provide a Python solution, edit solution.py
    To provide a Java solution, edit solution.java
    
    Test cases
    ==========
    
    Inputs:
        (int) w = 2
        (int) h = 2
        (int) s = 2
    Output:
        (string) "7"
    
    Inputs:
        (int) w = 2
        (int) h = 3
        (int) s = 4
    Output:
        (string) "430"
    
    Use verify [file] to test your solution and see how it does. When you are
    finished editing your code, use submit [file] to submit your answer. If your
    solution passes the test cases, it will be removed from your home folder.
    
    11 条回复    2018-10-25 15:28:52 +08:00
    Morriaty
        1
    Morriaty  
       2017-10-31 14:21:10 +08:00
    所以你去面试了没?

    一直只用 google 搜问题,却从来没触发过
    ryd994
        2
    ryd994  
       2017-10-31 16:40:58 +08:00 via Android
    第四关第二题挂了

    @Morriaty 留个联系方式吧
    我现在在删数据二刷,晚些时候给你邀请
    Morriaty
        3
    Morriaty  
       2017-10-31 16:56:01 +08:00
    @ryd994 这东西还能邀请的?

    丘丘 & WeChat:NjkwOTI5MzE5
    zzy8200
        4
    zzy8200  
    OP
       2017-10-31 22:11:21 +08:00 via iPhone
    @ryd994 无向图最大匹配那道题么,那个要用带花树算法
    ryd994
        5
    ryd994  
       2017-10-31 23:31:11 +08:00 via Android
    @zzy8200 我挂的是 expanding nebula,关于 cell automata 的
    你说的那题是叫什么?
    zzy8200
        6
    zzy8200  
    OP
       2017-11-01 00:28:28 +08:00 via iPhone
    @ryd994 那题目不一样 我的是 distract guards
    ryd994
        7
    ryd994  
       2017-11-01 01:51:21 +08:00
    @zzy8200 那题我做过,没用 Edmonds Blossom,用了个 heuristic 硬刷过去了
    zzy8200
        8
    zzy8200  
    OP
       2017-11-01 03:24:02 +08:00
    @ryd994 WTF 贪心过么? 我当时强行用匈牙利算法,错了一个点,以为必须要 blossom...
    ryd994
        9
    ryd994  
       2017-11-01 06:01:16 +08:00
    @zzy8200 不算是贪心
    具体细节我忘了,但是你看数字大了以后,其实整个图的连通性是很好的,大多数数之间都可以 pair,以此为基础其实就可以硬来了,我不想在这里贴代码,你可以联系我 telegram
    zzy8200
        10
    zzy8200  
    OP
       2017-11-01 06:13:06 +08:00 via iPhone
    @ryd994 我已经 AC 了 233 我觉得 huristic 可以的话 N^2 贪心应该也可以,从最难匹配的点开始 每个点往后找匹配,找不到就标为无法匹配,找到把这两个点删了
    sandwich
        11
    sandwich  
       2018-10-25 15:28:52 +08:00
    DALAO 这道题可以给点提示吗|· ω · ` )
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1044 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 19:17 · PVG 03:17 · LAX 12:17 · JFK 15:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.