giorgosgiapis's blog

By giorgosgiapis, history, 7 years ago, In English

Sixth round of COCI 2017/2018 season will take place this Saturday at 14:00 UTC.
You can find the full schedule for this season here and register for the contest here.

Let's discuss the problems here after the contest.

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

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

How to solve F?

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

    Anybody? Seems like a nice problem

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

      Well during the contest I had the following idea that gave me 112/160 points. I already sent my idea to someone else so I guess I'll just copy-paste it here:

      Spoiler because long explanation
      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 5   Vote: I like it +18 Vote: I do not like it

        The final part can be done with dp[{c1, c2, ..., cn}] is the minimum cost to distribute first s = c1 + 2c2 + ... + ncn bag of candy (assume that we sorted the bags in increasing order) into a set of cycles, with ci cycles of size i. An important observation is that the number of dp state is not large (which could be found out using another dp).

        I learned this solution from I_love_tigersugar. Feel retarded for not realizing that the number of dp states is small.

        I wonder if there is a polynomial solution to this problem.

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

          As the author of the problem, I can confirm that this was indeed the intended approach.

          Also note that although the first three observations made by Noam527 are correct, the last part is not. As a counterexample, consider a permutation with cycles of sizes 3, 3, 4 and let the quantities of candies be 1, 1, 1, 1, 1, 5, 10, 10, 10, 10. In this case, the greedy algorithm fails to produce a valid distribution when "mid" is equal to 5 in the binary search. I apologize for the weak test data, I was not aware of this particular approach.

          As a final remark for the mathematically-minded, it can be shown that the complexity of the solution is roughly , although it is much less in practice. I doubt that a polynomial solution exists.

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

            Can you give me a 100-point solution or an AC code. This is a nice problem which seems had a clever trick, but I can't solve it.The state of my dp is too large.

            PS:I can't see your dp in your discussion,it showed "Unable to parse markup [type=CF_TEX]"

            Thank you very much

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

          The maximum number of states for the DP function is 4230144 in case we have 16 cycles of 1 node, 8 cycles of 2, 5 of 3, 3 of each size 4 and 5, 2 cycles of 6 and 7, and one of each size from 8 to 12.

          abeker I wonder if you put this test in the dataset :D Thank you for such a nice problem with a lot of greedy observations, but ends up with a DP approaches :D

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

            Yes, I did include this test in the dataset, along with some other tests with a large number of states. I'm glad to hear you liked the problem :D

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

Why would this code get SGKILL for C?

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

    Memory limit on C is 128MB, your dp array takes over 300MB.

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

B and C today is harder than usual, but D is easier than usual (and easier than C).

Btw, how to solve E? I can prove that answer always exist due to Dirichlet theorem, but can't come up with anything else.

UPD: Turned out C is really harder than D (D has 39 AC, but C only has 32).

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

    I got 28 points at first by submitting a solution where I wrote b instead of b - 1, which would've gotten the 140 points (I checked right after the results). I did not prove anything, it was just pretty heuristic.

    I had an array of vectors, in which cell number X contains the indicies of values in the progression with digit sum X (in base B). Once some cell in that array was a vector of size M I outputed its elements. So what I did was:

    if B < 50, go over the indicies in bruteforce (by order), and keep pushing back to the vectors. The running time of this should be worstcase if I'm not wrong (by pigeonhole principle; The maximal digit sum for a base B should be approximately ).

    otherwise, I did something very similar; I started with the index = 1, but instead of doing jumps of 1, I did jumps of B - 1 (in the submission of 28 points I accidentally did jumps of B). Resubmitting after the contest, this gave me 140 points.

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

      f(x) — sum of digits of number x.

      f(x) % (b — 1) = f(x + b — 1) % (b — 1) (in base B)

      our sequence is (c * n + d), where n = k * (base — 1), so f(c * n + d) % (b — 1) = f(d) % (b — 1).

      Complexity:

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

      I am the author of the problem.

      In essence, what you wrote in the last paragraph is the official solution. Dirichet's pigeonhole principle, when increasing the index variable by 1, gives worst-case complexity of , where the maximal number is a polynomial of the numbers in the input.

      One can notice there are far fewer "boxes" while increasing the index by B - 1, because every integer is congruent to the sum of its digits in base B modulo B-1. This brings the complexity down to , which should pass for all B because is close to 1.

      (Note that the above approach can be implemented using memory.)

      Does anyone know of an another approach that leads to a correct solution? There are many other methods, but I am not aware of another solution with a time complexity that does not depend on B heavily.

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

        I'm glad to know I was at least close to the solution :).

        Also, how do you actually propose a problem for COCI?

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

        Nice solution and nice problem.

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

          Be confident! No one solved perfectly it during contest. You had gotten almost every main ideas of this.

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

    How to get full marks on D? I was only able to come up with bitmask dp.

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

      You just needed to do 2 observations, and then you can do DP in O(n2): First off, for any point (x, y), we can change it to (abs(x), abs(y)). So from now we'll suppose all points have positive coordinates.

      Secondly, if you have a pair of points (X1, Y1) and (X2, Y2), so that X2 ≥ X1 and Y2 ≥ Y1, then you can completely ignore point (X1, Y1), because any rectangle covering the other one will cover this one too.

      So now, what I did is first maintaining a map that contains the maximal Y value for all points with the same X value. Note that the map will also have the points in increasing values of X. Then, you need to get some kind of a decreasing sequence (decreasing in the Y value) of points:

      Let's say we'll build this sequence on some vector A. So for every point K from left to right, we will pop the elements from the back of vector A as long as the element at the back has a Y value lower than or equal to the Y value of point K, and then you push point K to the back of the vector. Now our task is reduced to just making rectangles for these points in vector A. This algorithm has a running time of O(n).

      Then, notice that every rectangle you create will cover a contiguous segment of points in vector A. I will leave the O(n2) DP solution for you.

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

        We can make complexity O(nlogn) with CHT or LiChao segment tree, am I correct?

        I think it would fit better to D if limits were big enough :)

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

          If we'll denote X(A), Y(A) as the X and Y values of point A respectively, then the recurrence is:

          DPi = min1 ≤ j ≤ i(DPj - 1 + 4 * Y(Aj) * X(Ai)).

          This falls under the CHT category (though I think if this had to be the solution, it wouldn't fit for a D problem... at least an E).

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

        Thanks, got AC. Why do we need to maintain maximal Y value for all points with same X? If there are two points (x, y1) and (x, y2) with y2 > y1, can't we forget about (x, y1)?

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

          This is exactly what we're doing; we're taking the maximal Y value, which means we ignore all points with equal X value but lesser Y value.

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

My O(n2 * 26) solution to the problem C gets TLE at two last tests. What is the probably reason? (link)

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

https://hastebin.com/nilitahoju.cpp My O(n*26*26) solution on C got TLE on the last 2 tests. How can I improve my code?

I also want to ask how to solve B. Thanks.

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

    Your solution is not O(n * 26 * 26) it is O(n3), so TLE is justified