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
We have seen weak test cases in many contests they didnt get unrated.
We have seen weak testcases but not outright wrong ones
2 Likes
My code does give output as 7 for n = 7
I think, you need to learn to compute LCM
Can anyone explain this Question from Dementia Contest
The Problem is CodeChef: Practical coding for everyone
I want to know about the Logic and Mathematical Formulation Used.
Weak testcases are acceptable to some extend but how come one can give wrong output.
1 Like
Your code will give wrong results if n=1 or 2 or 3 .
For n=7
It could be 8
1 2 3 4 5 6 7
(STARTS HERE)
1 6 6 4 5 6 7
1 6 30 4 30 6 7
1 6 30 4 210 6 210
1 6 30 4 210 420 420
1 6 30 420 420 420 420
1 6 420 420 420 420 420
1 420 420 420 420 420 420
420 420 420 420 420 420 420
We are aware of this. We are trying to find correct solution to this problem.
1 Like
Not for only n = 7, output is wrong but for n = 8 , n= 9 …so on… output is wrong.
we can prove like,
according to setters logic
to make all primes to be equal to final LCM, we need to take (p-1 + p-2) time but it can be proved that we need exactly one less than that
if primes -> 4
a, b, c, d -->
- ab, ab, c, d
- ab, ab, cd, cd
- abcd, ab, abcd, cd
- abcd, abcd, abcd, abcd
if primes -> 5
a, b, c, d, e
- ab, ab, c, d, e
- ab, ab, c, de, de
- ab, abc, abc, de, de
- ab, abc, abcde, abcde, de
- ab, abcde, abcde, abcde, abcde
- abcde, abcde, abcde, abcde, abcde
similarly for primes -> 6 and so on…
1 Like
yes you are right e.g. I checked for 7 during the contest and got the answer as 7 for it but according to others solutions output is 8, I wasn’t able to crack it during the contest because I applied 2-3 logics and the answer was not optimal for some cases in each of the logic.
@admin please make the contest unrated.
You can only assign two indexes the same value at one second, even if the quantity minimum of one value is bigger than 1.