Hi all!

The 2018 ACM-ICPC Asia Shenyang Regional Contest has ended on October 21. At this site, 186 official teams and 6 guest teams selected from the preliminary online contest have competed in **5 hours**, trying to solve **13 problems**.

We are glad to invite you all from Codeforces, one of the greatest programming communities, to participate in its online-mirror contest, 2018-2019 ACM-ICPC, Asia Shenyang Regional Contest!

Please notice the online-mirror contest will start at an unusual time, Saturday, November 24, 2018 at 18:00 (UTC+8), when we are able to answer your questions during the online contest. By the way, we have added the onsite board, so when you are participating (during the mirror contest or virtual participation), you may take advantage of it!

This contest follows the ACM-ICPC rule and it will be **unrated**. Both personal registration and team registration are recommended. You may register for this contest **6 hours before** it starts, but it is temporarily inaccessible before registration starts.

Also, many thanks to:

- Teachers, volunteers and technical staff from Northeastern University for holding such a wonderful contest;
- AHdoc, Claris, niike0goood, quailty and me for problem setting;
- yefllower, zscc, wangyenjen, adrien1018, eddy1021, waynetuinfor, boook, johnchen902, yp155136 and pr3pony for testing;
- MikeMirzayanov for Codeforces and Polygon platforms;
- icpc.foundation, JetBrains and Jisuanke for sponsoring the regional contest.

Besides, we kindly ask everybody who has already read the problems not to participate or discuss solutions in public before the contest has ended. Please keep the sportsmanship all the time!

Hope you enjoy the problems!

**UPD1:** Our sponsor Jisuanke will hold another online-mirror contest soon after the contest on Gym. If you missed this one, you could participate the other one, which will start on Sunday, November 25, 2018 at 12:00 (UTC+8) without the onsite board.

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

**UPD3:** Contest has ended. Any discussion will be greatly appreciated. If needed, we will discuss solutions after tomorrow.

I have practiced or participated onsite of 2018 Shenyang, 2018 Nanjing and 2018 Xuzhou Contests. From my perspective, I think Shenyang is typical of this year's ICPC East-Continent Regional contest for both problem structure and the onsite regional result. Can't wait to discuss about the problem after the mirror contest~

Thanks skywalkert, Claris, quailty along with other problem setters or testers for sharing this amazing contests in the community. and BTW, I believe it is unrated~~~

Thanks to the problem setter and tester, interesting contest.

Hi, how to solve K?

it seems that using only DP formula F(N,K) = (F(N-1, K) + K)%n is not enough...is there any critical observation?

Problem K is a typical Josephus problem, so its solution may be a well-known method.

Let the answer decreased by 1 as

f(n,m,k). We could find the recurrence relation is that and .If

m≤k, we can calculatef(n-m+ 1, 1,k),f(n-m+ 2, 2,k), ...,f(n,m,k) in order. The time complexity in this case isO(m).If

k≤m, we can find out that during the calculations fromf(n-m+ 1, 1,k) tof(n,m,k), there are many positionsxsatisfyingf(n,x,k) =f(n- 1,x- 1,k) +k(i.e. the modulo operation doesn't affect atx). From the statef(n,x,k), we can find the minimum integertsuch thatf(n,x,k) +tk≥n+tand skip the statesf(n',x',k) (x<x' <x+t). Ifk> 1, the "jump" process has at most steps. (It may not be a tight upper bound, since it is just obtained from inequality scaling.) It is easy to show (using Cauchy's mean value theorem), so the time complexity in this case is .Actually, the time complexity of the skip method is . You can fix the case that

k= 1 and use this skip method to get accepted.