Try printing a large number, like 1 billion, without any setprecision (locally), and see what happens
7 Likes
After this editorial many users got -
34 Likes
Because by default, double values print decimal points upto 2 places. Thus, your answer would have been correct if the absolute error did not exceed 10^{-2}. Using setprecision(8) makes the answer print upto 8 decimal places. That is the difference.
1 Like
Both of them are trying to maximize their gold, so wouldn’t it be optimal to go to a mine where the gold digging rate g/a (or g/b) is maximum ?
17 Likes
No. Default precision is 6 significant figures. Note that significant figures are different from decimal places.
1 Like
Even I did same mistake cout takes scientific notation by default for large values so it might fail there
1 Like
By significant digits do you mean the values in before the decimal point too? Because usually I have noticed that on my terminal they print 2 decimal places. Maybe I have my facts wrong, thanks for correcting me.
I understand the idea behind this, but does this problem really make sense mathematically? The proof says “Suppose, at some time, Chef and Chefu are working in the different mine, and Let’s say Chef is about to get more than X gold (implying Chefu would get less than Y gold). Then Chefu can always switch to the mine Chef is working, to gain at least Y units of gold, which is the optimal choice for Chefu.” But the problem is that at Chef can move to a different mine at the same instant, so you end up with Chef and Chefu switching mines at an infinite rate. The idea is that both Chef and Chefu have the ability to force the outcome to be X and Y, but I think that might not be mathematically correct.
To illustrate my point, let’s say we have a single bit that is either 1 or 0. At any moment in time Chef and Chefu can instantaneously flip the bit. Chef wants to maximize the total time when the bit is 1 and Chefu wants to do the opposite. What will be the outcome after one hour then if both Chef and Chefu play optimally? Using a similar argument to the one in the editorial, you could say that Chef can make the bit 1 any time it is 0, therefore Chef will win. But this obviously isn’t valid. With the gold mines, if Chef always switched to whatever mine Chefu was in, Chefu can always move to another mine whenever Chef is in the same mine. Therefore the outcome is indeterminate.
30 Likes
Yes. Significant figures counts the number of digits of precision after and including the first nonzero digit.
1 Like
Not really satisfied with the editorial…needs more clarification with the proof of the lemma
7 Likes
This is better…
I have been scammed
Hi Guys try this video Solution,
Hope it helps.
2 Likes
Can you define “optimal” ?
If Chef optimises Chefu’s gold decreases and Chef’s increases, and vice versa.
I’d really appreciate any one from the contest admins/editorialists/setters/testers or more importantly “statement verifiers” solve my doubt ?
Because I think the problem was so poorly written, that it should have been rejected during problem submissions. What is the reader supposed to understand by “optimise” ?
IMO, optimise will mean greedily start mining the mine, which gives more profit.
Consider this example:
1
4
10 1 9
20 9 1
40 1 9
50 9 2
for this case, I think, Chefu will go for G4, because he can get 25 units of gold per day, and Chef will go for mine G3, because it’s optimal for him.
So, if they both play optimally, Chef should take away (40+10+2) = 52 and Chefu should take (50+18) = 68 units of gold.
But the “intended” solution gives 64.0909090909091 55.9090909090909
14 Likes
“Suppose, at some time, Chef and Chefu are working in the different mine, and Let’s say Chef is about to get more than X gold (implying Chefu would get less than Y gold). Then Chefu can always switch to the mine Chef is working, to gain at least Y units of gold, which is the optimal choice for Chefu.”
@taran_1407 or anyone else please tell how chefu will gain atleast Y units of gold after switching .
If someone has different but concrete proof please share.
1 Like
Getting TLE, can someone point out what to change in this code. Here’s the gist:
typedef long double lld
int main(){
int t; cin>>t;
while(t–){
lld A=0, B=0;
int n; cin>>n; lld g[n]; lld a[n]; lld b[n];
for(int i=0; i<n; i++){
cin>>g[i]>>a[i]>>b[i];
}
for(int i=0;i<n;i++){
A += g[i] * b[i] / ( a[i]+ b[i]);
B += g[i] * a[i] / ( a[i]+ b[i]);
}
cout<<fixed<<setprecision(6)<<A<<" "<<B<<endl;
}
Same doubt
(post withdrawn by author, will be automatically deleted in 24 hours unless flagged)