# ARRFILL - Editorial

Setter: Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

Easy

# PREREQUISITES

Basic Number Theory

# PROBLEM

Given an array A of length N filled with 0, you can apply given M operations in any order so as to maximize the sum of integers in the array A after all operations are applied.

An operation is described by two integers (x_i, y_i). In one operation, choose a subset of indices S such that

• 1 \leq j \leq N
• j \bmod y_i \neq 0
• A_j = 0
Then update A_j = x_i for all j \in S

# QUICK EXPLANATION

• Apply operations in non-increasing order of x_i, so that if a position can be chosen, it should be chosen immediately.
• After each operation, the set of positions j such that A_j = 0 are multiples of a constant value.
• If multiples of C are the positions containing 0 and we apply operation (x_i, y_i), then after this operations, multiples of lcm(C, y_i) would be the positions containing 0

# EXPLANATION

Since we need to maximize the sum of operations, It would be optimal to apply operations at all positions where it is possible.

### Only two operations

Let’s assume M = 2 for now. The two operations are (x_1, y_1) and (x_2, y_2). A position p such that 1 \leq p \leq N shall fall into only one of the following cases

• p \bmod y_1 = 0 and p \bmod y_2 = 0: Neither operation can cover position p, So A_p = 0 after operations
• p \bmod y_1 = 0 and p \bmod y_2 \neq 0: Second operation can cover position p, So A_p = x_2 after operations
• p \bmod y_1 \neq 0 and p \bmod y_2 = 0: First operation can cover position p, So A_p = x_1 after operations
• p \bmod y_1 \neq 0 and p \bmod y_2 \neq 0: Both operations can cover position p, So, we shall apply operation with higher x first, leading to A_p = max(x_1, x_2) after operations

Assuming x_1 \geq x2, last two cases lead to A_p = x_1. So, we can merge the two cases, just checking if p \bmod y_1 \neq 0.

This way, assuming x_1 \geq x_2, we divide positions into three groups

• p \bmod y_1 \neq 0
• p \bmod y_1 = 0 and p \bmod y_2 \neq 0
• p \bmod y_1 = 0 and p \bmod y_2 = 0 which implies p \bmod lcm(y_1, y_2) = 0

### Original Problem

Now we have many operations, but we can generalize the whole thing.

Let’s consider the operations in non-increasing order of x. This way, we can see that if we can pick position p in some earlier operation, we must pick it in an earlier operation.

Specifically, for position p, if operation q is the first operation where position p can be picked, then we can see that p \bmod y_q \neq 0 and p \bmod y_r = 0 for all r \lt q. Second condition can be written as p \bmod \text{lcm}_{r \lt q}{ y_r } = 0.

If we want to write cases like M = 2 case, we can divide it into M+1 cases, after sorting operations by x

• p \bmod y_1 \neq 0 leads to A_p = x_1
• p \bmod y_1 = 0 and p \bmod y_2 \neq 0 leads to A_p = x_2
• p \bmod lcm(y_1, y_2) = 0 and p \bmod y_3 \neq 0 leads to A_p = x_3
• p \bmod \text{lcm}_{r \lt M}{y_r} = 0 and p \bmod y_M \neq 0 leads to A_p = x_M
• p \bmod \text{lcm}_{r \lt M}{y_r} = 0 leads to A_p = 0

Observation: After each operation, the set of empty positions shall be positions p such that p \bmod z_i = 0, if \displaystyle z_i = \text{lcm}_{j < i} (y_j)

Example
Consider N = 10 and operations (5,2), (6,3)
Initially [0,0,0,0,0,0,0,0,0,0]
After operation (6, 3), array becomes [6,6,0,6,6,0,6,6,0,6]. All empty positions are multiples of 3
After operation (5,2), array becomes [6,6,5,6,6,0,6,6,5,6]. All empty positions are multiples of 6 = lcm(3, 2) = 6

Hence, after each operation, we can represent all empty positions in A as multiples of a constant value.

### Computing the sum of array

Now we know the order of operations. We also know that before some operation (x, y), only the positions which are multiples of z are empty for some z. We want to figure out how many positions the current operation is applied to.

Before current operation, \displaystyle \left \lfloor \frac{N}{z} \right \rfloor positions are empty. After current operation, \displaystyle \left \lfloor \frac{N}{lcm(z, y)} \right \rfloor positions are empty. Hence, current operation is applied at \displaystyle \left \lfloor \frac{N}{z} \right \rfloor - \left \lfloor \frac{N}{lcm(z, y)} \right \rfloor positions, contributing sum \displaystyle \left( \left\lfloor \frac{N}{z} \right \rfloor - \left \lfloor \frac{N}{lcm(z, y)} \right \rfloor \right ) * x.

Hence, if we maintain LCM after each operation, we have solved the problem. To make sure lcm doesn’t overflow, we can see that as soon as z \gt N, all positions in the array are filled, so we can stop applying operations.

# TIME COMPLEXITY

The time complexity is O(M*log(M)) per test case.

# SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;

