1624C - Division by Two and Permutation

Meaning of Question

gived a sequence with n length, need to element in array divide by 2, make the sequence contains from 1 to n. determinate if can be, if it can print "YES", "NO" otherwise.

Intuition

We can sort the sequence with decreasing, then judge n if can obtain, the n — 1, n — 2, ... , 1. since that we can avoid repeative calculation. for maximum element in sequence. wo loop through divide by 2 operation unti the element is 0, in addtion, we use bool array to store n whether used?

JAVA

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            Integer nums[] = new Integer[n];
            boolean used[] = new boolean[n + 1]; // judge ith element if can obtain
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            Arrays.sort(nums, (a, b) -> b - a);
            boolean isOk = true;
            for (int i = 0; i < n; i++) {
                int x = nums[i];
                while (x > n || used[x]) // obtain x closest and less than n or x has ben used  
                    x /= 2;
                if (x > 0) used[x] = true;
                else {
                    isOk = false;
                    break;
                }
            }
            System.out.println(isOk ? "YES" : "NO");
        }
    }

CPP

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    scanf("%d", &t);
//    cin >> t;
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<int> nums(n), used(n + 1);
        for (auto &i : nums) {
            scanf("%d", &i);
        }
        sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; });
        bool isOk = true;
        for (auto &num : nums) {
            int x = num;
            while (x > n || used[x]) {
                x /= 2;
            }
            if (x) used[x] = 1;
            else {
                isOk = false;
                break;
            }
        }
        printf("%s\n", isOk ? "YES" : "NO");
    }
}

1625B - Elementary Particles The problem need us giving two same length sequence. Assuming the length of sequence is n. that one's index from 1 to n — 1, another from 2 to n. And two sequence at least exists one index position, make the value of same index is same and the length of sequence as large as possible.

Now that the value is same, we can enumberate the gived array, suppose a value A in array is correct answer. To find out same value B , calculating distance between B to last element in array and plus the distance between the first element to A. So we can summarize a formula. for example array = [3 1 5 2 1 3 4],

we can see the second 3 appears in behind first 3, . so first 3 is 1 and second 3 is 7 — 6 = 1, so ans = 1 + 1 = 2

we can see the second 1 appears in behind first 1, . so first 1 is 2 and second 1 is 7 — 5 = 2, so ans = 2 + 2 = 4

suppose

lenA is the length that 0 to index of A

lenB is the length that B to index of n

ans = lenA + lenB

Furthermore, in order to conveniently obtain lenA, we use array to store every element occurrence of time.

Java

 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int nums[] = new int[2 * (int) 1e+5];
            int ans = -1;
            for (int i = 1; i <= n; i++) {
                int j = sc.nextInt();
                if (nums[j] != 0) {
                    ans = Math.max(ans, n - i + nums[j]);
                }
                nums[j] = i;
            }
            System.out.println(ans);
        }
    }

CPP

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    scanf("%d", &t);
//    cin >> t;
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<int> nums(2 * 1e+5);
        int ans = -1;
        for (int i = 1; i < n + 1; ++i) {
            int j;
            scanf("%d", &j);
            if (nums[j]) {
                ans = max(ans, n - i + nums[j]);
            }
            nums[j] = i;
        }
        printf("%d\n", ans);
    }
}

For this probelm. needed to smallest XOR of sum of sequence from 0 to n (excluded) that has been permutated.

Intuition

The feature of XOR bitwise is the same is 0,otherwise 1. How we make the sum of sequence smallest? for 0 to n — 1 the n numbers. We should make pair that same length of binary bit go XOR operation. Such as 111(7) ^ 110(6) = 1 you will find their height bit turn into 0. So the solution is that make same length of binary bit go XOR operation.Base on this opeartion, we can obtain the answer.

Java

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int k = 0;
            while ((1 << k) < n ) { // k is closest but less than n 
                k++;
            }
            k--; 
            for (int i = (1 << k) - 1;i >= 0;i--) { // print same length of binary bit 
                System.out.print(i + " ");
            }
            for (int i = (1 << k);i < n;i++) {  // print same length of binary bit
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

CPP

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int k = 0;
        while ((1 << k) < n) { // k is closest but less than n 
            k++;
        }
        k--;
        for (int i = (1 << k) - 1; i >= 0 ; --i) {  // print same length of binary bit
            printf("%d ",i);
        }
        for(int i = (1 << k);i < n;i++) {  // print same length of binary bit
            printf("%d ", i);
        }
        printf("\n");
    }
}