SRM 577 div2

I solved all 3, and placed 7th in div2.

p1000 is worth some thoughts. Given an int arr[] with 50 elements, each no more than 10^5, find number of elements to insert so that no two adjacent numbers have gcd > 1 when sorted.

First attempt: is one insertion always enough?
The problem setter is friendly and give case 1 showing the claim is false.

Second attempt: is two insertion always enough?
The answer is yes, and here is why. (UPDATE, apparently the proof is very difficult and I do not know one, although you can write a program to check the claim for the range of numbers, 1 to 10^5)

Let a and b be two adjacent numbers, and first we run all numbers from a+1 to b-1 to see if one of them is coprime with both a and b, if yes we are done and need to insert only one element. Otherwise we claim that a+1 and b-1 suffices to make a, a+1, b-1, b adjacent coprime. Note that since gcd(a,b) > 1, we must have b-a >= 2, and since no number from a+1 to b-1 is coprime with both a and b, we actually have a+1 < b-1.

Now comes the proof that a, a+1, b-1, b are adjacent coprime.
Since we know that every number from a+1 to b-1 have some gcd > 1 with either a or b. We can group them according to this:

class b shares gcd > 1 with b and class a shares gcd > 1 with a, and every number from a+1 to b-1 must fall into one of the two classes. Note also that gcd(a, a+1) = 1, as is gcd(b, b-1) = 1

class b: a+1, b-2, ...
class a: b-1, a+2, ...


Not finished, but checking all a,b=1 to 10^4 works with a+1, b-1

The intended solution, according to mystic, is also cryptic. The observation is that if B - A is at least 504 = 72 * 6, then you can find one prime between A and B and B is not divisible by that prime. This is based on the observation that for numbers less than 10^5, prime gaps are no more than 72. Then you can work on the case B < A + 504 and this is much more manageable.

SRM 575 div 1

250, had some idea but could not finish. Submitted an obviously faulty version.

The problem is a game, given integer C, in each move you can subtract d from C such that d is a divisor of C and 1 < d < C. The player cannot make a move loses.

To start, make a table for C = 1 to 16, and this gives some idea.

if C is 2^k, then 2 is LOSE, 4 is WIN, 8 is LOSE, 16 is WIN. So a guess is that 2^k is LOSE if k is odd and is WIN if k is even.

and all odd numbers are LOSE, 1, 3, 5, 7, ...
and other numbers, 2^k * l for odd l > 1 are WIN.

If you have gone this far, an induction proof is all you need, and that's easy.

if C is 2^k, for even k you can make a move to 2^(k-1) which is an odd power of 2 and a LOSE, so you must be in WIN. For odd k we need to show every move leads to WIN. You possible moves are 2^l for some l >= 1, and C - 2^l = 2^k - 2^l = 2^l (2^(k-l) - 1), so it is  of the form 2^l * odd, and that is a WIN.

if C is odd, then we need to show every move leads to WIN.  An odd C can only have odd divisor d and d must be greater than 1, less than C. so C - d is even, and since d also divides C - d, the number C - d must be of the form 2^l * odd, and hence a WIN.

if C is 2^l * odd for l >= 1, then we need to find a move to LOSE. And that was easy. Let C = 2^l * d, for some odd d, then C - d = 2^l * d - d = d * (2^l - 1). The product of two odd numbers must be odd, and odd is LOSE.

We are now complete in the induction proof.

SRM 572 div1

