Seeking edge cases - Codeforces

Faraz's blog

Seeking edge cases

By Faraz, history, 3 hours ago, In English

Hello Codeforces!

I submitted my solution for 2275D - Precision Alignment , but I'm getting WA 2 I have spent a while trying to find where my logic fails or what edge case breaks my binary search check function, but I haven't been able to spot the bug yet.

My Approach: Binary Search on Answer: I am binary searching for the answer mid in the range [-3e18, 3e18] using __int128 arithmetic to prevent overflow.

Check Function (check(mid)): For each element/triplet $$$A[i] = (a, b, c)$$$, I evaluate if we can meet or adjust the condition using available operations $$$k$$$: Compute signs of differences: $$$a - b$$$, $$$a - c$$$, and $$$b - c$$$.If $$$a = b = c$$$, I immediately return false. If the signs indicate a non-increasing state ($$$\le 0$$$) , I calculate the minimum operations needed (sm1) by adjusting values (using delta logic with abs) and adding the remaining needed magnitude to reach mid Accumulate total operations into op and ensure op <= k.

My Submission : 393623669

Faraz
3 hours ago
10

Comments (10)

Write comment?

ZainUlHaq

3 hours ago, hide # |

im unable to open ur submission can you send ur code to me somehow maybe write it in reply or write it in ideone and send me the link

→ Reply

Faraz

3 hours ago, hide # ^ |

Spoiler

/*
Author: @FarazSoomro
 
**VENI VIDI VICI**
 
********************* بسم الله الرحمن الرحيم ***********************
*********************** وَقُل رَّبِّ زِدْنِي عِلْمًا **************************
 
╔══════════════════════════════════════════════════════╗
║                                                      ║
║        ███████╗ █████╗ ██████╗  █████╗ ███████╗      ║
║        ██╔════╝██╔══██╗██╔══██╗██╔══██╗╚══███╔╝      ║
║        █████╗  ███████║██████╔╝███████║  ███╔╝       ║
║        ██╔══╝  ██╔══██║██╔══██╗██╔══██║ ███╔╝        ║
║        ██║     ██║  ██║██║  ██║██║  ██║███████╗      ║
║        ╚═╝     ╚═╝  ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝╚══════╝      ║
╚══════════════════════════════════════════════════════╝
*/

// #include <bits/stdc++.h>
#include <iostream>
#include <functional>
#include <map>
#include <algorithm>
#include <set> 
#include <cassert>
#include <numeric>
#include <iomanip>
#include <string>
#include <utility>


using namespace std;

// #pragma GCC optimize("O3,Ofast,unroll-loops")

#define int                     long long 
#define vl                      vector<int>
#define all(x)                  (x).begin(), (x).end()
#define print(vec)              for (auto x : vec) {cout << x << ' ';} cout << endl;
#define pb                      push_back
#define done                    endl
#define gimme(x)                cerr << "("  << __LINE__ << ") " << #x << ": " << x << done;
#define CODE_BY_FARAZ           ios::sync_with_stdio(nullptr); cin.tie(false); cout.tie(false);
#define Spooder                 signed 
#define sz(x)                   ((int) x.size())
#define yes(x)                  cout << (x ? "Yes\n" : "No\n") << done;
#define bigit                   __int128
constexpr long long INF = 3e18;
const int Maxn = 2e5 + 67;

// WHY DO YOU KEEP SPYING ON MY CODE GO SOLVE A PROBLEM -_-

// ---------------- Main Solution: ----------------


