It would be cool to have some discussion here on Knuth's Christmas -- formerly Christmas Tree -- lecture for this year. The video can be found here!

So I've been working on this problem today in Java. I have code that finds the permutations in the correct order, i.e. A > a > B > b > C > ...

I get Time Limit Exceeded, though. Could anyone make any recommendations on how I could optimize my program? Below is my code. Thanks for reading.

My code here!

Hi guys,

Embarassingly having quite a bit of trouble on problem 462 of UVA. It seems to be a (lengthy) simulation problem and my (verbose) code is passing the example tests I run it againsts from the UVA forums and uDebug, yet I still run into WA. Any advice on what I could be doing wrong here?

Thanks!

I'm working on LightOJ problem 1002 and I can see that the problem requires a variant of Dijkstra's algorithm. When I refer to books, however, they require a different type of PriorirtyQueue than what is included in Java's Collections library.

My question is, for those of you who have had to implement Dijkstra's in a contest or even from an OJ while practicing, have you had to write your own Heap and PriorityQueue implementation usually, or is there a quicker way? I've been told before that TreeSet could be used in replacement for PriorityQueue. I've tried to look around a bit for shortest path tagged problems and how people have used Dijkstra's here on Codeforces, but implementations seem to vary so drastically, and it makes it quite confusing to know which style to follow and study. Could someone show me an example of how they implement Dijkstra's algorithm for contests in Java. It would be really helpful to learn from and reference from. Thanks.

I was hoping to ask for a bit of advice on a USACO question. It is the Number Triangles problem in section 1.4. The problem statement can be found here

My initial idea is that it cannot be avoided that this tree-like structure must be traversed in all possible ways, they've listed (downwards left diagonal or downwards right diagonal).

In the example input they give in the problem statement, with 5 rows, it can be worked through that there are 16 possible traversals of the tree. In an example of 4 rows, there are 8 possible ways, ..., and in an example with 1 row there is one possible way. So there are 2^(r-1) possible traversals that need to be checked for maximum sum.

I believe this can be solved if I can find out a way to represent static trees in an array data structure, where I will traverse each possibility given the constraints they've laid out.

That's all fine and dandy, and I think is realistic to do but the problem statement is in the last section of chapter 1, called Introduction to Binary Numbers. Because of this, I cannot for the life of me think of if this is the way the authors intended me to go about solving the problem or if there is an approach I am completely blind to. If I were to solve the problem using the approach mentioned above, I could use binary representations for each node but I see no particular reason to do so when the same could be done with decimal representations. Here is my thought process on paper to show I have put some time into the problem.

If you have any input you could share, I would be most grateful. Also, I've only been working on this problem today. I almost feel like I am cheating by asking you for hints. When you are solving problems, how much time do you generally give yourself to think alone before reaching out for help. Am I doing the right thing?

Thank you for reading.

Hello,

I am trying to work on a problem from acm.sgu and was wondering if I could ask for guidance in the right direction. The problem statement is here: http://acm.sgu.ru/problem.php?contest=0&problem=101

The way I conceptualize it right now is that it is a DFS problem that can be solved similarly to how N-queens is solved. Is this correct?

For the example input we have: (1)<1,2> (2)<2,4> (3)<2,4> (4)<6,4> (5)<2,1>

A tree or graph of sorts would need to be constructed and traversed like the following:

So that I have an easier time modeling the process/structure in ASCII, let the node (k)*<i,j> represent both the pair (k)<i,j> and the reverse (k)<j,i>

(1)*<1,2> ... (other combinations e.g (2)*,(3)*,etc.)
                              /        \         /        \
                        (2)*<2,4>     (3)*<2,4>  (4)*<6,4>   (5)*<2,1>
                  /    /       \            ..............
         (3)*<2,4>  (4)*<6,4>  (5)*<2,1>
       /    \             ......
 (4)*<6,4> (5)*<2,1>
      .......

Ofcourse with the * notation at each node, the reverse pair would need to be searched as well. I believe DFS can be used here to fine the correct sequence that matches the constraints given by the problem set. Something about this bugs me, though. Because I've never done any graph or tree problems, I don't understand whether I need to precompute a proper graph/tree to fit this problem or if new nodes at the next level down are to be created, checked, searched further or backtracked depending on whether they meet the constraints.

Is this the correct idea of DFS for this problem? If it is, is the tree/graph to be precomputed and then searched, or searched while being created dynamically depending on constraints. If not, could you lend advice on the correct approach for this sort of problem? As a bonus perhaps some sort of reference to follow for representing graphs/trees properly in this sort of situation with C++?

I only have a formal understanding of DFS, so my idea could very likely be wrong. Because I might have a bit of a conceptualization issue here, is it best for me to just read the chapter on graph data structures in CLRS first (I intend to eventually do this, but only if I have to). Again I'm sorry for the bad ASCII job but I figured it was worth sharing to show that I've thought about the problem before asking for advice, though.

Thank you for reading.