Codeforces Round #449 Editorial
Difference between en8 and en9, changed 0 character(s)
[897A — Scarborough Fair](↵

For every $i$ in range $[l,r]$, if $c_i$ is $c_1$ then change it into $c_2$...↵

Because $n, m$ are all very small, $O( nm )$ can easily pass it.↵

PS. You can use binary search tree to solve it in $O( mlogn )$ time.↵

[897B — Chtholly's request](↵

The $k$-th smallest zcy number is $conn(str(k),rev(str(k)))$, where $str$ denotes the decimal representation of a positive integer as a string, $conn$ denotes the concatenation two strings, and $rev$ denotes the reverse of a string.↵

Then go over the smallest $k$ such numbers and sum them up to obtain the answer.↵

[896A — Nephren gives a riddle](↵


First we can compute the length of $f(n)$ for all possible $n$.↵

For a pair of $(n,k)$, we can easily determine which part the $k$-th character is in.↵

If it's in $f(n-1)$, we can solve the problem recursively.↵

The complexity of this algorithm is $O(n)$, which isn't sufficient to pass all tests.↵

Obviously, $length(f(n))\ge length(f(n-1))\cdot 2$, so $length(f(60))\ge max(K)$.↵

It means that for all $n>60$, the $k$-th character of $f(n)$ can only be in $str_1$ or the first $f(n-1)$.↵

Then we can answer a query in $O(\log k)$ time.↵

[896B — Ithea Plays With Chtholly](↵

As the initial sheet "has already" in a non-decreasing order (although it has no numbers), what we should do is just "maintain" this order.↵

We use a simple method to do so: find the first sheet whose number is strictly greater than the given number (or it's an empty sheet) and replace it with the new number.↵

For each round, we either replace an existing number with a strictly smaller one, or fill in an empty sheet. The first case will happen at most $c-1$ times for each sheet, and the second case will happen only once for each sheet. Thus in total, we will modify a sheet for at most $c$ times. Thus, the total rounds won't be more than $n \times c$.↵

To pass all the tests, we only need to maintain 2 similar sequences, one non-decreasing from the first and one non-increasing from the last, which makes a total round of $(n-1)\times \lceil \frac{c}{2} \rceil +1$, precisely, and use binary search or brute force to complete the "finding" process.↵

[896C — Willem, Chtholly and Seniorious](↵

This is an interesting algorithm which can easily deal with many data structure problems------if the data is random...↵

I initially named it as "Old Driver Tree" ( Which is my codeforces ID ).↵

(But now I call it Chtholly Tree~).↵

We can find that there is an operation that makes a range of number the same.↵

We can use an interval tree (std::set is enough) to maintain every interval that consists of the same number.↵

And for operation $2$, we destory all the intervals in range $[l,r]$ , and put in a new interval $[l,r]$ into the interval tree.↵

For operations $1$, $3$, $4$, we can brute-forcely walk on the tree, find every interval in range $[l,r]$, and do the required operation on it.↵

Proof of time complexity:↵

We suppose that we have a randomly selected range $[l,r]$ now, and we randomly choose which operation it is, suppose that there are $x$ intervals in this range.↵

1/4 possibility we use $O( x )$ time to erase $O( x )$ nodes.↵

2/4 possibility we use $O( x )$ time to erase nothing.↵

1/4 possibility we use $O( x )$ time to erase nothing and add 2 new nodes into the tree.↵

So we are expected to use $O( x )$ time to erase $O( x )$ nodes.↵

By using interval tree to maintain, the time complexity of this problem is $O( mlogn )$.↵

If operation $3$ and $4$ are changed into output the sum of $a_i$ for every $i$ range $[l,r]$, it seems that the time complexity may change into $O( mloglogn )$ , but I do not know how to prove it...↵

[896D — Nephren Runs a Cinema](↵

First let's consider a simpler problem that there are no customers with VIP cards and there are no 50-$yuan$ notes left. For convinence, we suppose that $n$ is an even number. The situation that $n$ is an odd number will be similar.↵

By defining points (number of customers currently, number of 50-$yuan$ note left) on a 2d-plane, the answer to our second question is the ways of drawing lines from (0,0) to (n,0), such that two adjacent points' y-axis have a difference of 1, and that all the points are above the x-axis.↵

The total routes will be $C_{n}^{n/2}$, but some of them are invalid. Consider another route starting from (0,-2).↵

For each invalid way in the previous route, consider the first point (x,y) that y<0 (y=-1).↵

By creating a symmetry route with y=-1 for the route before this point, this route will become exactly one route starting from (0,-2), and every route starting from (0,-2) will become an invalid route in a similar way.↵

So the number of invalid routes is $C_{n}^{n/2-1}$ (that is the number of routes from (0,-2) to (n,0)). Thus the answer will be $C_{n}^{n/2}-C_{n}^{n/2-1}$.↵

Similarly if there are [l,r] 50-$yuan$ notes left, the answer will be $C_{n}^{n/2-r/2}-C_{n}^{n/2-l/2-1}$.↵

Now let's enumerate how many customers are there with VIP cards. If there are $i$ of them, the answer will time a factor $C_{n}^{i}$. ↵

One last question is about the modulo number. First separate it into forms like $(p_1^{a_1})*(p_2^{a_2})$... where $p_1...$ are primes. We can calculate how many factor $p_i$ are there in $(j!)$, and the modulo value of the remaining ones.↵

Each time we take out a facter $p_i$ in $(j!)$, and it becomes some product of numbers that are not divisble by $p_i$ as well as a remaining part $(j/p_i)!$. For example, we want to calculate the number of factor 3 in (16!), and the product of numbers that are not divisble by 3 in (16!) mod (3^2). Then we have:↵

16! = (1 * 2 * 4 * 5 * 7 * 8 * 10 * 11 * 13 * 14 * 16) * (1 * 2 * 3 * 4 * 5) * (3^5)↵

The first part are not divisble by 3, so we can calculate their value (mod 3^2) in advance, the second part is a smaller problem (5!), so we can solve it recursively. For the number of factor 3, just add 5 in this case and solve it recursively.↵

After calculating how many factor $p_i$ in $(j!)$ and the modulo value of the remaining ones, we can calculate the combnation numbers correctly. Finally use Chinese Remainder Algorithm to combine them.↵

[896E &mdash; Welcome home, Chtholly](↵

I'm really sorry for letting the brute force algorithm pass the tests...↵

My code uses about 800ms, in order to let some algorithms with large constant or larger time complexity ( like $O( m\sqrt{nlogn} )$ ) pass, I set the time limit to 3000ms.↵

The most naive brute forces uses about 8000ms to 9000ms, I added some tricks and the fastest can pass the tests in 5600ms.↵

In all the contests I've attended, pragma GCC was not allowed to be used...↵

But on codeforces, this can optimize brute force algorithm from 5600ms to about 2500ms...↵

<img src=''>↵

Thanks to [user:MrDindows,2017-12-03] and [user:Shik,2017-12-03] for teaching me this lesson...↵

My solution to this problem:↵

Split the array into $O( \sqrt{n} )$ blocks, each containing $O( \sqrt{n} )$ numbers.↵

In each block, for example block $x$, use $f[x][v]$ to represent the number of $v$ in block $x$.↵

For each number $i$, $belong[i]$ is the the block that $i$ is in.↵

We need to maintain each number in the block.↵

This can be maintained by using DSU or linked list.↵

By maintaining this, we can get the value of every number in a block in $O( \sqrt{n} )$ time.↵

Notice that this two operations are the same:↵

$1.$For every number that is bigger than $x$, decrease it by $x$↵

$2.$Decrease every number by $x$, and for every number that is less than $1$, increase it by $x$↵

For operation $1$:↵

We get the value of each number in block $belong[l]$ and $belong[r]$ using the DSU or linked list, then for every number that should change, we change them.↵

Then we build block $belong[l]$ and $belong[r]$ up again.↵

For blocks numbered from $belong[l] + 1$ to $belong[r] - 1$:↵

If $x \times 2$ $\leq$ max value in block $p$↵
We merge all the numbers in range $[1,x]$ to $[x+1,x\times2]$, and add $x$ to $tag[p]$ , $tag[p]$ means that all the numbers in block $p$ has decreased by tag[p].↵

If $x \times 2$ $\textgreater$ max value in block $p$↵
We merge all the numbers in range $[x+1,max value]$ to $[1,max value - x]$.↵

For operation $2$:↵

We get the value of each number in block $belong[l]$ and $belong[r]$ using the DSU or linked list.↵

We only need to traverse all the numbers in blocks $belong[l]$ and $belong[r]$, and traverse all the blocks between $belong[l]$ and $belong[r]$.↵

For block $i$ in range $[l,r]$, $f[i][x + tag[i]]$ is the number of $x$ in block $i$, so we just need to add this into the answer↵

Proof of time complexity:↵

There are $O( \sqrt{n} )$ blocks.↵

The difference between the max number and the min number in each block is initially $n$.↵
So the sum of this in every block is $O( n\sqrt{n} )$.↵

For each operation $1$, we use $O( x )$ time or $O( max - x )$ time to make the difference of max and min element $O( x )$ or $O( max - x )$ smaller.↵

For each operation $2$, we traverse $O( \sqrt{n} )$ numbers and $O( \sqrt{n} )$ blocks.↵

So the total time complexity if $O( n\sqrt{n} + m\sqrt{n} )$↵

There seems to be another algorithm with the same time complexity, and has a smaller constant, but I couldn't prove its complexity so I used this algorithm instead.↵

<img src=''>↵

(The missing picture on Div. 1E)↵

If you don't like it, just skip it please.


  Rev. Lang. By When Δ Comment
en16 English ODT 2017-12-04 15:46:03 4 Tiny change: 'ission/32912088)\n\n<img ' -> 'ission/32920862)\n\n<img '
en15 English ODT 2017-12-04 13:39:01 8 Tiny change: 'ssion/32912133)\n\n[896D' -> 'ssion/32917976)\n\n[896D'
en14 English ODT 2017-12-04 06:53:30 79
en13 English ODT 2017-12-04 06:49:00 74
en12 English ODT 2017-12-04 05:39:51 193
en11 English ODT 2017-12-03 15:51:23 20
en10 English ODT 2017-12-03 12:58:07 3 Tiny change: ', which isn't sufficien' -> ', which is sufficien'
en9 English ODT 2017-12-03 12:48:47 0 (published)
en8 English ODT 2017-12-03 12:47:47 78
en7 English ODT 2017-12-03 12:46:26 847 (saved to drafts)
en6 English ODT 2017-12-03 12:32:19 264
en5 English ODT 2017-12-03 12:26:06 0 (published)
en4 English ODT 2017-12-03 12:24:29 2 Tiny change: '38.png'>\n(The mis' -> '38.png'>\n\n(The mis'
en3 English ODT 2017-12-03 12:23:50 141
en2 English ODT 2017-12-03 12:11:10 86
en1 English ODT 2017-12-03 12:08:59 8719 Initial revision (saved to drafts)