Count the Chaos

Discussions Toph Problems
2

What is the problem in my code.

a=int(input())
c=0
x=list(map(int,input().split()))
for i in range(len(x)):
    for j in range(i,len(x)):
        if x[i]>x[j]:
            c+=1
print(c)

Please help me

3

The first criteria is that i < j.

But in your nested loop, i will always be greater than j.

Your outer loop is starting i from 0. And your inner loop is starting j from i. While i is at any value, j will start from i and will be incremented until it is len(x).

4

Is there any way to solve this problem without using merge sort?

5

Yes.

Hint: Check the tags of the problem. :slight_smile:

1 Like
6 
n=int(input())
num=list(map(int, input().split()))[:n]
count=0

for j in range(n):
    for i in range(j):
        if num[i]>num[j]:
            count=count+1

print(count)

Help me

7

This kind of approach will not work here. You will get TLE.
You have to a more efficient way to solve the problem.
You can learn counting inversions with merge sort after you have learnt merge sort.
To learn merge sort, see this.
To know how to count inversions using merge sort, see this

8 
unsigned long long int n,t=0,a,b;
    cin>>n;
    int A[n];
    for(a=0; a<n; a++)
    {
        cin>>A[a];

            for(b=0;b<a;b++)
            {
                if(A[a]<A[b])
                {
                    t++;
                }
            }
    }
    cout<<t<<endl;

the code isn’t effecient enough
can anyone send me an efficient code please

9

@PIS_Shami
I have already answered your question above.

10 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int c=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(a[i]>a[j])
                c++;
        }
    }
    cout<<c;
}

what’s the problem this code?please help me.(CLE?)

11

What’s wrong with my code.
On the last test case it say CPU limit exceeded.

#include <stdio.h>

int main()
{
    int N,i,j,result;
    result=0;
    scanf("%d",&N);
    int num[N];

    for(i=0;i<N;i++){
        scanf("%d",&num[i]);
    }

    for(i = 0; i < N; i++){
        for(j = i+1; j < N; j++){
            if(num[i] > num[j]){
                result++;}
        }
    }
    printf("%d",result);
    return 0;
}
12

Why all submissions not rejudged after adding test case 7??

13

Yes.
you can use policy base data structure.Here my solution base to pbds https://pastebin.com/KAC8Cj72

14

my solution isn’t efficient ok fine… but I tried the same logic as this submission https://toph.co/s/324356 why not getting AC!

15

Why there is no python solution?
Is this a bug or something?
@hjr265

16

TL : 1e5 but N_sqaure is nicely working here ! lol
cases should be stronger !

1 Like
17

Thank you for the feedback, @MR.Jukerburg11.

An additional test case has been added.

It seems your last submission is now getting a “Wrong Answer”. I can see a reason for it in your code. May be take another go at it? :slightly_smiling_face:

18

but i expect tle , everyone is getting ac with n sqaure, how is it possible at 1e5… i was cheking but my code got ac. i think test case is still weak . chk the shortest code

19

The shortest code would also get a WA now for the newly added test case. And if same bug in that code was corrected (which is also present in your code), then it would get a TLE for both of the last two cases.

But since that submission is from a contest, we won’t rejudge it.

20

Something goes wrong in the test case 8. This test case should be rechecked

21

Can you provide the solution again? I have used pbds but it’s getting WA on test case 8