skywalkert's blog

By skywalkert, 12 days ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • +265
  • Vote: I do not like it  

»
12 days ago, # |
Rev. 3   Vote: I like it +127 Vote: I do not like it

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~

»
12 days ago, # |
  Vote: I like it -73 Vote: I do not like it

Is it rated?

»
11 days ago, # |
  Vote: I like it +40 Vote: I do not like it

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

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
Rev. 2   Vote: I like it -75 Vote: I do not like it

(:ᗤ」ㄥ)

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The link is unavailable now....I just enterd the home page of codeforces when I click on it.

  • »
    »
    4 days ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 days ago, # ^ |
    Rev. 2   Vote: I like it +26 Vote: I do not like it

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

    if m < n, then the graph is just k = n - m paths (some may be trivial though). Let's say we fix that there are d non-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)

  • »
    »
    4 days ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

  • »
    »
    4 days ago, # ^ |
    Rev. 6   Vote: I like it +40 Vote: I do not like it

    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 (Li, Ri], find whether we can cover the interval (0, N] without overlapping. It's equivalent to finding whether we can reach N from 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 .

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it +21 Vote: I do not like it

    First, count how many palindromes begin with si and let the number be fi.

    Then, find the maximum length d (d ≥ 0) such that si - k = tk for each k = 1, 2, ..., d and let the length be gi.

    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) with t, 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?

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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.

»
2 days ago, # |
Rev. 2   Vote: I like it +41 Vote: I do not like it

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

simple solution

This was much easier than

other solution
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D — Country Meow?
I was thinking of radius of smallest sphere that can enclose all the points

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

»
2 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve E — Eva and Euro coins ?

  • »
    »
    45 hours ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      33 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks :)

    • »
      »
      »
      12 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you give a proof?

      • »
        »
        »
        »
        4 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
29 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    28 hours ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 from u to v), the normalized adjacency matrix be E (the probability of one step moving from u to v), the identity matrix of size n be I and the all-one matrix of size n be J, there exists a diagonal matrix G such that F = EF + J - G. If G has been determined, what remains is to solve the equation F(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 as Fi, i is always 0. What can we do with this condition? We may construct infinite solutions of the above equation by setting the values F1, 1, F2, 2, ..., Fn, n freely and then determining other values in the matrix. It can tell us each solution is in the form of Fi, j = FFi, j + xj where x1, x2, ..., xn are free variables and FF is any solution, so we can simply apply Gaussian elimination to reduce the first (n - 1) rows and get a specific solution FF. Then, fix the values by the condition Fi, i = 0.

    Did I miss something? Emmm... The calculation of G. Actually, I don't know how to explain it easily, but where Pi is the stationary probability (in stationary distribution of a Markov chain) that a random-walking object appears at i. You may calculate the vector P by the equations PE = P and .

    The above solution is in time complexity O(n3). 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.jpg

    By 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?

  • »
    »
    11 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.