Lowes Codeathon 2021 Round 2

general
1

Hey,to everyone who gave the round 2 of Lowes Codeathon. Could anyone give any idea (or hint) for the first question (the subset one).
Thanks in advance : )

1 Like
2

The main observation was the Ai<=30. If you look at the possible subset that only have unique prime factors in their product then there won’t be that many as there are only 10 primes upto 30 and 8 more no.s which are just product of some primes with no primes coming more than once . So in my solution I just brute forces all the subset with pre computation of 2^18(the length of the array A in compute function will be 18) . For every test case I then just calculated the count for each subset which can be done by using a frequency map.
Code:

#include "bits/stdc++.h"
#define ll long long
using namespace std;
const int mod = 1e9+7;
vector<vector<int>>a;
void compute(){
    vector<pair<int,vector<int>>>A;
    for(int i = 2;i<31;i++){
        int v = i,p=0;
        vector<int>b;
        while(v%2==0){
            v/=2,p++;
        }
        if(p>1)continue;
        if(p)b.push_back(2);
        bool flag = true;
        for(int j = 3;j<=i;j++){
            if(v%j==0){
                p = 0;
                while(v%j==0){
                    v/=j,p++;
                }
                if(p>1){
                    flag = false;
                    break;
                }
                b.push_back(j);
            }
        }
        if(flag)A.push_back({i,b});
    }
    ll l = A.size(),m = 1LL<<l;
    for(int i=1;i<m;i++){
        int j = i,k=0;
        set<int>s;
        bool flag = true;
        vector<int>b;
        while(j){
            if(j&1){
                for(int prime:A[k].second){
                    if(s.count(prime)){
                        flag = false;
                        break;
                    }
                    s.insert(prime);
                }
                b.push_back(A[k].first);
            }
            j>>=1,k++;
        }
        if(flag)a.push_back(b);
    }
}
long long solve(int n,vector<int>&A){
    map<int,int>d;
    for(int v:A)d[v]++;
    ll ans = 0;
    for(auto arr:a){
        ll val = 1;
        for(int v:arr){
            val = (val*d[v])%mod;
        }
        ans = (ans + val)%mod;
    }
    return ans;
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    compute();
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int>a(n);
        for(int i = 0;i<n;i++)cin>>a[i];
        cout<<solve(n,a)<<"\n";
    }
    return 0;
}
2 Likes
3

Man do i feel dumb ;_;
Anyway thanks : ) its clear now.

4

Hi , In your while(j) loop before b.push_back(A[k].first); can we add the condition if(flag==false) break; ?
Thanks in advance.

5

Did you guys solved the second question of “Road Construction”? If yes! please share your approach ;_;

6

Yes u can

7

This is the only solution idea that I found.

2 Likes
8

Can anyone share the round 2 questions of Lowe’s Codeathon.
Thanks in advance.