std::vector<long long> tstCases;
std::vector<long long> okset;
std::vector<long long> testset;
for(int i =0;i<2;i++){
long long cases;
std::cin >> cases;
tstCases.push_back(cases);
}
long long n = tstCases.at(0);
long long k = tstCases.at(1);
Make sure you understand the requirements of the problem. From the problem page, we see
$$
0 \leq K \leq 1,000,000\\
Subtask_1: 2 \leq N \leq 2000\\
SubTask_2: 2 \leq N \leq 100,000
$$
Whenever values are within a sane countable range, just use int. Once a number gets to a point you wouldn't want to personally count to, say a couple thousand, then move to the fixed width types provided by <cstdint> (std::int32_t, std::int64_t). For this problem, N and K are best represented at 32-bit integer types (std::int32_t) instead of long long (which is at least a wasteful 64 bits).
The worst case scenario for this problem is that every pair meets the hardiness limit. The first few \$N\$'s produces counts of \$[1, 3, 6, 10, 15, 21]\$, which would be the sequence for the triangle numbers. \$N = 100,000\$ would be the \$99,999^{th}\$ triangle number for our sequence (started at 1). To find the \$n^{th}\$ triangle number, we can use the formula
$$
T(n) = \frac{n(n+1)}{2}
$$.
So,
$$T(99,999) = \frac{99,999(100,000)}{2} = 4,999,950,000$$.
Use of a 64-bit integer would be more appropriate since a 32-bit integer cannot store that worst case count size.
You can minimize (re)allocations by reserving space before appending to your container. We know how large the data set is going to be because it's provided by the subtasks as the first value read. Use the information provided.
Keep functions short and simple making them easier to read and test. Functions should perform a single logical operation. Look for opportunities to reuse code.
An example; Let's start with some basic IO helpers that uses NRVO. You can extend it to print out prompts, validate input, but for this exercise, it's something basic and can be used on all of the challenge sites.
#ifndef IO_READ_H
#define IO_READ_H
#include <algorithm>
#include <iosfwd>
#include <iterator>
#include <vector>
namespace io {
template <typename Result>
Result read(std::istream& in) {
Result result{};
in >> result;
return result;
}
template <typename Result>
std::vector read_n(std::istream& in, std::size_t element_count) {
std::vector<Result> results;
results.reserve(element_count);
std::copy_n(std::istream_iterator<Result>(in), element_count,
std::back_inserter(results));
return results;
}
} // namespace io
#endif
Now in your program, you get straight to the point. Keep main() clean. Use it to parse/forward command-line arguments and configure the environment in which your tests/program will operate in.
void run_zoc13003() {
const auto gum_count = io::read<std::size_t>(std::cin);
const auto hardiness_limit = io::read<std::int32_t>(std::cin);
auto hardiness_quotients = io::read_n<std::int32_t>(std::cin, gum_count);
std::sort(hardiness_quotients.begin(), hardiness_quotients.end());
// .. calls to other functions to do work.
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
run_zco13003();
}
I changed my whole algorithm to get rid of that TLE error and also almost got that but for the last test it still gets stuck.
Your program still attempts to brute force it's way through the sequence, comparing each and every element in the worst case (\$O(n^2)\$). Exploit the properties of the sequence (sorted/contiguous). You can search for things efficiently. For each element, find the first element that falls below the limit (reverse linear search). The elements beyond that point would make invalid pairs. Elements upto that point can be summed with your current element to make a valid pair. Since we are only interested in unique pairs, we just count the number of gums between our current gum and its pair.
Consider the equation \$A_i + A_j = K\$. If \$K\$ never changes and the value of \$A_i\$ increases, we would expect the value of \$A_j\$ to decrease. Since they are converging, you can resume your search from where you left off. Once \$i == j\$, you've exhausted all the possible unique combinations. Putting all of this together, you have an algorithm that counts the valid pairs in \$O(n)\$ time. Combined with the \$O(n log(n))\$ sort, it's still much faster than your brute-force approach.
You can also optimize for the special case that the last two elements are below the limit. If they are, you just calculate the triangle number in constant time.
k, not greater. \$\endgroup\$