void Faraz()
{
        int n, k; cin >> n >> k;
        vector<vector<int>> A(n, vector<int>(3));

        for (int i = 0; i < n; ++i) {
                cin >> A[i][0] >> A[i][1] >> A[i][2];
        }

        

        auto check = [&](bigit mid)
        {
                bigit op = 0;
                for (bigit i = 0; i < n; ++i) {
                        bigit a = A[i][0], b = A[i][1], c = A[i][2];
                        if (a + b + c >= mid) continue;
                        bigit sgn1 = 0;
                        if ((a - b) > 0) sgn1 = 1;
                        if ((a - b) < 0) sgn1 = -1;
                        if ((a - b) == 0) sgn1 = 0;
                        bigit sgn2 = 0;
                        if ((a - c) > 0) sgn2 = 1;
                        if ((a - c) < 0) sgn2 = -1;
                        if ((a - c) == 0) sgn2 = 0;
                        bigit sgn3 = 0;
                        if ((b - c) > 0) sgn3 = 1;
                        if ((b - c) < 0) sgn3 = -1;
                        if ((b - c) == 0) sgn3 = 0;

                        if ((sgn1 == 0 and sgn2 == 0 and sgn3 == 0)) return false;

                        if ((sgn1 <= 0 and sgn2 <= 0 and sgn3 <= 0))
                        {
                                bigit sm1 = INF;
                                // if (sgn1 != -1 and sgn2 != -1) return false;
                                if (sgn1 == -1)
                                {

                                        bigit idk = abs(a - c) + 1LL;
                                        c -= idk;
                                        sm1 = min((bigit)abs(a - c) + 1LL + max((bigit)mid - (a + b + c), (bigit)0LL), sm1);
                                        c += idk;
                                        idk = abs(b - c) + 1LL;
                                        c -= idk;
                                        sm1 = min((bigit)abs(b - c) + 1LL + max((bigit)mid - (a + b + c), (bigit)0LL), sm1);
                                        c += idk;

                                }
                                if (sgn2 == -1)
                                {
                                        bigit el1 = (abs(a - b) + 1LL);
                                        bigit idk = el1;
                                        b -= idk;
                                        sm1 = min(el1 + max((bigit)mid - (a + b + c), (bigit)0LL), sm1);
                                        b += idk;
                                }
                                
                                if (sm1 > k - op) return false;
                                op += sm1;
                                if (op > k) return false;
                                continue;
                        }
                        bigit sm = a + b + c;
                        if (mid - sm > k - op) return false;
                        op += mid - sm;
                        if (op > k) return false;
                        
                }
                return op <= k;
        };

        int lo = -INF, hi = INF, ans = -INF;
        while (lo <= hi) 
        {
                    int mid = lo + (hi - lo) / 2;
                    if (check(mid)) 
                    {
                                ans = mid;
                                lo = mid + 1;
                    } 
                    else 
                    {
                                hi = mid - 1;
                    }
        }

        cout << ans << done;


}



Spooder main()
{
        int T = 1;
        cin >> T; 
        while (T--)
        {
                Faraz();
        }
        return 0;
}

→ Reply

ZainUlHaq

2 hours ago, hide # ^ |

tho this code gave some compilation errors which I needed to fix for some reason but yeah I found this case:

Test Case

1
1 10
0 10 16

my code gives 26 for this while yours gave 27

here is a possible explanation:

Explanation + fix

look at this block of code

idk = abs128(b - c) + 1LL;
c -= idk;
sm1 = min((bigit)abs128(b - c) + 1LL + max((bigit)mid - (a + b + c), (bigit)0LL), sm1);
c += idk;

In your sgn1 == -1 block, you update c -= idk and then immediately recalculate abs128(b — c) inside the min(...) function. Because c is now exactly b — 1, that absolute difference always = 1, which I have a suspicion that this isnt true lol

The Fix: Use your pre-calculated idk inside the min() call instead of re-evaluating the modified variables, exactly like you did for el1 below.

the fix mentioned above did give me an ac here is the corrected sgn == -1 if you need it:

Code

                                if (sgn1 == -1)
                                {
                                        bigit idk = abs128(a - c) + 1LL;
                                        c -= idk;
                                        sm1 = min(idk + max((bigit)mid - (a + b + c), (bigit)0LL), sm1);
                                        c += idk;
                                        
                                        idk = abs128(b - c) + 1LL;
                                        c -= idk;
                                        sm1 = min(idk + max((bigit)mid - (a + b + c), (bigit)0LL), sm1); 
                                        c += idk;
                                }

→ Reply