Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Kirito in labyrinth CodeChef Solution
Problem -Kirito in labyrinth 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.
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) {
InputReader s = new InputReader(System.in);
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]))
a.add(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;
}
}
}
}
}
class InputReader {
private final InputStream st;
private final byte[] buf = new byte[8192];
private int cc, sc;
private SpaceCharFilter f;
public InputReader(InputStream st) {
this.st = st;
}
public int t() {
if (sc == -1)
throw new InputMismatchException();
if (cc >= sc) {
cc = 0;
try {
sc = st.read(buf);
} 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;
}
public String readString() {
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
buf, _ = ioutil.ReadAll(os.Stdin)
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.
“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!
