Can you please elaborate as to why check(mid) will be O(N/mid)? I'm unable to understand the complexity.

To achieve this complexity you need to keep your interval tree balanced, for example by using a splay tree. I looked at your submission (26724827) and it seems it will time out on a case such as:

50000 1
1 2 ... 50000
100000
2 1 1
2 2 2
...
2 50000 50000
2 1 1
2 2 2
...
2 50000 50000

Sorry, I know this is an old post, but can you explain to me the difference between a segment tree and an interval tree? I thought they were the same.

Welcome to "Python isn't so fast, as C++" club!

Choose m by (l+r)/2, try to do text with m lines, if you can m = l, else r = m. So you get answer in l when became r — l <= 1.

Define function f(w) — number of lines you will require if its width is limited to w. This function is monotonous, f(w) ≥ f(w + 1) for every w. And binary search is usually applied to monotonous functions.

Let's consider the case when GCD isn't a divisor of n. Let it be some value g. Then resulting sequence looks like x₁·g, x₂·g, ..., x_k·g. Its sum is equal to x₁·g + x₂·g + ... + x_k·g = g·(x₁ + x₂ + ... + x_k). That is divisible by g. The sum is equal to n. Thus n is divisible by g. This lead us to contradiction(? I'm not sure of right word to use).

We need to check n — s > (k — 1) * d, because sequence must be ascending. If this inequation is false, then last number is breaking this rule. There is no need of checking for gcd(n — s, d) = d. If n is divisible by d and all other numbers from sequence, which sum is equal to n, are divisible by d, the last number also must be divisible by d.

"Don't forget that you should consider d and n / d, if you check divisors up to square root of n." Maybe, you should get acquainted with fast algorithm to find all divisors.

Let's say we have a set S of K elements. The power sets (all possible subsets including null sets is 2^K)

Now for this problem we are given an array a1, a2, ..., aN and here we have to find subsequences of this array such that all GCD is equal to 1.

Let's try all g (all possible GCDs) from 100k to 1. ans[g] is how many possible subsets we can make with GCD in this subset is equal to g. Our answer will be in ans[1]

We now iterate for all possible g, let's denote the number of elements which has GCD equals to g as cnt(g). Then the value of cnt(g) is sum of all numbers of elements which has divisors of g, 2g, 3g, and so on.

The number of possible subsets with GCD = g is equals to 2^cnt(g) — 1 (since we have to exclude null subset). However for some multiple of g, we have already counted before. That's why by using inclusion-exclusion ans[g] value will be equal to 2^cnt(g) — 1 — ans[2g] — ans[3g] — ...

To have a better understanding, you can view my solution Submission

Consider the dp_{i j} table from the tutorial. For a given i, all j such that dp_{i j} are true must be in one continuous segment. Therefore, you can do dynamic programming by storing the min and max of this segment for all i instead of storing the boolean for all i by j

My code (java) might be easier to understand than my explanation: 26787020

I was able to do greedy in O(n) with a stack (Submission).

From the start, keep a running sum of the score. Treat (W) as +1, (L) as -1, and ignore (D)s and (?)s.

At any point, if the score becomes k or -k, assign the nearest (?) to a (W) if score=-k, or (L) if score=k. Here, you can keep track of the nearest (?) by using something like a stack.

Now be careful, after changing you'll have to slide the whole window after that (?). If the shift will make a part of the score still hit k or -k, then output NO. Otherwise, keep going.

Now once you reach the end, we'll need to make the score k or -k so we simulate both options. Making use of the stack of (?), to target score=k, we assign the last k — score unknowns as (W)s. The remaining (?)s can be (D)s. Similarly, do it for (L) with score — (-k) unknowns. Check if it still satisfies everything, then we can output either working answer (otherwise, output NO).

We're trying to maximize a the GCD of a (positive strictly increasing) sequence of length k that sums to n.

Consider any sequence that has a GCD greater than 1:

• 2,4,6,8
• 3,6,12,15
• 7,21,49

Note that if a sequence has a GCD > 1, we can factor that number out:

• 2{1,2,3,4}
• 3{1,2,4,5}
• 7{1,3,7}

Because we can factor this number out, n (the sum of the sequence) must be divisible by the factor.

Also note that the smallest possible sequence of length k, {1,2,...,k}, sums to k*(k+1)/2.

We can combine these two observations in the following way.

• Iterate from 1 to root(n) to find the factors of n.
• For every factor x, we can consider if it's possible to make a valid sequence of length k where every element is a multiple of x.
• We know that for this factor, the smallest possible sum is obtained with the sequence x*{1,2,...,k}
• Therefore, the sequence is possible if and only if x*[k*(k+1)/2] <= n.
• That's all there is to this problem. Also note that once you find the largest factor that satisfied the above equality, you can stop searching, since any smaller factor will yield a smaller GCD
• The edge cases where you should return '-1' are where the equality x*[k*(k+1)/2] <= n doesn't apply for even the smallest factor, x=1.

Below is an example:

Consider the input "12 3"

• The factors of 12 are [1,2,3,4,6,12]
• k*(k+1)/2 = 6
• We need to find the largest factor of 12, x, such that 6x <= 12
• x is obviously 2.
• The answer will be some sequence 2{a,b,c} that sums to 12
• The answer is therefore "2 4 6"

I hope that helps!

In submission 26808542 your output is 500000003 1000000006 1500000012. 500000003 is not divisible by 3 so clearly your output's gcd is not 3. Further you can check gcd of your output is 1.

Err, the gcd can be much larger than 1000

Think of the first line, suppose by using the greedy logic you decide that you can have n words in the first line. Since greedy is taking as many words as possible, no other solution can have more than n words in the first line. Also, by taking more words, you're leaving fewer words for the remaining k-1 lines. So if a solution is possible by taking more than n words in line 1, it should be possible by taking exactly n also.