Help me in solving CURSED problem

help
,
1

My issue

include
#include<bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>> t;
while(t–){
int n;
cin>>n;
vector ans(n);

    for(int i = 0; i< n; i++){
        cin>> ans[i];
    }
    sort(ans.begin(), ans.end());
    int cnt =0;

    
    
    vector<long long>prefix(n);
    // prefix sum
    prefix[0] = ans[0];
    if( n >= 1)prefix[1] = ans[0];
    if(n > 2){
        for(int i =2; i< n; i++){
        prefix[i] = prefix[i-1] + ans[i-1];
      }
    }
    // comparison 
    
    for(int i = 1; i<n; i++){
        if(prefix[i] >= ans[i]){
            cnt++;
        }
    }
    cout<< cnt<< endl;
    for(int i = 0; i< n; i++){
        cout<< ans[i]<< " ";
    }
    cout<< endl;
}
return 0;

} Could anyone tell what am I doing wrong in this, the sample test case is running fine but on submission it is giving wrong, please help!

My code

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	return 0;
}

Problem Link: Cursed Indices Practice Coding Problem - CodeChef

2

@aashi3007
here, refer my c++ code for better understanding of the logic

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    long long int n;
	    cin>>n;
	    long long int a[n];
	    vector<long long int> v;
	    map<int,int> mp;
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
	    sort(a,a+n);
	    long long int val=a[0];
	    v.push_back(a[0]);
	    mp[0]=1;
	    while(1)
	    {
	        int u=upper_bound(a,a+n,val)-a;
	        if(u!=n)
	        {
	            v.push_back(a[u]);
	            mp[u]=1;
	            val+=a[u];
	        }
	        else
	        break;
	    }
	    cout<<n-v.size()<<endl;
	    for(int i=0;i<v.size();i++)
	    {
	        cout<<v[i]<<" ";
	    }
	    for(int i=0;i<n;i++)
	    {
	        if(mp[i]==0)
	        cout<<a[i]<<" ";
	    }
	    cout<<endl;
	}
	return 0;
}
1 Like
3

no…the approach is correct for trivial testcases…your solution fails for the testcases [1,2,3,5] as the count will be 2 but the correct rearrangement will be [1,2,5,3].u have discarded all the values which is less than the prefix sum values…and forgot to substract it from the prefix array .so the test cases are failing…a little bit of updation to ur code will make it work perfectly…my code :

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String args) throws java.lang.Exception
{
// your code goes here
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t>0){
int n =sc.nextInt();
int arr=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();

	Arrays.sort(arr);
    ArrayList<Integer> correct=new ArrayList<>();
    ArrayList<Integer> failed=new ArrayList<>();
    correct.add(arr[0]);
    int pre=arr[0];
	int ans=0;
	for(int i=1;i<n;i++){
	    if(arr[i]<=pre){
	        ans++;
	        failed.add(arr[i]);
	        continue;
	    }
	    pre+=arr[i];
	    correct.add(arr[i]);
	}
	correct.addAll(failed);
	System.out.println(ans);
	for(int i=0;i<correct.size();i++)
	System.out.print(correct.get(i)+" ");
	System.out.println();
	t--;

}
}
}

1 Like
4

Oh I see, thanks a lot for pointing out my mistake!

5

Thank you!