Dementia rated contest

help
84

ok thank you

87

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

88

@admin / @dj_r_1

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 :slight_smile:

3 Likes
90

We dont want the contest to be unrated because of this :frowning:

1 Like
91

[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
92

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
93

My bad, yes, it’s 7 steps. I thought he used pairs with same values in one step.

1 Like
94

@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
95

Yes.

96

Sorry, too much going on at the moment!

97

No issues

98

your code gives the answer for n=7 as 8,
but for n=7 it can actually be done in 7 operations

99

I could not do it. Can you provide the method

100

We have seen weak test cases in many contests they didnt get unrated.

101

We have seen weak testcases but not outright wrong ones

2 Likes
104

My code does give output as 7 for n = 7

105

I think, you need to learn to compute LCM

106

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.

107

Weak testcases are acceptable to some extend but how come one can give wrong output.

1 Like
108

Your code will give wrong results if n=1 or 2 or 3 .