For those who upvoted my question above :)

Say, a sequence of numbers sum to t. Out of all such sequences, what can be the gcd of all numbers in the sequence? It has to be a divisor of t. Let it be d = gcd(a₁, ..., a_k). Because all a_i is divisible by d, thus the sum is also divisible by d, where the sum is t.

Hope this helps..

Hi I had thought of something like this but have a doubt.

Can you please answer the query over here in this comment?

Thanks!

Oh, your solution sounds exactly like one found by me! I've solved the problem in C language, but after the contest has already ended... (((

what will be output for following test case? and how ? please reply 5 elements : 4 3 5 1 2

hello,i saw your code and ran it for the test case 5 1 2 3 5 4 it gave the answer 5 while even if we remove 4 the number of records is going to be the same.Can you please explain where am i mistaken?

It's a bug. Correct explanation should be: decrease by one all integers in the sequence, represent them in unary system with zeros, and split them with ones.

You can think of it like this way. We have n ones in a lines. Let's say our n = 5. This will correspond to 11111. Now, there are are 4 positions in between those "ones" (more precisely, consecutive ones) where we can place a barrier. What I mean by barrier is like this (11|11|1) where | represents a barrier, hence our paritition will be (2, 2, 1) for 5 or we can place our barriers like this (1|111|1) where our partition will be (1, 3, 1) or like this (111|1|1) which corresponds to another valid partition (3, 1, 1). Hence, we can say that at each of 4 positions, we can choose to place a barrier on it or not and it will always produce a unique partition. Therefore, we have 2^(5 - 1) = 2⁴ choices (2 because we can have a barrier in between consecutive ones or not). Hence, if we have n ones, we'll have n - 1 barriers to place, so we'll have 2^n - 1 choices to make. Interstingly, this technique can be used to prove some more important problems, like proving "dividing n among k groups where each group gets atleast 1 which we can say selecting by k - 1 barriers out of n - 1 barriers". I hope you understand it now.

Thank you, we didn't think about such case. We'll be more attentive next time.

That's how I understand it.

First if x does not divide y, then the answer is zero, since the gcd has to divide every number, it must divide the sum.

Now to the case where x divides y, we need to calculate all sequences that sum to y / x with gcd 1, why? Because any valid sequence can be transformed to such form if you take the gcd as a common factor. Let's say a1 + a2 + a3 ...an = y, and the gcd of a1,a2,a3.. an is g, then we can write it as g*b1 + g*b2 + g*b3...g*bn = y, which is the same as g*(b1+b2 + b3 +..bn) = y, now divide by g, and you get b1 +b2 +b3 + b4...bn = y/g.

Now to count the sequences of sum X and gcd 1, you start by saying that all sequences are valid, so you add all sequences that sum to X ( To get that number, check the comment by I_Love_Equinox, he explains it perfectly, or google stars and bars theorm).

After you do so, you need to subtract bad sequences with gcd > 1 and sum equal to y / x, the gcd must divide the sum again (y/x) , so you re-enumerate the process by finding numbers that sum to (y/x)/g, where g divides y /x. You keep doing so recursively.

Think it like this way. How do we actually calculate where a < b. We multiply a = a * 10 until a ≥ b, then in quotient of the division, is appended and we calculate the new division for a%b. For example, . We do a = 5 * 10 = 50. We append to our quotient and calculate 50 - 49 = 1. This 50 - 49 is nothing but 50%7 = 1 and hence we'll now start off the new step of the division from here (i.e. again multiply 1 with 10 and our new quotient will be 0.71...). So, if two remainders in the process are same, the whole process will repeat, and consequently the period will repeat. Since, there are b distinct remainders and will always be  ≤ 9, hence, due to pigeon hole principle, atleast one value of remainder will repeat and period will be

First of all, we need find if is possible make a string t starting of position i.

