p_321052's blog

By p_321052, history, 3 years ago, In English
#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://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;
}
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by p_321052 (previous revision, new revision, compare).

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I didn't check the correctness of your code, but there is indeed more efficient algorithm for this problem.

First, binary search is not needed, since as #ride become smaller, mins increase monotonically. This will eliminate a logn factor in time complexity.

Second, a simpler approach is possible for checking whether some s is valid given #ride. Consider team size $$${v_i}$$$, Now you first take largest v, and then you want to see if another smaller team can go with them. It can be shown that instead of taking the team with maximum possible size, you can just look at $$$v_1$$$. So basically you take elements only from left and right side of the array. No need to use set.

My code: 127899137

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    after i changed not to use binary search and multiset, i'm still getting WA for same test case with same wrong answer...i think there's some critical wrong implementation that i'm missing. but your advice helped. thanks!

    i have one question. even though "s" monotonically decreases as "r" increases, isn't that eventually takes O(r+n*k) time which is slower compared to binary search O(r*k*logn)?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right.

      The method I mentioned has time complexity O(nk). If binary search is used, it becomes O(k^2logn).

      Since n=0.5m, k=8k, the complexities are about the same. If monotonicity is used to optimize binsearch, it should be several times faster.

      I'm being careless when doing the analysis XD.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by p_321052 (previous revision, new revision, compare).