the_art_of_war's blog

By the_art_of_war, history, 12 months ago, In English,

Pre-Elimination round of SnackDown will take place today.

But I can't understand the rules with Judging Criteria, how they will sort the teams with equal number of tasks (or points).

On the page of round it is written (Link):

Users are ranked according to the most problems solved. Ties will be broken by the total time for each user in ascending order of time.

However, on the page of the SnackDown2019 it is written (Link):

The qualification & pre-elimination rounds will use score based ranking system.

And if we go by the link, what it is score based ranking system, we get ( Link )

The ties are unresolved. The time elapsed is not considered.

So we have contradiction in the rules, what the rules will be used in the contest? It is good to know it before that start of the contest.

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

»
12 months ago, # |
  Vote: I like it +24 Vote: I do not like it

I think it is with high probability they will use ACM ICPC rules. I dont know if the penalty will be 20 mins or it will be changed.

Adding PraveenDhinwa. he should be capable of answering.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it allowed to use 2 computers during the round?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    As there is basically no way to supervise it, I'd guess it is.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think he meant parallel login to the same account using both PCs. It was allowed in all previous rounds so maybe it will be allowed in this also.

      • »
        »
        »
        »
        12 months ago, # ^ |
        Rev. 2   Vote: I like it +13 Vote: I do not like it

        Isn't it enough to login with your personal profile and submit from there? I think it counts as a team submission then.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yes, it's allowed.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

From the announcements section of the contest: "16:30 IST, 3 Nov: Teams will be ranked according to number of problems solved. Ties will be broken according to ACM Rules, but with a penalty of 10 minutes for each unsuccessful submission."

»
12 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Did anyone actually enjoy the problemset?

