tourist's blog

XVII Open Cup: GP of Gomel
By tourist, history, 7 years ago, translation, In English

XVII Open Cup Stage 10: Grand Prix of Gomel takes place on Sunday, February 5, 2017, at 11:00 AM Petrozavodsk time.

The link to the contest. You need an Open Cup login to participate.

I'm the writer of all the problems.

This problemset will also be used at Barcelona ACM ICPC Bootcamp on Monday, February 6. Unfortunately, this means I have to ask you to refrain from discussing the problems in public until the end of the contest in Barcelona on Monday, 5:30 PM Barcelona time.

Let's discuss the problems here on Monday evening!

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

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

Hi, could you please give me more info about open cup?

  • What is open cup? (I never heard it before)
  • Is problem statement in English? (The link provided seems to be in Russian)
  • How to get Open Cup login? (I didn't see any register button there)

I'm interested in participating since I'm free this Sunday.

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

    Unfortunately based on what I read in this discussion, link, there is no simple way to get an Open Cup login :(

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

will this problemset be available for those who don't have authentication credentials?

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

Can somebody provide a link to live standings of Barcelona ACM ICPC Bootcamp contest?

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

Is there some PDF/text file of the problemset publicly available?

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

The contest is over. How to solve B,D,E?

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

    B. Suppose that we add x to the first two disks. Then for each pair of adjacent disks the number we should add to the pair can be represented as a linear function of x. Let f(x) = min(x%m, m - x%m). The problem is about minimizing the sum of a function of the form f(x) + f( - x + a) + f(x + b) + f( - x + c) + ..., and this is a standard task. Notice that we should add two cases (depending on the parity of n) separately.

    D. Reduce it to a knapsack problem, where the cost and the volume of each item is up to 400. We want the total cost to be exactly x and we want to minimize the volume. When $x >= 400^2", we can choose "the most efficient one" greedily. After that do some DP.

    A. The definition of the object we want to count look overwhelming — how to solve it?

    F. We can see it as a game on two stacks. The critical case is when it's Appleman's turn, in both stacks the top is apple, and the two fruits at the bottom are different. In this case I assumed that he should always take an apple from the stack whose bottom is apple — how to prove this?

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

      A: Let's look at some solution. Assume at some moment maximum used value is x and now you used value y < x. After this all values in (y + 1;x - 1) become "locked" — you can't use them. So we can just think we took value y, but maximum value becomes y + 1. It means that at any moment last value equals to maxValue or maxValue - 1. So we can consider following dp[position][maxValue][maxCan][difference] — we stay at some position, largest used number is maxValue, maximum number you can use now is maxCan (It's number of ascents plus 1). Difference equal 1 if last number you picked equal maxValue and 0 otherwise. This dp has O(n3) states and it's easy to calc it in O(n4) time. To reduce time to O(n3) you need notice some "add to prefix offline" parts in formulas and do it.

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

      What is the solution for "the standard task" in B? I did not see this problem before. The way I solved may be a bit complicated.

      For n odd: I get equation 2x = a (mod m). I solve for x using extended gcd. There are not many solns for x within [0, m) [at most 4]. So I try each of them and select the minimum.

      For n even: I convert -x+a -> x+a'. Then I solve circular version of another standard problem: given location of some points in the circle, select a location so that, sum of distance from this point to other points is minimum. This problem can be solved using "kind of circular sweep".

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

        Yes, I did the same thing for even n (f( - x + a) = f(x - a)). For odd n, we don't need extended gcd — such x is either a / 2 or (a + m) / 2.

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

      In D: Do you mean digit-dp like dp? I mean, there are 400 numbers, each with weight 1, 2 ... 400. And there is cost associated with them as well. We need to make sum of weights x such that the cost is minimum. And probably it can be solved using digit dp like dp. Each time you fix lsb of the numbers, then the next one and so on.

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

How to solve E and I?

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

    I: Let f(x) be the number of integers smaller than x, but lexicographically larger than x. For example when n = 2345, we want to compute f(1) + ... + f(2345).

    Divide it into two parts: f(1) + ... + f(999) and f(1000) + ... + f(2345). The latter is harder. For a 4-digit number "abcd", we can prove that f("abcd") = (9 + 99 + 999) - 111a - 11b - c. Using this, we can compute f(1000) + ... + f(2345) by performing O(#digits) biginteger operations, so it will be O(#digits^2).

    To make it faster, our goal is to represent the answer of the form a1 + a2 * 11 + a3 * 111 + ... using small integers a1, a2, ... (then we can get the decimal representation of the answer easily). It turns out that we can compute these coefficients using bunch of prefix sums and FFTs.

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

    E:

    Sort the people by their rating. Then we perform a sweep. We have the following querries: 1. update the sum on an interval 2. ask for the greatest sum that ever occurred on an interval

    This can be done using a segment tree with lazy propagation. We need to store the following values in every node: current maximum in the segment, the best maximum that ever occurred in the segment, the sum that needs to be propagated to the subtree, the greatest sum of the propagation that ever occurred after the last time this node propagated to its children.

    Now it is fairly simple to correctly maintain all of these values.

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

How to solve C?

→ Reply