An odd permutation is one that can be reached by an odd number of two-element swaps.
This is not an odd permutation since it can be reached in four swaps.
1 2 3 4 5 6 7
6 2 3 4 5 1 7
7 2 3 4 5 1 6
7 3 2 4 5 1 6
7 3 5 4 2 1 6
3 Likes
oh I see, can you please review my code once??
I’ve tried a lot but I can’t find where my code is failing
I can’t figure out your exact approach. Can you just brief me?
Odd permutation means it has odd number of inversions.
refer to the above question
1 Like
if in case first and second were to be swapped with each other(7 6 5 4 3 2 1 eg 1 and 7) then we cannot find our required “three” so we choose third index randomly which is not at its correct position
if we cannot find third at all, then it means only 2 numbers are at wrong position so its impossible to sort…
Ive divided array into two parts and if later part is completely sorted then i have changed the position of “end”
and when start > end is achieved; array is sorted
One of the mistakes I could find on a quick glance is that you’re actually ‘left-shifting’. This shouldn’t matter as long as you’re getting elements at their right position but you also have to print the sequence of moves you made.
Also why are you sorting them? This will make the sequence of the triplet wrong.
It probably worked for the example test case because there were only three at wrong positions and the answer was 1 3 4 (which is in ascending order).
1 Like
I tried both with sorting and without sorting.
but when I sorted them, one part of subtask got cleared so I used that
Don’t sort. You need i j k in the order you made the shifts. Just fix your code to do ‘right-shift’ instead of ‘left-shift’. Let’s see if that works.
1 Like
I will advice you to try for following two test cases :
11
2 1 5 7 6 11 4 10 3 9 8
output:
3 5 6
3 11 8
3 10 9
1 2 4
1 7 4
test case 2:
9
9 8 7 3 2 4 6 5 1
output:
2 8 5
3 7 6
1 9 3
3 1 4
i too faced similar issue, pondering these two made me do it.
happy coding.
best wishes
3 Likes
And it will be too kind if you tell me what should I study from now on…What are some of the must know things to level up myself.
PS:
I just got 3rd star and have no idea what to study next. Thanks for sharing your solution unfortunately I am not capable enough to understand it.
Brother I see you doing left shifts…unfortunately I too did nearly 30 wrong submissions just because I was doing left shift thinking it as right shift.
Happy coding.
Best wishes
Thankyou so much brother! It was only left shift issue 
too bad I couldn’t correct it in time…
1 Like
I realised the mistake bro; thanks a lot for your time
Could someone help me out in finding out at which test case my code would fail for the first sub task:
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
void solve()
{
lli n = 0, k = 0;
cin >> n >> k;
vector result[k];
lli A[n + 1];
for (lli i = 1; i <= n; i++)
cin >> A[i];
lli start = 1, end = n, v1 = end - 1, count = 0;
bool notPossible = false;
while (start < end)
{
if (count >= k)
{
notPossible = true;
break;
}
if (end != start + 1)
{
result[count].push_back(v1);
result[count].push_back(start);
result[count].push_back(end);
}
else
{
result[count].push_back(start);
result[count].push_back(end + 1);
result[count].push_back(end);
}
start++;
v1–;
end–;
count++;
}
if (!notPossible)
{
cout << count << ‘\n’;
for (lli i = 0; i < count; i++)
{
for (auto j : result[i])
{
cout << j << ’ ';
}
cout << ‘\n’;
}
}
else
cout << -1 << ‘\n’;
}
int main()
{
lli t = 0;
cin >> t;
while (t–)
solve();
return 0;
}
Hello fellow coders,could anyone help me and tell me why my code shows TLE for some of the subtasks(AC for some),it would help me a lot.Thanks!!
https://www.codechef.com/viewsolution/32987278
This line is somewhat misleading, by permutation I think he meant the permutations where the number of swaps(required to sort) are odd. Because a permutation like for ex 15324 is of odd length but is easily sortable with 2 shifts 15324 -> 14352 -> 12345
After reading this editorial, i feel lucky enough to score 50
https://www.codechef.com/viewsolution/32913571
- I just made a right shift on some (j)th-index with (arr[j]-1)th index and “(arr[arr[j]-1]-1)th-index” (if it was not equal to first and second index ,or if it was , i choose any arbitrary position from the right of the array which is on its wrong position)
- This approach passes all test cases expect last… Can anyone suggest where it goes wrong??
Even and odd in the case of permutations always means the parity of the permutation and not the order of the group. I think its clear enough
Please indent your code. It makes for a much pleasurable experience. You can even link your submissions like this. Does your code work when the array is already sorted?
Hello coders,could anyone help me and tell me why my code fails ( or test cases where it can fail) for two of the subtasks , it would help me a lot. Thanks!!
here is my code: CodeChef: Practical coding for everyone