SRVR Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Tester: Kasra Mazaheri
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

We have N tasks, each consists of a number of processes that need to be executed every second. Let’s denote the number of processes for the i_{th} task by D_i.

Roger went to buy a server for his system. Unfortunately, there are Q different servers on sale (numbered 1 through Q), but Roger can only afford one. For each valid i, Roger knows that the i-th server’s performance is described by two integers C_i and P_i with the following meaning:

  • Let’s split a second into P_i equal time segments .
  • The server has C_i cores. During each time segment, each core may execute a process or do nothing.
  • During each second, each process must be executed exactly once ― by exactly one core during exactly one time segment.
  • If two processes belong to the same task, they may not be executed by different cores during the same time segment due to synchronization issues.
  • Processes that belong to the same task do not have to be executed by the same core or in any particular order. They also do not have to be executed during contiguous time segments.

Since tasks can be extreme sometimes, all the servers are equipped with a new technology named Exclusive Processing . Initially, we may choose one task which should run in exclusive processing mode (since it demands a lot of power). Then, instead of executing one process, each core may execute two processes belonging to this task during any time segment. Executing just one process belonging to this task during one time segment is also allowed. However, it is still not allowed for different cores to execute processes belonging to the same task during the same time segment.

Now Roger needs your help. For each server, he wants to know the number of subsets of the N tasks that can be served by this server. Since these numbers can be very large, compute them modulo 987,654,319.

DIFFICULTY:

Easy-Medium

CONSTRAINTS

  • 1≤N≤600
  • 1≤Q≤360,000
  • 1≤D_i≤600 for each valid i
  • 1≤C_i≤600 for each valid i

EXPLANATION:

Let’s assume we are solving the problem for a single server with parameters P,C.

If we ignore the Exclusive Processing feature for a bit, you can observe that we cannot pick any task which has more processes than P. (because we will be forced to run 2 processes during the same segment at least once).

Let’s assume we picked a subset S, there is another condition we must satisfy which is \displaystyle \sum_{x \in S} D_x \leq P*C which means that the total number of processes of all picked tasks must be less than or equal to the total number of processes our server can handle during 1 second.

Having the Exclusive processing feature would allow us to pick up one extra task which has up to 2*P processes.

First of all, let’s sort all tasks in increasing order of D.

Let’s maintain a traditional subset sum dp table.

dp[i][total] denotes the number of subsets that we can form using the first i servers such that their total number of processes (of tasks inside the subset) is exactly equal to total.

dp[i][total]=dp[i-1][total]+dp[i-1][total-D_i]

Let’s change our table a little bit such that dp[i][total] refers to the number of subsets which total processes less than or equal to total not only equal. This is also straightforward.

dp[i][total]= dp[i][total]+dp[i][total-1]

Now the last part would be figuring out the answer for a server with parameters P,C

It’s always optimal to use the exclusive processing feature on the task with most processes (if it has more than P then it must be used on it, and if every task has less processes than P then it doesn’t matter).

Also, let’s find the upper bound of P in the array D. Let’s say the upper bound has an index z.

Let’s loop over all jobs and fix our heaviest job, assume for a fixed job with index idx we have S processes, we need to add dp[min(idx,z)-1][P*C-\lceil \frac{S}{2} \rceil] to our answer. Of course S \leq 2*P. Notice here the minimization in the first index, because we assumed that the current fixed task is the heaviest one and on the other hand, none of the remaining jobs can have processes more than P.

As you can notice the answer for each server can be found in O(N).

Complexity: O(N*N*Max(D_i)) + O(Q*N) = O(N^3) + O(Q*N)

In the worst case, both are the same so to simplify we can assume it’s O(N^3)

Tester Solution 
   // In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 609, MXN = N * N, Mod = 987654319;
int n, q, D[N], dp[N][MXN];
inline void Add(int &a, int b)
{
    a += b;
    if (a >= Mod)
        a -= Mod;
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &D[i]);
    sort(D + 1, D + n + 1);
    dp[0][0] = 1;
    for (int i = 1, SM = D[1]; i <= n; i ++, SM += D[i])
        for (int j = 0; j <= SM; j ++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= D[i])
                Add(dp[i][j], dp[i - 1][j - D[i]]);
        }
    for (int i = 0; i <= n; i ++)
        for (int j = 1; j < MXN; j ++)
            Add(dp[i][j], dp[i][j - 1]);
    for (int i = 1; i <= q; i ++)
    {
        int c, p, tot = 1;
        scanf("%d%d", &c, &p);
        int up = upper_bound(D + 1, D + n + 1, p) - D - 1;
        for (int j = 1; j <= n && (p << 1) >= D[j]; j ++)
            Add(tot, dp[min(up, j - 1)][min(c * p - (D[j] + 1 >> 1), MXN - 1)]);
        printf("%d\n", tot);
    }
    return 0;
}