Hackerrank HourRank 17

I haven’t done any questions for a long time. . . I didn’t work hard enough to achieve the goals I set last year, but I still couldn’t accomplish them. . . Keep up the good work this year. . .

I have been brushing through LeetCode in the past three months and have gained a lot. But I feel like I’m not very proficient in it all over again, and time is so tight. . .

Title link and Code link

The Hurdle Race

Let’s not talk about the water issue. . .

Organizing Containers of Balls

The meaning of the question is to give $n(n<100)$ balls of colors and $n$ boxes. You can exchange one ball in the two boxes each time, and ask whether you can eventually reach a state where all the balls of the color are in one box, and there are only balls of one color in the box.

Sort all rows and columns to determine whether they are equal.

GCD Matrix

The meaning of the question is to give sets A and B, the number of set elements $n(n<10^5)$, and the numerical range of set elements $x<10^5$. Now take an element from each of the two sets and ask what kind of GCD can be obtained.

Because the value range is smaller than $10^5$, one shot is tolerated.

int A[maxn], count[maxn], Ma[maxn], n;
for(int i=1; i<=n; i++) 
    count[A[i]] ++;
for(int i=1; i<=100000; i++) {
    int j = i;
    while(j <= 100000) {
        Ma[i] += count[j];
        j += i;
    }
}


int Ma[maxn], Mb[maxn], ans[maxn];
for(int i=100000; i>=1; i--) {
    ans[i] = Ma[i] * Mb[i];
    int j = i;
    while( j <= 100000 ) {
        if(j > i) ans[i] -= ans[j];
        j += i;
    }
}

Number Game on a Tree

The meaning of the question is to give a game rule. There are a bunch of numbers, A and B. Remove one number from each of them, but the number removed this time must not be greater than the number removed last time. The person who cannot continue to remove numbers loses. Then there is now a tree with $n$ nodes ($n<5*10^5$). The numbers on the paths of each two leaf nodes are used as a list. How many lists can guarantee that A wins this game, and A goes first.

First consider the conditions for winning first. If every number is an even number, then the second player will definitely win. Because no matter which one is removed first, the second one will do the same. Then once a number with an odd number of elements appears, the first player will definitely win. If the first player removes that element, it will become the situation mentioned in the former.

Now consider how many numbers on the paths of two leaf nodes are even numbers. Consider XOR and change $color$ to $(1<<color)$ as the value on each node. This can ensure that when the XOR value of the path is 0, it must be an even number. Then there is another problem here: $(1<<color)$ will have an overflow problem, and the hash modulus is taken.