How I got to the 'hidden page' notepaded the compiled class file, noticed references to caesar cipher pulled my code2.cpp (decaesar) out of mothballs from the symantec decoding comp ran it with -40 if(s1.compareToIgnoreCase("nqdsvdfn") != 0) Therefore, voila, website. (went for speed, not for time in this case) (recalled later that code2.cpp that I had written was for rolling ciphers with variable c values) http://calypso.cs.ucla.edu/?q=node/view/118 The company wants to use RFID to reduce shipping costs by ensuring all its trucks are fully loaded when they leave the distribution site. Basically, this company receives thousands of consumer products into its warehouse everyday. Each product that comes in to the site is scanned by RFID scanners and data on the product (such as name, size, weight, et cetera) is added to the database you are working on. The company then piles a random collection of these products onto a large pallet and ships off this block of products to one of its local stores. Since they ship so many pallets to their different stores, it doesn’t matter what products get onto the pallet. It only matters that the pallets are completely full (so as to avoid partially empty trucks and such). A pallet is considered full if the cumulative weight of all the products on a pallet equals the pallet’s maximum capacity. Your mission is to write a program that, given the max capacity of the current pallet and the weights of all the products in the distribution center, outputs a way to fully load the pallet using a subset of the products currently in stock. For instance, suppose there are only five products in the warehouse, weighing 4, 7, 5, 9, and 1 pounds respectively. The current pallet ready to leave has a max capacity of 17 pounds. Thus, your program could output 7, 9, 1, which is a weighing that will completely fill the pallet. Of course, most of the time we are talking about pallets that can hold tons and a warehouse that holds thousands of products. You can solve the above problem in general and arrive at a correct answer. However, as a further optimization, sometimes there is a pattern in the weighing of the consumer products that come in. On any given day, there is a 20% chance that all products in the warehouse are ordered 1..N such that for any product indexed at i, the weight of product i is greater than the sum of the weights of products 1..i (in math, this would be called superincreasing). This optimization comes about because of RFID technology in warehouses that the products visit before arriving at your warehouse (just roll with it). You will know that you have a superincreasing product set because the weight of the first product is one (non-superincreasing sets will never start with a weight of one). Now for the nitty gritty. You are welcome to program in any language as long as it will compile on a SEAS machine (although see grading criterion below and realize your language choice may have an impact on running time). Your program, once compiled, must take as a command line argument a file called data.txt. data.txt’s first line is filled will comma-delimited values for the weights of products in the warehouse. You do not know the number of products ahead of time and must plan for a large data set. data.txt’s second line contains the maximum capacity of the current pallet. Your program should output a comma delimited full weighing of the pallet or the words “CANNOT FILL PALLET” if no weighing is possible (that is, no combination of the products’ weights exactly equals maximum capacity). The biggest prizes will go to those participants whose code runs the fastest in repeated trials (20% of these trials will have superincreasing product sets). Thus, language choice and raw efficiency of the solution is important. Other substantial prizes will go to participants who can prove and explain, as a text attachment, the algorithmic efficiency of their solution (this is language independent). For this competition, the competitors are divided into two categories: a) students who have not taken an upper division CS course at UCLA, b) other undergraduates, and c) graduate students. In addition, for category a, you are very lucky because you get to call in sick on days when the product sets are non-superincreasing. Thus, lower division students can assume that all product sets begin with one and are superincreasing. Submit your assignment by February 28th by emailing it to ucla.acm.mpc@gmail.com. Make sure to include your source, what category you fall into (lower div, other ugrad, or graduate), and your contact information. Early submittals are eligible for extra prizes. You can also direct questions to that account. Good luck! Well, its a knapsack problem alright. Google turns up (TONS) on superincreasing and non-superincreasing knapsack problems, before I read any of them too closely, let me try to solve part of it myself. Creating data.txt with values. [rizwank@GEEKYMEDIA ~/acm]$cat data.txt 8,7,5,6,3,2,1,4,9 11 I did a knapsack problem for CS331 at Cal Poly Pomona, fetching that now. note superi means that in > sum of in-1 .. 1 a noteable superset 64 32 16 8 4 2 1 Branch and bound would try to add greatest weight first (actually doesn't it grab highest ratio first?) need to include alternate handling for superincreasing, as it ends up being binary calculation (Although this does work too) We need to quit once we've found a solution that works, rather than wait for the most optimal (that doesnt exist, btw) for smbolism just switch backpack for palette and item for crate/box