Helping hands question of the Dementia contest asks us to find the minimum number of steps to make all the elements equal.
This problem is very much similar to the GOSSIP problem: https://www.math.uni-bielefeld.de/~sillke/PUZZLES/gossips.pdf
If there are k primes (k>=4) then we can make all numbers equal by 2*k-4 + (n -k) = k + n - 4 steps.
For example in the case n=7:
And three more steps to make 1,2,6 to 420. Thus in total 7 steps = 4 + 7 - 4 =k+n-4
1 Like
output for n=7 -> 8 seconds is getting accepted but i can do n=7 in 7 seconds.
1 2 3 4 5 6 7 initial
1 2 12 12 35 6 35 +2 second ( selected i=3,j=4 and i=5,j=7 )
1 2 420 420 420 6 420 +2 second (selected i=3,j=5 and i=4,j=7)
3 remaining -> +3second (select i= 1,2,6 with j=5)
total-7 second; but i submitted a code now seeing others solutions and it got accepted with ans=8(for n=7). were test cases weak?
2 Likes
humane
August 13, 2020, 7:27pm
5
Test cases were not weak, they were “wrong”
2 Likes
The approach used by most people n + p - 3 fails for n = 2, n = 7
#define _GLIBCXX_DEBUG
#pragma GCC optimize "trapv"
#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 gives the correct answer for all cases I tried and could verify by hand@humane @therealnishuz could anyone point out a mistake?
Can you please explain your dp?
Just found one, i failed to handle n = 1.
1 Like
With p/2 moves, we can reduce the number of primes into two equal subgroups containing floor(p+1/2) elements each.
1 Like
Someone said that the solution for n = 23 is 27. But I do not have the patience to do it by hand. The code gives 34 as the answer
I doubt anyone has the patience to write it out and solve it
I am curious to see what actually is the solution
1 Like
There is a high chance of making a mistake for computing the answer for n = 23 by hand.
It is only possible to do if one has a proven algorithm in mind
what would be the answer for n = 10?
10 according to my logic.
(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)
AC solution (n+p-3) gives 11, was the question wrong then?
The question was alright. There is a problem with the testcases