250, find pos that must be equal, this is an equivalence relation. Group by the equivalence then exclude the max occurred letter. (did not see it until reading petr's solution)

500, the length n is only 9, but brute force cannot work as we have 10^9 numbers to check, each need to go through 50 guesses. It appears that if n is smaller, say 4 or 5, then we can work out by brute force. How do we do that?

Reading tourist and petr's solution, and the editorial, it finally makes sense. Let's consider one guess, we can cut a number with 9 digits to left with 4 digits and right with 5 digits. Then we try all 0 to 99999 to count the number of bull. If left bull and right bull add up to the right bull, then the left guess and right guess makes a valid guess. Now we have a number of guesses.

What happens if we try 0 to 9999 for left and 0 to 99999 for right. And we record the signature of each try on left in a map, a signature is essentially the bull for each guess in the input, a vector of int with 50 elements. And we also record the signature of each try on the right, put in a second map. Each map entry has the signature as key, and number of tries with the signature as value.

Now we can iterate through the first map, for each entry, we can compute its complement key in the second map and look for matches.

In the end, we can count how many valid numbers with bulls matching all the input guesses. And it is trivial to respond 0, 1 or 2 for the problem.

Code here:
// from 0 to 9999, try left
// from 0 to 99999, try right
//
// map count of tries to key = bull
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

map< vector<int>, int > cnt_left, cnt_right, val_left, val_right;

class EllysBulls
{
public:

string getNumber(vector <string> guesses, vector <int> bulls)
{
    int len = guesses[0].size();
    int g = guesses.size();
    int lim, l1, l2;
   
    lim = 1; l1 = len / 2; l2 = len - l1;
    for (int i = 0; i < l1; ++i) lim *= 10; cout << lim << endl;
    for (int i = 0; i < lim; ++i) {
        vector<int> vec;
        for (int k = 0; k < g; ++k) {
            int val = i;
            int bull = 0;
            for (int p = l1-1; p >= 0; --p) {
                if (guesses[k][p] - '0' == val % 10) bull++;
                val /= 10;
            }
            vec.push_back(bull);
        }
        val_left[vec] = i;
        cnt_left[vec]++;
    }
    lim = 1;
    for (int i = 0; i < l2; ++i) lim *= 10; cout << lim << endl;
    for (int i = 0; i < lim; ++i) {
        vector<int> vec;
        for (int k = 0; k < g; ++k) {
            int val = i;
            int bull = 0;
            for (int p = l2-1; p >= 0; --p) {
                if (guesses[k][p+l1] - '0' == val % 10) bull++;
                val /= 10;
            }
            vec.push_back(bull);
        }
        val_right[vec] = i;
        cnt_right[vec]++;
    }

    // from right search left
    int ans_left = 0, ans_right = 0;
    int ans = 0;
    for (int i = 0; i < lim; ++i) {
        vector<int> vec, other;
        for (int k = 0; k < g; ++k) {
            int val = i;
            int bull = 0;
            for (int p = l2-1; p >= 0; --p) {
                if (guesses[k][p+l1] - '0' == val % 10) bull++;
                val /= 10;
            }
            vec.push_back(bull);          
        }
        bool good = true;
        for (int k = 0; k < g; ++k) {
            int entry = bulls[k] - vec[k];
            if (entry < 0) { good = false; break; }
            other.push_back(entry);
        }
        if (!good) continue;
        if (cnt_left.count(other)) {
            ans_right = i; ans_left = val_left[other];
            ans += cnt_left[other] * cnt_right[vec];
            if (ans >= 2) break;
        }
    }
    if (ans == 0) return "Liar";
    if (ans >= 2) return "Ambiguity";
    string str;
    for (int p = 0; p < l2; ++p) {
        str += char(ans_right % 10 + '0');
        ans_right /= 10;
    }
    for (int p = 0; p < l1; ++p) {
        str += char(ans_left % 10 + '0');
        ans_left /= 10;
    }
    for (int p = 0, q = str.length()-1; p < q; ++p, --q) {
        char t = str[p]; str[p] = str[q]; str[q] = t;
    }
    return str;
}

};


p1000, seems very similar to the div2 500 problem, since same letter goes through same transformation, we only need to consider distinct letters and there are only 26 of them. Each pair can use either forward or backward transformation and we have 2^26 = 10^7 to deal with. And does that solve a div1 hard?

SRM 572 div2

p500
// check feasibility
// for two intervals opposite, if overlap, then dead
// suppose no two opposite intervals overlap, then they are independent
// we can work with two sets, one forward and one backward
// For same direction set, if one interval is fully contained in another, then dead
// if not, then there is a ways to do the transformation
// select the farthest one (closest to the goal) and move to the goal

#include <string>
using namespace std;

class NextOrPrev
{
public:

bool check(int a, int b, int c, int d)
{
    int a1, b1, c1, d1;
    a1 = min(a,b); b1 = max(a,b);
    c1 = min(c,d); d1 = max(c,d);
    if ((a-b) * (c-d) <= 0) {
        // opposite direction
        if (c1 <= a1 && a1 <= d1) return false;
        if (c1 <= b1 && b1 <= d1) return false;
        if (a1 <= c1 && c1 <= b1) return false;
        if (a1 <= d1 && d1 <= b1) return false;
    } else {
        if (c1 <= a1 && a1 <= d1 && c1 <= b1 && b1 <= d1) return false;
        if (a1 <= c1 && c1 <= b1 && a1 <= d1 && d1 <= b1) return false;
    }
    return true;
}

// because no wrap around, there is only one way from transform one char to another char
int getMinimum(int nextCost, int prevCost, string start, string goal)
{
    int n = start.length();
    int cost = 0;
   
    for (int i = 0; i < n; ++i) {
        int cur;
        if (start[i] > goal[i]) cur = prevCost * (start[i] - goal[i]);
        else cur = nextCost * (goal[i] - start[i]);
        cost += cur;
    }
    // check impossible
    // if opposite directions, then cannot overlap
    // if same direction, cannot fully contain
    bool good = true;
    for (int i = 0; i < n; ++i)
    for (int j = i+1; j < n; ++j)
    {
        if (!check(start[i], goal[i], start[j], goal[j])) {
            good = false; goto done;
        }
    }
    done:
    if (good) return cost;
    else return -1;
}
};

p1000

// for each K = 1 to M
// count number of ways to have sum = N with K elements
//
// it appears that the sequence is unordered, which makes counting rather difficult
// however we can impose an ordering, since each element has distinct S[i] % M
// we can count all sequences with mod M ordered increasingly, then the ans is obtained
// by multiplying by K factorial
//
// Now our job is to count number of sequence of K elements with mod M ordered increasingly
// if N is small, then we can use dp to count dp[sum][x][l] for number of sequences with
// total = sum and use only mod M from 0 to x-1, with exactly l elements
// however N is huge, 10^18, so we need to work with N mod M somehow
//
// look at a valid sequence
// S[1] + S[2] + ... + S[K] = N
// this is true if and only if
// sum of (S[i] % M) = N % M + S / M  where S = sum of S[i]
// and
// sum of (S[i] / M) = N / M - S / M
//
// if we write S[i] = Q[i] * M + R[i]
// then
// sum of R[i] = N % M + R / M  where R = sum of R[i]
// and
// sum of Q[i] = N / M - R / M
//
// if we have the R[i]'s, all we need is to find Q[i]'s to complete this equation
//
// Let dp[sum][x][l] be the number of ways to get total = sum, using mod M from 0 to x-1 (at most x-1)
// with exactly l elements,
// then for a given K, we look for adding up dp[sum][M][K] for which sum % M = N % M
// moreover, we need to multiply such dp[sum][M][K] by (Q + K-1 choose K-1) for Q = N/M - sum/M
// notice that K is at most 50 so the combination number can be computed efficiently

#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int MOD = (int)(1e9+7);
int dp[1300][55][55];
int fact[55], invfact[55];

class DistinctRemainders
{
public:

void refadd(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}

int mult(int a, int b)
{
    return (long long)a * b % MOD;
}

int gcd(long long a, long long b)  // use long long even though only one of them can be long long
{
    if (b == 0) return a;
    return gcd(b, a % b);   
}

int choose(long long a, int b)  // compute (Q + K-1 choose K-1), K is at most 50, although Q can be 10^18
{
    int ans = 1;
   
    vector<int> v;
    for (int i=1; i<=b; ++i) v.push_back(i);
    for (int i = 0; i < b; ++i) {
        long long k = a - i;
        for (int j = 0; j < b; ++j) {
            int g = gcd(k, v[j]);
            if (g > 1) { k /= g; v[j] /= g; }  // careful, forgot to divide v[j] earlier
        }
        ans = (long long)ans * (k % MOD) % MOD;  // watch integer overflow, must reduce k by MOD
    }
    for (int j = 0; j < b; ++j) { if (v[j] > 1) cout << a << ' ' << b << endl;
      assert(v[j] == 1);
    }
   
    //for (int i = 0; i < b; ++i) ans = mult(ans, (a-i)%MOD);
    //ans = mult(ans, invfact[b]);
    return ans;
}

int fastexp(int a, int b)
{
    int ans = 1;
    int base = a;
    while (b) {
        if (b&1) ans = mult(ans, base);
        base = mult(base, base);
        b /= 2;
    }
    return ans;
}

int inv(int a)
{
    return fastexp(a, MOD-2);
}

void init(int n)  // n is at most 50 in this problem
{
    fact[0] = 1;
    for (int i=1; i<=n; ++i)
        fact[i] = mult(fact[i-1], i);
    for (int i=0; i<=n; ++i)
        invfact[i] = inv(fact[i]);
}

int howMany(long long N, int M)
{
    if (M == 1) return 1;  // careful, M = 1 is special
    init(M);
    int ans = 0;
    for (int K = 1; K <= M; ++K) {
        //for (int sum = N%M; sum < M*M/2; sum += M)
        //for (int x = 0; x <= M; ++x)
        //for (int l = 0; l <= K; ++l)
            //dp[sum][x][l] = 0;
        dp[0][0][0] = 1;  // dp[sum][x][l] is number of increasing seq with total = sum using max <= x-1 with exactly l elements
        for (int sum = 0; sum < M*M/2; ++sum)
        for (int x = 0; x <= M; ++x)
        for (int l = 0; l <= K; ++l)
         {
             if (sum + x + l == 0) continue;
             dp[sum][x][l] = 0;
             if (x > 0) dp[sum][x][l] += dp[sum][x-1][l];
             if (sum >= x-1 && x > 0 && l > 0) dp[sum][x][l] += dp[sum - (x-1)][x-1][l-1];
            if (dp[sum][x][l] >= MOD) dp[sum][x][l] -= MOD;
        }
        //cout << K << endl;
       
        int cur = 0;
        for (int sum = 0; sum < M*M/2 && sum <= N; ++sum)  // careful, sum can only be up to N
        if (sum % M == N % M) {
            //for (int x = 0; x <= M; ++x) {
                int tmp = dp[sum][M][K]; //cout << sum << ' ' << x << ' ' << K << ' ' << tmp << endl;
                long long Q = N / M - sum / M;
                assert(Q >= 0);  // careful, without check sum <= N, Q might be < 0 here
                tmp = mult(tmp, choose(Q + K-1, K-1));
                refadd(cur, tmp);
            //}
        }
        refadd(ans, mult(cur, fact[K]));
       
    }
    return ans;
}
};

// now it TLE, the dp I wrote is too slow, 50^6 is not acceptable in TC
// still fail, for N=14, M=7, ans is 643
// my return is 6403, how come? sum needs to be <= N