xproxmess's blog

2017 Hackatari Codeathon
By xproxmess, history, 8 years ago, In English

Hi,

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

Thanks in advance!

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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
    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks, will try it! :)

→ Reply