ko_osaga's blog

By ko_osaga, history, 6 years ago, In English

Hmm.. Am I the only one not appearing in the scoreboard?!?

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

»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Same here... Are only people that participated at the MIPT camp shown on the scoreboard?

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

We see a bug in Yandex.Contest standings generator that won't allow us to properly generate standing for contests with large number of registeder users (aounr 6000 for opencup rounds because of sector system). We're investigating the issue, will do our best to fix it by the next opencup round. I am very sorry for the trouble.

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

    This bug is at least several months old =)

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

      not exactly, contest log generation for previous opencup round took around 5 minutes and allowed teams to appear on official opencup standings (though it is definitely far from good)

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

The important thing on B:
You SHOULD NOT output the answer like
! 2 2
11
00

The "correct" answer is:
!
11
00

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

How to solve C.Array and D.Modular Knapsack?

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

    C: Let M = min(A). If M occurs in A once, then the answer is M. Otherwise, consider the first occurence of M.

    Note that, any aj such that aj > ai, j > i are useless. Thus, we can conclude that the "modulo chain" before the first occurence are strictly decreasing. Also, After passing the first occurence, the value Xi will never decrease unless it is M. We will find a set of numbers that can be the result of xi after passing the first occurence.

    Then, we should find all number N such that N can be represented as ... when ai > aj > ak. This can be done with DP. Sort A and remove duplicates. Let DP[i][j] =  (true iff j is possible outcome after passing some subset of modulo chain for length-i prefix). This can be calculated easily in O(n2), and with some bitset labor you can reduce it to O(n2 / 64).

    D: Let's solve minimization problem instead. It seems that the one with large weights are mostly useless, as it seems they can be replaced with smaller ones. The tests are intentionally broken, so this is enough. Add the item in the order of weights, run the program for 1.45 second and quit. You can easily transform the min. problem solution into max. problem.

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

      In C, is it like: say upto i, the bitset is B, then at i+1, you will divide the bits in a[i+1] lengths, and OR them with B to get newB? That yields, n^2log(n)/64, right? Any better way?

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

        Exactly that. And it is N^2/64 + NlogN.

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

          How do you get [bit_i, bit_j] quickly?

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

            I implemented my own bitset.

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

              Finally I solved this problem and it was really difficult for me to implement operation get_segment in bitset and what I done is something like sqrt decomposition: shift left pointer until it is on a start of some bucket (in our case bucket is an int and it's size is 32), then shift right pointer until it is on the end of some bucket and then process all buckets between left and right pointers. Processing is just splitting current bucket into two parts — one with size (32 — how_much_we_shifted_left_pointer) (head) and the other one is what is left (tail), and then save these parts in a new bitset in bucket i and i+1 respectively — head part goes to i and tail part goes to i+1 bucket.

              My implementation is here. It uses long insted of int, but it doesn't matter.

              It may seem overcomplicated, but this is the only proper method I can imagine. Could you share your bitset implementation or/and tell something how it works?

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

      Also there is deterministic solution for D with idea of convex hull and stack.

»
6 years ago, # |
  Vote: I like it +45 Vote: I do not like it

How to solve B?

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

    +1
    How many people who wrote AC solution for B are interested in how to solve it?

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

      Let me try. (I'm not very confident, I don't understand suffix automatons very well.)

      Let's call a string of length n "row string" if it appears at least once as a row of the secret board. We want to determine all row strings. Then it's easy to recover the entire board in O(n2) more steps.

      Suppose that we currently know that s1, ..., sk are row strings for sure. We want to find another row string, or conclude that there are no more row strings.

      Let's construct a suffix automaton for the string s1 + 'x' + s2 + 'x' + ... + sk. For each state in this automaton, let t be the shortest string that reaches this state. Let's query "t + 'a'" in case the automaton doesn't accept it; if the secret board contains it, we can get a new row string by extending it. Do the same for t + 'b'. If we can't find new row strings this way, we've found everything.

      Since we can construct the automaton incrementally, the total number of new states we get is O(n2), and the number of queries is O(n2).

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

    The solution is to find all different rows of the table one by one and then in n2 queries restore it.

    If you have found k rows, you need to find any string that is not a substring of any of these k rows. Then it can be expanded to the whole row in at most 2n queries.

    Consider a trie of all substrings of already found rows. You can try to go by non-existent transitions of the trie and ask if there is such a string in the whole table, do this in the order of length increase. However, in its simplest form, it will work in cubic number of queries. Here comes the trick to make it 2n2 overall — if you already know that some substring of the string you are about to ask doesn't exist, skip this query.

    If you consider the trie as a suffix automaton of k strings, you can prove this upper bound. There will be at most 2n2 states in the automaton and among all transitions by the same character from each vertex you will ask only about the shortest string, skipping the others.

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

When the upsolving of this and past div.2 contests will be available?

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

How to solve the "hellish" problem G? Is there an article on arXiv or somewhere else about this problem?

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

    I have some kind of "editorial" for G.

    Recall the algorithm for building automaton. Let's calculate expected number of cloned states then add n + 1. Consider adding last character of string s. Let t be the longest suffix which occurs more than once and let a be the character preceding t. Then vertex cloning had happened iff there is character b ≠ a such that it preceds each occurence of t except for the last one.

    For string s denote sequence |s|, |π(s)|, |π(π(s))|, ... 0 as chain(s) (here π(t) is longest suffix shorter than t equals to prefix of t). Let's calculate all possible triples (chain(t), chain(at), chain(bt)), where a and b are different characters. Also for each triple we need to know the number of triples of strings (t, at, bt) which corresponds to this triple. Knowing only (chain(t), chain(at), chain(bt)), it's possible to calculate number of strings s such that vertex cloning happened.

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

      You don't need triples. You need to calculate for each t number of strings that contain it and subtract those in which all occurences of t are preceded by the same character a. Only pairs (chain(t), chain(at)) are needed for that.

»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Is it really possible to solve problem J in 19 minutes or is that AC in 19 mins some kind of a hoax xd?

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

    It took me 30 minutes to solve it, 19 mins doesn't sound crazy.

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

      Btw how to solve it?

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

        Suppose that all coefficients of polynomials are in F2. The key observation: P(x)2 = P(x2).

        For an integer n and a polynomial Q, let f(n, Q) be the number of nonzero terms in Pn * Q.

        • In case n is odd, use f(n, Q) = f(n - 1, PQ).

        • In case n is even, first decompose Q into "even part" and "odd part": Q(x) = R(x2) + xS(x2). Then f(n, Q) = f(n / 2, R) + f(n / 2, S).

        This way we reach only O(2dlogn) states.

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

          Did you actually implement this as recursion with memoization? Because it looks like it's rather hard to fit into the memory.

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

        rng_58's solution is cool and I think that I do mostly the same thing, but I came up with that in a very different way.

        I will also use that P(x)2 = P(x2), so P(x)n = P(x2a0)P(x2a1)... P(x2am - 1). Now let's calculate (imaginary) DP[i][j]: we multiplied first i polynomials and interested in coefficient for xj (basically DP[i] is a product of i first polynomials). We can see that if j1 and j2 have different remainders modulo 2ai then they are independent, so our DP is a set of 2ai independent DPs, corresponding to different remainders modulo 2ai. Each of these DPs have only d interesting states, all other values are zeroes. So we can count the number of DPs with given mask of values in another dp, now real (in the code). We have to make transitions for imaginary DP, they will correspond to transitions in our real DP.

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

      You're crazy, it took me rather something like 2-3 hours xd. But it seems my solution looks significantly more complicated. I didn't even use explicitly the fact that P(x)2 = P(x2), I base my solution on fact that is odd iff i1, i2, ..., ik are submasks of n in binary system.

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

    J is a well-known problem in China:

    Version 1

    Version 2

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

      We were afraid that it could be well-known(

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

      OK, "HDU-coach" team name and this question being asked on HDU online judge explains a lot, I suspected that's likely reasonable explanation.

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve A, E, H?

  • »
    »
    6 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    H: Note that if k is the largest value of a n-beautiful multiset A, then the elements of A that are smaller than k have to form a k - 1-beautiful multiset. If there are x copies in k, then we get x·k + (k - 1) = n, so k is a proper divisor of n + 1. Conversely, taking such a k and adding x copies of k to a k - 1-beautiful multiset, we always get a n-beautiful multiset. We can hence use dp to compute the number and total size of n-beautiful mutisets as follows

    The number of states used in computing DP[n] is equal to the number of divisors of n + 1.

    Edit: Does someone have a good bound on the number of divisors summed over divisors of n to bound the total runtime? (Something better than this comment.)

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

      Actually, intended solution for H was with convolution repeated times, but we failed to set time limit properly.

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

        If number of good pairs of good divisors for maxtests is something like d(n)2 / 60 (with d(n) ≈ 60000 then good luck with distinguishing it from :P

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

          Yes, the number of good pairs is around 107, but I also had to index all the states properly. I wrote solutions with a binary search and a trie to do indexing on dp states, and they both worked very slow comparing to the main solution. My bad I didn't force somebody not so retarded in writing fast solutions to try to fit this into TL.

          But anyway, the possible solution would only be to increase constraints to 1018 (and make bigger TL also). I'd say it's controversial whether it'd really improve the problem.

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

            I agree that indexing is some kind of an issue we should deal with (and I used unordered_map for this on beginning), but it can be easily solved by computing corresponding indices recursively along with other info we compute (I was not sure whether by last sentence in first paragraph you meant that you're retarded cause you didn't notice it or whether because you didn't try hard enough to do some other optimizations)

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

    A: Let's say that ai dominates aj if i, j are incompatible and ai > aj. For every k, we can color it with the length of the longest dominating chain ending with ak (so ak the the largest element in the chain). Note that is is optimal, as every chain forms a clique.

    To compute the coloring quickly, we compute for every bitmask m two numbers: The largest color C of a value ai contained in the mask and the maximum number D of bits in which some such ai differs from m. If m occurs in a and D ≥ k, then we increment C and set D to 0. From every mask, we can transition to other masks by setting another bit. The total runtime is O(22·222 + n).

    I also had a funny issue where declaring array<pair<int8_t, uint8_t>, 1<<22> exceeded the compiler memory limit for some reason.

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

    E: For every node we'll compute the total cost if the capital was placed there. This can be done efficiently with centroid decomposition.

    For a fixed centroid C, we root at C and compute for every vertex v the contribution of towers t not located in the subtree of C containing v. For a fixed tower t, its contribution on a vertex v in a different subtree only depends on the depth (=distance from v to C). Moreover, as a function of this depth, the contribution is piece-wise constant with pieces of length k (and an infinitely long piece for 0), so we can efficiently get the total contribution for every depth by prefix-summing over each residue class mod k separately, then prefix summing over the whole array.

    To deal with the whole not-in-its-subtree, we compute the contribution of every subtree (only for depth up to the height of the subtree) and the total contribution for every depth. The total runtime is , even for k up to n.

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

Can I be solved in O(nlogn)?

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

    Can you tell the easier (slower?) approach, please? :D

    After the contest BledDest told me the solution and also mentioned that it's about the same as in 911G - Mass Change Queries. I can't believe that's what everybody submitted, looks really advanced to me tbh. :D

    Let's maintain the segment tree over the queries (segments). At the beginning every node is the identity 2x2 matrix. The merge is matrix multiplication. Then you process all 2n ends of segments in the ascending order. When reaching the beginning of some segment, update the corresponding node in the segment tree with matrix ((100 — p, p), (p, 100 — p)), the end is back to identity matrix. The answer for the end is the root of the tree.

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

      You can just build a lazy segtree (where you only do updates, no queries) over the positions, where the lazy stores the probability of being repainted. The lazy-merge function is similar to what you get with your matrix multiplication: merge(p1, p2) = (1 - p1)p2 + p1(1 - p2). First compress the li and ri to 0, ..., 2n - 1. For every request, you update [li, ri - 1] with p. Then you push all updates down to the leaves of the segment tree. For every leaf, you add it's value times the length of the corresponding uncompressed segment to the answer. Total runtime is .

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

        Ye, it's not the application of ST that seems advanced to me but that presence of ST by itself. Like that path I took was about "do the basic events sort thingy; however, we want to delete elements, that would require matrix division". Then I coded some (so it would not require division, like recalcing the whole dp with matrix exponentiation on each step) that somehow turned not precise enough, I believe (or that WA was purely of my bad implementation). I can't understand what should have pushed me to think about ST.

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

      My solution is in . It's unnecessarily complicated. Basically, I have decomposed the segments into chunks. Then proceeding the events from left to right, when an enter/exit event occurs we have to update it's corresponding chunk in time order of chunk size. By updating, for each chunk we will keep the probability of taking odd segments from this chunk. Each query can be answered in by going over the values calculated for each chunk.

      It was not the intended solution. I had to optimize a lot to ACe it. However, what I was doing in my solution can be done with a segment tree too. But I didn't notice during contest time.

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

        My solution is the same and the only thing I had to optimize is to replace List<Integer> to int[]. I thought it would be absolutely useless, but it worked =)

        This solution doesn't seem complicated as for me. And yes, after the contest I realized that it worked for 0.983s.

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

      I had some wrong ideas at the beginning and wrote more complicated O(pn) solution (p = 101). I basically maintain the count for each pi, and compute the matrix multiple in O(p) time with appropriate precomputation.

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

        What are those precomputations? It seems, I can't squeeze my by any means)

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

          WLOG assume 0 ≤ Li < Ri ≤ 2N. For each interval [i, i + 1] we can have the histogram of each pi occurence with difference arrays. Let qpi be such occurence. Then we want to calculate M0q0 × M1q1 ×  ... when Mi is the state transition matrix for probability i. We can simply precompute those powers in O(pn) time, Now we can calculate the answer in O(p) time.

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

            Oh, I thought about the difficulty of storing all of them and never even cosidered multiplying them right away. Nice approach, thanks)

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

    This is probably the fastest to code solution.

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

      I tried to implement the same idea after the contest, but got WA. Probably because I did multiplication/division instead of log addition/subtraction which cost a lot of precision error. How did you know that you need to do the calculations in logarithmic scale at first?

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

        It's a common practice actually, without logarithms it's possible to construct a test in which at first the product becomes very small (of order 2 - n), and after that it becomes close to 1 again, but the precision is lost in the first phase.