Блог пользователя xproxmess

Автор xproxmess, история, 8 лет назад, По-английски

Hi,

Can someone explain the solutions for problems F and I of the 2017 Hackatari Codeathon?

Thanks in advance!

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Well, only three guys solved it. Let's mark them! :D

Deemo

Noureldin (Oh I know you from a previous post of mine. Hi! :D)

Pleeease help us. :D

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    for problem F

    imagine that there is a boundary to the grid colored in some color (say 0)

    build a graph where nodes are islands/colores and two colors (say c1 and c2) share an edge if there are two adjacent cells where one cell is colored in c1 and the other in c2

    an island (with color c1) contains another (say c2) only if c1 lies on every path from 0 to c2 ,this part can be computed using dfs

    PS: to be honest I didn't know how to compute the last part until I peeked into Deemo 's solution

    as for problem I

    • solve it offline
    • build the array keeping track of the insertion time and value of each element using some fast DS (I used sqrt-decomposition)
    • binary search for the time where LIS == K and output the answer according to the rules of the game
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks, will try it! :)