Helping Hands - Dementia (Minimum steps: k +n - 4)

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:
Let’s take initiall 4 numbers to be 3,4,5,7
Step 1: 12 12 5 7
Step 2: 12 12 35 35
Step 3: 420 12 35 420
Step 4: 420 420 420 420

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

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.
We have however solved the problem of reducing floor(p+1/2) elements into one element.
Thus dp[p] = p/2 + 2*dp[(p+1)/2]

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

My “AC” code gives 29.

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.

Yep. Too many variables

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