Codeforces round #107 : "undefined"

Edit: So, lack of an announcement makes me think that maybe the match won't be canceled. I am still not sure if that's a good idea.

This match started well. But now I guess it will be canceled. There was a rather extreme typo in problem C (E ind div2) that completely changes the meaning of the problem and it was announced rather late. I really think it will get canceled, if it doesn't then I think it would mess up the rating statistics.

I am starting to write this 58 minutes after the start of the match (of course, I won't click publish until the match ends). I did the first two problems correctly, I never felt this comfortable with a div1 problem set in codeforces before. Oh well... I hope tomorrow's SRM don't drags this bad luck. Right now I know that my algorithms are correct, but there may be silly implementation bugs that make them fail.

Div1 A / Div2 C
Problem statement
Take a look at the examples. When q = 1 , it is easy to see that the first player wins. Then we have a case in which first player forcibly loses: 6. There are only two divisors, two prime factor of 6: 3 or 2. It does not matter which one player 1 picks, player 2 will get a prime number and thus win.

Whenever the number has exactly two prime factors, player 2 wins. Whenever the number has only one prime factor, player 1 wins by default. What about the remaining cases? Well, the number will have more than 2 prime factors, but player 1 will really like it to give player 2 a number with only 2 prime factors (Then he will lose). And player 1 can easily do that, because the product of two factors will be a divisor of the number.

Thus, you just need to extract the prime factors of the number q. It can be done in O(sqrt(q)). After that, count the number of prime factors. If they are less than 2 you already know the answer. Else just let player 1 pick any product of 2 of its prime factors, and that is a winning step.

// The I/O part grabs q from input and then does something with the return 
// value of this function. This function returns -1 if player 2 wins, else 
// returns the number player 1 picks (or 0 if there is none). 
long long solve(long long q) 
{ 
    if (q == 1) { 
        return 0; 
    } 
    //count the number of prime factors 
    long long p = 2; 
    int c = 0; 
    long long prime = -1; 
    vector< long long > primeFactors; 
    while (p <= q / p) { 
        while (q % p == 0) { 
            primeFactors.push_back(p); 
            c ++; 
            q /= p; 
        } 
        p++; 
    } 
    if (q != 1) { 
        primeFactors.push_back(q); 
    } 
     
    if (primeFactors.size() == 1) { 
        return 0; 
    } 
    if (primeFactors.size() == 2) { 
        return -1; 
    } 
    //leave only two prime factors 
    return primeFactors[0]*primeFactors[1]; 
} 

Div1 B / Div2 D
(Link to problem statement)
Well, the first thing to notice is that because of the condition that each substring of length k must be a palindrome, there will be many positions that will forcibly have the same character.

Imagine n = 5, k = 4. Ok that's the last example case, and you see clearly that all letters must be equal. So, try k = 3 instead. If we decide a character for the first position, since k=3 then the third position should also have this character and so should the fifth. You will find that all odd positions need the same character and all the even positions need the same character (not necessary that all positions have it).

We will call each group of positions that need to have the same character a "component". Of course, I am just getting clever here, because component is exactly what you would call it if this was a graph problem. And this IS a graph problem. Let's see... Given a certain position x, then for each substring of length k that includes x, there will be a position y that is the mirror of x with respect of the k-long string. You will see that there are at most K such ys. And that calculating this mirror position is possible once you fix the starting location of the string that includes x. All the positions y that share an edge with x may also share edges with other positions of their own and so and so.

What we need to do is to split the positions in connected components. That can be done easily with a Depth-first search (DFS). In fact, we only need the number of connected components. Let us say this number is compos. Then for each connected component, we have m choices we can take. The choices for the components are independent of each other and sacrosanct combinatorics tells us the result is m^compos.

const int MOD = 1000000007; 
 
int modPow(int x, int y) 
{ 
    long long res = 1; 
    long long a = x; 
    while (y > 0) { 
        if (y % 2 == 1) { 
            res = (res * a) % MOD;  
        } 
        a = (a * a) % MOD; 
        y /= 2; 
    } 
    return (int)(res); 
} 
int visited[2000]; 
void dfs(int x, int n, int k) 
{ 
    if (visited[x] == -1) { 
        visited[x] = 1; 
 
        for (int p = 0; p < k; p++) { 
            // imagine x is in p-th position of k-long string 
            // the beginning of the k-long substring  
            int b = x - p; 
            if ( (b >= 0) && (b+k <= n) ) { 
                //the mirror 
                int q = k - p - 1; 
                int y = q + b; 
                dfs(y, n,k); 
            } 
             
        } 
 
    } 
} 
 
int solve(int n, int m, int k) 
{ 
    memset(visited, -1, sizeof(visited)); 
    int compos = 0; 
    for (int i=0; i<n; i++) { 
        if (visited[i] == -1) { 
            compos++; 
            dfs(i, n, k); 
        } 
    } 
    //cout << "##" << compos<<endl; 
    // Result is (m ^ compos) % MOD 
    return modPow(m, compos); 
} 

Div1 C / Div2 E
(Link to problem statement)
Oh , so I read this problem, and at first I thought that you could give each customer multiple tickets for different routes inside the customer. This way, you can for each segment, pick exactly then number of costumers that will have a ticket. I thought that because... that's what the problem statement said. In fact, the solution for this problem is quite nice. It requires a line sweep and other funny tricks. I was about to get close to the climax of the solution when I see the codeforces browser window and there is a popup that says "Undefined". I bet the popup was supposed to say something interesting, so I went to the problems page to find out that the wording in this problem was wrong. Decided to start to write this.

Div2 A
(Link to problem statement)
I wonder if it is possible to register both for div2 (unofficially) and div1 so you get a chance to solve div2 problems if you get bored of div1. I will try this next time.

I cannot really test the div2-exclusive problems, so I will just insert some guesses. First of all, at first I had no idea what the limes had to do with the result of the problem. I didn't actually get that each toast is supposed to have a slice of lime until I read the examples. It is probably something that people with common sense would know, but I don't have such thing...

So, you have a set of variables. The number of slices, the total milliliters of drink and the total milligrams of salt can all be calculated from the input arguments (or are input arguments). Then each of these variables induces a condition of the maximum number of toasts that can be made. Let us call these three constraints A,B and C. (The number of toasts cannot exceed A,B or C). Well, in fact, just pick the minimum min(A,B,C), that's our new constraint. However, the final result must be a multiple of n, because each friend must do the same number of toasts. So just pick the maximum multiple of n that is smaller than or equal to min(A,B,C). The constraints are so small that you could even do brute force. But in fact, you can also get clever with modulo operations and do ( min(A,B,C) - min(A,B,C) % n)

Div2 B
(Link to problem statement)
This is just an implementation problem. Make functions to know if a telephone number is a pizza number, a taxi number or else a girl number. Then just count the number of telephones of each type for each friend and finally, pick the friend with the most telephones of each type.

Comments?
What did you think of the match? I liked the division 1 for the most part, except for the huge glitch in C. I also liked problem A in division 2 although it was convoluted. Problem B in division 2 seems a little too implementation-centric, but probably necessary in that division.