marcosvcloures's blog

By marcosvcloures, history, 6 years ago, In English

Since the 2018-2019 ACM-ICPC Brazil Subregional Contest doesn't have an Official Editorial, I propose that we make an "Community Editorial".

B — Nim

We can think of every position [i, 0], [0, i], [i, i] as "insta-winning" positions. To model so, we can give them a very high Grundy number, so they doesn't conflict with any other possible Grundy number. That way, the cells that can only move you to an "insta-winning" cell, recieve an Grundy number of 0, meaning that they are losing positions.

After that, we can preprocess all possible positions and get it's Grundy number.

The final answer is just the nim-sum of every starting ball.

Accepted code

C — Sweep line

To make things easier, we can think of every cut as an straight line. First, we need to observe two things:

  • Every line splits an area into two new areas.
  • Every line intersection splits an area into two new areas.

Then, the answer must be h + v lines from the first observation  +  h * v lines from the second observation (every vertical line intersects with every horizontal line)  +  the number of intersections of lines in the same orientation.

It's easy to see that lines of the same orientation can only intersects if (starti < startj and endi > endj) or (starti > startj and endi < endj).

One fast way to count how many times the above is true is to use an sweep line (from left to right, bottom to top, etc).

Accepted code

D — Ad hoc

Just count the number of numbers ! = 1

Accepted code

E — String

Just follow the statement.

Accepted code

F — DP

We can model the problem with the following indexes: The stages that we've already seen and the current time.

Since there are at maximum 10 stages, we can store the first index in a bitmask.

Then, we can apply the following recurrence:

dp[0][0] = 0;

for(i : possibleBitmasks)
    dp[i][0] = -infinity

for(j : [1, 86400])
    for(i : possibleBitmasks)
        dp[i][j] = max(dp[i][j], dp[i][j - 1])                                    // watch nothing

        for(k : [0, number of stages - 1])
            if(i & (1 << k))                                                      // the bit k is on
                for(s : stages[k].shows)
                    if(s.endTime == j)
                        dp[i][j] = max(dp[i][j],
                                   max(dp[i][s.initTime] + s.songs,               // been on this stage before
                                       dp[i ^ (1 << k)][s.initTime] + s.songs))   // first time on this stage

But it's not fast enought :(

To fix it, "skip" to the relevant moments (aka, the end time or the start time of an show) and calculate only the values of the relevant moments.

Accepted code

I — Ad hoc

We can think of the lights as "bits" in an bitset, and the light switches as xor operations. After that, it's kinda easy to notice that we'll cicle through all possible values after 2 * M operations.

Then, we just simulate what is described in the statement (with an limit of 2 * M operations) and print the result.

Accepted code

Full text and comments »

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