Sunday, December 22, 2013

SRM 601: Another slow day

At least it wasn't catastrophically bad this time.

Div1 250 - The one with apples and organges

You have `n <= 50` bags. Bag `i` has apples[i] apples and oranges[i] oranges. The process to make a valid gift involves taking exactly X fruit (`X > 0`) from each bag (The number of apples and oranges you take from each bag must be exactly X). The number of apples and oranges determines the kind of gift you make. Count the total number of different kinds of gifts you can make, that is, the total number of distinct pairs `(A,O)` where `A` is the number of apples and `O` is the number of oranges.

The trick is to notice that the value of `X` you pick uniquely determines the sum `(A + O = nX)`, which means that it is impossible to get the same pair using two different values of `X` . The problem is now about counting the number of pairs for each `X`.

Given `X`, then the number of apples you get in total uniquely determines a pair `(O = A - nX)`, so we just need to count the total number of ways to pick `A` given `X`

The next important fact is to notice that the set of valid `A` values ought to be a interval. So if you know `a_0` and `a_1` are valid and `a_0 <= a_1` , then all `a_0 <= i <= a_1` must be valid too. Then you just need to find the minimum and maximum possible number of apples. The maximum can be found by picking the largest possible number of apples from each bag. The minimum number of apples can be found by picking the largest number of oranges from each bag. Once you get the minimum and maximum number of apples, just subtract them to count the total number of ways to pick it.

long getNumber(vector<int> apple, vector<int> orange)
{
    int n = apple.size();
    int m = 2000000;
    for (int i = 0; i < n; i++) {
        m = std::min(m, apple[i] + orange[i]);
    }
    long res = 0;
    
    // For each valid X:
    for (int X = 1; X <= m; X++) {
        // If we take X, then there are nX in total.
        
        // maximum:
        int mx = 0;
        for (int a: apple) {
            mx += std::min(X, a);
        }
        // minimum:
        int mn = 0;
        for (int o: orange) {
            mn += std::max<int>(0, X - o );
        }
        // total:
        if (mx >= mn) {
            res += mx - mn + 1;
        }
    }
    return res;
}

Div1 500: The one with xor

I couldn't think of a solid solution. I did make the conclusion that you can first pick the first bit position at which the xors differ. Then the problem is about counting the number of ways to have xors: yyyyy1????? and yyyyy0?????. It seems this is the starting point of a solution, but no luck yet.

Comments?

So far it seems like an ok match. Time to write the editorial. Got to rush because I don't want to be busy with it during Christmas. ... Or do I?

11 comments :

vijay said...

I think we don't need the if condition in d1 easy

vexorian said...

That's right.

ZeForce said...

Hi vexorian! I thought that in the 250 pt, the solution which most of the people submitted would time out. So, I came up with a O(n) solution where n is the size of the apple vector.
Have a look.

class WinterAndPresents {
public:
long long getNumber( vector apple, vector orange ) {
long long res = 0;
long long lim = apple[0] + orange[0], n = apple.size();
for (long long i = 0; i < n; ++i)
lim = min(lim, 1LL * apple[i] + orange[i]);

res = (lim * (2LL * (n + 1) + (lim - 1LL) * n)) / 2LL;
for (long long i = 0; i < n; ++i) {
if (lim > orange[i])
res -= ((lim - orange[i]) * (lim - orange[i] + 1)) / 2LL;
if (lim > apple[i])
res -= ((lim - apple[i]) * (lim - apple[i] + 1)) / 2LL;
}
return res;
}
};

ZeForce said...

Hi vexorian! Alternate solution with a better complexity -> http://ideone.com/yKmHhD

Stanisław said...

500 : Can't we just count the number of ways of choosing a subset from X, that have xor 1...(2^ceil(log2(N))) and the same for Y.
The rest is trivial.

vexorian said...

The choices are independent, so if you pick a number for X it cant be used in Y (or I don't get you)

The solution I found is like this:

The two numbers X and Y are such X < Y.

Let's pick i for the most significant bit at which the two integers differ:

So the two numbers will be of the kind:

Y = abcde1?????
X = abcde0?????


Bits larger than i must be equal, bit i must be 1 in Y and 0 in X. The remaining bits can have anything.

This actually means that the XOR of the most relevant bits (including i) must be 00..0001 . So you can make a dp: f(t, r, b)
- t: Is the number of numbers remaining: So you can still decide numbers 1 <= n <= t.
- r: Is the current xor value between X and Y. Adding a number q to X makes r = r ^ q, adding a number q to Y makes r = r ^ q too.
- b: Is the state of the i-th bit in X.

Stanisław said...

Oh, i forgot :)

vexorian said...

0.3 seconds in c++

Anon said...

Hi Nishant, How smart of you to apply summation formula and reduce the complexity ! , I am sure nobody would have been able to think of that , except a ACM world finalist like you ;) ....

ZeForce said...

Why Anon?

Anon said...

Why do you fucking care about who am I ?