### p_321052's blog

By p_321052, history, 4 weeks ago,

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?

• 0

By p_321052, history, 2 months ago,

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

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?

• +12

By p_321052, history, 3 months ago,

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.

• +91

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