C++

Forum

 
good permutations

closed account (287LhbRD)
This is my code for "good permutations " on codechef
i am getting correct ans for test case but wrong ans on submitting

https://www.codechef.com/problems/GOODPERM
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
 #include<bits/stdc++.h>
using namespace std;


int is_valid(int *d, int n, int k)
{
    int counter = 0;
    
    for (int i = 1; i < n; i++)
    {
        if (d[i] > d[i - 1])
        {
            counter ++;
        }
    }
    if (counter == k)
	 return 1;
	 
	 
    return 0;
}




int main(){
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		
		int a[n];
		
		for(int i=0;i<n;i++)
		cin>>a[i];
		
		int pos[n];   // to find the positions of zeroes
		int j=0; 
		 
		int arr[8]={1,2,3,4,5,6,7,8};    // default
		 
		
		int m;    // no of zeroes in array
		
	     for(int i=0;i<n;i++)
		{
				if(a[i]==0)
			{
			pos[j]=i;
			j++;
			m=j;
		     }
		     
	    }
		
		for(int i=0;i<n;i++){
			  
			for(int j=0;j<8;j++){
				
				if(a[i]==arr[j])  // just substitute the values of arr as 0 if it is present in array "a" 

				arr[j]=0;
					
			}  
			
		}
		
		int c=0;
	
         int b[m];	 // array which will replace zeroes in "a"
		 
		 		
		for(int i=0;i<m;i++)
		{
			
			while(arr[c]==0)// so that values in "a" don't repeat
			c++;
		
			b[i]=arr[c];			
			c++;
		}
		
		int count=0;
	do	
	{
		int l=0;
		
		int p[n];    // final array in which zeroes are replaced
		
		for (int i = 0; i < n; i++)
            {
                if (a[i])
                {
                    p[i] = a[i];      
                }
                	// if a[i] is 0 replace the value

                else
                {
                    p[i] = b[l];
                    l++;
                   // cout<<p[i]<<" ";
                }
            }
            //cout<<endl;
		
		
		   if (is_valid(p, n, k))
            {
                count++;
            }
        
		} while (std::next_permutation(b,b+m));
		
		
        
		   cout<<count<<endl;
		   

	}
	
	
	
	return 0;
}
I have edited the code with comments
Last edited on
tpb (1495)
I'm not sure what's going on in your code, but here's a working version I came up with.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
#include <iostream>
#include <algorithm>

bool is_valid(int *a, int n, int k) {
    int cnt = 0;
    for (int i = 1; i < n; i++)
        if (a[i] > a[i - 1])
            cnt++;
    return cnt == k;
}

int main(){
    using std::cin;
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;

        int a[8];
        bool x[9] = {false}; // x[i] is true if i is present in a

        for (int i = 0; i < n; i++) {
            cin >> a[i];
            x[a[i]] = true;
        }

        // b contains the missing numbers.
        int b[8], nb = 0, f = 1; // max f is 8! == 40,320
        for (int i = 1; i <= n; i++)
            if (!x[i]) {
                b[nb++] = i;
                f *= nb;
            }

        int cnt = 0;
        for (int i = 0; i < f; i++) {
            int c[8];
            for (int j = 0, k = 0; j < n; j++)
                c[j] = a[j] ? a[j] : b[k++];
            if (is_valid(c, n, k))
                ++cnt;
            std::next_permutation(b, b + nb);
        }

        std::cout << cnt << '\n';
    }
}

closed account (287LhbRD)
Thanks for the solution.
Can someone please spot the error in my solution?
i have tried many cases it's working but giving wrong ans on codechef.
tpb (1495)
It's too bad we can't get the test data that chef is using.
I'll take a look at your code, though
You should edit your original post and repaste your code in code tags to preserve indentation so that people are more likely to actually try to read it. Even more so if you add a comment or two explaining your reasoning.

[code]
your code here
[/code]

EDIT: I took another look at your code. I doesn't make sense to me so I can't help you with it.
Last edited on
closed account (287LhbRD)
Could you please check it again?
I have edited the code with comments.
lastchance (6980)
@shreyk5,

Your code would be illegal in standard C++: you can't declare "standard" array sizes at run time. For example, a line like
int a[n];
is not valid. Nor is it necessary, because you are actually given a maximum size for arrays as one of the constraints. This is only allowed as a non-standard extension by some compilers because some languages (like the C99 version of C, or for allocatable or automatic arrays in Fortran) do permit VLAs (variable-length arrays).

Your comments aren't helpful, I'm afraid - nor is your indentation nor your naming of variables (a,b,c,...). No idea what your pos[] array was intended for, but nothing in it is ever used.

The sequence given in the codechef example is not very representative - you should make up a few of your own. Make sure that you look at all the "special cases" - e.g. no zeroes.

Why don't you add a few lines to isValid() to print out which permutations you are actually using. Then you may be able to debug.

As the competition is no longer live and it's relegated to a "practice" exercise, here's a version using vectors. It is probably doing something akin to your code, or, at least, your intention, but I don't understand your code enough to judge.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//======================================================================

bool isGood( int N, int K, const vector<int> &p )          // Check permutation for "good"ness
{
   int num = 0;
   for ( int i = 1; i < N; i++ )
   {
      if ( p[i] > p[i-1] )
      {
         num++;
         if ( num > K ) return false;
      }
   }
   return ( num == K );
}

//======================================================================

int process( int N, int K, vector<int> &a )                // Process a single sequence
{
   vector<bool> notUsed( N + 1, true );                    // Not using the [0] index here
   vector<int> freeValue, freePosition;

   // Find the available slots and values
   for ( int i = 0; i < N; i++ )
   {
      if ( a[i] ) notUsed[a[i]] = false;
      else        freePosition.push_back( i );
   }
   for ( int i = 1; i <= N; i++ )
   {
      if ( notUsed[i] ) freeValue.push_back( i );
   }

   // Special case with no free slots - just check original sequence
   if ( !freePosition.size() ) return (int)isGood( N, K, a );

   // Now create all permutations and check them
   int nGood = 0;
   do
   {
      for ( int i = 0; i < freePosition.size(); i++ ) a[freePosition[i]] = freeValue[i];
      if ( isGood( N, K, a ) ) nGood++;
   } while ( next_permutation( freeValue.begin(), freeValue.end() ) );

   return nGood;
}

//======================================================================

int main()
{
   int T;                    // Number of tests
   int N, K;                 // Length of sequence; number in order

   cin >> T;
   while( T-- )
   {
      cin >> N >> K;
      vector<int> a( N );
      for ( int i = 0; i < N; i++ ) cin >> a[i];
      cout << process( N, K, a ) << '\n';
   }
}

//======================================================================

Last edited on
closed account (287LhbRD)
Thanks @lastchance for your code.
My code is now working.I had missed a special case where n is 1 and k is 0.
Sorry for the poor variable naming.
I am trying to improve.
Topic archived. No new replies allowed.