304 North Cardinal St.
Dorchester Center, MA 02124

# Kirito in labyrinth CodeChef Solution

## Kirito in labyrinth CodeChef Solution in C++14

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

#define ll int64_t
#define endl '\n'

const int mx = 1e7;

int lpf[mx + 5];
void sieve() {
for (int i = 2; i <= mx; i++) {
if (lpf[i])continue;
lpf[i] = i;
for (int j = 1; j * i <= mx; j++)if (lpf[i * j] == 0)lpf[i * j] = i;
}
}
void solve() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++)cin >> v[i];
vector<int> dp(1e7 + 1, 0);
int ans = 1;
for (auto x : v) {
set<int> s;
while (x != 1) {
int p = lpf[x];
x /= p;
s.insert(p);
}
int t = 0;
for (auto p : s)dp[p]++, ans = max(ans, dp[p]), t = max(t, dp[p]);
for (int p : s)dp[p] = t;
}
cout << ans << endl;
}
int main() {
int t = 1;
sieve();
cin >> t;
while (t--) {
solve();
}
return 0;
}``````

## Kirito in labyrinth CodeChef Solution in C

``````#include <stdio.h>
#include <stdlib.h>
#define M 10000002
#define C 9
int factor[M];
int max(int l ,int r)
{
if(l > r)
return l;
else
return r;
}

void initialize()
{
int i;
for(i=1;i<M;i++)
{
factor[i]=i;
}
}

void sieve()
{
int i,j;
for(j=4;j<M;j=j+2)
factor[j]=2;

for(i=3;i*i<M;i=i+2)
{
if(factor[i]==i)
{
for(j=i*i;j<M;j=j+i)
{
if(factor[j]==j)
{
factor[j]=i;
}
}
}
}
//for(i=0;i<M;i++)
//  printf("%d : %d \n",i,factor[i]);
}

int main()
{
int t,n,i,j,tmp,k,*size,*a,**table,maximum,glmax,max_el;
//FILE *fp;
//fp = freopen("t1.txt","w",stdout);
initialize();
sieve();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
a = (int*)malloc(sizeof(int)*n);

table = (int**)malloc(sizeof(int*)*n);
for(i=0;i<n;i++)
table[i] = (int*)malloc(sizeof(int)*C);

max_el = -M;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
max_el = max(max_el,a[i]);
}

size = (int*)malloc(sizeof(int)*max_el+1);
for(i=0;i<=max_el;i++)
{
size[i]=0;
}

for(i=0;i<n;i++)
{
for(j=0;j<C;j++)
{
table[i][j]=0;
}
}

for(i=0;i<n;i++)
{
tmp=a[i];
k=0;
while(tmp!=1)
{
if( k==0 || (table[i][k-1] !=  factor[tmp] ) )
{
table[i][k]=factor[tmp];
k++;
}
tmp = tmp/factor[tmp];
}
}

glmax = -M;
for(i=0;i<n;i++)
{
maximum = -M;
for(j=0;table[i][j]!=0;j++)
{
tmp = table[i][j];
size[tmp]++;
maximum = max(maximum , size[tmp]);
}

for(j=0;table[i][j]!=0;j++)
{
tmp = table[i][j];
size[tmp] = maximum;
}
glmax = max(glmax , maximum);
}
if(glmax == -M)
glmax = 1;
printf("%d\n",glmax);
free(size);
free(a);

for(i=0;i<n;i++)
free(table[i]);
free(table);

}
return 0;
}``````

## Kirito in labyrinth CodeChef Solution in JAVA

``````import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;