»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve Strange Transform?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it -33 Vote: I do not like it

    Spent too much time on it thinking it must be easy :(

  • »
    »
    12 months ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    Could you understand the pattern at all? I just tried to find some pattern per k%4 but just couldnt. After that it was per query 32 * logn for querying one out of 4 segment trees, I thought.

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it

    Solution of my teammate: use sqrt decomposition.

    For K <= 2^9 calculate answer

    For K <= 2^18: run recursion.

    Total time ( n + q) * 2 ^ 9

    Code

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

    My solution is . If k is small, use (precompute all such values with this formula). Otherwise use , where pw is the largest power of 2 which is not greater than k. Couldn't fix all bugs before the end of contest...

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Interesting idea! I did notice powers of two, but couldn't find this recurrence.

  • »
    »
    12 months ago, # ^ |
    Rev. 5   Vote: I like it +19 Vote: I do not like it

    Note, that fk(a)x = xor over{j which is submask of k} a_{x+j}.

    Note, that you can get k modulo 218 (implied by first statement)

    Precalculate all fk(a) for k ≤ 29.

    Now you are given k = l + m, where l is divisible by 29 (and therefore contains at most 9 bits) and m ≤ 29. Find fl(fm(a))x. fm(a) is precalculated and finding the rest can be done by enumerating submasks in 29.

    Overall complexity

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

      How to prove the first observation?

      I only know that it is related to the parities in Pascal triangle.

      edit: It is easy to be proved by M.I. but is there some more intuitive way to reach this conclusion, other than pattern observation?

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        First you should notice is each one has binomial coefficients. And later we need coefficients mod2 so whem we apply Lucas thoerem, we get that observation that r must be submask of n for nCr to be odd.

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        First proof how f2 works, then how f2k works (by induction). Then it's easier to see

»
12 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

When upsolving usually becomes available?

UPD: now it works

»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve Painting Tree ?

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

    At first let's calculate fk — number of ways to choose k non-intersecting paths.

    With this + some simple combinatorics you can get the answer.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't trivial dp to compute fk is O(n^3)? Although it's not that trivial!

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know whether we about the same dp, but there's is pretty straightfowrard one and it's O(n^2) because in each vertex it's not O(n^2) but O(left_size * right_size) which is O(n^2) in total.

      • »
        »
        »
        »
        12 months ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it

        Same trick used in the Polish problem Barricades (see Looking For A Challenge) reduces it to O(n2).

»
12 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Didn't know CC problems are not ranked to difficulty initially :((

»
12 months ago, # |
  Vote: I like it -18 Vote: I do not like it

I think that a part of the statement of QUEENS was misleading:

Let's denote a unit square in row r and column c by (r,c). Chef lives at square (X,Y) of this chessboard.

Here y-coordinate is denoted by X and x-coordinate by Y. Yes, the statement is technically correct, but the choice of variables is against the common conventions. Was this an oversight or an intentional attempt to mislead contestants?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    the only reasonable choice of order, imho.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Matrix conventions are different from the 2D cartesian plane conventions. According to convention in a matrix, rows are numbered from 1 to n from top to bottom and columns from 1 to m from left to right.

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

      Yes, the notation (row, column) was indeed correct. What I meant is that in the statement a variable called X was used to represent row (the "y-coordinate" in matrix) and Y to represent column ("x-coordinate"). In my opinion, the names of the variables X and Y should have been swapped.

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

        That's my point. There isn't any concept of x-coordinate and y-coordinate in a matrix. As a row number is written first and when (X,Y) is being used to describe a pair, X is used to describe the first number, so it makes sense to denote row number by X and column number by Y. I am not saying you are wrong, just want you to see the other perspective.

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

    As it usually goes, the first coordinate in an array is x, the second coordinate is y, the third is z and so on (or i, j, k and so on). Makes perfect sense unless you're programming in Befunge or Logo.

    I remember a contest (Polish maybe?) where rows were y and columns were x. Boy, was that confusing.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it -44 Vote: I do not like it

      Of course man, if you are referring to matrices coordinates by z and y you should do (y,x), not that freaking most confusing in world (x,y) for row and column. I don't care about whether x comes before y or not, I care about their meaning. x is left right and y is up down. If not necessary you should omit denoting matrices coordinates by x and y, but sometimes we think of our matrix as a map where some units are moving or whatever.

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

        not that freaking most confusing in world (x,y) for row and column

        But it isn't (x, y) for row and column. It's (r, c) for row and column, right there in the statement. It's just that specific coordinates aren't also named r and c, they're named X and Y. If they were named A and B or Bacon and Popper, that wouldn't change the fact that which coordinate is the row and which is the column is explicitly spelled out precisely to make sure the statement explains such misunderstandings.

        Perhaps not the best choice, sure, but I don't know what's the best choice and am not going to bother when I'm sick.

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it -20 Vote: I do not like it

        I agree that x and y shouldn't be used in grids, especially with x denoting row.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Heap Pirates?

I only know how to solve it when we have a bamboo (it's just a line of length n that looks like 010101).
And the other case i know is the sun (graphs with edges like (1-2) (1-3) (1-4) ... (1-n)). For n=4 it looks like this:
10101
00000
Are there any other figures?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    What does 8-connected mean?

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

      It means that cells (A,B) and (X,Y) are connected if and only if abs(A-X) <= 1 AND abs(B-Y) <= 1. In this problem these cells should have the same value written in it.

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it -21 Vote: I do not like it

        Seriously? This is 8-connected and they didn't feel the need to explain this definition?

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          From the statement

          A cell in 8-connected terminology is neighboring to another cell if they have a common side or a common corner.

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
              Vote: I like it -25 Vote: I do not like it

            I thought this was AFTER 8-connected nodes were formed.

            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              That's what it meant?!?!?!?!? I thought it meant the same as like k-connected in a graph definition, and that each "big node" was connected by that definition above. No wonder I couldn't solve it. Luckily my teammate did.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 months ago, # ^ |
                  Vote: I like it -9 Vote: I do not like it

                I thought that 8 cells are connected together in a component. And nice sample test cases too.

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
            Rev. 2   Vote: I like it -8 Vote: I do not like it

            But what is an 8-connected component that is supposed to be considered as one node of the graph?

            Edit: I just got it. It just means a connected component where connection is defined as sharing a side or a corner. The term '8-connected' confused me into thinking that 8 is relevant here, that is either we are talking about a connected component of 8 cells or something related to the 8 cells that surround any cell in a matrix. I still feel it should have been explained better because I googled '8-connected component' during the contest and it's not a commonly used term.

            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it
              0 0 0 1 1
              1 1 1 0 0
              

              For example, there are two 8-connected components here. One is all zeroes and the other is all ones. So to convert this to graph form, it would be two nodes with one edge between them (because the two components are adjacent to each other).

              I didn't solve this tho so don't expect much more help lol.

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          To be honest, I did think about it, but it was late at night and I'm sick, so I decided that hey, everyone who doesn't exactly know what 8-connected means will just use LMGTFY, better than writing out boring definitions (define adjacency of cells, define 8-connectivity in components, define adjacency of components).

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
            Rev. 2   Vote: I like it -14 Vote: I do not like it

            You could've dropped a link to the definition, unless it's a made-up term, in which case you definitely should have written the explanation, or given a better example with explanation. You do realize it's a 3hr contest, and this is not the only problem in the contest?

            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
              Rev. 2   Vote: I like it +18 Vote: I do not like it

              It's not a made-up term, as you'd know if you actually tried this at some time — either during the contest, after the contest or even just before posting this comment.

              There even was a sort-of definition in the problem statement, as has been pointed out to you, and yet you act like there was nothing.

              You do realise I'm sick, so I'm not going to do the things you suggest because breathing is tough?

              And it's not my job to make samples.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Exactly definitions should have been given.

  • »
    »
    12 months ago, # ^ |
    Rev. 4   Vote: I like it +13 Vote: I do not like it
    Spoiler, Read a comment below for a hint first
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    There is an answer for any tree. Root the tree and generalize your idea :)

»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

what is the complexity for activity selection O(n^6) with small constant. or can it be done in better complexity ?

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did O(n^5), however it is pretty clumsy to describe :f. I would be disappointed if it turns out that O(n^6) was sufficient to solve this problem. Can somebody that tried to squeeze O(n^6) write here what was the outcome? My code is here: https://ideone.com/Qwtbse, but I am not sure whether it is of any help without some description :P

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I just wrote straightforward n^6 solution and it passed right away

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

        R u sure yours is n^6 because contraint on m was m <=50.

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes. My solution is n^2km^3

      • »
        »
        »
        »
        12 months ago, # ^ |
        Rev. 2   Vote: I like it +12 Vote: I do not like it

        Yes, unfortunately, some O(N6) solutions did pass, I apologize for this.

        My solution was O(N4M) and it ran quite slow without any constant optimization, so I thought O(N6) solutions are not feasible. Lesson to learn from this is that a constant factor is actually quite achievable given the large variety of O(N6) solutions with small constant factors out there.

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

    O(n^5) is quite straightforward.

    Let's use dynamic programming. We'll add intervals in an increasing order of their right border.

    The state is (last_right_border, current_k, current_k_pos, current_intervals_count). The value of the state is the number of ways to pick exactly current_intervals_count intervals so that the current longest sequence of non-overlapping intervals has length current_k, the leftmost of such sequences ends in the current_k_pos position and we've considered all possible intervals that end in last_right_border or to the left from it.

    To make a transition, we iterate over the number of the intervals that end in the last_right_border + 1 position. Once this value is fixed, we've got two options: 1. The new intervals will not change the current value of K (which means they start before the current_k_pos). 2. They will increase K by one. It means that at least one of them starts after the current_k_pos. Either way, the number of ways to choose the new intervals is some binomial coefficient.

    By the way, this solution takes around half a second to complete in the worst case (I didn't do any constant optimization, though), so I don't think that an O(n^6) solution can pass.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have troubles understanding how that is n^5. I think currentintervalscount is up to n^2, so you have dp table of n^5 size and as I think of it you need to have linear number of transitions from every state where you add those binomial coefficients. What am I missing here? Are you doing last step in more clever way?

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

        The total number of intervals is up to 50 (according to the problem statement), so I counted it as n.

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

          Oh no, FML... My solution runs in n^5 for M<=(n choose 2) though (I don't have M in complexity at all)

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

            Lol, after this discussion I saw the question and realise its min(50,...). sad life :(

            Anyways if possible give a brief description of your idea. no need of complete details

            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              In kraskevich's solution he keeps track of how many intervals he chose and what is our current result on prefix. I call intervals contributing to result as important (k of them) and others unimportant (m-k of them). I do not decide when do I take unimportant intervals when doing transitions, I just count in how many places I could have put them and keep track of that (corresponding to variable 'luzne' in my code) and in the end I chose m-k out of luzne. Advantage of that is that I can optimize this by suffix sums because instead of adding some weird binomial coefficients I just add some fixed constant on some interval.

              If my last important interval on some prefix ended at index e and I am considering adding intervals ending at i then I either:
              1) chose not to increase result by not adding any interval [b, i] for b>e and then I have e places for unimportant intervals looking like [b, i] for b<=e
              2) chose to increase result by adding some interval [b, i] for b>e (I look at one with biggest b) and then I have b-1 places for unimportant intervals

              Trick is that I do not have to iterate over b in second case since this can be seen as adding constant on interval (b iterates from e+1 to i).

»
12 months ago, # |
  Vote: I like it +144 Vote: I do not like it

When you waste an hour not noticing that heaps can have 0 counters in buddynim :(

»
9 months ago, # |
  Vote: I like it +20 Vote: I do not like it

What about T-shirts?