wilcot's blog

Eastern Grand Prix
By wilcot, history, 7 years ago, In English

Very interesting contest.

But, how to solve task K, L and H?

Thanks in advance.

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

Comments Comments (31)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

L: We construct tree greedy , then solve problem with centroid-decomposition code: https://ideone.com/kzZmuP

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

L: Once we have the shortest paths tree, computing the answer can be done using centroid decomposition.

The tree can be computed with Dijkstra's algorithm, modified to prefer parents with a smaller path from the root (with respect to the lexicographical order). Checking if a path is smaller can be done with binary lifting, in a way similar to the computation of LCAs.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You can build tree without comparing pathes. After Dijkstra algorithm you can use DFS using only edges related to some shortest path, one thing you need before DFS is to sort edges by destination.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

H. Let p = x - y, q = y - z, r = z - 1. Then, in pqr-space, a subhill is of the form p ≥ const, q ≥ const, r ≥ const, p + q + r ≤ const.

Fix the value of p + q + r (try all O(N) possibilities). Now the task is a standard 3D-sum problem. In total it works in O(N4).

I believe it's also possible to solve it in O(N3) but looks quite messy.

→ Reply
»
7 years ago, # |
  Vote: I like it +29 Vote: I do not like it

H: Let's split each 3d update/query into <=100 2d updates/queries. For fixed y, we get update/query on some rectangle. First do all updates using inclusion/exclusion (adding +-1 to points (X,Z) to denote adding +-1 to all x>=X, Z>=z and then taking partial sums to find value at position (x,z)); now you can answer each 2d sum query in O(1) using partial sums once again.

K: Kind of divide-and-conquer. Let's assume that each query contains element n/2. In this case we can calculate dp for each suffix of the left part of the array and for each prefix of the right part; now in order to answer a query you can combine corresponding suffix of first part and prefix of second part in O(D). Now we are left with queries which are completely contained within left or right subarray; OK — let's solve them recursively. That gives us O(D * M) to answer all queries and O(N * D * logN) to calculate all DP values at each level of recursion.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any new upsolving? When I access upsolving system, the last problem is old -> "O-17 Sphenic Numbers".

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give the links of old problems? I don't understand what is Grand Prix. I see blog of its discussion on codeforces but there is no link to the actual problems. Is it a private contest?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      It is private, but very good contest. Site is p̶r̶i̶v̶a̶t̶e̶c̶u̶p̶.̶r̶u̶ opencup.ru You can participate if you are registered in team, and your coordinator (in my case he is a lecturer in my university) gave you credentials.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Yes, it's a private series of ACM ICPC-style contests called Open Cup (website is in Russian only). Problems are private, participation is restricted to "sectors" only (it's basically a multi-site contest).

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Is there a site where old problems are available for public in English? Is it illegal for the participants to share the problem statements?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          I don't think there is one. No idea about the legality.

          → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          Actually, there are a lot of problem statements of previous seasons in public access here: http://opencup.ru/

          Just choose season in left menu with the button "Выбрать сезон".

          Then choose stage in menu "Выбрать этап" and there you can find problem statements.

          → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Finally, upsolving have apear!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ...and later disappeared by 'Service is not available' :(

      → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can i find problems?

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

F?

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

B?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Find the rightmost '(' that can be paired with some ')' in the range, and the leftmost ')' that can be paired with it, and remove them.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    We can get digit D as answer if all non-null digits in N are not less than D and all digits after first occurence of D in N are equal to 9. Find the biggest D we can get.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Lets compare digits by parameter 'how much this digit meets in the range 1..N'. How to make this comparator: The base observation is an each digit meets equal amount of times in numbers in the range 1..10^x-1. So lets process digits of number N from left to right, suppose current digit is X, there are three cases (suppose lhs < rhs):

    1. if x > rhs or x < lhs just continue, because it means that lhs and rhs occured equal times in numbers, in numbers with this prefix.
    2. if x == lhs, than lhs is better
    3. if x == rhs, than lhs is better, excluding the case if remaining suffix contains only '9', in this case we should just continue as we did in the first case.

    If lhs not better than lhs, we can take rhs. So as result we can find maximum D where D have the same amount occurences as 1.

    → Reply
»
7 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Does anybody know when (approximately) contest will be unfrozen? Just curious.

→ Reply
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Problem A is copied from this one.

And I think problem F is also copied from problems of Multi-University Training Contest in China. In my mind, I have solved this problem before.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C??

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider all 4! permutations, after left,right,top,bottom fixed, you can fix horizontal & vertical offsets between left & right. After that you can find answer using dp (hint: for fixed horizontal offset precalc cnt[i][j] for top/bottom strings — count positions p, that s[p]=i and s[p+offset]=j).

    → Reply