Getting WA although the question statement seems pretty basic

[4z86RXSz]

Write your question here.
Jitendra has won a lottery of K rupees. He wants to utilize this money optimally.
He wants to travel different cities in consecutive order with help of money he won in lottery.For travelling every city, he has to pay some amount. He wants to travel as many number of cities he can travel with the available lottery money.
Help Jitendra to find the maximum number of cities he can travel and the remaining money.
Constraints:
1 <= T <= 10
1 <= N <= 100000
1 <= K <= 1000000000
1 <= a[i] <= 1000000000 , for each valid i
Example:
Input:
1
5 5
3 5 2 1 7
Output:
2 2
Explanation:
He can travel maximum of 2 cities and cost of visiting them is 2+1.Hence, the remaining money is 5-3=2.

  Put the code you need help with here.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define re(n) for(ll i = 0 ; i < n ; i++)
#define rep(i , j , n) for(ll i = j ; i < n ; i++)
int main()
{
    SPEED;
    // Code
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        ll a[n];
        re(n)
        cin>>a[i];
        sort(a,a+n);
        ll c=0;
        rep(i,0,n)
        {
            if(a[i]<=k)
            {
                k-=a[i];
                c++;
            }
            else
                break;
        }
        cout<<c<<" "<<k<<endl;
    }
    return 0;
} 

the question seems pretty easy am i missing something, why am I getting a Wrong Answer :/

[jonnin]

If you are going to continue to use 1 letter variable names, I am not going to read your code.

can he go to the same city twice, and if he does, does it count? Does where he starts matter? What number represents the city, and what number the cost to get there, and from where? It should be pairs ... that is, from one to two costs 10, from two to three costs 15, etc. I don't see any sensible pairings. You need pairs because one to two, one to three, one to four, etc...

also, I am not going to look at another of these until the example is documented. what are the inputs you gave? I mean I see you read t (whatever that is) and then n and k (whatever those are).

are you familiar with the traveling salesman problem and the difficulty thereof? this is a subvariation of it, but the complexity may still be more than trivial...

[4z86RXSz]

There is a guy named jetendra now he won K bucks in a lottery and he wants to use this money to visit some cities

We are given N and K
Where N is number of cities and K is the amount of money he won

cost of visiting the ith city is a[i]

I have to print the maximum number of cities he visits and the amount left after that

1
5 5
3 5 2 1 7
Output:
2 2
Explanation:
He can travel maximum of 2 cities and cost of visiting them is 2+1.Hence, the remaining money is 5-3=2.


I have to use the money optimally
now I don't think that he can visit the same city twice as in the example
he is going to city with cost (1,2) and the remaining money is 2 after visiting 2 cities
my code works correctly for this output

But i think i am missing something as when a submit my code it is giving wrong answer

//working of my code
I am just sorting the array and subtracting the ith element from k and checking if a[i]<=k
plus i am incrementing c(number of cities he is visiting)
when the condition is false i break out of the loop and print number of cities and remaining money

I am aware of the travelling salesman problem but this problems seems different atleast it's problem statement is different

[4z86RXSz]

@tpb can you help with this

[tpb]

Well, sorting the array is totally wrong since the original order is important. You need to find the maximum number of consecutive cities that you can visit. So for 3,5,2,1,7 its the cities with values 2,1, that's 2 cities costing 3 dollars with 2 dollars left over.

BTW, if you want others to read your code then those "rep" and "re" things are idiotic.

[4z86RXSz]

cool so i just need to find the longest subarray such that its sum <=k

[4z86RXSz]

@tpb

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int main()
{
    SPEED;
    // Code
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,k;
        cin>>n>>k;
        ll a[n];
        for(ll i=0;i<n;i++)
        cin>>a[i];
        ll beg = 0, end = 0;
	ll counter = 0, d = INT_MIN;
	ll length = n;
	ll sum = 0;
	ll resBeg = -1, resEnd = -1;
	while (end < length)
        {
		if (sum <= k)
		{
			sum += a[end++];
		}
                else
                {
			sum -= a[beg++];
		}

		if (sum <= k)
               {
			if (d < end - beg)
			{
				d = end - beg;
				resBeg = beg;
				resEnd = end - 1;
			}
		}
	}
	ll sum1=0;
	for(int i=resBeg;i<=resEnd;i++)
	{
	    sum1+=a[i];
	}
        cout<<d<<" "<<k-sum1<<endl;
    }
    return 0;
}

I coded it using window sliding techniques still getting WA :/

[tpb]

My interpretation of these problems is often wrong. :-(

[ne555]

I suppose that you should use the remaining money as a tie breaker.

[tpb]

you should use the remaining money as a tie breaker

That turns out to be the case. The only clue to that is "he wants to use the money optimally". However, usually one would think that "optimal" means to save money if possible. But in this case, you're supposed to spend as much as possible.

#include <iostream>
int main() {
    static int a[100000];
    int t;
    std::cin >> t;
    while (t--) {
        int n, k;
        std::cin >> n >> k;
        for (int i = 0; i < n; i++)
            std::cin >> a[i];
        int i = 0, j = 0, len = 0, sum = 0, maxsum = 0;
        while (true) {
            if (j < n && sum + a[j] <= k)
                sum += a[j++];
            else {
                if (j - i > len || (j - i == len && sum > maxsum)) {
                    len = j - i;
                    maxsum = sum;
                }
                if (j >= n)
                    break;
                sum -= a[i++];
            }
        }
        std::cout << len << ' ' << k - maxsum << '\n';
    }
}

Note that (32-bit) ints are good enough since k and all a[i] max out at a billion.

[4z86RXSz]

@tpb
Thanks it worked, found out my mistake too :)

[shubhum]

@iamdad3
i have looked all the condition still getting wrong answer ,
saved as money as he can