Hello, Codeforces!

We intend to share some ACM-ICPC regional contests with you! Here is one of them.

An online-mirror contest of 2018-2019 ACM-ICPC, Asia Nanjing Regional Contest will start on Nov/17/2018 13:00 (Moscow time). You may register for this contest 6 hours before it starts, but it is temporarily inaccessible before registration starts.

By the way, this contest will consist of **13** problems and you can solve them within **5** hours.

Wish you will learn great experience through that time!

Waaaaait!

There is another online-mirror contest, The 2018 ACM-ICPC Asia Qingdao Regional Contest (Mirror), which will be held at acm.zju.edu.cn on Saturday, November 10, 2018 at 12:00 (UTC+8), a week before the contest on Gym!

This contest is prepared by our friends from Zhejiang University and indeed a very interesting contest. If you are eager to participate, please do not hesitate to register a handle on it and take part in time!

**P.S.** Please do not discuss any solution before contests are finished. Thanks for your cooperation.

**UPD1:** Ranking that suits for Gym has been parsed from data provided by the host school (Nanjing University of Aeronautics and Astronautics). Enjoy it.

**UPD2:** Registration starts. You may view this page to register.

**UPD3:** In order to be consistent with the onsite one, the duration is extended by 10 minutes.

Bravo! Many thanks to skywalkert for sharing this contest on Codeforces and also recommending the Qingdao Regional Contest prepared by us~

I am pretty sure that these two contests are both very interesting and worth practicing since I watched the whole match on the spot. From my opinion, I am very excited to see the result of talented teams from all over the world participating in Chinese ICPC Regionals. The comparison must be very interesting.

BTW, I hope there will be more and more Chinese ACM-ICPC Regional Contests being shared on Codeforces Community. So we can practice and discuss about them afterwards~

Is it rated?

Of course not

Oops, it is coincided with an opencup round. May you change the time?

Thanks for your reminder! Would it coincide with other contests if online-mirror contest starts one day in advance? If suitable, we can shift it to an earlier date.

UPD:Starting time is advanced from Sunday to Saturday. Wish you all have known.Can't wait to take part in the online-mirror of Asia Xuzhou Regional Contest! Should I expect it or not? Whatever, thank you, skywalkert.

Indeed, You can see it sooner or later. BTW, Asia Xuzhou Regional Contest is extremely difficult, compared to this one. :)

(:ᗤ」ㄥ)The link is unavailable now....I just enterd the home page of codeforces when I click on it.

As it is temporarily inaccessible, please be back just 6 hours before the starting time.

Is there a tutorial available for the Quindao Regional contest? I want to know the solution for problem I and L.

L: if

m>n, the answer is 0, and ifm=n, it's just number of ways to make a single cycle.if

m<n, then the graph is justk=n-mpaths (some may be trivial though). Let's say we fix that there arednon-trivial components (have at least 2 vertices).Then there are ways to choose the endpoints of the non-trivial components, and for each choice, we want to find number of ways to pair them up, which is .

From the remaining vertices, there are ways to choose the vertices in the trivial components.

And finally, the remaining vertices can be freely permuted and then distributed à la balls and bins, in ways -- during the contest, I did this part with Exponential Generating functions; it requires more theory, but very little creativity, so it's easier for me.

We also had to add an edge case for

m= 0 (the answer is 1).(edited to fix grammar)

I: There are at most

O(n) segments to group. So let's sort them and make a two-pointer. What we need to do is to check whether there is a valid division. Segment tree works here, since the information of two segments can be merged easily.I: Sort the valid 2 *

N- 1 intervals by their weight. Let's enumerate the minimum and find the corresponding maximum. Consider a simpler problem: Given some intervals (L_{i},R_{i}], find whether we can cover the interval (0,N] without overlapping. It's equivalent to finding whether we can reachNfrom 0 by the edges . Because the length of a interval is at most 2, we can maintain a segment tree, where the segment [L,R] stores the connectivity between [L,L+ 1] * [R- 1,R]. It's easy to merge the information. Using a 2-pointer and maintaining the connectivity dynamically, we can solve the problem in .M is too difficult for me TAT. How to solve it using SAM? I know I should use manacher first, and then I can do nothing using SAM qwq.

