Perfect Imperfections 2 Codechef Solution

by

Perfect Imperfections 2 Codechef Solution

An array of integers is called good if all its elements are perfect squares. You are given an array A of N integers. In one move, you can do the following:

Pick a subset of indices of the array, say {i1,i2,…,ik} where 1≤i10 Finally, multiply the value at each chosen index by X, i.e, set Aij to Aij⋅X for each 1≤j≤k Find the minimum number of moves required to make the array good.

Note: The value of X is fixed for a given move, but can vary between moves.

Input Format

  • The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
  • Each test case contains two lines of input.
  • The first line of each test case contains N, the size of the array.
  • The second line contains N space-separated integers A1,A2,…,AN.

Output Format
For each testcase, output in a single line the minimum number of moves required to make the array good.

Constraints

  • 1≤T≤104
  • 1≤N≤104
  • 1≤Ai≤108
  • The sum of N across all testcases won’t exceed 104.

Subtasks
Subtask #1 (100 points): Original constraints

Sample Input 1
5
3
15 2 4
4
15 14 4 9
3
10 3 6
2
4 9
2
2 8

Sample Output 1
2
2
3
0
1

Explanation

Test case 1: One possible sequence of moves is:

Multiply the first element by 15
Multiply the second element by 2
The array is now [225,4,4]=[152,22,22], which is good.

Test case 3: One possible sequence of moves is:

Multiply the first and third elements by 8
Multiply the second and third elements by 3
Multiply the first element by 20
The array is now [1600,9,144]=[402,32,122], which is good.

Test case 4: The array is already good, since [4,9]=[22,32], so no moves need to be made.

SOLUTION

Program: Perfect Imperfections 2 Codechef Solution in Python

T = int(input())
for i in range(T):
    N = int(input())
    num = list((map(int, input().split(" "))))
    if len(num) == N:
        k = 0
        change_count = 0
        for j in num:
            y = (j**(1/2)) * 10
            if y % 10 == 0:
                continue
            else:
                num[k] = j*j
                k += 1
                change_count += 1
        print(change_count)

Program: Perfect Imperfections 2 Codechef Solution in C++

#include <bits/stdc++.h>
using namespace std;
#define maxn 10010
vector<int> pr, pos[maxn], big[maxn * 10];
map<int, int> mp;
int id[maxn], Tcnt, n, vis[maxn], arr[maxn];
bitset<maxn> bit[1400];
int make_id(int x) {
    if(mp.count(x)) return mp[x];
    return mp[x] = Tcnt ++;
}
void prime() {
    for(int i = 2; i < 10000; i ++) {
        if(vis[i]) continue;
        pr.push_back(i);
        for(int j = i * i; j < 10000; j += i) vis[j] = 1;
    }
    for(int i = 0; i < pr.size(); i ++) id[pr[i]] = i;
}
int calc() {
    int ans = 0;
    for(int i = 0; i < n; i ++) {
        if(pos[i].empty()) continue;
        ans ++;
        int fir = pos[i][0], sec;
        for(int j = 1; j < pos[i].size(); j ++) {
            sec = pos[i][j];
            bit[sec] ^= bit[fir];
            int pp = bit[sec]._Find_next(i);
            if (pp >= maxn) continue;
            pos[pp].push_back(sec);
        }
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    prime();
    int tcase;
    cin >> tcase;
    while(tcase --) {
        cin >> n;
        for(int i = 0; i < n; i ++) cin >> arr[i];
        for(int i = 0; i < Tcnt + 5; i ++) big[i].clear();
        mp.clear();
        for(int i = 0; i < pr.size(); i ++) bit[i].reset();
        Tcnt = 0;
        for(int i = 0; i < n; i ++) {
            int reg = arr[i];
            for(int j = 2; j * j <= reg; j ++) {
                if(reg % j) continue;
                int cnt = 0;
                while(reg % j == 0) {
                    cnt ++;
                    reg /= j;
                }
                bit[id[j]][i] = cnt & 1;
            }
            if(reg > 1) {
                if(reg < 10000) bit[id[reg]][i] = 1;
                else big[make_id(reg)].push_back(i);
            }
        }
        int ans = 0;
        for(int i = 0; i < Tcnt; i ++) {
            ans ++;
            int fir = big[i][0], sec;
            for(int j = 1; j < big[i].size(); j ++) {
                sec = big[i][j];
                for(int k = 0; k < pr.size(); k ++)
                    bit[k][sec] = bit[k][sec] ^ bit[k][fir];
            }
            for(int j = 0; j < pr.size(); j ++) bit[j][fir] = 0;
        }
        for(int i = 0; i < n; i ++) pos[i].clear();
        for(int i = 0; i < pr.size(); i ++) {
            for(int j = 0; j < n; j ++) {
                if(bit[i][j]) {
                    pos[j].push_back(i);
                    break;
                }
            }
        }
        ans += calc();
        cout << ans << endl;
    }
}

Program: Perfect Imperfections 2 Codechef Solution in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
    static boolean isPerfectSquare(int x)
    {
        if (x >= 0) {
           
            int sr = (int)Math.sqrt(x);
 
            return ((sr * sr) == x);
        }
        return false;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
	Scanner sc = new Scanner(System.in);
	int count=0;
	int t =sc.nextInt();
	while (t-->0){
	    	int n=sc.nextInt();
	    	int a[]=new int[n];
	    	for(int i=0;i<n;i++){
	    	    a[i]=sc.nextInt();
	    	}
	    	for(int i=0;i<n;i++){
	    	    if(isPerfectSquare(a[i])){
	    	        continue;
	    	    }
	    	    else
	    	    a[i]=a[i]*a[i];
	    	    count++;
	    	}
	    	System.out.println(count);
	}
	
	}
}

Related:

Leave a Comment

four × 5 =