Home » 国际竞赛 » Details

USACO 2022 February Contest, Platinum Problem 2. Sleeping in Class

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午4:12

USACO 2022 February Contest, Platinum Problem 2. Sleeping in Class

Bessie the cow was excited to recently return to in-person learning! Unfortunately, her instructor, Farmer John, is a very boring lecturer, and so she ends up falling asleep in class often.

Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class. There are $N$ class periods ( $2 \leq N \leq 10^{5}$ ), and Elsie logs that Bessie fell asleep $a_{i}$ times ( $1 \leq a_{i} \leq 10^{18}$ ) in the $i$ -th class period. The total number of times Bessie fell asleep across all class periods is at most $10^{18}$ .

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures.

The only ways Elsie may modify the log are by combining two adjacent class periods or splitting a class period into two. For example, if $a = [1, 2, 3, 4, 5],$ then if Elsie combines the second and third class periods the log will become $[1, 5, 4, 5]$ . If Elsie then chooses to split the third class period into two, the log can become any of $[1, 5, 0, 4, 5]$ , $[1, 5, 1, 3, 5]$ , $[1, 5, 2, 2, 5]$ , $[1, 5, 3, 1, 5]$ , or $[1, 5, 4, 0, 5]$ .

Given $Q$ ( $1 \leq Q \leq 10^{5}$ ) candidates $q_{1}, \dots, q_{Q}$ for Bessie's least favorite number ( $1 \leq q_{i} \leq 10^{18}$ ), for each of them help Elsie compute the minimum number of modifications to the log that she needs to perform so that all the numbers in the log become the same.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of each test case contains $N$ , and the second contains $a_{1}, a_{2}, \dots, a_{N}$ . The third contains $Q$ , followed by $Q$ lines each containing an integer $q_{i}$ , a candidate for Bessie's least favorite number.

OUTPUT FORMAT (print output to the terminal / stdout):

For each $q_{i}$ , compute the minimum number of modifications required for Elsie to convert every entry of the log into $q_{i}$ , or $- 1$ if it is impossible.

SAMPLE INPUT:

6
1 2 3 1 1 4
7
1
2
3
4
5
6
12

SAMPLE OUTPUT:

Elsie needs at least four modifications to convert the log into all 3s.

   1 2 3 1 1 4
-> 3 3 1 1 4
-> 3 3 1 5
-> 3 3 6
-> 3 3 3 3

It is impossible for Elsie to convert the log into all 5s, which is why the correct output for that candidate is $- 1$ .

SCORING:

In test cases 2-4, $N, Q \leq 5000$
In test cases 5-7, all $a_{i}$ are at most $10^{9}$ .
Test cases 8-26 satisfy no additional constraints.

Problem credits: Jesse Choe and Benjamin Qi

USACO 2022 February Contest, Platinum Problem 2. Sleeping in Class 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Daniel Zhang, Benjamin Qi)

Partial Credit: $N, Q \leq 5000$

To solve this subtask, we need to be able to answer each query in $O (N)$ time. Define $S = a_{1} + a_{2} + \dots + a_{N}$ , and suppose that the candidate we are considering is $d$ .

If $d ∤ S$ , then the answer is $- 1$ .
Otherwise, define $p_{i} = \sum_{j = 1}^{i} a_{j}$ for $1 \leq i \leq N$ to be the $i$ -th prefix sum of the input sequence. Consider how the set of prefix sums changes with each operation. Splitting a class period inserts a number into the set of prefix sums, while merging two class periods removes a number from the set of prefix sums. The set of prefix sums is initially all $p_{i}$ , and at the end is all multiples of $d$ up to $S$ . Hence, the minimum number of operations is the size of the symmetric difference between the two sets. Letting $x_{d} = (# of i such that d | p_{i})$ be the number of prefix sums in common between the initial and final sequences, the size of the symmetric difference is $N + \frac{S}{d} - 2 x_{d}$ .

This immediately leads to an $O (N Q)$ solution.

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class SleepingInClassHarder {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        long[] times = new long[n];
        long sum = 0;
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        for (int j = 0; j < n; j++) {
            times[j] = Long.parseLong(tokenizer.nextToken());
            sum += times[j];
        }
        StringBuilder out = new StringBuilder();
        for (int q = Integer.parseInt(in.readLine()); q > 0; q--) {
            long targetNumber = Long.parseLong(in.readLine());
            if (sum % targetNumber == 0L) {
                long res = ((long) n) + (sum / targetNumber);
                long curr = 0;
                for (long time : times) {
                    curr += time;
                    if (curr % targetNumber == 0L) {
                        res -= 2L;
                    }
                }
                out.append(res);
            } else {
                out.append(-1);
            }
            out.append('\n');
        }
        System.out.print(out);
    }
}

Full Solution: We need a faster way to compute $x_{d}$ .

Define $q_{i} = gcd (p_{i}, S)$ . If $d | S$ , then $d | p_{i} \Leftrightarrow d | q_{i}$ , so we can ignore all the $p_{i}$ and instead count the number of $i$ such that $d | q_{i}$ . Each $q_{i}$ is a factor of $S$ . Knowing the number of times each factor occurs is enough to answer all queries, so we first count them.

Let $σ_{0} (S)$ denote the number of factors of $S$ . The maximum number of factors that can occur within the input constraints is achieved by the largest highly composite number not exceeding $10^{18}$ . This is

