It feels more longer to users whom Div.3 contest is unrated for.

Wish not.

Unfortunately, no :(

I don't think so.

B and C are difficult for Newbies.

D is easy if you know some number theory, but B is just casework, I don't think it's harder.

bilal saeed hoooooooooooooooo!!!!!!!!!!!!!!!!!!!

I consider C as a problem which I've solved it before.Unfortunately,I couldn't remember it exactly while the round.Now I can get it.

Find g=gcd(a,m). Divide m by g, i.e. let f=m/g. Find Euler Totient Function value of f i.e. phi(f).

keep segtree on array where arr[i]=cost if you split at i, start by putting everything on the right and leaving the left empty, so arr[0]=a[0], arr[1]=a[0]+a[1]... then start by putting 1 on the left, then 1 and 2, then 1,2 and 3 and so on. when you put a new number on the left the cost for all splits with that number already on the left decrease by a[position[i]], the cost of all the splits without that number (the ones with i<position[i]) increase by a[position[i]]. each time get the minimum in range (0,n-2) (because you can't split at last element).

Another segment tree solution that doesn't require range update/lazy propagation:

Represent each segment by the triple $$$(suml, sumr, cost)$$$. Define the combination of two segments as follows: $$$A + B = (suml_A + suml_B, sumr_A + sumr_B, \min(cost_A + suml_B, sumr_A + cost_B))$$$ (this operation is not commutative, but it is associative)

Start with $$$tree[p_i] := (0, a_i, 0)$$$. Iterate $$$i$$$ over $$$[1, n-1]$$$ by updating $$$tree[p_i] := (a_i, 0, 0)$$$, then grabbing the $$$cost$$$ value from the "sum" of the entire segment tree. The answer is the minimum $$$cost$$$ value retrieved.

Explanation: Fix a split of the permutation to sets $$$L$$$ and $$$R$$$. $$$suml$$$ represents the sum of the costs of $$$L$$$ in that segment, likewise $$$sumr$$$ for $$$R$$$. Now consider how to combine the statistics for segments $$$A$$$ and $$$B$$$. Combining the sums is obvious, but what is $$$cost$$$? Consider there is a point $$$x$$$ within the segments where we want to move all points $$$i > x$$$ from $$$L$$$ and $$$i < x$$$ from $$$R$$$. If $$$x$$$ is in the left segment ($$$A$$$), the new cost is $$$cost_A + suml_B$$$, as we must move all members of $$$L$$$ in the right segment ($$$B$$$). If $$$x$$$ is in $$$B$$$, the new cost is $$$sumr_A + cost_B$$$ as we must move all members of $$$R$$$ in $$$A$$$. We thus pick the minimum of these two scenarios. The updates progressively move elements from $$$R$$$ to $$$L$$$ as the initial split. Be sure not to move the last element, or your answer would always be spuriously $$$0$$$.

Sample: 69829539

Let $$$d = gcd(m, a)$$$ and $$$m_1 = m / d$$$, $$$a_1 = a / d$$$, $$$b_1 = b / d$$$. Then $$$gcd(m_1, a_1) = gcd(m_1, b_1) = 1$$$.

In other words, you have to count numbers $$$b_1$$$ with $$$0 \le b_1 < m_1$$$ which are coprime to $$$m_1$$$. This is actually an Euler function, $$$\varphi(m_1)$$$.

Yes, but there is one more condition on b, that b >= a. It can be easily done by just altering the algorithm for calculating the Euler Totient Function.

We can reduce the problem to couting the number of numbers relatively prime to m on interval [0..m/gcd(a, m)]. Let's say that m = m/gcd(a, m). Firstly you need to factorise m and store vector of unique prime factors. Then you can use the principle of inclusion and exclusion to calculate the number of such numbers that have common prime divisor with m.

I've done it kinda differently compared to the Euler Totient guys here. Using the statement notations, we have a, m, and x. a = gcd*u and m = gcd*v, where (a, m) = gcd so (u, v) = 1 gcd must divide (a+x) so gcd must divide x therefore we have x = gcd*y

Which brings us to an equivalent problem: find the count of y for which: (u+y) and v are coprime, where y is in range [0, v), aka their gcd is 1.

For that, I used the principle of inclusion/exclusion because v had something like 12 factors maximum. And because I was in full blown panic mode and couldn't think of Euler.

How did you come up with gcd(m,a) = gcd(m, b). Couldn't understand this part.

How do you make GCD (a, m) = GCD (b, m)

One who uses hakase as profile is always on a roll :)

my_submission

dp[i][j] -> nearest index of alphabet(j) after index i

and iterate through string t and solve problem greedily

Store indexes for every letters 'a' to 'z' from String s. After storing, sort the indexes of individual letters. At first make a variable idx set to 0 before iterating String t. set ans to 0. While iterating on String t, you can check if current character happens from idx to afterwards in String s by just doing binary search on that character's stored indexes. if idx is not found in stored indexes, set idx to 0 again and now it must be found. just increment the ans when idx is not found.

just in case when at least one letter in String t is not in String s, then the ans is -1.

This question was copied from here not fair:( https://stackoverflow.com/questions/53065084/minimum-no-of-operations-required-to-create-string-a-by-appending-subsequence-of

Short solution summary (div1 500)

Me too. The error message "Illegal Contest ID" is shown

Me too.

Same

ya, yep, yes, yo

And one of the funniest thing is that ma_da_fa_ka even tried to hack himself,although that hack was unsuccessful. xD

So why Codeforces can't stop them from cheating?

I think that will be a big problem.

Wish MikeMirzayanov can manage to stop them.

Instincts....

Let $$$d = gcd(a, m)$$$.
Since $$$0≤ x < m$$$ and $$$1 <= a < m$$$, we easily conclude that $$$(a + x)$$$ mod $$$m$$$ can take values in the range $$$[0, m - 1]$$$ and we know that $$$gcd(a + x, m) = gcd(m, (a+x)\ mod \ m) = d$$$

Let's look at the case when $$$d = 1$$$, let $$$b = (a + x)\:mod\:m$$$, our goal is to find all the values of b where $$$gcd(m, b) = 1$$$ which is by definition $$$\phi(m)$$$ given that we concluded earlier that b can take any value in the range $$$[0, m - 1]$$$.

Now, let's consider the case where $$$d \neq 1$$$. Clearly, the values of b that we are looking for in the range $$$[0, m - 1]$$$ must be multiples of $$$d$$$, so let's enumerate all the $$$m / d$$$ multiples of $$$d$$$ in this range as follows: $$$ 1, 2, ..., (m / d)$$$. Let $$$i$$$ be the enumeration of the $$$i^{th}$$$ multiple, we want to count $$$i$$$ such that $$$gcd(i * d, m) = d$$$, but since $$$d \ | \ m \ and \ d \ | \ (i * d)$$$, we really want to count $$$i$$$ such that $$$gcd(i, m / d) = 1$$$, which turns out to be $$$\phi(m / d)$$$.

Learn to read.

read the entire statement, it also mentioned Note that the answer may not fit in the standard 32-bit or 64-bit integral data type.

Agree, I would have spent years trying to debug my solution if I did not decide that solving C first is a better idea...

You can create an array $$$cnt_0$$$ and $$$cnt_1$$$ in which $$$cnt_x[i]$$$ is the number of characters $$$x$$$ are from $$$0$$$ to $$$i$$$. Also, you can calculate $$$delta[i]$$$ which is $$$cnt_0[i] - cnt_1[i]$$$. Then, when the string is repeated again, the same pattern of $$$delta$$$ is going to occur but increased by a constant, because the number of $$$0$$$ and $$$1$$$ that you have from the previous string are accumulated. I'm going to concatenate $$$s$$$ two times to make the pattern visible.
Let's analyze the following input
$$$n = 6, x = 10, s = 010010$$$
$$$cnt_0: 1, 1, 2, 3, 3, 4 | 5, 5, 6, 7, 7, 8$$$
$$$cnt_1: 0, 1, 1, 1, 2, 2 | 2, 3, 3, 3, 4, 4$$$
$$$delta: 1, 0, 1, 2, 1, 2 | 3, 2, 3, 4, 3, 4$$$
Every time a string has finished, delta is going to change in a constant. Let's called that constant $$$d = delta[n] - delta[0]$$$. For each position $$$i$$$ between $$$0$$$ and $$$n - 1$$$, you know that you can reach all the numbers of the form $$$delta[i] + kd$$$, in which $$$k \geq 0$$$ because it is the number of times that the string is going to be repeated. So, for each $$$delta[i]$$$, $$$i$$$ between $$$0$$$ and $$$n - 1$$$, you have to check if it possible to obtain a non negative $$$k$$$ such that $$$x = delta[i] + kd$$$. The only corner cases are in which $$$d = 0$$$, then, if you have at least one solution, you are going to have infinite solutions of this form. Finally, check the case of the empty string if the solution is no infinity. The time complexity is $$$O(n)$$$.

take '0' as $$$1$$$ and '1' as $$$-1$$$ and calculate the prefix sum $$$pre$$$.

then for each $$$pre_i + x\cdot pre_n = balance$$$_$$$value$$$, if there is a non-negative integer $$$x$$$ satisfying the formula, add 1 to the answer. if balance_value is zero then add another 1 to the answer.

if $$$pre_n=0$$$ then if there exists an $$$pre_i=balance$$$_$$$value$$$, then answer is -1; else answer is 0.

2 6 2 001001 3 0 011

See 69759300

It is correct for sure.

why is it really bad? is it because you didn't do well in this contest.

what a good contest for you would look like?

Bruh salty. Edus are getting better ever since they reduced it to 6 problems.

BRs82 was one of the worst person in all of the codeforces users.The comments were really bad.i hope to see better user in future.

This has already been explained in previous comments.

Let $$$gcd(a, m) = g$$$
We have $$$gcd(a, m) = gcd(a+x, m) = gcd((a+x) \ \% \ m, \ m)$$$
Notice that as $$$x$$$ increases, $$$(a + x) \ \% \ m$$$ will end up taking all values in $$$[0, m)$$$
So we only need to find the number of $$$k \in [0, m)$$$, such that $$$gcd(k, m) = g$$$

Since $$$gcd(ca, cb) = c \iff gcd(a, b) = 1$$$, we can take any integer coprime to $$$m/g$$$ and multiply it by $$$g$$$ to find a suitable $$$k$$$.

[Nothing bruh]

Educational CF Round and Div.3 Round have no points for successful hacking attempt.

The EMPTY STRING is also a valid prefix.

It was ensured in the announcement.

It means that one of the problem makers' solution is incorrect. (The official solutions had a different answer to each other.)

A very simple testcase in Problem C was hacking testcase for many solutions.

1

aaaa....a(length is 100000)

aaaa....a(length is 100000)

If I woke up early, I could do more hacks.

For problem A,the number has two forms:

111...111

or

7111...111

If n is even,the first form is better,otherwise,the second form is better.

The editorial of B,C and D are showed in former discussions.

I haven't solved problem E,F yet,so you can ask tourist . :D

Nope,but INMAK also uses DP.

It's 3.

There are three prefixes that satisfied the condition:""(EMPTY STRING),"01","0110".

Let X be gcd(a,m),so gcd(a/X,m/X)=1.

If gcd(a+x,m)=X,then (a+x)%X equals to 0,x%X also equals to 0.

So gcd((a+x)/X,m/X) equals to 1.

Find all the x in eular algorithm.

It would surely be published. Not sure about the release time.

In your loop for(int i=0; i<((n-1)/2); i++), it should be i < (n — 3)/2 instead, as 7 takes 3 resources.