p_321052's blog

By p_321052, history, 4 weeks ago, In English

i'm solving this problem : https://codeforces.com/contest/1280/problem/D and my code : https://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?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By p_321052, history, 2 months ago, In English

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

my code : https://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?

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By p_321052, history, 3 months ago, In English

https://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.

Read more »

 
 
 
 
  • Vote: I like it
  • +91
  • Vote: I do not like it

By p_321052, history, 11 months 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;
}

Read more »

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it