sjNxksbzj's blog

By sjNxksbzj, history, 2 months ago, In English

Just as I thought I almost qualified in round 1B for round 2 with 85 points, here comes round 1C

Yep, its that hard

only got 19 points and cannot even get full score for one question

Tags gcj
 
 
 
 
  • Vote: I like it
  • +38
  • Vote: I do not like it

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

Auto comment: topic has been updated by sjNxksbzj (previous revision, new revision, compare).

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

Auto comment: topic has been updated by sjNxksbzj (previous revision, new revision, compare).

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

Same bro , problem 2 is pure math somehow solved the first subtask by googling the equation formula, submitted task1 of problem 1 with 2 penalties.

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

I found the second problem easier than the first one, lol

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

    Same. Although, I didn't participated, but I was solving the problems and they felt harder than 1A and 1B.

    First one felt constructive to me and more, while in second one, you just have to observe that you can do it in at most $$$2$$$ operations, only if either condition is true: $$$sum \neq 0$$$ or $$$sum\text{_}sq = sq\text{_}sum$$$.

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

      The second problem seemed to me like a bit of mathforces (play around with the cases k = 1 and k = 2), while the first one was a greedy/constructive which had a few key details that I initially missed. This somewhat bogged me down and because of this I have a slightly large penalty time.

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

Question 1 can be tricky for inputs like the following:

