f2lk6wf90d's blog

Find value of sum of a set of rows in a submatrix
By f2lk6wf90d, history, 6 years ago, In English

Hello everyone, I came up with this problem and I can't figure a solution out. I don't know if it has appeared before.
You are given a matrix of size n × m. Answer two types of queries:
- 1 k i1 i2 ... ik: Set the active set to {i1, i2, ..., ik}.
- 2 x: What is the value of ai1, x + ai2, x + ... + aik, x, where i1, i2, ..., ik are the current elements in the active set?
There are less than n queries of type 1, and less than m queries of type 2 between a pair of queries of type 1.
1 ≤ n, m ≤ 2000, however solutions with any reasonable complexity are welcome.
Also, if a query of type 1 appears for the i-th time, 1 ≤ k ≤ i, and all the indices in the query do not exceed i.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What are the constrains on total number of queries (q)? And I think there should be a constrain on . If there isn't, then this sum can go up to O(qn), and your program won't even be able to take input in time limit.

Then you can split the queries into two parts, call this light query, and call this large query. And you can see that you can't have more than large queries.

You can solve light queries by brute force, and take special measures (some pre-calculation) to solve heavy queries. It will lead you to a solution with complexity something like overall.

You can solve this problem — 348C - Subset Sums, similar problem with same idea. Here you have update query too.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The constraint on can be easily derived from the problem statement. Yes, the solution for that problem can be used to solve this one too, however all queries in this problem are obviously light, so the complexity (assuming n = m) is O(n3).

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your problem is essentially matrix multiplication.

Let A be the m × n matrix with (A)i, j = aj, i. For an update let u be a column vector of length n where . The answer to a query x after this update is (A·u)x. If we know the updates in advance, we can let U = (u1 u2 ... un) and compute A·U to precompute all the answers. This can be done in (for m = n).

Since the input does not restrict A and U other than U being boolean and we can always query all values of x, a solution to your problem can be used to compute the boolean matrix product A·U, so your problem has a lower bound of Ω(nω).

→ Reply