ParadiseSoul's blog

By ParadiseSoul, history, 4 weeks ago, In English,

SEERC 2018 is finished now, and I’d like to know impressions of other contestants. Especially, what happend to the team with +40 on problem E? And how it was organized in Ukraine?

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

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

That was not a really productive contest for our team, but it was rather fun(we spent most of the time on the unsolved task K:).

By the way, does anybody have a better solution than O(Qlog2(N)) time and O(Q2) memory?(or O(Qlog3(N)) time and O(QlogQ) memory).

What about problem A? On the analysis after the contest nobody explained how it should be solved.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is fun, in Romania, we don’t even have analysis after the contest.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    time and memory. You can count points inside rectangle with 2d Segment Tree. And to count rectangles that contain the point, count rectangles that don't contain the point. Like an inclusion-exclusion, with 4 simple ST and 4 2D ST

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

      Will the 2d segment tree use O(QlogQ) memory? We used 2D Fenwick Tree based on maps to make it have O(QlogQ) memory.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Coordinates compression and Fenwick trees in the nodes of Segment Tree as a standard approach.

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

      Second part could be done using the same method.

      Add rectangle = add 1 to points (x1,y1), (x2,y2) and -1 to (x1,y2), (x2,y1). All coordinates are  ± 1 of correct ones :)

      Query point = find sum in rectangle (0,0,x,y).

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried doing this in the gym and apparently it's not nearly fast enough

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I tried what RomaWhite wrote, and my solution got AC in 1 sec.

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

          Well, I can't compete with you when it comes to writing constant-optimized code :)

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Well, it's not hard =) Other AC submissions use some D&C approach, and it works much faster.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My friend biza suggested an interesting idea for problem A: Try all bitmasks representing positions where a carry will happen during addition of two numbers. For example, if we have A + B = 4332 and the carry mask is 0110, the actual digit-wise sum of A and B is 3, 12, 13, 2 (big endian). I have no idea how to complete the solution though.

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

      Iterate over the lengths of palindromes.

      If it's equal, digits are independent and we can find a number of ways to create each digit and the answer is a product of those numbers. In such case, we can iterate over carry mask of lower 9 digits (but still 2^18 should be ok).

      If palindromes have different lengths, we know the largest digit of a longer palindrome -> we know its smallest digit -> we know the smallest digit of shorter palindrome -> mirror this digit in smaller palindrome and find next digit in larger one. We could restore all digits of both palindromes using such process. Also, we can iterate over carry mask of only higher 9 digits.

»
4 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

I created an interactive standings with unfrozen results. You can find it here: http://acmallukrainian.ho.ua/2018/3/standings.html

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Is there any place for virtual participation? Seems a challenging set of problems.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Team which got 40 penalty attempts solved it with some kind of segment tree and it wasn't fast enough, so they optimized it. Computers switched off two times during the contest so our team lost ten minutes of computer time. In my opinion all problems were nice, except of problem J. It is too straightforward and required only careful coding

»
4 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

For those who understand Ukrainian, there are our comments on problems and their solutions here.

»
2 weeks ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it
Time Limit: 0.3 seconds (C/C++)
Time Limit: 0.2 seconds (C/C++)
Time Limit: 0.1 seconds (C/C++)
Time Limit: 0.4 seconds (C/C++)
Time Limit: 0.5 seconds (C/C++)
Time Limit: 0.4 seconds (C/C++)
Time Limit: 1.5 seconds (C/C++)
Time Limit: 0.4 seconds (C/C++)
Time Limit: 0.1 seconds (C/C++)
Time Limit: 0.4 seconds (C/C++)
Time Limit: 2 seconds (C/C++)

neal will be surprised.

»
2 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Problem J

This line in the problem — "The rabbit is considered to cheat ONLY if he changes the direction of the path and the new path that he will take is strictly faster than the original one (otherwise, there is no point to cheat)" is wrong.

