DIVEO - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Soumyadeep Pal
Tester: Samarth Gupta
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

SIMPLE

PREREQUISITES:

Prime factorization

PROBLEM:

Given an integer N \gt 1, the following operations is performed until N becomes 1:

  • Choose an integer x \gt 1 that is divisible by N and divide N by x. If x is even, we get A points, else we get B points.

We need to find the maximum number of points achievable.

EXPLANATION:

Let us first do the prime factorization of N. Let the total sum of even powers be even and the total sum of odd powers be odd.

For example, if N = 180 then N = 2^23^25^1. Therefore, even = 2 and odd = 2+1 =3.

Now the problem can be solved in various cases depending on A and B:

Case 1: \hspace{1 mm} A \geq 0 and B \geq 0

  • In this case, since both A and B are non-negative, we want to divide N as many times as possible by both even and odd primes.

  • Therefore, in this case, the answer will be even \cdot A +odd\cdot B.

Case 2: \hspace{1 mm} A \leq 0 and B \leq 0

  • In this case, since both A and B are not positive, we don’t want to divide N many times as this could reduce the cost. We want to get it done in one go i.e, divide N by N itself.

  • Therefore, in this case, the answer will be A if N is even or else it will be B .

Case 3: \hspace{1 mm} A \geq 0 and B \leq 0

  • In this case, we wan’t to divide N by 2 as many times as possible. We also wan’t to avoid dividing N by odd numbers.

  • Suppose y is the maximum odd number divisible by N. If N is even, the first step we could do is divide N by 2 \cdot y and then keep on dividing N by 2. Or else y = N and we need to divide N by N itself.

  • Therefore, in this case, the answer will be even \cdot A if N is even or else it will be B.

Case 4: \hspace{1 mm} A \leq 0 and B \geq 0

  • In this case, we want to divide N by odd primes as many times as possible. We also want to avoid dividing N by even numbers.

  • Suppose N is odd. Then we can divide N as many times as possible by odd primes. If N is even, we want to remove the even part in one operation itself. Then we can continue removing odd primes one by one.

  • Therefore, in this case, the answer will be odd\cdot B if N is odd or else it will be odd \cdot B + A.

TIME COMPLEXITY:

O(\sqrt N) for each testcase for doing the prime factorization of N.

SOLUTION:

Editorialist's solution

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

int main()
{
     int tests;
     cin >> tests;
     while (tests--)
     {
          int n, a, b;
          cin >> n >> a >> b;

          int even = 0, odd = 0;
          while (n % 2 == 0)
          {
               n /= 2;
               even++;
          }

          for (int i = 3; i * i <= n; i++)
          {
               if (n % i == 0)
               {
                    while (n % i == 0)
                    {
                         n /= i;
                         odd++;
                    }
               }
          }

          if (n != 1)
               odd++;

          int ans = 0;

          if (a >= 0 && b >= 0)
          {
               ans = even * a + odd * b;
          }
          else if (a <= 0 && b <= 0)
          {
               if (even)
                    ans = a;
               else
                    ans = b;
          }
          else if (a >= 0 && b <= 0)
          {
               if (even)
                    ans = even * a;
               else
                    ans = b;
          }
          else if (a <= 0 && b >= 0)
          {
               if (even)
                    ans = a + odd * b;
               else
                    ans = odd * b;
          }

          cout << ans << endl;
     }
}

Setter's solution

#include<bits/stdc++.h>
using namespace std;
template <class T> ostream &operator << (ostream &os, const vector<T> &p) { os << "["; for (auto&it : p) os << it << " "; return os << "]";}
template <class S, class T> ostream &operator << (ostream &os, const pair<S, T> &p) { return os << "(" << p.first << "," << p.second << ")";}
#ifndef ONLINE_JUDGE
#define deb(...) dbs(#__VA_ARGS__,__VA_ARGS__)
template <class T> void dbs(string str, T t) { cerr << str << ":" << t << "\n";}
template<class T, class...S> void dbs(string str, T t, S... s) { int idx = str.find(','); cerr << str.substr(0, idx) << ":" << t << ","; dbs(str.substr(idx + 1), s...);}
#else
#define deb(...){}
#endif

