What's the name of the contest you're logging in to?

Just a rainbow of GCDs and LCMs :D:D

That is mine (full acc):

   int a,b,x,y; cin>>a>>b;
    int gcd=GCD(a,b);
    x=a/gcd;
    y=b/gcd;
    if (x == 1)
    {
        cout<<a*(y-1);
        return 0;
    }
 
    int ans=(y/x)*(a);
    int nashti=x*(y%x);
    
    int lcm = LCM(x, (y%x));
    ans+=gcd*(lcm/x-1);
    cout<<ans;

Well, Java solutions are not tested yet, but answer is m — gcd(n, m) I believe

First we build suffix array of a big string. For each pattern string we want to know first occurrence in the big string. We find interval in suffix array in which pattern occurs by binary searching suffix array then we find out suffix in that interval that starts in the minimum position. Finding minimum can easily be done with segment tree.

Example:

• big string = 4234343.
• pattern = 343.
• suffix array:
• 1 234343.
• 6 3.
• 4 343.
• 2 34343.
• 0 4234343.
• 5 43.
• 3 4343.

• matching interval is:

• 4 343.
• 2 34343.
• minimum is 2.

We sort pattern strings by position of first occurrence in big string. For each pattern string we want to find out number of positions where none of the letters is matched, where only one letter is matched, first two letters are matched and so on. Of course we are only interested in part of the big string before out first occurrence. Again finding interval in which first k letters of pattern string are matched can be done binary searching suffix array. Now we want to know how many of suffixes in that interval are positioned left of pattern's first occurrence. We can do that with Fenwick tree because we sorted pattern strings by their first occurrence so after we're done with some pattern we need to put 1-s on certain positions in Fenwick tree before we process next pattern

100% is 50% solution with multiset =) 100%

Sort the bags by increasing size, the objects by increasing weight.

List all objects that can go to the smallest bag. It's obvious that you want to take the most expensive one (since those objects can't go to any larger bag), if there is one. So you do it.

For the 2nd bag, take all objects except the one you added before, and add to them all that can go to the 2nd bag but not to the 1st. You're in an identical situation as before, so take the most expensive object. And so on for all bags.

It can be implemented with 2 pointers and 1 multiset, in .

A possible 50% solution uses dynamic programming (first i elements cover first j bags, how much can it be worth?), or just this idea without sorting and adding objects efficiently. It can be different, but doesn't have to.

First choose some (i, j) as common corner of the two fields. And then add all sums sum(p, q, i, j) where p ≤ i and q ≤ j to an array (lets say V₁) and sort it. Similarly add all sums sum(i + 1, j + 1, p, q) where i + 1 ≤ p and j + 1 ≤ q to an array (lets say V₂) and sort it too. Then find how many numbers X(=some number) are in V₁ (lets say it is cnt₁) and in V₂ (let it be cnt₂). Then increase answer by cnt₁ * cnt₂. This can be done in O(V₁.length() + V₂.length()). Here is how it is done in C++:

#define sz(X) (int)(X).size()
...
int l1=0, r1=0;
int l2=0, r2=0;

while (l1 < sz(v1) && l2 < sz(v2)) {
    bool ok1 = (v1[l1] <= v2[l2]);
    bool ok2 = (v2[l2] <= v1[l1]);
    
    if (ok1)
        while (r1 < sz(v1) && v1[r1] == v1[l1]) r1++;
    
    if (ok2)
        while (r2 < sz(v2) && v2[r2] == v2[l2]) r2++;
    
    res += (r1-l1)*(r2-l2);
    
    l1 = r1;
    l2 = r2;
}

Above is the case when one field is in up-left and the other is in down-right of the common corner. Do the same when one field is in up-right and the other is in down-left of the common corner.

Complexity: maximum possible value of V₁.length() and V₂.length() is N², so O(2 * N² * 2(N² + N²log₂N²)) = O(N² * N²log₂N²)

P.S. sum() function is inclusive :)

I have an , too, but it runs in 0.88s on the largest test case. If you have an additional log-factor, it's important to take down large constants (like, by looping from i to N, not from 0 to N).

There's a pure O(N ^ 4) solution. Let's fix the left — top corner of one rectangle. Then we need a number of rectangles that upper and left from the fixed corner. So let's iterate in O(N ^ 2) for all possible left top corners of second rectangle and increase a count of certain sums. Then let's iterate over all possible right — bottom corner of first rectangle and add to our answer the count of certain sum. Do this for a left bottom case simmetrically. O(N ^ 4) total. Code.

Since the maximum number is 2000000, just iterating all possible factors will get AC in very short time.

http://ideone.com/pzdlwJ