### vudduu's blog

By vudduu, 8 years ago, ,
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)

• +7

 » 8 years ago, # | ← Rev. 2 →   0 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...
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Oh thanks, i'm resolving the problem H.H - Hedge Mazes (Graph Bridges, Strongly Connected Components)
•  » » 8 years ago, # ^ |   +3 D seems like NEERC 2011 DMaterials: http://neerc.ifmo.ru/regional/index.html
•  » » 8 years ago, # ^ |   0 Can you give a hint on how to solve F using suffix array?
•  » » » 8 years ago, # ^ |   +1 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.
•  » » 8 years ago, # ^ |   0 D - prefix/suffix trie + insights
 » 8 years ago, # |   0 Are the solutions published anywhere? I found only tests but can't find the solutions :(
•  » » 8 years ago, # ^ |   0 I have 5 solutions now and i will paste this solutions in the link
•  » » » 8 years ago, # ^ |   0 Great! Wating for them.
•  » » 8 years ago, # ^ | ← Rev. 4 →   +3 Here's my solution to problem C — Candy's Candy.Here's my solution to problem G — Garden Fence.
•  » » » 6 years ago, # ^ |   0 hey, I know it's been a "little" while since you've posted this, but can you explain the idea behind your solutions? I'm studying this questions and the only solution I could find was yours