Lewin's blog

By Lewin, history, 7 years ago, In English
Police Patrol
Alphabetic Subsequence
Infinite Graph Game
Stamp Stamp Stamp
Increasing Sequence
Yet Another Binary Matrix
  • Vote: I like it
  • +81
  • Vote: I do not like it

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

When opened the author's solution for C and got that v_i can be zero :(

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

For problem C it seems that an O(nk) solution works. I didn't submit it during the contest because I assumed it would be too slow, but I submitted it after the contest (mostly to check that I'd gotten the corner cases right before trying a smarter version) and it passed.

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

    And on the other part of the world, there was me, who got TLE on O(nk) solution.

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

      Did you have any mods in your inner loop? My inner loop avoided them.

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

        Yes. I have a modinv inside outer loop. May be avoiding that would have done the trick.

        https://pastebin.com/QXp88ZeK

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

          This part of your code

              for (int i = 1; i <= k; i++) {
                  int u = s[i];
                  for (int v : V[u]) {
                      G[v].push_back(cnt[v]);
                  }
                  cnt[u]++;
              }
          

          is like saying "I can't decide if I want to get TLE or MLE, but I'll make sure to get at least one of them". If the input is a star, you're doing O(KN) push_backs...

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

          Here's my code that runs in just over 1s. The O(nk) part is simply adding v[x] for all neighbours of a vertex in a 64-bit accumulator, so it has low constant factor — but still ought to have timed out given the right test case.

          https://pastebin.com/WnMphk9Q

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

C: I thought O(n * sqrt(n) * log(n)) is not intended to pass.

It can be solved in O(N * sqrt(N) + k ) , where N = n + m.

My solution:

I calculated the value of vertex just before it divided by two. Then sum up all the values after first phase. Calculate the second time the same value but for the second phase and then multiplies it by constant. To get N * sqrt(N) solution, just need to split vertices in big and small by amount of edges.

Code, but code-style is bad

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

    C: I thought O(n * sqrt(n) * log(n)) is not intended to pass.

    Agreed, it looks like it should not pass. Actually my O(n * sqrt(n) * log(n)) solution passes in 2.433 s. I think the constraints have been set a bit too high.

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

    I think it is trivial to reduce to .

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

In D, also a simple greedy way to check a substring worked: repeatedly find a place where you can put a stamp and cover some new characters, and see if you can cover the whole string. This is O(n^5) but only took about 200 ms on the server; I don't know if we could find a test to break it.

»
7 years ago, # |
Rev. 4   Vote: I like it +28 Vote: I do not like it

C in O(n1.5)

Let's call a vertex heavy if its degree is at least sqrt(n). Otherwise, it's light.

For every vertex, we linearly compute the initial sum of values of its light neighbors. Then we process changes. When we change a light vertex, we iterate over its neighbors and change their "sums of values of light neighbours". When we change a heavy vertex we just update its own value. When we answer a query, we know "sum of values of light neighbours", and we must additionally iterate over heavy neighbours. It's fast because there are at most O(sqrt(n)) heavy vertices in the graph.

(in fact, we should change n to m in some formulas above, whatever)

quite simple code: https://pastebin.com/aLuidVN4

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

D in O(N3):

Let's try all k. For one k, let's look at all substrings with this length, group them by identity (using hashing) and look at each group.

If we're covering with a substring (stamp) w and it occurs at indices id1 through idn, we should find for each index idj the maximum length of a substring [l, r) surrounding it which can be constructed in the following way:

  • start with [l, r) = [idj, idj + k)
  • while there is a prefix of w which covers [l - d, r) (d is the length of this prefix), extend l to l - d
  • the same for a suffix of w which covers [l, r + d), extending r to r + d

Each substring [l, r) can obviously be covered with w. If there is a substring u of S that doesn't occur in either of those substrings, two situations can occur:

  • u is a prefix or suffix of S — there's no way to cover S with w
  • u is between two substrings [l, r) — iff u is a substring of w, then it's possible to cover S with w

Why? The situations where it's possible to cover S are clear. Otherwise, let's look at the last application of the stamp which covered some character in u. In this operation, we couldn't have covered a proper prefix or proper suffix of u, since that would mean we could either extend one of the strings [l, r) or (when u is a prefix/suffix of S) this prefix/suffix is also a prefix/suffix of S and we'd have one more index among id1..n. We couldn't have covered an inner substring of u, since we'd also have one more index among id1..n. The only remaining possibility is that u is fully covered in this one operation, which corresponds to it being an inner substring of w. (Which isn't an option if u is a prefix/suffix of S.)

The above process can be simulated quickly if we precompute the LCP of each pair of suffixes of S (straightforward, O(N3)). There are only O(N2) indices id in total. For each of them, we can keep extending the string by trying all possible values of d until we find one that fits (each can be checked in O(1) using the precomputed LCPs), where we stop and try again. This way, we spend O(N) steps on failing to extend or x steps on extending by x, and we can only extend by O(N) in total. Checking if u is a substring of w can also be done in O(N) by iterating over all suffixes of w and using precomputed LCPs. This way, we take O(N) time per each id.

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

    I came up with the same solution but with hashes instead of LCP's. I think(but not sure) it can be modified to O(N2). For each fixed l we can precompute maximum prefix at which substring can be extended for each r simultaneously in linear time. The rest part of the solution remains the same.

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

Can anyone elaborate the line sweep that will "find some point such that this point is not in F(i) or not in T(i) for all i" in problem E?

»
7 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

My solution for E:

It's clear that the flipped subsequence has to be decreasing and the non-flipped subsequence increasing. Some prefix of the flipped substring will then consist of elements that decreased when flipped (K - x < x) and the remaining suffix will consist of elements that increased when flipped.

Let's look at any prefix 1..p (possibly empty, the following is irrelevant for p < 2) containing no elements that increased. This prefix follows a simple rule: if xp - 1 < xp, then xp - 1 shouldn't be flipped; otherwise it should. (The latter holds since xp can't be any smaller; the former because element p is either non-flipped, where xp - 1 should be greedily maximised, or because it is flipped, in which case flipping xp - 1 wouldn't make the final sequence increasing.)

For each prefix and each state of its last element, we can now compute an interval of valid K in case it doesn't contain increased elements — we already know the states (flipped/non-flipped) of all previous elements, so this is straightforward O(N) DP.

A similar DP can be done for each suffix in case it doesn't contain decreased elements. Now we can check all cases "prefix 1..i is of the first type, suffix i + 1..N of the second type", try all (up to 4) options for the states of the last element of the prefix and the first element of the suffix (if they exist), compute an additional constraint on K, combine this with the intervals of valid K for the prefix and suffix, and if there's some valid K as a result, construct the solution greedily using it.

Also, my solution for B:

Meet in the middle. For each sequence of 5 numbers, compute the shortest prefix and longest suffix containing it, then check for each sequence in O(1) if it can be constructed. Time complexity O(10·9·8·7·6·|S| + 10!).