First, count how many palindromes begin with

s_{i}and let the number bef_{i}.Then, find the maximum length

d(d≥ 0) such thats_{i - k}=t_{k}for eachk= 1, 2, ...,dand let the length beg_{i}.The answer should be .

The first part can be solved using manacher algorithm as you know, and the second part is equivalent to calculate for every suffix of the reversed string

rev(s) the longest common prefix (LCP) witht, which can be solved using Z algorithm.Maybe it's an overkill to use suffix array or suffix automaton solving this problem, isn't it?

Thank you! I understand your solution. It's too difficult for SAM to solve it. I want to use SAM because ... my friend that took part in Nanjing regional contest told me: "There was a problem using SAM in this contest, I couldn't accept it because I have not learned it." So I try SAM all the time orz. And finally I think I should use prefix automation but I have not learned it LOL.

Did you know of the following solution for K (Kangaroo Puzzle)?

simple solutionJust print a uniformly random button 50000 times.

This was much easier than

other solutionIteratively finding a short sequence of moves that merges two kangaroo groups.

Why does the randomized solution work for K?

How to solve problem D — Country Meow?

I was thinking of radius of smallest sphere that can enclose all the points

I did ternary search on all 3 coordinates. Do a ternary search on x first, now for getting optimal answer for this x, do ternary search on y keeping x fixed, repeat this for z, keeping x and y fixed.

Thanks buddy. :)

How to solve E — Eva and Euro coins ?

delete the k-continuous 0/1 in the 2 string and compare them

Thanks :)

Can you give a proof?

We should first show that deleting k 0s or k 1s leads to a unique result from a starting string S. This is true as if a string of k 0s is deleted in some deletion sequence from S, then in any other sequence, eventually, at least one of these 0s must be deleted, and it has the same result as deleting all k of these 0s.

Now we should show that two strings which result in the same base string can be transformed to each other. However, it's possible to move a block of k 0s or k 1s past any single character, so each string can arrive at the state 00000000 + base string by moving the blocks to the left, in order of their deletion.

I enjoyed the problemset. Thanks!

How to solve F? I had a N^3 divide-and-conquer solution for it. It has a big constant factor and gets TLE. Any better algorithm?

The first thing to explain is that the following one is not the standard solution. We just tested all the problems but didn't understand solution from the problem author. Never mind.

Let the answer matrix be

F(the expected steps moving fromutov), the normalized adjacency matrix beE(the probability of one step moving fromutov), the identity matrix of sizenbeIand the all-one matrix of sizenbeJ, there exists a diagonal matrixGsuch thatF=EF+J-G. IfGhas been determined, what remains is to solve the equationF(I-E) =J-G.Since the rank of (

I-E) is (n- 1), we cannot directly solve the equation. But we know some additional conditions, such asF_{i, i}is always 0. What can we do with this condition? We may construct infinite solutions of the above equation by setting the valuesF_{1, 1},F_{2, 2}, ...,F_{n, n}freely and then determining other values in the matrix. It can tell us each solution is in the form ofF_{i, j}=FF_{i, j}+x_{j}wherex_{1},x_{2}, ...,x_{n}are free variables andFFis any solution, so we can simply apply Gaussian elimination to reduce the first (n- 1) rows and get a specific solutionFF. Then, fix the values by the conditionF_{i, i}= 0.Did I miss something? Emmm... The calculation of

G. Actually, I don't know how to explain it easily, but whereP_{i}is the stationary probability (in stationary distribution of a Markov chain) that a random-walking object appears ati. You may calculate the vectorPby the equationsPE=Pand .The above solution is in time complexity

O(n^{3}). However, as you've seen, there exists a solution which applies Gaussian elimination to each (n- 1)-subsets of vertices by divide and conquer. The onsite judges thought participants who have learned this solution could soon come up with the optimized solution, so the time limit is a bit strict. facepalm.jpgBy the way, I tested the divide-and-conquer solution (without setting an epsilon) and it passed all the test cases with 1513ms, while the first one passed with 202ms. Maybe you just need some optimization on CodeForces?

The matrices are similar for all terminals. They differ by only two rows. Thus you use Sherman–Morrison formula to maintain the inverse matrix.

My solution also gets TLE during the contest.