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 :

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

That's right.

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;

}

};

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

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.

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.

Oh, i forgot :)

0.3 seconds in c++

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 ;) ....

Why Anon?

Why do you fucking care about who am I ?

Post a Comment