RAINBOWA! [trying since 2 days]

help
1

Hello!
QUESTION HERE

I’ve thinking, been debugging about this question since some days. BUT NO FRUITS!.
It is passing the example but NOT the cases can SUPERHUMAN spot the problem .

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

int main()
{

    int t;
    cin>>t;
    ++t;
    while(--t)
    {
        int l,el,mpos;

        cin>>l;
        vector<int> v;
        bool flag1=0,flag2=0;
        for(int i =0;i<l;++i)
        {
            cin>>el;
            v.push_back(el);

        }
        if(l%2!=0)
        {
            mpos=((l+1)/2)-1;

        }else{
            mpos = (l/2)-1;
        }

        for(int i = 1;i<=v.at(mpos);++i) // checked for missing piece
        {
            if (count(v.begin(),v.end(),i) == 0){
                flag1 = 0;
                break;
            }else{
            flag1 = 1;


            }
        }

    // cond-2
    int sz = v.size();
    for(int i=1;i<sz;++i)
    {
        if(v[i-1]!=v[sz-i])
        {
            flag2=0;
            break;
        }
        else{
        flag2 = 1;}


    }





    if(flag1==0 or flag2==0){
    cout<<"no"<<"\n";
    }
    else{
        cout<<"yes"<<"\n";
    }





    }

}
2

Hello,

I think the issue here is that your program isn’t checking whether the numbers are in the right order.

One of the requirements is that the array have an ordering of:
1 → 2 → 3 → 4 → 5 → 6 → 7 → 6 → 5 → 4 → 3 → 2 → 1

, but when I ran your program with:

2 1 3 4 4 5 6 6 6 7 6 6 6 5 4 4 3 1 2

, it still outputted “yes”, despite the order being wrong (having a 2 appear before a 1).

That seems to be the main issue, so if you implement some check for the order of the elements, then it should work out.

I have a working modification of yours (EDIT: This is the updated code) here if you’d like to check it out, but you are super close, so I’d say you can finish it yourself.

I honestly can’t say my program is 100% correct, because it was written on the fly, but it passes at least.

Hope this helps.

-Nick

3

Hello!

/* This will be checked later in the program
        for(int i = 1;i<=v.at(mpos);++i) // checked for missing piece
        {
            if (count(v.begin(),v.end(),i) == 0){
                flag1 = 0;
                break;
            }else{
            flag1 = 1;


            }

How does your code satisfy this statement. Is it by this :

if(i > 1 && v[i-1] - v[i-2] > 1){
            
            flag1 = 0;
            break;
            
        }

What mine does is it goes till the range of middle element and finds out if there is any missing piece present.

4 
for(int i=1;i-1<=l-i;++i)
    {
        if(v[i-1]!=v[l-i]) // term from start = term from last

Why The ABove works. But Below doesn’t.
What is the difference in ABOVE?

sz= v.size();
for(int i=1;i-1<=sz;++i)
    {
        if(v[i-1]!=v[l-i]) // term from start = term from last

Is the difference is that:-

  • Yours ones check till the middle element that is if the difference between elements condition is checked it happens till the middle one?

Please Clear My Question
Thanks
Sincerely
Arnav

5

Yeah, the v[i-1] - v[i-2] > 1 part is meant to complete the same check.

Also, sorry! One part of my program is actually incorrect (I’ll get to that in a minute).

Here is how it works:

In order for the array to be a valid rainbow, we know it has to go from 1 to 2 to 3, etc.
We also know that there can be any number of 1’s, 2’s, etc. So there are two valid transitions between array elements:

  1. where v[i] = v[i+1], e.g. 3 → 3
  2. where v[i] + 1 = v[i+1], e.g. 2 → 3

From the initial check before the final loop (v[0] == 1), we can confirm that the starting value is 1.

At the final check, we also know that the middle element is 7 (v[l/2] == 7).

If either of them is false, then we can already say “no” is our answer, otherwise this check will work:

Knowing that our starting value is 1 and our mid value is 7, all we need to make sure, is that between each element, the value is either staying the same, or increasing by one.
If it does that, and starts at 1 and ends at 7 at the middle, then we know it made a valid half of the rainbow, because it would have had to pass through all valid numbers in an increasing way to reach 7 from 1.

That is what the if statement is looking for, it checks if that difference isn’t 0 or 1, in which case an invalid transition is made and the result will be “no”.

Since we are also making sure the value on the first half is the same as on the second half, this means we have a valid complete rainbow as well.

I need to add though, that the if statement I used actually isn’t correct, I forgot to add a check for a negative transition, because obviously we don’t want it going from a larger value back down to a smaller one, e.g. 1->2->1->2 looks correct to the current if statement even though it isn’t.

You will want to change the if to:
(i > 1 && (v[i-1] - v[i-2] > 1 || v[i-1] - v[i-2] < 0)
,to account for the negative transition as well.

-Nick

1 Like
6

Yep, stopping at the middle versus the end makes a difference.

Think of it this way:

You have a good array like this: 1 2 3 4 5 6 7 6 5 4 3 2 1

The program is iterating up to the middle, and everything is good, the transitions are proper, the elements in the first half and the second half are the same, and it has a 1 at the beginning and a 7 at the middle.

However, once you pass the middle element (the 7), you hit a 6.

We know that the array is proper, but because it is transitioning back down to a lower number, the program will think it’s wrong going from 7 → 6.

You could have a check for this and reverse the way the program looks at proper transitions when it reaches the halfway point, but that is a redundant calculation, because the v[l-i] is already checking the back half of the array.

I apologize, because the way I wrote that if statement before (in your other comment) would create some odd results with the loop going all the way to the end. That is because if didn’t check to fail those negative transitions.

I hope this clears up the issue.

-Nick

1 Like
7

Thanks a Lot For Clearing my doubt!
I’m a begginer [not working with c++ for more than 1 week yet]
Can you or anyone please tell me what the error means here:-
https://discuss.codechef.com/t/stack-smashing-error-cops-dangerous-logic/96635/13