I’m unable to find the bug can somebody help, what I did was, I collected all positive element index before the last negative indexes which are of the type [+,-,+] here’s my submission.
I used these test case to judge my solution…
there were build one by one as i was continuously getting WA ,
4
5
-4 2 -4 3 -5
3
-3 -2 -1
7
-2 5 -6 2 3 -7 -8
6
0 8 9 -8 8 -9
Hope it helps
keep eye on the 2nd & 4th one
The 0 in the array may be the culprit
2 Likes
for anyone thinking in terms of partition !!
1st
Don’t care about the 0s in the array bcoz of well asuring line
maximum sum of a contiguous subsequence (possibly an empty sequence, with sum 0)
2nd
So we are left with purely +ve and purely -ves..
3rd
start = 0,end=n-1;
while(start<end){
...
}
Now this is two pointers
4th
Inside while loop
increment the start untill you not get a pure -ve
decrement the end untill you not get a pure +ve
swap the purely -ve at start with purely +ves in the end
5th
Now finally see what your array looks like on console
by printing it
6th
Now this is what we want ,,,
Go ahead
smash it!!
The idea behind is to see the problem in terms of application of partition technique…
Strictly speaking we do not need a somewhat ad-hoc approach
Elementary knowledge of the partition will work
So use it…
It has so much to yield evertime…
Got correct ans-
here it is for your test cases-
5
2 2 5
0
0
10
4 2 4 6 7
25
4 2 3 4 6
https://www.codechef.com/viewsolution/38110243
Can anyoe tell the mistake i my soln’
Thanks in advance
I generally notice that if a problem is very easy to code codechef tags it as easy even though the complexity of coming up with the solution is not easy and needs out of the box thinking.
Thanks for the video editorial such a nice explanation with correctness
Hey pls tell me what is wrong here
#include
#include
using namespace std;
#define ll long long
int main()
{
ll t;
cin>>t;
while(t–)
{
ll n;
cin>>n;
ll a[n];
ll ans=0;
ll p=0;
vector vekt;
for(ll i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>0)
{
ans+=a[i];
p++;
}
}
if(ans==0|| p==n)
{
cout<<ans<<endl;
cout<<“0”<<endl;
continue;
}
for(ll i=0;i<p;i++)
{
if(a[i]<0)
vekt.push_back(i+1);
}
for(ll i=p;i<n;i++)
{
if(a[i]>=0)
vekt.push_back(i+1);
}
cout<<ans<<endl;
cout<<p<<" “;
for(auto go:vekt)
{
cout<<go<<” ";
}
cout<<endl;
}
}
https://www.codechef.com/viewsolution/38135024
The solution is based on the following understanding:
Suppose I have numbers -1 1 2 -3 -4 4 -5
Then I look up for the first sequence of negative numbers after a positive number is encountered. (In this case -3, -4). The index of the negative numbers are stored till I encounter a positive number.
Then in future all positive number indexes are stored (in this case index 6 for number 4).
Finally I have indexes 4 5 6 on the above case which is correctly reversing for the problem statement.
I took care of all corner cases as far as I am aware. However I am unable to find any error. I ran my code on countless test cases.
Can anyone help me?
I’m getting TLE for this code.
Is it because I used Stream API?
void main() throws IOException {
int T = in.ri();
while (T-- > 0) {
int N = in.ri();
ArrayList a = in.riaa(N);
int P = 0;
for (Integer integer : a) {
if (integer > 0) P++;
}
ArrayList toBeRev = new ArrayList<>();
for (int i = 0; i < P; i++) {
if (a.get(i) < 0) {
toBeRev.add(i + 1);
}
}
//out.prln(toBeRev);
for (int i = P + 1; i < a.size(); i++) {
if (a.get(i) > 0) {
toBeRev.add(i + 1);
}
}
a.sort(Comparator.reverseOrder());
int sum = a.stream().filter(x → x > 0).mapToInt(x → x).sum();
System.out.println(sum);
if (toBeRev.size() > 0) {
toBeRev.forEach(x → System.out.print(x + " "));
System.out.println();
} else {
System.out.println(0);
}
}
}
Why do we need to create a separate index list for negative numbers. The required sum that is the maximum sum is formed by the positive numbers only . Hence we can print only the positive numbers in the array. Why do we need negative numbers to be printed as well?