vudduu's blog

ACM ICPC Latin America 2011
By vudduu, 12 years ago, In English
Problem Set and Data Set: Acm-icpc-latin-america-2011

- C - Candy's Candy (Math)
- E - Electrical Pollution (Graph Traversal)
- F - File Retrieval (Stack, Suffix Array)
- G - Garden Fence (Sweep Line)
- H - Hedge Mazes (Graph Bridges, Strongly Connected Components)
  • Vote: I like it
  • +7
  • Vote: I do not like it

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

C - Candy's Candy (math)
E - Electrical Pollution (graph traversal)
F - File Retrieval (stack, suffix array)

G - Garden Fence (sweep line)

H - Hedge Mazes (bridges)


Still clueless on D...

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

    Oh thanks, i'm resolving the problem H.


    H - Hedge Mazes (Graph Bridges, Strongly Connected Components)
    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    D seems like NEERC 2011 D
    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Can you give a hint on how to solve F using suffix array?
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      First concatenate all of the strings using invalid characters as separators, and construct the suffix array sa[] and the corresponding longest common prefix lcp[] array (where lcp[i] is LCP of sa[i] and sa[i+1]).

      It's easy to see that if you have a sequence of LCPs such as 1, 2, 3, 4, 2, 4, 1, in which 2 is less than or equal to all of the others, except the first and the last, then the words that contain the suffixes related to the 2,3,4,2,4 LCPs will form a searchable subset (there is a substring that appears in only those words). The stack is used to keep track of when those subsets are formed.
      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    D - prefix/suffix trie + insights
    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Are the solutions published anywhere? I found only tests but can't find the solutions :(
→ Reply