The phrase 'original one' is quite ambiguous. It doesn't mean the original path, but means the next vertex in the original path (then the rabbit can cheat, i.e, take the shortest path to 'n').

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I got AC on J after reading this. It will be better to modify the description of J.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Shit, maybe our team didn't advance to WF because of that

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

    I disagree here. Put yourself in place of that rabbit and turtle. If you are standing in vertex X and your next vertex is Y and if you want to cheat in vertex X but the fastest way from X is to go to Y, then it's not really cheating (not for turtle), because turtle can't understand by your move if you're starting to cheat or not.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Take this scenario -
      There is a vertex Z (!= Y), such that the shortest distance from X to 'n' is through Z and is equal to D. Also, the distance of X-Y + shortest distance from Y to 'n' = D. The distance from X to 'n' in the original path is greater than D.

      This distance is strictly less than the distance of the 'original one' (original path). But we aren't considering this path (from Z) because we can cheat on Y. This is not mentioned in the statement.

      For you, 'original one' is implying direction, but for most of the others, it is implying the original path. That is why I am saying that statement is ambiguous.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't get your example. If we are in X and we have Y ≠ W (where W is the next vertex from X in our original path and dist(X, Y) + dist(Y, N) < dist(X, W) + dist(W, N)), then we should output X, and it doesn't matter if we have Z or not. In other words, you don't cheat when you are in vertex Y, you cheat when you start to go to vertex Y (which means you are in vertex X and only X should be printed).

        Y or Z can't be printed in answer (no matter what), because they are not part of the original path.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Let dist(A, B) denote shortest distance from A to B.
          Let dist1(A, B) denote the distance in the given path from A to B.
          Let W(A, B) denote the weight of the edge from A to B for rabbit.

          Currently we are at X. Next vertex in the path is Y. Let Z (!= Y) be some other vertex adjacent to X.

          According to the statement in the problem, the below equation should be true for us to cheat on X (ignoring the condition for turtle for now)
          W(X, Z) + dist(Z, N) < W(X, Y) + dist1(Y, N)

          But the equation they wanted is
          W(X, Z) + dist(Z, N) < W(X, Y) + dist(Y, N)

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

            Well, okay, now I get your example. Maybe you're right, but I remember in the contest I used the "final moment when the rabbit will finish if he doesn't cheat" to check if I can cheat from current vertex.

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

Any hints for G and H?

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it

    If I am not mistaken, for H, you could randomly partition the persons in two parts (L and R) and satisfy every wish (x, y) with and . The expected value for that is M / 4. If you get AC with that, notify me.

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

      I solved it like that during the contest, got AC on the first try

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

    UPD: just realized this is very much wrong, skip it.

    I have this idea for G, I haven't tested it though and I'm not sure it'll pass (the complexity is quite large), it's based on meet in the middle.

    So, you can preprocess the value for each matrix of size at most 210 × 210, there are at most 220 different matrix, which should be ok. If you see a matrix as a binary number, you can say to_number(M) = row0(M) + row1(M) + ... + rown(M), where + is the concatenetion as if they were lists. And, in a similar way, you can take the four submatrices out of a number (I think this is more tricky, but should be doable in around 20 steps).

    Now, to precalculate val(to_number(M)), you'll go through every number x in [0 .. 220) in order, and you split the matrix represented by x in the four submatrices, we can check that the given numbers of the submatrices must be smaller than x, then, their value is already stored.

    Now that we have this, we build a 4-ary tree, where each node is a matrix, and it's four children are the submatrices. Then, if you need to represent the matrix of size 220 × 220, you'll have a complete 4-ary tree with depth equal to 10, and each leaf will have a number which represents the matrix of size 210 that's there (for which you already have the value calculated).

    Now, for each query, you traverse the tree, and in each step you only go through 2 of the 4 children, because of how the queries are, so you'll end up in 210 leafs and need to change their value, when you go up, you update each node's value. In here you'd need to check if some submatrix becomes all white or all black.

    Now, since we have 106 queries, and each query costs 210 ~ 103, this is really slow (and huge on memory consumption), so maybe there's a better solution out there. Or a better setting of the values.

    As an observation, when you represent each matrix, you actaully have that rotate or negate a matrix doesn't change it's value, so, you could save some memory on the first step and have a larger amount of preprocessed matrices.

    As a second observation, I don't think you can build every matrix of size 210 × 210 with these queries, so maybe you could do something more lazy with memoization.

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

    A constructive algorithm for H: let's first solve a problem where you're given an undirected (multi)graph with m edges, and you're to color the vertices of the graph in two colors (say, red and green) so that the number of edges joining the vertices of different colors is strictly larger than m/2.

    How to do it? First take any two connected vertices, and color them complementarily. Then color the vertices one by one; when deciding on a color of a single vertex, we count the number of its red- and green-colored neighbors (possibly counting some multiple times in case of multiedges) and use the color that occurred fewer times. We can easily prove that this process gives us strictly more than m/2 "good" edges.

    Back to our problem: temporarily make the graph undirected (by simply purging the directions from the edges), take the coloring from the subproblem above, and restore the original directions to the edges. Notice now that either more than m/4 edges go from red to green vertices, or more than m/4 edges go the other way around.

»
7 days ago, # |
  Vote: I like it +24 Vote: I do not like it

Problem G: Matrix Queries is exactly same as JOI SP 2013: Collecting Images is Fun. I believe this is not a coincidence. That's sad.. and funny too.
I uploaded a translated version here, some months ago. You can find the editorial in JOI Site (In Japanese).