Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Triple Sort CodeChef Solution
Problem -Triple Sort CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Triple Sort CodeChef Solution in C++17
#include <iostream>
#include <vector>
using namespace std;
struct Operation {
int a, b, c;
Operation(int v1, int v2, int v3) : a(v1), b(v2), c(v3) {}
void print(){
cout << (this->a+1) << ' ' << (this->b+1) << ' ' << (this->c+1) << '\n';
}
};
inline void solve(){
int N, K;
cin >> N >> K;
int arr[N];
int pos[N];
int last_swap = -1;
vector<Operation> operations;
for (int i = 0; i < N; i++){
cin >> arr[i];
arr[i] -= 1;
pos[arr[i]] = i;
}
for (int i = 0; i < N; i++) {
if (arr[i] != i) {
if (pos[pos[i]] == i) {
if (last_swap == -1) {
last_swap = i;
} else {
if (pos[last_swap] == i) continue;
operations.emplace_back(last_swap, pos[last_swap], i);
operations.emplace_back(i, last_swap, pos[i]);
arr[last_swap] = last_swap;
arr[pos[last_swap]] = pos[last_swap];
arr[i] = i;
arr[pos[i]] = pos[i];
last_swap = -1;
}
} else {
operations.emplace_back(i, pos[pos[i]], pos[i]);
arr[pos[pos[i]]] = arr[i];
pos[arr[i]] = pos[pos[i]];
arr[i] = i;
arr[pos[i]] = pos[i];
}
}
}
if (last_swap != -1){
cout << -1 << '\n';
return;
}
if (operations.size() > K) {
cout << -1 << '\n';
return;
} else {
cout << operations.size() << '\n';
}
for (auto& operation : operations){
operation.print();
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--){
solve();
}
}Triple Sort CodeChef Solution in PYTH 3
# cook your dish here
for tc in range(int(input())):
n, k = [int(a) for a in input().split()]
a = [0] + [int(a) for a in input().split()]
res = []
for i1 in range(1, n):
while a[i1] != i1 and a[a[i1]] != i1:
i2 = a[i1]
i3 = a[i2]
res += [[i1, i2, i3],]
a[i2], a[i3], a[i1] = i2, i3, a[i3]
pair = [(i1, a[i1]) for i1 in range(1, n + 1) if a[i1] > i1]
if len(pair) % 2:
print(-1)
else:
while pair:
i1, i2 = pair.pop()
i3, i4 = pair.pop()
res += [[i1, i2, i3], [i1, i4, i3]]
print(len(res), *["\n" + ' '.join(map(str, r)) for r in res])Triple Sort CodeChef Solution in C
#include <stdio.h>
void swap(int *p,int *q)
{
int temp;
temp=*p;
*p=*q;
*q=temp;
}
int main(void) {
// your code goes here
int t,n,k,m,flag,i,count,a,b,c,j;
scanf("%d",&t);
while(t--)
{
m=0;flag=1;
scanf("%d %d",&n,&k);
int arr[n+1],ans[k+1][3];
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
}
for(i=1;i<=n;i++)
{
if(arr[i]!=i)
{
a=i;b=arr[i];
if(arr[b]!=a)
{
c=arr[b];
swap(&arr[a],&arr[b]);
swap(&arr[c],&arr[a]);
ans[m][0]=a;
ans[m][1]=b;
ans[m][2]=c;
m++;
i--;
}
}
}
for(i=1;i<=n;i++)
{
if(arr[i]!=i)
{
a=i;b=arr[i];
if(arr[b]!=a)
{
c=arr[b];
swap(&arr[a],&arr[b]);
swap(&arr[c],&arr[a]);
ans[m][0]=a;
ans[m][1]=b;
ans[m][2]=c;
m++;
i--;
}
else
{
for(j=1;j<=n;j++)
if((arr[j]!=j)&&(j!=i)&&(j!=arr[i]))
{
c=j;
swap(&arr[a],&arr[b]);
swap(&arr[c],&arr[a]);
ans[m][0]=a;
ans[m][1]=b;
ans[m][2]=c;
m++;
i--;
break;
}
}
}
}
for(i=1;i<=n;i++)
{
if(arr[i]!=i)
{
flag=0;break;
}
}
if(flag==1)
{
printf("%d\n",m);
for(i=0;i<m;i++)
printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
}
if(flag==0)
printf("-1\n");
}
return 0;
}
Triple Sort CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{ static AnotherReader scn;
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
scn=new AnotherReader();
int t=scn.nextInt();
while(t-->0){
int N=scn.nextInt();
int k=scn.nextInt();
int arr[]=new int[N+1];
for(int i=1;i<=N;i++){
arr[i]=scn.nextInt();
}
solve(arr,k,N);
}
}
public static void solve(int[]arr,int k,int N) {
//arr started its indexing at 1
ArrayList<Triplet>triplet=new ArrayList<>();
ArrayList<Pair>doub=new ArrayList<>();
boolean visited[]=new boolean[arr.length];
Arrays.fill(visited, false);
for(int i=1;i<=N;i++)
{
if(visited[i]==false) {
int j=i;
Deque<Integer>cycle=new LinkedList<Integer>();
while(visited[j]==false) {
visited[j]=true;
cycle.add(j);
j=arr[j];
}
while(cycle.size()>2) {
int z=cycle.pollLast();
int y=cycle.pollLast();
int x=cycle.peekLast();
triplet.add(new Triplet(x,y,z));
if(cycle.size()==1) {
cycle.pollLast();
}
k=k-1;
}
if(cycle.size()==2) {
doub.add(new Pair(cycle.poll(),cycle.poll()));
}
}
}
//we can even calculate size of triplet at the end to see if matched with original K then
//ans is possible else not
// also x is the connecting index if cycle contains elements more than 3 thus peekLast is used here
while(doub.size()>1) {
Pair one=doub.remove(0);
Pair two=doub.remove(0);
triplet.add(new Triplet(one.b,two.a,two.b));
triplet.add(new Triplet(one.a,one.b,two.a));
k=k-2;
}
if(doub.isEmpty()==false) {
System.out.println("-1"); return;
}
if(k<0) {
System.out.println("-1");
}else {
System.out.println(triplet.size());
for(Triplet trip:triplet) {
System.out.println(trip.x+" "+trip.y+" "+trip.z);
}
}
}
static class Triplet{
int x;int y;int z;
Triplet(int x,int y,int z){
this.x=x;
this.y=y; this.z=z;
}
}
static class Pair{
int a;int b;
Pair(int a,int b){
this.a=a; this.b=b;
}
}
static class AnotherReader {
BufferedReader br;
StringTokenizer st;
AnotherReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || st.hasMoreElements() == false) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
}
}
//time complexity is O(nlogn)Triple Sort CodeChef Solution in PYPY 3
for tc in range(int(input())):
n, k = [int(a) for a in input().split()]
a = [0] + [int(a) for a in input().split()]
res = [] # to store the transpositions
for i1 in range(1, n):
while a[i1] != i1 and a[a[i1]] != i1: # solving individual connected components
i2 = a[i1]
i3 = a[i2]
res += [[i1, i2, i3],]
a[i2], a[i3], a[i1] = i2, i3, a[i3]
pair = [(i1, a[i1]) for i1 in range(1, n + 1) if a[i1] > i1]
if len(pair) % 2 == 1:
print(-1)
else:
while pair:
i1, i2 = pair.pop()
i3, i4 = pair.pop()
res += [[i1, i2, i3], [i1, i4, i3]]
print(len(res), *["\n" + ' '.join(map(str, r)) for r in res])Triple Sort CodeChef Solution in PYTH
t = int(raw_input())
for i in range(t):
st = raw_input().split()
N = int(st[0])
K = int(st[1])
st = raw_input().split()
A = [0]
for x in st:
A.append(int(x))
# endfor x
L = []
P = []
for r in range(1,N+1):
while A[r] != r:
a = r
b = A[a]
c = A[b]
d = A[c]
if c == a:
P.append([a,b])
A[a] = a
A[b] = b
else:
L.append([a,b,c])
A[a] = d
A[b] = b
A[c] = c
# endif
# endwhile
# endfor r
sz = len(P)
if sz%2 == 1:
print '-1'
else:
r = 0
while r < sz:
a = P[r][0]
b = P[r][1]
r += 1
c = P[r][0]
d = P[r][1]
L.append([a,b,c])
L.append([a,d,c])
r += 1
# endwhile
n = len(L)
print n
for x in L:
print x[0], x[1], x[2]
# endfor x
# endif
# endfor i
Triple Sort CodeChef Solution in C#
#region Usings
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static System.Array;
using static System.Math;
#endregion
partial class Solution
{
public void Solve()
{
int T = Ni();
for (int t = 1; t <= T; t++)
{
int N = Ni();
int K = Ni();
int[] P = Ni(N, 1);
bool[] seen = new bool[N + 1];
var cycles = new List<List<int>>();
int parity = 0;
for (int i = 1; i <= N; i++)
{
if (seen[i])
continue;
var cycle = new List<int>();
int j = i;
while (!seen[j])
{
seen[j] = true;
cycle.Add(j);
j = P[j];
}
if (cycle.Count > 1)
cycles.Add(cycle);
parity += cycle.Count - 1;
}
if (parity % 2 == 1)
WriteLine(-1);
else
{
var list = new List<string>();
cycles.RemoveAll(c =>
{
for (int x = 1; x + 1 < c.Count; x += 2)
list.Add($"{c[0]} {c[x]} {c[x + 1]}");
if ((c.Count & 1) == 1)
return true;
c.RemoveRange(1, c.Count - 2);
return false;
});
for (int i = 0; i < cycles.Count; i+=2)
{
var c1 = cycles[i];
var c2 = cycles[i + 1];
list.Add(c1[0] + " " + c1[1] + " " + c2[0]);
list.Add(c1[0] + " " + c2[1] + " " + c2[0]);
}
WriteLine(list.Count);
foreach (var c in list)
WriteLine(c);
}
}
}
#region Library
#region Mod Math
const int MOD = 1000000007;
static int[] _inverse;
static long Inverse(long n)
{
long result;
if (_inverse == null) _inverse = new int[100001];
if (unchecked((ulong)n < (ulong)_inverse.Length) && (result = _inverse[n]) != 0)
return result - 1;
result = InverseDirect((int)n);
if (unchecked((ulong)n < (ulong)_inverse.Length))
_inverse[n] = (int)(result + 1);
return result;
}
public static int InverseDirect(int a, int mod = MOD)
{
int b = mod, p = 1, q = 0;
while (b > 0)
{
int c = a / b, d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
return p < 0 ? p + mod : p;
}
static long Div(long left, long divisor) =>
left * Inverse(divisor) % MOD;
static long Fix(long n) => (n %= MOD) >= 0 ? n : n + MOD;
static long ModPow(long n, long p, long mod = MOD)
{
long b = n;
long result = 1;
while (p != 0)
{
if ((p & 1) != 0)
result = result * b % mod;
p >>= 1;
b = b * b % mod;
}
return result;
}
static int[] _fact = new int[] { 1, 1, 2, 6 };
static int[] _ifact = new int[] { 1 };
static long Fact(int n)
{
if (n >= _fact.Length)
{
int prev = _fact.Length;
Ensure(ref _fact, n);
for (long i = prev; i < _fact.Length; i++)
_fact[i] = (int)(_fact[i - 1] * i % MOD);
}
return _fact[n];
}
static long InvFact(int n)
{
if (n >= _ifact.Length)
{
int prev = _ifact.Length;
Ensure(ref _ifact, n);
_ifact[_ifact.Length - 1] = InverseDirect((int)Fact(_ifact.Length - 1));
for (long i = _ifact.Length - 1; i > prev; i--)
_ifact[i - 1] = (int)(_ifact[i] * i % MOD);
}
return _ifact[n];
}
static long Fact(int n, int m)
=> m < n
? Fact(n) * InvFact(n - m) % MOD
: m == n ? Fact(n) : 0;
static long Comb(int n, int k)
=> k > 1
? Fact(n) * InvFact(k) % MOD * InvFact(n - k) % MOD
: k == 1 ? n : k == 0 ? 1 : 0;
#endregion
#region Common
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Ensure<T>(ref T[] array, int n)
{
if (n >= array.Length)
Resize(ref array, Max(n + 1, array.Length * 2));
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Swap<T>(ref T a, ref T b)
{
var tmp = a;
a = b;
b = tmp;
}
static int Bound<T>(T[] array, T value, bool upper = false)
where T : IComparable<T>
{
int left = 0;
int right = array.Length - 1;
while (left <= right)
{
int mid = left + (right - left >> 1);
int cmp = value.CompareTo(array[mid]);
if (cmp > 0 || cmp == 0 && upper)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
public static int Gcd(int n, int m)
{
while (true)
{
if (m == 0) return n >= 0 ? n : -n;
n %= m;
if (n == 0) return m >= 0 ? m : -m;
m %= n;
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static unsafe int Log2(long value)
{
double f = unchecked((ulong)value); // +.5 -> -1 for zero
return (((int*)&f)[1] >> 20) - 1023;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int BitCount(long y)
{
var x = unchecked((ulong)y);
x -= (x >> 1) & 0x5555555555555555;
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
return unchecked((int)((x * 0x0101010101010101) >> 56));
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static int HighestOneBit(int n) => n != 0 ? 1 << Log2(n) : 0;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static long HighestOneBit(long n) => n != 0 ? 1 << Log2(n) : 0;
#endregion
#region Fast IO
#region Input
static Stream inputStream;
static int inputIndex, bytesRead;
static byte[] inputBuffer;
static StringBuilder builder;
const int MonoBufferSize = 4096;
const char EOL = (char)10, DASH = (char)45, ZERO = (char)48;
static void InitInput(Stream input = null, int stringCapacity = 16)
{
builder = new StringBuilder(stringCapacity);
inputStream = input ?? Console.OpenStandardInput();
inputIndex = bytesRead = 0;
inputBuffer = new byte[MonoBufferSize];
}
static void ReadMore()
{
if (bytesRead < 0) throw new FormatException();
inputIndex = 0;
bytesRead = inputStream.Read(inputBuffer, 0, inputBuffer.Length);
if (bytesRead > 0) return;
bytesRead = -1;
inputBuffer[0] = (byte)EOL;
}
static int Read()
{
if (inputIndex >= bytesRead) ReadMore();
return inputBuffer[inputIndex++];
}
static T[] Na<T>(int n, Func<int, T> func, int z = 0)
{
n += z;
var list = new T[n];
for (int i = z; i < n; i++) list[i] = func(i);
return list;
}
static int[] Ni(int n, int z = 0) => Na(n, i => Ni(), z);
static long[] Nl(int n, int z = 0) => Na(n, i => Nl(), z);
static string[] Ns(int n, int z = 0) => Na(n, i => Ns(), z);
static int Ni() => checked((int)Nl());
static long Nl()
{
var c = SkipSpaces();
bool neg = c == DASH;
if (neg) { c = Read(); }
long number = c - ZERO;
while (true)
{
var d = Read() - ZERO;
if (unchecked((uint)d > 9)) break;
number = number * 10 + d;
if (number < 0) throw new FormatException();
}
return neg ? -number : number;
}
static char[] Nc(int n)
{
var list = new char[n];
for (int i = 0, c = SkipSpaces(); i < n; i++, c = Read()) list[i] = (char)c;
return list;
}
static string Ns()
{
var c = SkipSpaces();
builder.Clear();
while (true)
{
if (unchecked((uint)c - 33 >= (127 - 33))) break;
builder.Append((char)c);
c = Read();
}
return builder.ToString();
}
static int SkipSpaces()
{
int c;
do c = Read(); while (unchecked((uint)c - 33 >= (127 - 33)));
return c;
}
static List<int>[] NewGraph(int n, int m = 0, bool oneIndexed = true)
{
int off = oneIndexed ? 0 : -1;
n += 1 + off;
var g = new List<int>[n];
for (int i = 0; i < n; i++)
g[i] = new List<int>();
for (int i = 0; i < m; i++)
{
int u = Ni() + off, v = Ni() + off;
g[u].Add(v);
g[v].Add(u);
}
return g;
}
static string ReadLine()
{
builder.Clear();
while (true)
{
int c = Read();
if (c < 32) { if (c == 10 || c <= 0) break; continue; }
builder.Append((char)c);
}
return builder.ToString();
}
#endregion
#region Output
static Stream outputStream;
static byte[] outputBuffer;
static int outputIndex;
static void InitOutput(Stream output = null)
{
outputStream = output ?? Console.OpenStandardOutput();
outputIndex = 0;
outputBuffer = new byte[16384];
}
static void WriteLine(object obj = null)
{
Write(obj);
Write(EOL);
}
static void WriteLine(long number)
{
Write(number);
Write(EOL);
}
static void Write(long signedNumber)
{
ulong number = unchecked((ulong)signedNumber);
if (signedNumber < 0)
{
Write(DASH);
number = unchecked((ulong)(-signedNumber));
}
Reserve(20 + 1); // 20 digits + 1 extra for sign
int left = outputIndex;
do
{
outputBuffer[outputIndex++] = (byte)(ZERO + number % 10);
number /= 10;
}
while (number > 0);
int right = outputIndex - 1;
while (left < right)
{
byte tmp = outputBuffer[left];
outputBuffer[left++] = outputBuffer[right];
outputBuffer[right--] = tmp;
}
}
static void Write(object obj)
{
if (obj == null) return;
var s = obj.ToString();
Reserve(s.Length);
for (int i = 0; i < s.Length; i++)
outputBuffer[outputIndex++] = (byte)s[i];
}
static void Write(char c)
{
Reserve(1);
outputBuffer[outputIndex++] = (byte)c;
}
static void Write(byte[] array, int count)
{
Reserve(count);
Copy(array, 0, outputBuffer, outputIndex, count);
outputIndex += count;
}
static void Reserve(int n)
{
if (outputIndex + n <= outputBuffer.Length) return;
Flush(false);
if (n > outputBuffer.Length)
Resize(ref outputBuffer, Max(outputBuffer.Length * 2, n));
}
static void Flush(bool flush = true)
{
outputStream.Write(outputBuffer, 0, outputIndex);
outputIndex = 0;
if (flush) outputStream.Flush();
}
#endregion
#endregion
#region Main
public static void Main()
{
InitInput(Console.OpenStandardInput());
InitOutput(Console.OpenStandardOutput());
#if __MonoCS__ && !C7
var thread = new System.Threading.Thread(()=>new Solution().Solve());
var f = System.Reflection.BindingFlags.NonPublic | System.Reflection.BindingFlags.Instance;
var t = thread.GetType().GetField("internal_thread", f).GetValue(thread);
t.GetType().GetField("stack_size", f).SetValue(t, 32 * 1024 * 1024);
thread.Start();
thread.Join();
#else
new Solution().Solve();
#endif
Flush();
}
#endregion
#endregion
}Triple Sort CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
scanner := bufio.NewScanner(os.Stdin)
const maxCapacity = 2048 * 1024
buf := make([]byte, maxCapacity)
scanner.Buffer(buf, maxCapacity)
scanner.Split(bufio.ScanLines)
scanner.Scan()
T, _ := strconv.Atoi(scanner.Text())
for caseNumber := 1; caseNumber <= T; caseNumber++ {
scanner.Scan()
NK := strings.Split(scanner.Text(), " ")
N, _ := strconv.Atoi(NK[0])
K, _ := strconv.Atoi(NK[1])
input := make([]int, N)
scanner.Scan()
for i, e := range strings.Split(scanner.Text(), " ") {
eInt, _ := strconv.Atoi(e)
input[i] = eInt
}
permutations, M, solved := solve(input, K)
if solved {
if M == 0 {
fmt.Println(0)
} else {
fmt.Println(M)
fmt.Println(permutations)
}
} else {
fmt.Println(-1)
}
}
}
func solve(in []int, k int) (string, int, bool) {
var permutationsBuffer bytes.Buffer
M := 0
index := 0
skipCycle := true
lastResolvedIndex := -1
for index < len(in) {
found := true
for in[index] == index+1 {
index++
if index >= len(in) {
// if we reach the end of the list without finding a first element
// this means that the permutations are already sorted
return permutationsBuffer.String(), M, true
}
}
// stop if a non-sorted element is found after max allowed number of iterations
if M >= k {
return "", M, false
}
// first element that is not in its correct position
i1Index := index
// 2nd element is in the expected index of the 1st element
i2Index := in[i1Index] - 1
// the same applies to the 3nd element
i3Index := in[i2Index] - 1
cycleResolved := false
for i3Index == i1Index && skipCycle {
cycleResolved = true
if lastResolvedIndex == -1 {
lastResolvedIndex = i1Index
} else {
i1Index = lastResolvedIndex
}
if i1Index < len(in) {
i2Index = in[i1Index] - 1
i3Index = in[i2Index] - 1
} else {
skipCycle = false
i1Index = index
i2Index = in[i1Index] - 1
i3Index = in[i2Index] - 1
break
}
lastResolvedIndex++
}
if cycleResolved {
lastResolvedIndex--
}
// if the expected index of the 2nd element is the same as
// the 1st index, then 1st & 2nd elements are "sitting" in
// each other place and any other index to complete the
// permutation should do.
if i3Index == i1Index {
found = false
index++
for index < len(in) {
if index != i2Index && in[index] != index+1 {
i3Index = index
found = true
break
}
index++
}
if !found {
return "", M, false
}
}
if M != 0 {
permutationsBuffer.WriteString("\n")
}
permutationsBuffer.WriteString(strconv.FormatInt(int64(i1Index+1), 10) + " " + strconv.FormatInt(int64(i2Index+1), 10) + " " + strconv.FormatInt(int64(i3Index+1), 10))
tmp := in[i1Index]
in[i1Index] = in[i3Index]
in[i3Index] = in[i2Index]
in[i2Index] = tmp
M++
}
return "", M, false
}Triple Sort CodeChef Solution Review:
In our experience, we suggest you solve this Triple Sort CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Triple Sort CodeChef Solution.
Conclusion:
I hope this Triple Sort CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!