ynain2003's blog

SUM OF 4 VALUES

By ynain2003, history, 3 weeks ago, In English

HI I am currently stuck in CSES proeblem, LINK. I am using the 2 pointer concept. I am using 2 while loop and my time complexity is O(N^2). I am getting wrong answer , can someone help me out ?? code link

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i solved it much easier, checking all possible sums of two ellements, from i + 1 to n - 1,

and after it check do i have a k - sum_of_two_ellemnts, if yes, it's our answer, else we're putting to map all possible sums of two ellements, from 0 to i. Its' all what i was need to solve this problem

        ll n, k;
        cin >> n >> k;
        ll a[n];
        for (ll i = 0; i < n; i++) {
            cin >> a[i];
        }
        map<ll, pair<ll, ll>>mp;
        for (ll i = 0; i < n; i++) {
            for (ll j = i + 1; j < n; j++) {
                if (mp[k - a[i] - a[j]].fi != 0) {
                    cout << i + 1 << ' ' << j + 1 << ' ';
                    cout << mp[k - a[i] - a[j]].fi << ' ' << mp[k - a[i] - a[j]].se;
                    exit(0);
                }
            }
            for (ll j = 0; j < i; j++) {
                mp[a[i] + a[j]] = {i + 1, j + 1};
            }
        }
        cout << "IMPOSSIBLE";
→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you find error in my code ??

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your idea it's wrong, you're doing somethink like greedy not 2pointer. But perhap i didn't get your idea well

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

void solve() { int n, x; cin >> n >> x; vectorsol(n); for(auto &i : sol) cin >> i; map<int,pair<int,int>>mvp; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(i == j) continue; mvp[sol[i] + sol[j]] = {i, j}; } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(i == j) continue; int sm = sol[i] + sol[j]; int rem = x — sm; if(mvp.find(rem) != mvp.end()) { auto pp = mvp[rem]; setst; st.insert(i); st.insert(j); st.insert(pp.first); st.insert(pp.second); if(st.size() == 4) { for(auto k : st) cout << k + 1 << ' '; return; } } } } cout << "IMPOSSIBLE";

}

→ Reply