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 
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()&¬(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 : CodeChef: Practical coding for everyone
3 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+Bodd;
cout<<max(x,y,max(z,A))<<endl;
}
else if(even>0){
cout<<max(A,Aeven)<<endl;
}
else if(odd>0){
cout<<max(B,Bodd)<<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;
}
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
1 Like
Bro, can you tell me any corner case which I am missing?
https://www.codechef.com/viewsolution/52370165