lol
1 Like
is there any approach for the alternate solution I tried with one greedy approach but I got a WA 
I couldn’t find any except brute force recursion with memoization which is essentially same as solution 1.
I have used the same approch as given in alternate solution but I get WA .
Can anyone please help me where is mistake
My implementation
https://www.codechef.com/viewsolution/43233050
1 Like
What about this. I wonder why it’s not working.
The logic is same as above:
k is in the form of p_1 *p_2 or p^3
So I got all the powers of primes. Now I can always use p^3 so did %3 on each a_i
Now some 2’s and 1’s will be present. Any pair of 2’s or pair of 1’s can be reduced to zeroes. We’ll be left with at most one 2 and at most one 1 and casework.
Edit: as @watergun pointed out this won’t work
What if we are left with
2 2 2
All of these can be paired to get 1 as the result, right?
1 Like
Yes there are so many cases.
Now that you have correct solution which can work upto 10^6, you can check when answer is 3 or 2 and try to find some observation or pattern. This might lead to a better solution.
So the problem somewhat reduces to:
Given an array find the min number you can get if you can subtract 3 from an element or subtract 1 from 2 different elements! Is there a dp or any other approach to solve this as i can’t come up with anything?
I tried greedy approach but it didn’t work but I don’t know why it is not working (as I manually couldn’t find a test case failing this code). can anyone help me please?
/*
ॐ
JAI SHREE RAM
Hare Krishna Hare Krishna Krishna Krishna Hare Hare
Hare Rama Hare Rama Rama Rama Hare Hare
ॐ
*/
//Written by Bhuwanesh Nainwal
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
pbds;
#define fast ios_base::sync_with_stdio(false) , cin.tie(NULL) , cout.tie(NULL)
#define int long long int
#define vci vector<int>
#define vcvci vector<vector<int>>
#define vcpi vector<pair<int,int>>
#define vcs vector<string>
#define pb push_back
#define mpii map<int , int>
#define mpsi map<string , int>
#define mpci map<char , int>
#define umpii unordered_map<int , int>
#define umpsi unordered_map<string , int>
#define umpci unordered_map<char , int>
#define all(x) auto it = x.begin() ; it != x.end() ; it++
#define vcc vector<char>
#define vcs vector<string>
#define sti set<int>
#define stc set<char>
#define sts set<string>
#define pqmx priority_queue<int>
#define pqmn priority_queue<int , vi , greater<int>>
#define null NULL
#define ff first
#define ss second
#define stb(x) __builtin_popcount(x)
#define lzr(x) __builtin_clz(x)
#define tzr(x) __builtin_ctz(x)
#define prc(x , y) fixed << setprecision(y) << x
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
using namespace std;
const int mod = 1e9 + 7;
const int INF = 1e9;
const int LINF = 1e18;
const int N = 1e6 + 10;
const int chkprc = 1e-9; // Check for precision error in double
vector<bool> is_prime(N + 1, 0);
vector<int> primes;
void sieve()
{
is_prime[2] = 1;
primes.pb(2);
for(int i = 3 ; i <= N ; i += 2)
is_prime[i] = 1;
for(int i = 3 ; i <= N ; i += 2)
{
if(is_prime[i])
{
primes.pb(i);
for(int j = i * i ; j <= N ; j += i)
is_prime[j] = 0;
}
}
}
int prime_factorization(int n)
{
int total = 0;
int distinct = 0;
for(int i = 0 ; i < primes.size() ; i++)
{
if(primes[i] * primes[i] > n)
break;
if(n % primes[i] == 0)
{
int cnt = 0;
while(n % primes[i] == 0)
{
n = n / primes[i];
cnt++;
}
if(cnt % 3 != 0)
{
total += (cnt % 3);
distinct++;
}
}
}
if(n > 1)
{
total ++;
distinct++;
}
if(distinct == 1 && total == 2)
return 3;
if(total % 2 == 0)
return 1;
return 2;
}
void solve()
{
int n;
cin >> n;
cout << prime_factorization(n) << "\n";
}
void local()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
int32_t main()
{
fast;
sieve();
// local();
int T = 1;
cin>>T;
while(T--)
{
solve();
}
return 0;
}i don’t get this . anyone please explain it
A_n: Answer for n
D_n: Number of divisors of N
A_n = min(D_n, A_{n/k}) for all k being factors of N and having 4 divisors.
1 Like
Couple of facts about alternate solution
- With N upto 10^9, there’d be atmost 8 elements. The maximum value in A is also not so large.
- if max(A)*2 \leq sum(A), then we can reduce A to all zeros, or all zeros and one 1 using only first operation.
- In the end, there would be only one non-zero element, which would either be 0, 1 or 2.
- Even backtracking can give good results, considering very few elements.
I believe I have a solution, but since I haven’t tested it on tests nor having proven it, I cannot be sure. Nor do I want to spoil the fun 
2 Likes
Hi,
I could come up with this solution for the alternate approach to reduce the powers.
a) Reduced all the powers taking modulo 3 and kept track of the reductions.
b) Now the power array has only 0,1,2. We are only interested in the reduction of 1 and 2s and thats obvious.
The reduction was based on below observations.
- Even number of 1’s can be reduced to 0.
- If the powers array has both 1’s and 2’s, the 2’s can be reduced and the same number of ones remain because, if we combine 1 and 2, 1 vanishes and 2 converts to 1. So, if we have even 1’s, irrespective of number of 2’s can be reduced to 0.
- If we have only 2’s more than 1, can be reduced to 0. If there is only one single 2, it cannot be reduced.
- So we only investigate the cases for reduction (using the modulo 3 reductions tracked), a) Where we have odd number of ones. b) Where we have a single power 2.
- Important: If the reductions are at more than 3 places, the above 2 cases reduce to 0.
a) Where we have odd number of ones. Explanation: We can use a single 1 and pair with 9 available powers from 3 reductions. This leaves with 8 powers which can be paired and reduced to 0. Now if you see the number of ones also became even.
b) Where we have a single power 2. Explanation: We can pair this 2 with 2 powers( from 2 reductions), that leaves with 4 powers which can be reduced to 0 and original single 2 also vanished.
So, we only investigate above cases when reductions are 1 or 2.
I know this is a bit adhoc and haphazard. Appreciate if there is a simpler and better solution.
1 Like
To help me understand better, kindly explain with an example, say if powers are 5,3,1. Thanks
Just an idea, You may pick one AC solution and compute solution for first 1000 numbers and then compare with your solution to see the mismatches. This might help to figure out the issue if any.
is there even a case when answer is 3?
waiting for your response.
Yes for example 4
You cannot divide it by anything and it has 3 divisors 1,2 and 4
did the exact same thing
1 Like
I too followed the same approach and got WA , did u got to know where it failed
Yes , I did stress testing . It failed for n = 72 . Answer should be 2 but my code giving 3.
2 Likes