COWA19C-Editorial

PROBLEM LINK:

Practice
Contest

Author: Sai Teja
Tester: Sai Teja
Editorialist: Sai Teja

DIFFICULTY:

EASY

PREREQUISITES:

Sieve of Eratosthenes

PROBLEM:

Given a number N,we need to compute the sum of ,product of elements in a subset,of all subsets formed from the factors of N.

EXPLANATION:

We can compute the factors of a number in
O(sqrt(N)).Let the value to be computed be S(S=0 initially).Let us define S as the solution formed from the factors read so far.If we read a new factor for the number,
then the solution would be (S=S+f.S+f,f is the new factor).
Reason for the three terms:
Part 1(S) and Part2(f.S):
This new factor can be multiplied with all the subsets formed inititally forming (f.S) and the initial subsets must also remain forming (S).
Part 3(f):
So far we have covered all the subsets having the element f except one.The singleton set having f.So we add (f).
Example:
N=4
S=0,f=1
S=(0+0.1+1)=1

S=1,f=2
S=(1+1.2+2)=(1+2+1.2)

S=(1+2+1.2),f=4
S=((1+2+1.2)+(1+2+1.2).4+4)=(1+2+4+1.2+1.4+2.4+1.2.4)=29

We cannot find the factors for every test case with O(sqrt(N)) as it would cross the time limit.So we use the concept of Sieve to precompute the solutions.The time complexity of precomputations would be O(NlogN).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
int main()
{
    ll ans[100001];
    memset(ans,0,sizeof(ans));
    for(ll i=1;i<=100000;i++)
    {
      for(ll j=1;i*j<=100000;j++)
      ans[i*j]=(ans[i*j]*(1+i)+i)%mod;
    }
    ll t,n;
    cin>>t;
    while(t--)
    {
      cin>>n;
      cout<<ans[n]<<endl;
    }
    return 0;
}
1 Like

https://www.codechef.com/viewsolution/29025691 0.03 secs !?

I made a mistake while testing the test cases.My intention was to make people use sieve.This kind of thing won’t happen the next time.

@sai_teja02 Can we solve this problem using meet in the middle ? I tried but i am getting time limit exceeded

If you want to find the sum of all the subsets, you just want to find the sum, sum of two at a time, sum of three at a time and so on!

That’s just the sum of the coefficients of the polynomial (x+a)(x+b)(x+c)… minus 1 (None at a time: leading coefficient).

This can be calculated by substituting x = 1.
Thus for each factor multiply (factor+1) to the previous answer.
We finally subtract 1 from the answer.

Time Complexity goes O(Tsqrt(N)). And I agree making Sieve is a better choice for larger constraints.

My Code: https://www.codechef.com/viewsolution/29026791

will u please tell what is the logic of last ques? World War Preparation (COWA19E) .

can you give any mathematical proof for your equation
S=S+S.f+f

where f is new factor

1 Like

Please read the entire explanation.

can you please explain again the term
S.f in the equation

Its S multiplied by f.I used dot instead of *.

Can we have editorial for COWA19B ?

COWA19B (Pongal Bunk)

concept related: prefix array sum

Approach:-

Maintain two arrays (array1,array2).
-> first array (array1) to know the number of queries having the specific index in their range of L,R.
for each query apply, 1)array1[L]=array1[L]+1
2) array1[R+1]=array1[R+1]-1

->second array (array2) to know the final value of element in the specific index of array
for each query to apply, 1) array2[R+1]=array2[L]-(R-L+1)

After Performing All the queries operations,

->Run an iteration for prefix array sum for array1 i.e , array1[i]=array[i]+array1[i-1] where 1<=i<=N

->Run other iteration for array2 similar to prefix sum doing following operations array2[i]=array2[i] + array2[i-1] + array1[i] where 1<=i<=N

Now, array2 contains the final values of elements present in array

Time-complexity: O(n+q+m)

reference-code for the problem is given below
________________
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;

int main()
{
ll ans[1000002],ans1[1000002];
memset(ans1,0,sizeof(ans1));
memset(ans,0,sizeof(ans));
ll n,q,l,r;
cin>>n>>q;
while(q–)
{
cin>>l>>r;
ans[l]+=1;ans[r+1]-=1;
ans1[r+1]-=(r-l+1);
}
for(int i=1;i<=n;i++)
ans[i]+=ans[i-1];
for(int i=1;i<=n;i++)
ans1[i]+=ans1[i-1]+ans[i];
cin>>q;
while(q–)
{
cin>>l;
cout<<ans1[l]<<endl;
}
}
_______________
some-useful-links:-

https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/
https://www.geeksforgeeks.org/constant-time-range-add-operation-array/