Suppose you have a maze represented by a graph where each vertex represents a room and edges represent paths between rooms and each edge has a weight denoting the time it takes to go that way. Now here comes the tricky part: suppose each room needs a set of keys for you to enter, and inside each room you can find another set of keys. Keys can be repeated and one key may be needed to enter on more than one room. You can only enter the room if you have all keys required.

You have an arbitrarily large number of chests with gold inside and each chest needs one key which can be found in the maze. You already have a set of keys that you can use. You can use a key more than once. The question is: how do you collect the keys you need as fast as possible?

The only algorithm I could come up with was to have as state keys you have and node, so it'd be O(2^numberofkeys * numberofhalls)

I'm now facing a problem in real life involving efficient data structures (yay!): I need a data structure for storing key-value data and supports prefix-based searching and, considering N the amount of keys and M a key length, inserting and deleting in O(M). The data structure will be used in an embedded software, so it must be memory efficient.

My current solution is using a trie, but the memory overhead is too big for the application. It's an straight-forward trie implementation, but splitting strings in nibbles instead of bytes. Tips on improving the memory usage for the trie are welcome.

Any thoughts?

Hello, yesterday we participated in ACM ICPC 2014 South America Finals in Brazil. We'd like to know if there are websites that we can check the final results from other regions. Also, if you have info on how to solve some problem, please post it here :D

Thanks!

Link to the online contest:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=13&page=show_contest&contest=339

Hello, I'm trying to solve this question from SWERC: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4423

I tried to understand the editorial, but failed to do so. It is available here (under question H): http://users.dsic.upv.es/swerc/ProblemSet2013/solutions.pdf

I understood the recursion for the DP, but I can't understand why you can just go up when you bump into a "U" and use the same recursion. for me it'd recount some positions. An easy example is S="LL" and T="UL".

Could someone help me out?

Notice: this is a piece of a bigger problem I'm trying to solve, but I could figure the rest out, and I think this part would be a good resource for the community in general, as I couldn't find anywhere.

The problem: I have an origin point O and a set of several line segments that never crosses each other. I know the line segments have a common angle interval in which they all appear. This angle is measured according to a line parallel to X axis and that contains point O. I need to sort this set of line segments according to the distance from the origin point, meaning that in the angle interval that the line segments appear, if line A is always closer to the point O, A comes first in the set. This comparison must be made without floating point operations!

Here is a tiny (horribly made) pic to illustrate the problem:

The section between the dashed line is the region of interest. The expected result would be line 0 coming first and line 1 coming second.

Important notes:

• The line segments never crosses
• No three points are collinear (point O and the endings of the line segments)

I couldn't come up with anything that works, can anyone help me out?

If anyone is interested in the full problem, here is a link to it (though i UVa this sorting isn't necessary — weak test cases): UVa 12675 — Hide and seek

EDIT: I've managed to make it work! :D Here is the final comparison function:

inline bool cmpActive(line a, line b){
  if(a == b) return false; // if lines are the same, ignore

  // checks if b.p1 is in the sector defined by a.p1 and a.p2
  if(ccw(origin, a.p1, b.p1) && !ccw(origin, a.p2, b.p1)){
    // if it is, checks if b.p1 is on the same side of line a as origin
    return ccw(a.p1, a.p2, b.p1) !=  ccw(a.p1, a.p2, origin);
  }
  else if(ccw(origin, a.p1, b.p2) && !ccw(origin, a.p2, b.p2)){
    // if b.p1 isn't in the sector, but b.p2 is
    return ccw(a.p1, a.p2, b.p2) !=  ccw(a.p1, a.p2, origin);
  }
  else{
    // this was missing: when interval A is completely inside B, so we can
    // choose any point of A we want
    return ccw(b.p1, b.p2, a.p1) ==  ccw(b.p1, b.p2, origin);
  }
}

In this pseudocode, ccw(A,B,C) refers to testing wether C is in clockwise direction from B, taking A as it's rotation center

I'd like to thank brunoja for the help he provided!

I've been trying to understand how to solve this problem on UVa: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=3969

Abridged problem statement: You have N piles in different heights, each pile having a weight W. You can only move a pile if the next X is bigger than the pile you are moving, and each move costs W * Δ Height. You want to turn the N piles into K piles with the minimum cost possible (you can only move one pile to another place where there was a pile). constraints: 1 ≤ K ≤ N ≤ 1000 and W ≤ 10⁶

I've found lots of explanations (mostly in spanish and chinese), and all of them say "it's easy to see a DP solution of O(n*n*k), but that would TLE..." yeah, I can see one DP solution in O(n*n*k), but I can't understand their recursion and, more specifically, how to turn that into line equations and how to apply convex hull trick on it.

I've never solved any problem that needed convex hull trick or any DP optimization at all, so I'm quite a noob here. Any materials (apart from PEGWiki's article on convex hull trick), like simple problems solvable with it, are apreciated.

Thanks!

References (didn't help me, but maybe some of you can make sense out of it):

• C++ Implementation: https://github.com/marioyc/Online-Judge-Solutions/blob/master/UVA/Contest%20Volumes/12524%20-%20Arranging%20Heaps.cpp

• Explanation in spanish: http://chococontest.wordpress.com/2012/11/25/solucionario-regional-south-america-2012/

• Explanation in chinese (according to Google translate):http://blog.csdn.net/work_freedom/article/details/8915965