FoolForCS's blog

By FoolForCS, history, 23 months ago, , Problem Statement:

There are K containers each with a capacity vector defined in three dimensions as (X[i], Y[i], Z[i]), 1 <= i <= 15, i.e., 1 <= K <= 15.
When an object of capacity (a, b, c) is put into container of capacity (A, B, C), the containers remaining capacity becomes (A — a, B — b, C — c).
There are N objects of varying capcities to be put into containers. Determine if the all objects can be fit into the containers or not. If they can fit, also determine which object must be put in which container.
(1 <= N <= 150). The capacity ranges fit an integer.
An exact solution would be amazing, but a good heuristic that might be able to solve this problem reasonably well is much appreciated. Any ideas? dp?,
By FoolForCS, history, 3 years ago, , You are given an array of size N.
Update operation : < X, Y, L, R > : Add value Y to every X th element in [ L , R ].
Query operation : < X > : Return the value at position X .

Sample: Given array [1, 2, 3, 4, 5, 6]
1. update 2 1 2 5
The array will be transormed to [1, 2, (3 + 1), 4, (5 + 1), 6]
Any thoughts on the best time complexity we can achieve for the operations (online)? 