1 3 CCA ATT AAA

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

    CCAAAAATT Isn't it correct ? still WA (:

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

      Yes, my first attempt treated this as impossible. I was thinking hard to find a failing case.

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

      You lost one letter A somewhere. Need 5 letters A, but only have 4 in the answer.

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

      I found your profile on GCJ. Then downloaded and stress tested your latest contest submission. It fails the following testcase: 1 6 DD CAA BBB D DB C (reports IMPOSSIBLE, while DDDDBBBBCCAA is a valid answer).

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

    i got WA from

    1 4 AB BC CD AA

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

      I did toposort, still WA :(

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

        We cannot perform toposort because the graph might contain cycles.

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

          then the answer won't be possible if graph had cycles, bcz then there would be no possible way to arrange them continuously

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

            What if all the input strings are "A". Then even though it cannot be sorted topologically, but the answer is still possible.

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

              Yeah, that's why I didn't try toposort either. Although I do think some high rated user may have done it in that manner. If anyone has a submission using toposort approach please do share.

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

                code

                I upsolved it later. I didn't apply toposort directly, I preprocessed it a bit. This got accepted.

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

        Careful on inputs like AB DE BC to keep the Bs together (even though AB DE BC is also topologically sorted).

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

          ya i got my mistake , i wasn't checking for multiple components

          6
          RTTYYUUUII KLZZZXXCCV QQQWWWWEER OOPPAAASDD VBBBNNNMMM DFGGGGHHJJ
          -> QQQWWWWEERRTTYYUUUII + OOPPAAASDDDFGGGGHHJJ + KLZZZXXCCVVBBBNNNMMM
          
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

yes, hard round. To move to the next round, you need:
- 56 points in round 1A
- 85 points in round 1B
- 34 points in round 1C

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

    While R1C might indeed be harder than the previous two rounds, you can't just compare the scores like that. There are 3000 strong competitors that had already qualified to R2, so they didn't participate in R1C. Had they participated, the qualifying score could very likely be higher than 34.
    I think that if you want to compare the difficulties of the rounds, you should compare the solve times of the people in the first couple hundred places.

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

I'm not skilled enough to solve these questions. Got 19 score only. How can someone come up with a solution for problem B :cry

:cryalot

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

I barely made it and jumped in the last bandwagon. Finished at the ranking position 1464 with 34 points and 1:46:50 penalty time. A person at the ranking position 1501 had 1:50:08 penalty time and it's only 3 minutes difference! In the previous rounds 1A and 1B I also had exactly the cut-off amount of points and failed to advance because of high penatly time.

What's your GCJ handle? I can't find anyone with nickname sjNxksbzj there.

»
2 months ago, # |
  Vote: I like it +29 Vote: I do not like it

a few seconds late(

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

    BTW, how to solve without guessing. I got this formula:

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

      What is this sorcery?

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

      This is wonderfully simple; are you able to explain how you arrived at this formula? Thanks.

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

        Unfortunately, I got this formula using slow dp(which gets subtask 1 but I didn't submit) and my pattern guessing skills.

        I am not so good at spotting patterns so sometimes I use oeis to help me.

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

          Thanks! That's great deduction / pattern spotting regardless. A decidedly non-trivial formula.

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

            I remember there was a stream were scott_wu guessed pattern for some arc E in a blink of an eye. It was very impressive. Before watching that I didn't consider pattern spotting to be a practical way to AC problems, I rarely resort to it but it actually works...

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

      You can derive this formula purely combinatorially, but not in the 2.5h of contest time...

      As a warm up, for the given edge weights in the task, run the following procedure:

      • On the graph, we maintain a union find data structure.
      • In addition, we maintain an auxiliary rooted full binary forest (full binary = every node has 0 or 2 children) to build a rooted full binary tree in the end. At any point, every tree in this forest corresponds to a component in the union-find. Initially, the forest has one node for each vertex in the graph, and these will always be the (only) leaves in the forest.
      • For every edge in order of the permutation, if the edge connects two different components:
        • Pick a random orientation of the edge. Suppose the edge goes from $$$a$$$ to $$$b$$$.
        • In the union-find, unite $$$a$$$ and $$$b$$$.
        • In the auxiliary tree, add a new vertex whose left / right child is the tree containing $$$a$$$ / $$$b$$$.
      • In the end, we're left with a full binary tree with $$$n$$$ leaves, $$$n-1$$$ internal nodes, with 2 children each, and $$$2n-2$$$ edges. Moreover, the $$$k$$$ in the task is the number of internal nodes whose children are both leaves.
      • Note for later: If we remove the leaves for the auxiliary forest, we're left with a binary tree with $$$n-1$$$ nodes and $$$k$$$ leaves. http://oeis.org/A091894 will come in handy...

      Unfortunately, the above procedure is more likely to produce some auxiliary tree shapes than others.

      The key observation is that, in the above procedure, we don't really care about edges between two components of size $$$\geq 2$$$, as they don't affect $$$k$$$ in any way, so we may alter the probability of picking those edges -- as long as the relative probabilities of picking an edge between a components of size $$$1$$$ and a component of size $$$s \geq 1$$$ remains the same, the probability of us ending up with a specific value of $$$k$$$ will not change. Using this, here's an improved version of the above procedure.

      • We again maintain a union-find and an auxiliary tree.
      • As long as there are two or more components.
        • Pick an ordered pair of components where the probability of picking $$$(A, B)$$$ is $$$\frac{size(A)+size(B)-1}{Z_{\mathit{number\_of\_components}}}$$$ where $$$Z_c = n \cdot 2 \cdot (c-1) - 2 \binom{c}{2}$$$. (The main idea for later is that if one of $$$size(A), size(B)$$$ is one, then $$$size(A)+size(B)-1 = size(A)\cdot size(B)$$$, so the relative probabilities are unchanged in this case. Also note that $$$\prod_{c=2}^{n} Z_c = (2n-2)!$$$.)
        • Let $$$a \in A, b \in B$$$ be any vertices. In the union-find, unite $$$a$$$ and $$$b$$$.
        • In the auxiliary tree, add a new vertex whose left / right child is the tree containing $$$a$$$ / $$$b$$$.
      • In the end, we're left with a full binary tree, as above.

      We claim that

      1. This procedure has the same probability of ending up with a certain $$$k$$$ as the original procedure.
        • Proof: We say that an edge $$$(a, b)$$$ being processed is relevant if at least one of $$$a$$$ and $$$b$$$ was a component of size $$$1$$$. In both procedures, for the same history of relevant edges, the probability that the next relevant edge is between a particular component of size $$$1$$$ and a particular component of size $$$s$$$ is proportionate to $$$s$$$. By summing over components, we see that the probability that the next relevant edge is between two components of size $$$1$$$ is $$$\frac{\binom{O}{2}}{(n-O) \cdot O + \binom{O}{2}}$$$ where $$$O$$$ is the number of components of size $$$1$$$.. (In particular, non-relevant edges have no effect on this, as they do not change $$$O$$$, nor $$$k$$$.)
      2. This procedure produces all full binary trees with equal probability.
        • Proof: Fix an arbitrary full binary tree, fix a labeling of the leaves ($$$n!$$$ options) and fix an order $$$u_1, \dots, u_{n-1}$$$ in which the interior vertices are to be created. (The valid orderings are the max-heap orderings, their number is $$$\frac{(n-1)!}{\prod_{u \text{ interior}} (leaves[u]-1)}$$$).
        • For each interior vertex $$$u = u_i$$$, the probability of it being created at that specific time, with the specific children is $$$\frac{left\_leaves[u] + right\_leaves[u] - 1}{Z} = \frac{leaves[u]-1}{Z_{N-i+1}}$$$, where $$$Z_c$$$ was defined above. Hence, the probability of the tree being created in that order, with those specific leaf labels, is $$$\frac{\prod_u (leaves[u]-1)}{\prod_c Z_c}$$$,
        • Multiplying with the number of leaf labellings and number of heap orderings, we see that the probability of a given tree being created in any way is $$$\frac{(n-1)! n!}{\prod_{c=2}^{N} Z_c} = \frac{1}{\mathrm{Catalan}[n-1]}$$$.

      Hence, the answer is: (number of binary tree with $$$n-1$$$ nodes and $$$k-1$$$ leaves) / (number of binary trees with $$$n-1$$$ nodes). The numerator is http://oeis.org/A091894, with formula $$$2^{n-2k} \binom{n-2}{2k-2} \mathrm{Catalan}[k-1]$$$, the denominator is just the Catalan number $$$\mathrm{Catalan}[n-1]$$$. In total, we get the formula you guessed.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Weirdly enough I found this round easier than 1B and had a much better performance(was able to solve 2 problems), don't know why lol (probably just some lucky observations)

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Could someone explain the solution for the subtask 2 with $$$k > 1$$$ of the second problem. Thank you.

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

    Let's look at the case $$$k = 2$$$. Let $$$s$$$ be the sum of the numbers from the input and $$$s_2$$$ the sum of the squares of the numbers from the input. We are interested in finding out $$$x$$$ and $$$y$$$ such that

    $$$(s+x+y)^2 = s_2 + x^2 + y^2.$$$

    After expanding the left term and doing some clean-up, we get:

    $$$s^2 + 2sx + 2sy + 2xy = s_2.$$$

    Let's consider $x$ as a parameter; then, we can rewrite $$$y$$$ in terms of $$$x$$$ as follows:

    $$$y = \frac {s_2 - s^2 - 2sx}{2s+2x}.$$$

    We are interested in finding an $x$ such that there is an integer $$$y$$$ which satisfies the relation above. Since $$$y$$$ needs to be an integer, $$$2s + 2x$$$ must be a divisor of $$$s_2 - s^2 - 2sx$$$ (and $$$2s + 2x$$$ must obviously be non-zero). We can rewrite $$$y$$$ as follows:

    $$$y = \frac {s_2 - s^2 - 2sx}{2s+2x} = \frac {s_2 + s^2 - 2s^2 - 2sx}{2s+2x} = \frac {s_2 + s^2}{2s+2x} - \frac {s(2s+2x)}{2s+2x} = \frac {s_2 + s^2}{2s+2x} - s.$$$

    Now we are only interested in $2s+2x$ being a divisor of $$$s_2 + s^2$$$. Note, however, that $$$s_2$$$ and $$$s^2$$$ have the same parity. Then $$$s_2 + s^2$$$ is even, so 2 is one of its divisors! We can thus find $$$x$$$ such that $$$2s+2x = 2$$$ and we get $$$x = 1-s$$$. By replacing $$$x$$$ with $$$1-s$$$ in the relation above, we get $$$y = \frac {s_2 + s^2}{2} - s$$$.

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

      So, for K>=2, the answer is never IMPOSSIBLE?

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

        Never.

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

          The answer can be impossible when $$$s_2+s^2 \equiv{1}\pmod{2}$$$

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

            I guess that case cannot be encountered since $$$s_2$$$ and $$$s^2$$$, both have the same parity as is mentioned by Alex.

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

              Oh, didn’t read that part. Thanks for pointing it out!

              Edit: Actually, the user is asking if the answer is never IMPOSSIBLE for K >= 2, but that is not true.

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

      I had a similar solution that ended up using 1 as a divisor instead of 2.

      Define $$$corr(A) = \sum_{i < j} a_i a_j$$$. Then $$$A$$$ is squarry iff $$$corr(A) = 0$$$. For a general $$$A$$$, consider $$$A' = A + [p, q]$$$, we investigate the constraints on $$$p, q$$$ if we set $$$corr(A') = 0$$$.

      The constraint is: $$$corr(A) + (p + q) \sum_i a_i + pq = 0$$$.

      Letting $$$G = -corr(A), S = \sum_i a_i$$$, we rewrite $$$p$$$ in terms of $$$q$$$ as $$$p = \frac{G - qS}{S + q}$$$, and we are looking for any integer $$$p, q$$$ satisfying this. But then we can simply set $$$S + q = 1$$$ and we are done.

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

For problem Letter Blocks, a relatively simple strategy works:
- consider the strings s with s[0]==s[n-1] and concatenate them with any other string t with t[0]==s[0] or t[n-1]==s[0]
- consider the remaining strings s and concatenate them with any other remaining string t with t[n-1]==s[0]
- concatenate all the remaining strings to obtain the answer
- check if the answer is good or not
This is white2302's solution.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Didn't felt so about problem A. It wasn't straightforward. But I managed to solve both subtasks. I agree that Problem A was definitely harder for a usual problem A, even compared to 1A and 1B.

There were so many experts and Candidate Masters in my standings that I know are very good. They just gave up I think and didn't qualify. This round tested the patience more than the skill in my opinion.

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

In the analysis section of problem 1C, I note a rather complex solution involving a convolution and FFT. However, among the (only) 9 participants who correctly solved this question, I see a number of much simpler solutions based around combinatorics insight and Catalan numbers. If anyone is able to shed light on the underlying maths / counting arguments here I would be very grateful.