Codeforces Round #980 Editorial

→ Pay attention

Before contest
Codeforces Round (Div. 3)
4 days
Register now »

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3904
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3494
8	Um_nik	3396
9	gamegame	3386
10	maroonrk	3350

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	maomao90	164
1	cry	164
3	Um_nik	163
4	atcoder_official	159
5	awoo	158
6	adamant	157
6	-is-this-fft-	157
8	nor	154
9	TheScrasse	153
9	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

Ormlis's blog

Codeforces Round #980 Editorial

By Ormlis, history, 3 hours ago, translation, In English

Thank you for participating!

2024A - Profitable Interest Rate was authored and prepared by Helen Andreeva with Artyom123

2024B - Buying Lemonade was authored by Endagorion and prepared by sevlll777

2023A - Concatenation of Arrays was authored and prepared by Mangooste

2023B - Skipping was authored and prepared by adepteXiao

2023C - C+K+S was authored and prepared by yunetive29

2023D - Many Games was authored and prepared by Tikhon228

2023E - Tree of Life idea by isaf27, solution and preparation by Ormlis

2023F - Hills and Pits was authored and prepared by glebustim with vaaven

Tutorial is loading...

Ormlis
3 hours ago
12

Comments (12)

Write comment?

Krrishchanchal

3 hours ago, # |

+15

Ormlis when will hidden test case and source code of others be visible?

→ Reply

Ormlis

2 hours ago, # ^ |

Only administrators can do this, not me.

→ Reply

Krrishchanchal

2 hours ago, # ^ |

← Rev. 2 →

Oh sorry I didn't know. Btw great contest Thank you

→ Reply

errorgorn

3 hours ago, # |

← Rev. 2 →

Hi, I cannot prove my solution for div1D nor hack it I hope someone can hack or prove it.

Spoiler

287108342

code because it seems people can view other's submissions right now

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
ii arr[200005];
vector<int> w[105];

ii pp[200005]; //reconstruct stuff from this
signed dp[200005][100]; //dont care about weight 100!
double val[200005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
	rep(x,1,n+1) w[arr[x].fi].pub(arr[x].se);
	
	rep(x,1,100){
		sort(all(w[x]));
		reverse(all(w[x]));
	}
	
	double ans=0;
	
	int sum=0;
	for (auto it:w[100]) sum+=it;
	
	val[0]=1;
	rep(x,0,200005) if (val[x]!=0){
		if (x){
			rep(y,1,100) dp[x][y]=dp[pp[x].fi][y];
			dp[x][pp[x].se]++;
		}
		
		rep(y,1,100){
			if (dp[x][y]==sz(w[y])) continue;
			if (x+w[y][dp[x][y]]>=200005) continue;
			
			int x2=x+w[y][dp[x][y]];
			
			double v=val[x];
			v*=(double)y/100;
			
			if (val[x2]<v){
				val[x2]=v;
				pp[x2]={x,y};
			}
		}
		
		ans=max(ans,val[x]*(x+sum));
	}
	
	cout<<fixed<<setprecision(12)<<ans<<endl;
}

The idea behind my solution is to have $$$dp[\sum w]$$$ store the maximum probability that we can achieve.

As with the editorial, for a fixed $$$p$$$, we should only take a prefix of the weights (when we sort from biggest to smallest weights). So we will also store that information (in the code it is signed dp[400005][100];, for state dp[x], we take the biggest dp[x][y] elements with p=y.

When we transition, we will try for all y to do dp[x][y]++.

This doesn't seem right because it is possible for the optimal answer to be killed early when there is another state with a bigger probability for the same $$$\sum w$$$ but is worse at extending to larger $$$\sum w$$$

→ Reply

PaarthJuneja

3 hours ago, # |

i swear i can't figure out for the life of me why my solution to B isn't correct, and i'm not allowed to look at the failing test case either.

Spoiler

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int t; cin >> t;
	while (t--) {
		int n, k; cin >> n >> k;
		vector<int> v(n);
		for (int i = 0; i < n; i++) {
			cin >> v[i];
		}
		int ans = 0, l = 0, m = 0;
		sort(v.begin(), v.end());
		for (int j = 0; j < n; j++) {
			if (((v[j] - l) * n) + ans  < k) {
				ans += ((v[j] - l) * n);
				m++;
				n--;
				l += (v[j] - l);
			} else {
				cout << m + k << endl;
				break;
			}
		}
	}
	return 0;
}

→ Reply

xksark

2 hours ago, # ^ |

I dont know about the formulas, but you should use long long instead of int.

→ Reply

Krrishchanchal

2 hours ago, # ^ |

← Rev. 2 →

Bro your code won't return any output if k is equal to sum of all elements of the array.

Try

3 6

1 2 3

Comment if you want me to fix it

→ Reply

ibrahimwq

2 hours ago, # |

← Rev. 3 →

then $$$c_p \cdot q^{c_p} > (c_p - 1) \cdot q^{c_p - 1}$$$; otherwise, the smallest element can definitely be removed.

why?

→ Reply

Noluck_167

104 minutes ago, # |

C is a piece of dogShit,i mean why it had to be based on some crap observation.It could have been improved by giving a formal proof of why does that always work. Disappointed...

→ Reply

.-__-.

42 minutes ago, # ^ |

What's wrong with the proof provided?

→ Reply

Noobish_Monk

26 minutes ago, # ^ |

Another solution is to sort the arrays by comparing pairs $$$(min(a_{i,1}, a_{i,2}), max(a_{i,1},a_{i,2}))$$$. We can observe that if we move the array with minimal element to the left (and among these with the least maximum), the number of inversions cannot increase, so that's optimal order

→ Reply

dsarules

16 minutes ago, # ^ |

← Rev. 2 →

lol yeah that was my method

→ Reply