Solution wrongly hacked

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

So this is not a post accussing someone but more of a post for understanding the problem.

I was giving Codeforces 944 Div 4. I had done 5 problems but the next day it shows that the solution to my 5th problem has been hacked. I took the hack test case and when I ran it on my local machine, the answer matched the expected output but when I ran it on codeforces, it shows some deviation from the expected output.

The code ~~~~~

Code

...

void takeArrayInput(vector& arr, int l){ for(ll i = 1; i < l; i++){ cin >> arr[i]; } }

void print(vector& arr){ for(int i = 0; i < arr.size(); i++){ cout << arr[i] << " "; }

cout << "\n";

}

void solve(){ ll n, k, q; cin >> n >> k >> q; vector a(k + 1, 0), b(k + 1, 0);

takeArrayInput(a, k + 1);
takeArrayInput(b, k + 1);

for(int i = 0; i < q; i++){
    ll d;
    cin >> d;
    ll l = 0, r = k, ind = 0;
    while(r >= l){
        ll mid = l + (r - l) / 2;
        if(a[mid] <= d){
            ind = mid;
            l = mid + 1;
        } else r = mid - 1;
    }

    if(a[ind] == d){
        cout << b[ind] << " ";
        continue;
    }

    double dist = a[ind + 1] - a[ind];
    double time = b[ind + 1] - b[ind];

    double speed = dist / time;

    ll timeTaken = b[ind] + (d - a[ind]) / speed;
    cout << timeTaken << " "; 

}
cout <<"\n";

}

int main() { int T; cin>>T; while(T--) { solve(); } return 0; } ~~~~~

The Test Case ~~~~~ 1 45 16 33 6 26 28 32 34 35 36 37 38 39 40 41 42 43 44 45 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 26 9 15 2 14 44 20 28 29 11 23 40 15 45 17 9 7 15 29 28 19 5 36 18 3 40 9 22 32 26 3 1 13 ~~~~~

for the 4th query the answer should be 15 but my solution when ran on codeforces servers produces the answer 14.

I know that instead of calcuating speed I could have just used dist and time in the final expression but still I want to know why my answer comes out correct on my local but is wrong on codeforces.

Please help.

Комментарии (8)

Написать комментарий?

heinous_coder

7 месяцев назад, # |

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

→ Ответить

GOJO_GOKU_KURAMA

When I solve this question I applied the approach same as yours like a separate variable for speed then computing the final answer, but it gave me WA whereas putting everything into a single expression comes out to be the accepted answer.

7 месяцев назад, # ^ |

Same here. But the code is running fine on my local machine. Don't know what's the issue here. This question wasted a lot of my time as I was multiplying by speed to find time and now just because of this variable my solution has been hacked.

m_nature

← Rev. 2 →

Generally, you shouldn't use floating-point data types when not needed. Because there will be precision errors and you always want to avoid that whenever possible

With that being said, I don't exactly know why it happens on that particular test case though. Also, are you sure that your ind + 1 isn't accessing out-of-bounds?

nah I've handled the cases were it could've gone wrong.

VitalyKo

If you do this

double timeTaken = b[ind] + (d - a[ind]) / speed;
cout << fixed << setprecision(50) << (long double)timeTaken << " ";

You will see that this value is actually 14.99999999999999999913263826201159645279403775930405

I can't say exactly why we don't see that with just double, but the problem is still here — the precision of the floating point types

Probably it would better to use round here (or a solution without using double at all)

4 месяца назад, # |

Блог пользователя heinous_coder