Erering's blog

How is this solution for problem Sum of Three values on cses tle?
By Erering, history, 18 months ago, In English 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define inf INT_MAX
#define ll long long
#define mod 1000000007
map<ll,pair<ll,ll>> m;
int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  ll n,x; cin>>n>>x;
  ll a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
    m[a[i]].first++;
    m[a[i]].second=i+1;
  }
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      ll req=x-(a[i]+a[j]),h=m[req].first;
      if(req==a[i] && req==a[j] && h>=3){
        cout<<i+1<<" "<<j+1<<" "<<m[req].second;
        return 0;
      }
      else if((req==a[i] || req==a[j]) && !(req==a[i] && req==a[j]) && h>=2){
        cout<<i+1<<" "<<j+1<<" "<<m[req].second;
        return 0;
      }
      else if((req!=a[i] && req!=a[j]) && h>=1){
        cout<<i+1<<" "<<j+1<<" "<<m[req].second;
        return 0;
      }
    }
  }
  cout<<"IMPOSSIBLE";
}

The complexity is O(n^2/2*logN) considering that N is up to 5000 the complexity would be 10^8*1.5 which is enough for 1 second. I also do simple operations like addition and subtraction.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

CSES has rather strict TL.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Update: I used unordered map and it got accepted for some of the testcases that I originally got TLE on. Now its only 2 test cases out of the 25 testcases that get TLE. I think that complexity doesn't pass on CSES like it does for most CF questions.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Brother, try to pick the very first element as the first number, and then use two pointers method to the remaining part of the array. if that fails then, pick the second number as the first number and use two pointers method in the remaining part as usual to find out the remaining two numbers. Continue like that......Hope that helps, I got accepted by doing this

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

    So if the sum is greater than expected do you decrease the right or left pointer?

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

      Sorry, I forgot to say that, i have sorted the array in increasing order. So, if the sum is greater than expected, I will just decrease the right pointer which is initially pointing to the highest valued element.

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

        4 10 1 1 2 7 In that sample you will decrease the right pointer for when u have (1,1,7) when it is correct to increase the left pointer to get (1,2,7)

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          My bad your right I didn’t know that you made the 2 pointers start right after the ith element.

          → Reply
»
18 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Your solution might have $$$O(N^2\log N)$$$ time complexity, however it has a large constant factor. This is because std::map works slower with more complex data types. First of all, you don't need to use 64 bit integers, so you should swap ll for int. Secondly, you don't need to use a pair. You already keep track of the latest occurrence of a number with m[req].second. Just check if it is greater than $$$j$$$. You should also use m.count[req] rather than m[req] to check if such key exists, because the latter creates another key value pair to the map, slowing down the searching process making your time complexity $$$O(N^2\log (N^2))$$$.

This code barely passes.

Code

The problem is meant to be solved using either binary search or two pointers method, which both have a much smaller constant factor while having the same time complexity.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The two pointers solution has $$$O(n^2)$$$ complexity while the binary search solution has $$$O(n^2 \log n)$$$ time complexity.

    Also, $$$O(\log n^2) = O(\log n)$$$, since $$$\log n^2 = 2 \log n = O(\log n)$$$.

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

      Yeah, you're right about the two pointer complexity, my bad.

      It is true that $$$O(\log n)$$$ = $$$O(\log n^2)$$$, however since this solution's runtime is just under a second, not using count will result in TLE. I just noted it with big O so it would be clear why it happens.

      → Reply