How didn’t you get TLE? Your code is O(n\sqrt{n}).
we can reach 1 2 3 420 420 420 420 from 1 2 3 4 5 6 7 using following pairs of indices in only 4 operations:
(4 5) , (6 7), (5 6) , (4 7). Correct me if I am wrong. So the answer should be 4+3=7.
It seems correct bro, I agree with your above testcase answer.
I did the pre-computation before my test case loop. So for each test case, it is just O(1) and outside it is strongly O(sqrt(1000000))
My Solution
1 Like
in n=9 , highest power of 2 is 8 (2^3)
highest power of 3 is 9 (3^2)
highest power of 5 is 5 (5^1)
highest power of 7 is 7(7^1)
(4 5) , (6 7), (5 6) , (4 7)
bro pls be clear before saying something
for 7, ans is 7
1 2 3 (20) (20) 6 7
1 2 3 20 20 (42) (42)
1 2 3 (420) 20 (420) 42
1 2 3 420 (420) 420 (420)
(420) 2 3 420 420 420 (420)
420 (420) 3 420 420 420 (420)
420 420 (420) 420 420 420 (420)
pls disprove
@sebastian
2 Likes
Sorry apologies
ok thank you
this doesn’t work as you can convert the highest power of primes in lesser number of ways,
suppose highest prime powers are a,b,c,d
combine(a,b) and( c,d)
the result will be of form
e ,e ,f ,f
now if we combine the two pairs of (e,f) separately it saves one operation
while the way most of the solution work will use 5 operations to combine these 4 higest power primes
but they can be done in 4 operations
@admin please look into this. There was clearly a problem with the question and the checkers. in that case the contest should not be considered for rating
Re: Problem “Helping Hand”: CodeChef: Practical coding for everyone
Numerous reports that some AC solutions are giving the output:
8
for the test input:
1
7
whereas the correct answer seems to be 7 (see e.g. here).
Testcases are either very weak, or (worse!) wrong.
Please look into it 
3 Likes
We dont want the contest to be unrated because of this 
1 Like
[1,2,3,4,5,6,7]->
[1,2,3,4,5,42,42]->
[1,2,3,20,20,42,42]->
[1,2,3,420,20,420,42]->
[1,2,3,420,420,420,420]->
[420,2,3,420,420,420,420]->
[420,420,3,420,420,210,42]->
[420,420,420,420,420,420,420]
It’s 7 operations.
2 Likes
It is undesirable that the contest be unrated because of this but this has cost a lot of people time which could have been used to solve the other problems.
1 Like
My bad, yes, it’s 7 steps. I thought he used pairs with same values in one step.
1 Like
@ssjgz can you please provide a countercase to my solution
#include <bits/stdc++.h>
#define vi vector<int>
#define pi pair<int, int>
#define vs vector<string>
#define ll long long int
#define pb push_back
#define f first
#define s second
#define min3(a, b, c) min(min(a, b), c)
#define max3(a, b, c) max(max(a, b), c)
#define FOR(n) for(int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
using namespace std;
const int INF = 1e9;
const int mod = 1e9+7;
const int MAX_N = 1000001;
vi nump(MAX_N);
void sieve(){
fill(all(nump), 1);
nump[0] = 0;
nump[1] = 0;
for(int i = 2; i <= 1e3; i++){
if(nump[i] == 1){
for(int j = i*i; j < MAX_N; j += i){
nump[j] = 0;
}
}
}
}
vi counter(MAX_N);
void count(){
counter[0] = 0;
for(int i = 1; i < MAX_N; i++){
counter[i] = counter[i-1] + nump[i];
}
}
vi dp(80000);
void dpr(){
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
for(int i = 3; i < 80000; i++){
dp[i] += 2*dp[(i+1)/2] + i/2;
}
}
int main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
sieve();
count();
dpr();
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int p = counter[n];
cout << n - p + dp[p] << "\n";
}
return 0;
}
This works on the principal that if you have any number of primes, it could easily be broken into two groups containing the same elements of size floor(n+1/2)
1 Like
Yes.
Sorry, too much going on at the moment!
No issues
your code gives the answer for n=7 as 8,
but for n=7 it can actually be done in 7 operations
I could not do it. Can you provide the method