const int maxm = 1e5, maxtm = 1e6, maxx = 1e9, maxy = 1e9, maxn = 1e9;
vector<pii> v;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
int tm = 0;
int maxitr = 0;
ll n; int m;
int x, y;
while(t--){
v.clear();
cin >> n >> m;
tm += m;
for(int i = 0; i < m; i++){
cin >> x >> y;
v.pb({x, y});
}
sort(v.begin(), v.end(), greater<pii>());
int itr = 0;
ll d = 1, ans = 0, S = n;
for(pii p : v){
if(d <= n)d = (d * p.second) / __gcd(d, (ll)p.second);
ans += p.first * (S - n / d); S = n / d;
itr++;
if(S == 0)break;
}
maxitr = max(maxitr, itr);
cout << ans << endl;
}
assert(tm <= maxtm);
}

Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

uint32_t gcd(uint32_t a, uint32_t b)
{
return b ? gcd(b, a % b) : a;
}

uint64_t lcm(uint32_t a, uint32_t b)
{
return static_cast<uint64_t>(a) * b / gcd(a,b);
}

int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
ios::sync_with_stdio(false);
int T;
cin >> T;
forn(tc, T)
{
uint32_t N, M;
cin >> N >> M;
vector<pair<uint32_t, uint32_t>> V(M);
for (auto& vi : V)
{
cin >> vi.first >> vi.second;
}
sort(V.begin(), V.end());
reverse(V.begin(), V.end());
uint64_t res = 0;
uint64_t g = 1;
for(const auto & vi: V)
{
const auto x = vi.first;
const auto y = vi.second;
if (g <= N)
{
const auto prevG = g;
g = lcm(g, y);
res += x * (N / prevG - N / g);
}
}
cout << res << endl;
}
return 0;
}

Editorialist's Solution
import java.util.*;
import java.io.*;
class ARRFILL{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), M = ni();
int[][] op = new int[M][];
for(int i = 0; i< M; i++)op[i] = new int[]{ni(), ni()};
//Sorting operations by x
Arrays.sort(op, (int[] i1, int[] i2) -> Integer.compare(i2[0], i1[0]));
long lcm = 1;
long ans = 0;
for(int[] o:op){
long nlcm = lcm(lcm, o[1]);
ans += o[0]* (N/lcm - N/nlcm);
lcm = nlcm;
if(nlcm > N)break;
}
pn(ans);
}
long gcd(long a, long b){return b == 0?a:gcd(b, a%b);}
long lcm(long a, long b){return a * (b/gcd(a, b));}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new ARRFILL().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always.

1 Like

This is product or LCM?

i use Scala. idk why my code is TLE. someone helps me pls.

def solve(t: Int = 0): Unit = {
val a = new Array[(Int, Int)](m)
for (i <- 0 until m) {
}

var y = 1
var c = n
var rs = 0L

scala.util.Sorting.quickSort(a)((x: (Int, Int), y: (Int, Int)) => y._1 - x._1)

for (i <- 0 until m) {
y = LCM(a(i)._2, y)
val newc = n / y
rs += (c - newc) * a(i)._1
c = newc
if (newc == 0) {
writer.println(rs)
return
}
}

writer.println(rs)
}

@taran_1407 Can you please share the python solution of this question? I tried the following, but it timed out.

import os
import io
import math
import sys

def lcm(n: int, m: int) -> int:
return (n * m) // math.gcd(n, m)

for _ in range(int(input().decode())):
n, m = map(int, input().decode().split())
operations = [tuple(map(int, input().decode().split())) for i in range(m)]
operations.sort(key=lambda x: x[0], reverse=True)

max_sum = 0
N = n
lcm_ = 1

for i in range(m):
x, y = operations[i]
lcm_ = lcm(y, lcm_)
remaining = n // lcm_
max_sum += (N - remaining) * x
N = remaining

sys.stdout.write(str(max_sum) + '\n')


I used this approach I tried many test cases giving answer as expected. But on submitting it’s giving a run time error.

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner scan = new Scanner(System.in);
int test = scan.nextInt();
for(int t = 0; t < test; t++){
int n = scan.nextInt();
int arr[] = new int[n];
int m = scan.nextInt();
for(int i = 0; i < m; i++){
int x, y;
try{
x = scan.nextInt();
y = scan.nextInt();
}
catch(Exception e){
break;
}
for(int j = 0; j < n; j++){
if((j + 1) % y != 0){
if(arr[j] < x){
arr[j] = x;
}
}
}
}
int sum = 0;
for(int i = 0; i < n; i++){
sum += arr[i];
}
System.out.println(sum);
}
}
}


plz help

if i sort the M operations based on Value, then LCM is not required

Hello all,
for input
1
10 2
9 9
6 6
if you take the LCM it is not

Hello all,
for input
1
10 2
9 9
6 6
if you take the LCM it is not

#include
#include
#include <bits/stdc++.h>
#define long long int
using namespace std;

int main() {

ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
vector<pair<int,int>> p(m);
for(int i=0;i<m;i++)
{
cin>>p[i].first>>p[i].second;
}
sort(p.begin(),p.end(),greater<pair<int,int>>());
int pos=n,l=1,rem=0,ans=0;
for(auto (x,y) : p)
{
l=lcm(l,y);
rem=n/l;
ans+=(pos-rem)*x;
pos=rem;
if(pos==0)
break;
}
cout<<ans<<"\n";

}
return 0;
`

}

i changed everything in your code to LL and got AC

No, it’s 87 either way
[9, 9, 9, 9, 9, 9, 9, 9, 6, 9]