class KIRLAB {
static int MAX = 10000001;
static int[] lpd;

public static void main(String[] args) {
seive();
PrintWriter w = new PrintWriter(System.out);
int t = s.nextInt();
while (t-- > 0) {
int[] fin = new int[MAX];
int n = s.nextInt(), max = 1;
for (int i = 0; i < n; i++) {
int x = s.nextInt();
if (x == 1)
continue;
ArrayList<Integer> a = new ArrayList<>();
while (x > 1) {
if (!a.contains(lpd[x]))
x /= lpd[x];
}
int ans = 0;
for (int j = 0; j < a.size(); j++) {
ans = Math.max(ans, fin[a.get(j)]);
}
max = Math.max(max, ans + 1);
for (int j = 0; j < a.size(); j++)
fin[a.get(j)] = ans + 1;
}
w.println(max);

}
w.close();
}

public static void seive() {
lpd = new int[MAX];
lpd[1] = 1;
for (long i = 2; i <= MAX - 1; i++) {
if (lpd[(int) i] == 0) {
lpd[(int) i] = (int) i;
for (long j = i * i; j <= MAX - 1; j += i) {
if (lpd[(int) j] == 0)
lpd[(int) j] = (int) i;
}
}

}
}

}

private final InputStream st;
private final byte[] buf = new byte[8192];
private int cc, sc;
private SpaceCharFilter f;

this.st = st;
}

public int t() {
if (sc == -1)
throw new InputMismatchException();
if (cc >= sc) {
cc = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (sc <= 0)
return -1;
}
return buf[cc++];
}

public int nextInt() {
int c = t();
while (isSpaceChar(c)) {
c = t();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = t();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = t();
} while (!isSpaceChar(c));
return res * sgn;
}

public long nextLong() {
int c = t();
while (isSpaceChar(c)) {
c = t();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = t();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = t();
} while (!isSpaceChar(c));
return res * sgn;
}

public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}

int c = t();
while (isSpaceChar(c)) {
c = t();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = t();
} while (!isSpaceChar(c));
return res.toString();
}

public String nextLine() {
int c = t();
while (isSpaceChar(c))
c = t();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = t();
} while (!isEndOfLine(c));
return res.toString();
}

public boolean isSpaceChar(int c) {
if (f != null)
return f.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}``````

## Kirito in labyrinth CodeChef Solution in GO

``````package main

import (
"fmt"
"io/ioutil"
"os"
)

var N = 11234567
var M = 112345

func max(a, b int) int {
if a > b {
return a
}
return b
}

func main() {
a := make([]int, M, M)
b := make([]int, M, M)
c := make([]int, N, N)
d := make([]int, N, N)
for i := 0; i < N; i++ {
c[i] = i
}
for i := 2; i*i < N; i++ {
if c[i] == i {
for j := i; j < N; j += i {
c[j] = i
}
}
}
ints := getInts()
var t int
t, ints = ints[0], ints[1:]
for t > 0 {
t--
var n int
n, ints = ints[0], ints[1:]
for i := 0; i < n; i++ {
a[i], ints = ints[0], ints[1:]
}
b[n] = 0
for i := 0; i < N; i++ {
d[i] = n
}
ans := 0
for i := n - 1; i >= 0; i-- {
b[i] = 0
k := a[i]
for k > 1 {
x := c[k]
for k%x == 0 {
k /= x
}
b[i] = max(b[i], 1+b[d[x]])
d[x] = i
}
ans = max(ans, b[i])
}
if (ans == 0) && (n > 1) {
ans = 1
}
fmt.Printf("%d\n", ans)
}
}
func getInts() []int {
//assumes POSITIVE INTEGERS. Check v for '-' if you have negative.
var buf []byte
var ints []int
num := int(0)
found := false
for _, v := range buf {
if '0' <= v && v <= '9' {
num = 10*num + int(v-'0') //could use bitshifting here.
found = true
} else if found {
ints = append(ints, num)
found = false
num = 0
}
}
if found {
ints = append(ints, num)
found = false
num = 0
}
return ints
}``````
##### Kirito in labyrinth CodeChef Solution Review:

In our experience, we suggest you solve this Kirito in labyrinth 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 Kirito in labyrinth CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Kirito in labyrinth 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!