out 12 team that received medals:
4 teams from China,
4 teams from Russia,
1 team from Croatia,
1 team from Japan,
1 team from Poland,
1 team from Slovakia.
I might be cool to let user select which "type" of random street he/she will stumble upon. For example "random landscapes", "random city", "random village", etc.
That's pretty cool. It's actually non-trivial problem.
Did you write some sort smart bruteforce? Or you had figured some DP approach?
There was a simplified version of it on IOI 2004 (http://olympiads.win.tue.nl/ioi/ioi2004/contest/day2/phidias...) which asked to cut the room by a series of horizontal and vertical cuts. At the end each of remainder blocks can either be fully covered by predefined set of fixed-dimension panels or thrown away. The problem asked to minimize what we throw away. It was solvable using DP due to the fact that cuts are always split the room into separate parts.
Hold on, so you did you bruteforce all-all possible solutions and then just picked the best one out of them?
How many products you had? Was it close to what I have?
In my case there are just too many possible solution. I waited for an hour on my current one and it didn't finish :)
What was your strategy with regards of how much each bag type you select? Try all possible from current_max downto 7,500?
Can somebody tell me if the following problem is solvable using knapsack (so far I've been only able to come up with bruteforce solution with some optimizations):
We have different product types and for each product know it's amount. Let's say we have 20 different product types. For each type we know how much we've got (i.e. 10k of product type 1, 15k of product type 2, etc.)
Now we want to put those products into different bags. Each bag must have 5 products.
A particular combination of products inside of the bag is considered a "bag type". If we choose a particular "bag type" we must to have at least 7,500 units of such bag type.
For each bag type we have a certain cost function.
Now the problem is to find bags types and corresponding amounts such that total cost is maximized.