897612484786617600 = 28 \times 34 \times 52 \times 72 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 31 \times 37

which has $103680$ factors (see OEIS).

In the worst case, there are $O (σ_{0} (S))$ distinct nontrivial queries. If we can answer each query naively in $O (σ_{0} (S))$ , this part by itself will take $O (σ_{0} (S)^{2})$ , which is too slow.

A faster way is to observe that if we arrange the factors in a multidimensional array, with a dimension for each prime factor, answering the queries from the frequencies is just computing multidimensional prefix sums.

Using inclusion-exclusion, we can compute each prefix sum in $O (2^{ω (S)})$ , where $ω (S)$ counts the number of distinct prime factors of $S$ (not to be confused with the $ω$ from complexity theory), but this is still slow.

A better way is to iterate over the dimensions, and compute prefix sums along that direction. This is a generalization of what is commonly referred to as Sum Over Subsets (SOS) and runs in $O (ω (S) σ_{0} (S))$ .

To compute the dimensions of the array, it helps to know the prime factorization of $S$ . One way to do this is to use a factorization algorithm that is fast enough to factor numbers up to $10^{18}$ . Alternatively, one can use trial division up to $10^{6}$ to eliminate all but at most two prime factors, then compute $gcd$ s of the remaining factor with the prefix sums and the queries. It is possible that a semiprime is left unfactored, but treating it as prime will not affect the correctness of the queries in that case since no query could distinguish it from being prime.

#include <cstdio>
#include <vector>
#include <numeric>

int N;
long long prefix[100005];
int Q;
long long queries[100005];

std::vector<std::pair<long long,int> > primes;

int num_factors(){
  int cnt=1;
  for(int i=0;i<primes.size();i++){
    cnt*=primes[i].second+1;
  }
  return cnt;
}

int freq[103680];

int& get_freq(long long num){
  int code=0;
  for(int j=0;j<primes.size();j++){
    int cnt=0;
    while(num%primes[j].first==0){
      num/=primes[j].first;
      cnt++;
    }
    code=code*(primes[j].second+1)+std::min(cnt,primes[j].second);
  }
  return freq;
}

int main(){
  scanf("%d",&N);
  for(int i=1;i<=N;i++){
    scanf("%lld",&prefix[i]);
    prefix[i]+=prefix[i-1];
  }
  long long rest=prefix[N];
  for(int p=2;p<=1000000;p++){
    if(rest%p==0){
      int cnt=0;
      while(rest%p==0){
        rest/=p;
        cnt++;
      }
      primes.emplace_back(p,cnt);
    }
  }
  //now rest has at most two prime factors
  for(int i=1;i<N;i++){
    long long tmp=std::gcd(rest,prefix[i]);
    if(tmp!=1&&tmp!=rest){
      if(tmp>rest/tmp){
        tmp=rest/tmp;
      }
      if(tmp*tmp==rest){
        primes.emplace_back(tmp,2);
      }else{
        primes.emplace_back(tmp,1);
        primes.emplace_back(rest/tmp,1);
      }
      rest=1;
    }
  }
  scanf("%d",&Q);
  for(int i=0;i<Q;i++){
    scanf("%lld",&queries[i]);
    long long tmp=queries[i];
    if(rest%tmp==0&&tmp!=1&&tmp!=rest){
      if(tmp>rest/tmp){
        tmp=rest/tmp;
      }
      if(tmp*tmp==rest){
        primes.emplace_back(tmp,2);
      }else{
        primes.emplace_back(tmp,1);
        primes.emplace_back(rest/tmp,1);
      }
      rest=1;
    }
  }
  if(rest!=1){
    //assume it is prime; can't tell anyway
    primes.emplace_back(rest,1);
  }
  for(int i=1;i<=N;i++){
    get_freq(prefix[i])++;
  }
  int block=1;
  for(int i=primes.size()-1;i>=0;i--){
    for(int code=num_factors()-1;code>=0;code--){
      if(code/block%(primes[i].second+1)!=0){
        freq[code-block]+=freq;
      }
    }
    block*=primes[i].second+1;
  }
  for(int i=0;i<Q;i++){
    if(prefix[N]%queries[i]!=0){
      printf("-1\n");
    }else{
      long long ans=N+prefix[N]/queries[i];
      ans-=get_freq(queries[i])*2;
      printf("%lld\n",ans);
    }
  }
}

In the implementation above, each factor $f$ of $S$ gets encoded to a location $code (f)$ in the $freq$ array. This encoding is generalized to other numbers $g$ by mapping them to the location $code (gcd (S, g))$ .

The part that performs the multidimensional prefix sum is as follows:

int block=1;
for(int i=primes.size()-1;i>=0;i--){
  for(int code=num_factors()-1;code>=0;code--){
    if(code/block%(primes[i].second+1)!=0){
      freq[code-block]+=freq;
    }
  }
  block*=primes[i].second+1;
}

Initially,
freq[code(f)]
freq
stores the number of $q_{i}$ that equal $f$ (equivalently, the number of $p_{i}$ such that $gcd (p_{i}, S) = f$ ).
After processing some primes,
freq[code(f)]
freq
will store the number of $i$ such that $\frac{q_{i}}{f}$ only contains prime factors among the already processed primes.
After processing all primes,
freq[code(f)]=xf
freq
=xf
: the number of $q_{i}$ such that $q_{i}$ is a multiple of $f$ (equivalently, the number of $p_{i}$ that is a multiple of $f$ ).