August Long Challenge Array Filling Solution

Contents

1 Array Filling Solution
- 1.1 Solution
2 Codechef Long Challenges
- 2.1 August Long Challenge 2021 Solutions

Array Filling Solution

You are given an array AA of size NN. Initially, the array is filled with 00-s.

There are MM types of operations that you can perform on array AA. The ithith operation can be described by two integers (xi,yi)(xi,yi). In this operation, you choose a set of indices SS such that

Also See: August Long Challenge 2021 Solutions

1≤j≤N1≤j≤N,
(jmodyi)≠0(jmodyi)≠0,
Aj=0Aj=0,

, then you set Aj=xiAj=xi for all j∈Sj∈S.

You can perform the operations in any order, but one type of operation can’t be done more than once. What is the maximum sum of integers of the array AA you obtain if you perform the MM operations optimally?

For example, consider the array A=[0,0,0,0]A=[0,0,0,0].

Suppose x=3,y=2x=3,y=2. Here you can choose indices 11 and 33 and set A1=A3=3A1=A3=3. So the array A becomes [3,0,3,0][3,0,3,0]. In this operation you can’t choose the indices 22 and 44 because (2mod2)=0(2mod2)=0, (4mod2)=0(4mod2)=0.
Suppose x=5,y=3x=5,y=3 and you set A2=5A2=5. So the array AA becomes [3,5,3,0][3,5,3,0]. Here you can’t choose index 11 because A1>0A1>0 and index 33 because (3mod3)=0(3mod3)=0 and A3>0A3>0. However, you could also set A4=5A4=5.
Suppose x=4,y=4x=4,y=4. Now you can’t choose any index because Aj>0Aj>0 for all 1≤j≤31≤j≤3 and (4mod4)=0(4mod4)=0. So the array remains same.

Note: Since input-output is large, prefer using fast input-output methods.

Input Format

The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
Each testcase contains M+1M+1 lines of input.
The first line of each test case contains two space-separated integers N,MN,M.
MM lines follow. For each valid ii, the ithith of these lines contains two space-separated integers xi,yixi,yi – parameters of the ithith operation.

Output Format

For each test case, output in a single line the maximum sum of integers of the array AA after MM operations.

Constraints

1≤T≤126001≤T≤12600
1≤N≤1091≤N≤109
1≤M≤1051≤M≤105
1≤xi≤1091≤xi≤109
2≤yi≤1092≤yi≤109
The sum of MM over all test cases does not exceed 106106.

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1

Sample Output 1

25
41
5

Explanation

Test case 11: Optimal filling is [5,0,5,0,5,0,5,0,5,0][5,0,5,0,5,0,5,0,5,0].

Test case 22: Optimal filling is [6,6,5,6,6,0,6,6][6,6,5,6,6,0,6,6].

Test case 33: Optimal filling is [2,1,2][2,1,2].

Solution

Program C++: Array Filling Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  
  int T;
  cin >> T;
  while(T--) {
    ll n, m;
    cin>>n>>m;
    vector<pair<int,int>>tractor;
    for (int i=0; i < m; i++)
    {
      ll x, y;
      cin>>x>>y;
      tractor.push_back({x,y});
    }
    sort(tractor.begin(), tractor.end(), greater<pair<int,int>>());
    
    ll lcm=1;
    ll tesb=n;
    ll res=0;
    
    for (int i=0; i<m && tesb>0; i++){
        ll a= tractor[i].first,b=tractor[i].second;
        lcm = lcm*b/__gcd(lcm,b);
        res += (tesb-n/lcm)*a;
        tesb= n/lcm;
    }
    cout <<res<<endl;
  }
  return 0;
}

Program Python: Array Filling Solution

from math import gcd
for T in range(int(input())):
    n,m=map(int,input().split())
    query=[]
    for i in range(m):
        query.append(list(map(int,input().split())))
    query.sort(reverse=True)
    ans=0
    pp=1
    z=n
    for x,y in query:
        if z==0:
            break
        pp=pp*y//gcd(pp,y)
        number_of_x=z-n//pp
        ans+=number_of_x*x
        z-=number_of_x
    print(ans)

Array Filling Solution

Solution

Codechef Long Challenges

August Long Challenge 2021 Solutions

Leave a Comment Cancel reply