Dementia rated contest

help
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 .

109

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

110

We are aware of this. We are trying to find correct solution to this problem.

1 Like
111

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

  1. ab, ab, c, d
  2. ab, ab, cd, cd
  3. abcd, ab, abcd, cd
  4. abcd, abcd, abcd, abcd

if primes -> 5
a, b, c, d, e

  1. ab, ab, c, d, e
  2. ab, ab, c, de, de
  3. ab, abc, abc, de, de
  4. ab, abc, abcde, abcde, de
  5. ab, abcde, abcde, abcde, abcde
  6. abcde, abcde, abcde, abcde, abcde

similarly for primes -> 6 and so on…

1 Like
112

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.

113

@aryanc403 pls tell the correct ans.

114

You can only assign two indexes the same value at one second, even if the quantity minimum of one value is bigger than 1.

116

@admin weak test cases are okai but wrong test case cant be acceptable