Codeforces 598 B doubt

Can someone please explain where my code is going wrong for the following problem ?

Problem link : http://codeforces.com/contest/1256/problem/B

The question is to print the lexicographically smallest array by doing atmost n-1 consequtive swaps . Each pair i,i+1 must be swapped only once .

My code :

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		int a[n+1];
		for(int i = 1 ; i <= n ; i++ ){
			cin >> a[i];
		}
		int m = n-1,k=1,pos;
		while(m>0)
		{
			for(int i = 1 ; i<=n ; i++  ){
				if(a[i]==k){
					pos = i;
					break;
				}
			}
			if(pos<k)
			{
				while(m>0 && pos!=k && pos<n){
					swap(a[pos],a[pos+1]);
					m--;
					pos++;
				}
			}
			else if(pos>k)
			{
				while(m>0 && pos!=k && pos>1){
					swap(a[pos],a[pos-1]);
					m--;
					pos--;
				}
			}
			k++;
			if(k==n && a[n]==n){
				break;
			}
		}
		for(int i = 1 ; i<=n ; i++ ){
			cout<<a[i]<<' ';
		}
		cout<<'\n';
	}
}

Does anyone know why is codeforces down? Would the round be rated?

4 Likes

The site went down like half an hour before the end

4 Likes

Test Case :
1
5
1 4 3 2 5
Output :
1 2 4 3 5
While Your code gives 1 2 3 4 5.
you need to make sure if you swap i with i+1 then that i can’t be used again.

5 Likes

in addition to using each unique operation atmost once, you also need to check if the number on the left is greater than the number being considered, if not then don’t swap and break.

1 Like

Try this, I think it will give an error
Test Case:
1
6
4 2 5 6 1 3

3 Likes

Check this test case:
1
1 2 6 5 4 10 7 5 9 3
This test case will give an error. I cross checked it.

3 Likes

Thanks a lot everyone , by the way where am i reusing the i,i+1 pair . in the above inputs . @naveen19991124

You are reusing it ,try to debug the above test cases you will automatically become acknowledged.

3 Likes

Got it !! I thought that a[i] and a[i+1] should be swapped atmost once instead i,i+1 positions :slight_smile:

1 Like

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

int find_min_ind(int arr[],int l,int r)
{
int minn=l;
for(int i=l+1;i<=r;i++)
{
if(arr[i]<arr[minn])
{
minn=i;
}
}

return minn;

}

void fun(int arr[],int n)
{
int left=0,right=n-1;
int count=0;
int i=find_min_ind(arr, left, right);
while(count<n-1)
{

    if(i!=0 && arr[i]!=i+1)
    {
        swap(arr[i],arr[i-1]);
        i=i-1;
        count++;
        
    }
    else
    {
        if(left<right)
        	i=find_min_ind(arr,left+1, right);
        
    }
   
}

for(int i=0;i<n;i++)
{
    cout<<arr[i]<<" ";
}
cout<<endl;

}
int main()
{
int q;
cin>>q;

while(q--)
{
    int n;
    cin>>n;
    
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    if(n==1)
    {
        cout<<arr[0]<<endl;
    }
    else
    {
    
    
        fun(arr,n);
    }
    
    
    
    
}
return 0;

}

what is wrong with this too??
give time limit exceed

https://codeforces.com/contest/1256/submission/64262040
check this one

1 Like

Can you please explain your code , what is the logic behind it?

since we want smallest possiboe array and we can perform one kind of oepration only once i find out the min element and bring it to its position now see all moves before its real pos has been used so i updated s likewise

I was also stuck trying to think about this Problem.Can you explain me what is lexicographically minimum Possible combination. and To approach for this Problem.

Logic to solve B
Intuition was easy but implementation was difficult.

Now we need to check in every pass minimum value in between a particular set of indices i to n and place it at front at i and shift each value one step beyond… for example we have 5 4 1 3 2 now when we traversed for first time we got minimum value as 1 and at index 2 so we swap indices 2 and 1 then indices 1 and 0 to get 1 in front then in another pass we will start from indices 2 to indices n and then find the minimum again as at index 4 then we will swap indices 4 and 3 then indices 3 and 2 to get the final array 1 5 2 4 3 to satisfy the condition that no two indices can be swapped again.

Solution link