problem is from NEERC 2011 named "gcd guessing game"

you are given number N which is less than or equal to 10000. (1 <= N <= 10000) number X is hidden. (1 <= X <= N) for each query, you can choose any number Y from 1 to N and get gcd(X,Y). at least how many query you need to determine number X?

solution for this problem is to gather all prime numbers from 1 to N and group them so that product of each group does not exceed N. minimum number of group is our answer. let's say this number G.

my question is with strategy above, we can only determine which prime factor does X have. for example if X is (2^3) * (3^5) , we can say X is multiple of 6 but can't tell how many 2 and 3 does X have. so we need additional query to determine it. so there can be a number we can't certain with G queries. how can we prove there are no such numbers?

sorry for my poor english.

i'm solving this problem : https://mirror.codeforces.com/contest/1280/problem/D and my code : https://mirror.codeforces.com/contest/1280/submission/163753815

i thought this is just tree knapsack dp but for some reason, get's wrong answer for test3

dp[i][j] means (maximum number of winning region, maximum advantage of component involving i) when partitioning subtree of i into j regions

can someone tell me what's wrong with my code?

this problem : https://mirror.codeforces.com/contest/1369/problem/D

my code : https://mirror.codeforces.com/contest/1369/submission/158768076

dp[i][j] = maximum number of yellow nodes of tree of level i. if j = 0, it's root is not colored. otherwise it's root is colored.

well, it seems reasonable but since it returns maximum value modulo 1e9+7, we can't tell which value is actually bigger one.

but my code passed. why does it work? or is it because of weak test data?

https://mirror.codeforces.com/contest/1684/submission/157727918

this is my code for case

1

5 1

1 2 3 4 5

my code outputs 4 and the answer is 0 because you can move 5 to 0 yet, my code passed systest. in my code, if some number is maximum MEX and is given as input, it can't be detected as MEX.

i mean...this was very strange experience in my codeforces life.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
vector<int>arr;
bool pos(ll s,ll ride){
	if(s<arr.back()) return 0;
	ll r = 0;
	multiset<int>st(arr.begin(),arr.end());
	while(st.size()){
		r++;
		int cur = *st.begin();
		if(cur>s) return 0;
		st.erase(st.begin());
		if(st.size()==0) break;
		auto it = st.upper_bound(s-cur);
		if(it==st.begin()) continue;
		st.erase(prev(it));
	}
	return r<=ride;
}
ll f(ll ride){
	ll l = 0;
	ll r = INT32_MAX;
	while(l<=r){
		ll mid = (l+r)>>1;
		if(!pos(mid,ride)) l = mid+1;
		else r = mid-1;
	}
	return ride*l;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	map<int,int>m;
	for(int i=1; i<=n; i++){
		int a; cin>>a;
		m[a]++;
	}
	for(auto p : m) arr.push_back(p.second);
	sort(arr.begin(),arr.end());
	if(arr.size()==1){
		cout<<arr.back();
		return 0;
	}
	ll ans = INT64_MAX;
	for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(); i++){
		ans = min(ans,f(i));
	}
	cout<<ans;
}

https://mirror.codeforces.com/problemset/problem/1250/B

this problem has no editorial. i just iterated all possible r and calculate minimum s with binary search

doing binary search, i greedily tried to take two teams at one ride if it's possible. if s is fixed and current team has c member, i checked whether there's a team with maximum number of members d <= (s-c) if there's such team, two team can ride together, otherwise just take one time at this ride.

is it logically wrong? or implementation is wrong? need help! (also i wanna know if there's a solution with complexity k^2 or faster , since my code is too slow )

UDP: another version that doesn't use binary search and multiset yet produces same Wrong Answer.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
vector<int>arr;
int pointer;
 
bool pos(ll s,ll ride){
	if(s<arr.back()) return 0;
	deque<int>deq(arr.begin(),arr.end());
	ll ret = 0;
	while(deq.size()){
		ret++;
		int sz = deq.back();
		deq.pop_back();
		if(deq.size() && deq.front()+sz<=s){
			deq.pop_front();
		}
	}
	return ret<=ride;
}
ll f(ll ride){
	while(pos(pointer,ride)) pointer--;
	pointer++;
	return ride*pointer;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	map<int,int>m;
	for(int i=1; i<=n; i++){
		int a; cin>>a;
		m[a]++;
	}
	for(auto p : m) arr.push_back(p.second);
	sort(arr.begin(),arr.end());
	if(arr.size()==1){
		cout<<arr.back();
		return 0;
	}
 
	pointer = n;
	ll ans = INT64_MAX;
	for(int i=(arr.size()/2+arr.size()%2); i<=arr.size(); i++){
		ans = min(ans,f(i));
	}
	cout<<ans;
}