long long readInt(long long l, long long r, char endd) {
  long long x = 0;
  int cnt = 0;
  int fi = -1;
  bool is_neg = false;
  while (true) {
    char g = getchar();
    if (g == '-') {
      assert(fi == -1);
      is_neg = true;
      continue;
    }
    if ('0' <= g && g <= '9') {
      x *= 10;
      x += g - '0';
      if (cnt == 0) {
        fi = g - '0';
      }
      cnt++;
      assert(fi != 0 || cnt == 1);
      assert(fi != 0 || is_neg == false);

      assert(!(cnt > 19 || ( cnt == 19 && fi > 1) ));
    } else if (g == endd) {
      if (is_neg) {
        x = -x;
      }
      deb(l, r, x);
      assert(l <= x && x <= r);
      return x;
    } else {
      assert(false);
    }
  }
}
string readString(int l, int r, char endd) {
  string ret = "";
  int cnt = 0;
  while (true) {
    char g = getchar();
    assert(g != -1);
    if (g == endd) {
      break;
    }
    cnt++;
    ret += g;
  }
  assert(l <= cnt && cnt <= r);
  return ret;
}
long long readIntSp(long long l, long long r) {
  return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
  return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
  return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
  return readString(l, r, ' ');
}


#define int long long
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define pr(x) {cout << x << '\n'; return;}
#define nl cout<< '\n'
#define rep(i,n) for(int i = 0; i < n; i++)
#define re(i,n) for(int i = 1; i <= n; i++)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
template<class T> inline T Bit(T x, int i) { return (x >> i) & 1;}
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; }
// const int N = 1e5 + 3; // check the limits



void solve(int tc) {
  int n, a, b;
  n = readIntSp(2, 1e9);
  a = readIntSp(-1e3, 1e3);
  b = readIntLn(-1e3, 1e3);
  int even = 0, odd = 0;
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      n /= i;
      if (i % 2) odd++;
      else even++;
    }
  }
  if (n > 1 && n % 2) {
    odd++;
  }
  if (n > 1 && n % 2 == 0) {
    even++;
  }
  int ans = 0;
  if (a >= 0) ans += even * a;
  else if (even > 0) ans += a;

  if (b >= 0) ans += odd * b;
  else if (even == 0 && odd > 0) ans += b;
  cout << ans << '\n';
}

signed main() {
  ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int t = readIntLn(1, 500);
  for (int i = 1; i <= t; i++) solve(i);
  assert(getchar() == -1);
  return 0;
}

Tester's solution
t = int(input())
for _ in range(t):
    n, a, b = map(int, input().split())
    i = 2
    even_sum, odd_sum = 0, 0
    while(i * i <= n):
        if(n%i == 0):
            cnt = 0
            while(n%i == 0):
                cnt += 1
                n /= i
            if(i%2 == 0):
                even_sum += cnt
            else:
                odd_sum += cnt
        i += 1
    if(n > 1):
        if(n%2 == 0):
            even_sum += 1
        else:
            odd_sum += 1
    ans = 0
    if(a >= 0):
        ans += (a*even_sum)
    elif(even_sum > 0):
        ans += a
    if(b >= 0):
        ans += (b*odd_sum)
    elif(even_sum == 0 and odd_sum > 0):
        ans += b
    print(ans)

        

Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

4 Likes

Can anyone tell me why my solution is giving WA?
https://www.codechef.com/viewsolution/52378833

Your code fails for this case:

1
10 1 -1
2 Likes

my code gives 0 as the answer for the case you mentioned. According to you what should be the answer?

The answer should be 1, as you can divide N by itself

1 Like

Your code overlooks the fact that multiplying an odd and even number gives you an even number. Therefore, you can skip the division by an odd number, hence there’s no need to add B

1 Like

oh yeah thanx bro :slight_smile:

1 Like

I solved this problem with dp.
Firstly i computed all the factors of n and saved them into an array.
And then checked every possible answer.
Here is the code :

#include<bits/stdc++.h>
#define ll int64_t
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T> using pbds = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update >; // find_by_order, order_of_key
ll MOD=1e9+7 ;
const int MAXN=1e7;
ll mod(ll a){return ((a%MOD)+MOD)%MOD;}
ll add(ll x,ll y){return mod(mod(x)+mod(y));}
ll mul(ll x,ll y){return mod(mod(x)*mod(y));}
ll binpow(ll a, ll b) {a %= MOD;ll res = 1;while (b > 0) {
if (b & 1)res = res * a % MOD;a = a * a % MOD;b >>= 1;}return res;}
ll fact(ll n){ll num=1;for(ll i=1;i<=n;i++){num=mul(num,i);mod(num);}return num;}
ll ncr(ll n,ll r){ll fn=fact(n);ll rn=mod(fact(r)*fact(n-r));return mod(fn*binpow(rn,MOD-2));}
ll inv(ll a){return binpow(a,MOD-2);}
/*------------------------------------------------------------------------------------------------*/
map<ll,ll>dp;
ll helper(vector<ll>&div,ll n,ll a,ll b){
    if(n==1ll)
        return 0ll;
    if(not dp.empty()&&not(dp.find(n)==dp.end())){
        return dp[n];
    }
    ll cnt=INT_MIN;
    for(int i=0;i<div.size();i++){
        if(n%div[i]==0ll){
            cnt=max(cnt,helper(div,n/div[i],a,b)+(div[i]%2ll?b:a));
        }
    }
    return dp[n]=cnt;
}
void solve() {
    dp.clear();
    ll n,a,b;
    cin>>n>>a>>b;
    vector<ll>div;
    ll s=sqrt(n);
    div.push_back(n);
    for(ll i=2ll;i<=s;i++){
        if(n%i==0ll){
            div.push_back(i);
            if(not(n/i==i)){
                div.push_back(n/i);
            }
        }
    }
    //sort(div.begin(),div.end()); // In my submissions i also sorted the array but it is not needed.
    cout<<helper(div,n,a,b)<<endl;
}
int32_t main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);//read
    freopen("output.txt","w",stdout);//write
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        //cout<<"test : "<<t<<endl;
        solve();
    }
    return 0;
}