Lets make a dp only for odd positions. This dp[position][letter] answer the longest string can be create, just looking odd positions, starting with the letter in second state and only using this letter or '?'. Do the same thing for even positions.

There are in string t exactly ceil(|t| / 2) a's and floor(|t| / 2) b's (|t| is the length of string). So, to check if string t exists starting of position i, you can just look the previous dp check dp[i]['a'] >= ceil(|t| / 2) and dp[i]['b'] >= floor(|t| / 2)

The cost of make this string is exatly the number of '?' between indexes i and i + |t| — 1.

Now, we know if is possible to make string t starting to index i and which is the cost to do that. So, we can write another dp to solve the final part of the exercise.

If is possible make a string t starting on position i

dp[i + |t|] = best(dp[0 .. i]) + costStartingPosition(i);

In this case, dp[x] is a pair (maximum number of words, minimum cost).

So, the cost of make a string finishing on position i + |t| is the best cost between indexes [0 .. i] plus the cost of starting a word on position i.

This best(dp[0 .. i]) can be implemented with a segtree dp or just mantain the best dp of the indexes [0 .. i] in linear time.

Solution: http://mirror.codeforces.com/contest/900/submission/33138394

As mentioned already in some comments in the discussion, fft could be used for general strings t.

For this one I did the following. First for each position pos find the maximum prefix of the word t that can be built, which ends in pos and count the cost of building it.

There are few cases: if pos has '?', you can extend the previous prefix if the previous prefix had length < m. If not you can either construct the prefix of length m (if you had at least m-1 continuos positions with '?' before pos) or m-1 (if there is at least one letter, it uniquely determines the prefix).

If pos has a letter you can try to extend it, if the parity of the previous prefix is ok (even for 'a', odd for 'b'). Again you will be able to extend it, if the length was < m, if not, you will be able to get m-1.

Whenever you add '?' or move the beginning and get rid of initial '?' update cost correctly.

The last case is when you can't extend previous prefix, which means that you have a letter at pos. In that case try to get as many continuous '?' as possible, ending at pos — 1 and create new prefix.

Once you computed the values above you just need to run simple dp to count maximum number of disjoint occurences and minimum cost of it.

Code for reference.

A similar algorithm was used using C++ STL sets to find the position of the digit c in problem 900B - Position in Fraction in the decimal (base-10) representation of the fraction a/b during the contest, where items of the set are distinct co-prime pairs <a,b>, 1 <= a < b <= N, where N = 100000 generated using long division of co-prime pairs computed using the __gcd function. This could lead to faster execution time when b is non-prime.

33128670

The aforementioned algorithm was extended as follows using C++ STL bitset and template for more efficiency, and to be used for any Radix and any N rather than 10 and 100000, respectively.

33151934

+1

I would say it is more difficult since D is the only problem I need one submission to get accepted, but I could not solve E.

Yup. E is a trivial dp problem.

You should use Mobius inversion formula to solve D. At first we have such expression: . If we use Mobius inversion formula, we are getting a new expression to calculate f(t): . Sorry for my bad English.

Editorial solution has O(n) time complexity where n is length of s.

But if string t has an arbitrary form it is possible to use FFT algorithm to find positions where occurences can start. So time comlexity will be O(length log length) due to FFT.

e-maxx in his post said that he had found such an interesting fact here: "for all ε > 0, d(n) = o(n^ε)". He also gave other estimates but he said that on practice we use numbers less than 10¹⁸ so it's easier to use an estimate that is more rough than others.

Permutation can't contain repeated integers by its definition. A permutation is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. You can read about it here for example.

The problem states that it would provide you a permutation of 1 to n Find out a single integer 'x' from the given permutation; which has the longest increasing subsequence to its right so that every number on that increasing subsequence is greater than all the numbers left to 'x' and every number on that increasing subsequence is strictly less than 'x'. If there are more than 1 such numbers with equal length of increasing subsequence at its right, pick the minimum one.

This is how I understood the problem and solved it.