spoj

Problem: Please find the problem here. Solution: A necessary condition is that the total number of candies can be distributed evenly, therefore we check if sum % N == 0. In that case, all bags with less candies must get filled, and there must be one available. So we sum the total number of candies needed to fill and that’s the answer. Code:

Problem: Please find the problem here. Solution: I started the problem using the a simple complete search of all path. Of course, we are not going to be able to enumerate through all the paths. But fortunately we don’t have to, once we have tried a path we can memoize the result as follow. If I am at a certain node n1 with certain an initial time constraint T1before, and with time t12 I can get to node n2, recursively we know the best path to get to market from n2 with budget T-t12 take time T2after and has minimal cost C2after, then we have one best path candidate from n1 to n2 within time constraint T1before that actually spend time T2after + t12 with cost C2after + c12.

Problem: Please find the problem here. Solution: Using the segment tree like in SPOJ_LITE_2. This time the summary is the sum instead of on light count, but it is just as easy to update those summaries. Code:

Problem: Please find the problem here. Solution: After doing some optimization - the previous solution still cannot be accepted - need to try something else. Previously I was worried about memory consumption creating a full blown segment tree by virtualizing the segments. What if I just create it? Again, we consider this simple example of inserting the segment [1, 5] and [3, 7] Initially the tree is completely empty. 00000000000000 Now we insert [1, 5]

Problem: Please find the problem here. Solution: This problem is really a hard nut to crack. I know there exist simpler solution, but I am going with my idea and implement that complex idea first. The goal is, really, to prove to myself that my idea works, and that to practice coding and debugging complex algorithm. It all started with some simple observations. Judging from the numbers, I believe we can’t allow update to take time proportional to the interval length, or otherwise one could easily construct an example to just keep flipping the whole interval and we are screwed with awful performance.

Problem: Please find the problem here. Solution: To celebrate I have done with my 42nd problem, I decided to attempt this question. Apparently, this isn’t really a question, we can just get it accepted blindfolded - yes, it is that easy :p Consider this a joke in this blog! Code:

Problem: Please find the problem here. Solution: An adhoc problem. The key idea to solve this problem is to try to keep the left hand side as small as possible. For example, if the input is 1921, we can assert the answer is 1991. To see why, decreasing any digit on the right hand side must also decrease a digit on the left hand side, and with we decrease any digit on the left hand side, the number is less than 1900!