here is the link : Solution: 52354337 | CodeChef

2 Likes

we know 10^8 operations takes almost 1sec
but here
(10^4.5) X ( 2 X 10^3) = 63245553 ~= 6*10^7 operations
why time limit is very tight (0.5 sec)

Please help with my code
if(even>0 and odd>0){
int x=Aeven+Bodd;
int y=Aeven+B;
int z=A+B
odd;
cout<<max(x,y,max(z,A))<<endl;
}
else if(even>0){
cout<<max(A,Aeven)<<endl;
}
else if(odd>0){
cout<<max(B,B
odd)<<endl;
}
else
cout<<0<<endl;

for a test-case
1
12 2 -1
the editorialist soln is coming 2*2=4 but after dividing 12/2=6 6/2=3 3 should be divided by 3 too
which should give 4+(-1)=3
please explain this

2 Likes

First divide by 2 and then divide by 6 directly to get 1. Since you divided by an even number each time, your total score will 2+2 = 4. Notice that when we have odd factors, we have can skip dividing by them, by simply stopping at the moment in time when only a single 2 is left in the prime factorization.

1 Like
Spoiler
12 = 2*6 which gives (2+2 = 4)

If Codechef provide the hacking like Codeforces, I will hack everyone’s code (at least python3).
T = 2000
N <= 10^9
Overall = 2000 x 3 x 10000 = 6 x 10^7 (Not possible in 2.5 second)

1 Like

you can type your testcase i’ll more than happy to run it over my solution.
You can find my solution in the upper comments.

Can please anyone tell me where I am making the mistake

My concept is first to find all the prime factors of n and their count and then if the factor is even then multiply the count by a otherwise b and add it to ans.

https://www.codechef.com/viewsolution/52392432

map stores all the factors as key and their count as value

or please tell me on which test case this code fails

I dont know why my solution is giving WA -
I have considered every scenario (might not be exactly same as editorial) -

Edit - This code works fine now:

#include<bits/stdc++.h>

using namespace std;

void Optimized(long long n , long long &even , long long &odd)
{
    for(long long i=2 ; i*i<=n ;i++)
    {
        if(n%i == 0)
        {
            long long cnt =0;
            while(n %i == 0)
            {
                cnt++;
                n= n/i;
            }
            if(i%2 == 0)
                even += cnt;
            else
                odd +=cnt;
        }
    }
    if(n >1)
    {
        if(n%2 == 0)
            even++;
        else
            odd++;
    }
}


int main()
{
    int t;
    cin >> t;
    while(t--){
        long long n , a, b;
        cin >> n >> a >> b;
        long long even = 0,odd = 0;
        Optimized(n,even,odd);
        long long ans = INT_MIN;
        if(a>=0 && b>=0)
        {
            ans = (even *a) + (odd*b);
        }
        else if(a>=0 && b<0)
        {
            if(n%2 == 0)   
            {
                ans = even*a;
            }
            else{
                ans = b;
            }

        }
        else if(a<0 && b>=0)
        {
            if(n%2 == 0)
            {
                ans = max(b*odd + a , a);
            }
            else{ ///it does not contain any even part
                ans = b*odd;
            }
        }
        else if(a<=0 && b<=0){
            if(n%2 == 0)
                ans = a;
            else
                ans = b;
        }
        cout << ans << endl;
    }
    return 0;
}

Can someone help me with this WA pls.
https://www.codechef.com/viewsolution/52391615

I have handled all the cases. Yet my code is giving WA.
Can anyone check where I am wrong.
Here is my solution:
https://www.codechef.com/viewsolution/52342895

Why I am getting WA for my code ???
(Solution: 52392062 | CodeChef)