### sjNxksbzj's blog

By sjNxksbzj, history, 2 months ago, 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  Comments (44)
 » Auto comment: topic has been updated by sjNxksbzj (previous revision, new revision, compare).
 » Auto comment: topic has been updated by sjNxksbzj (previous revision, new revision, compare).
 » 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.
 » I found the second problem easier than the first one, lol
•  » » 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 →   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.
 » Question 1 can be tricky for inputs like the following:1 3 CCA ATT AAA
•  » » 2 months ago, # ^ | ← Rev. 2 →   CCAAAAATT Isn't it correct ? still WA (:
•  » » » Yes, my first attempt treated this as impossible. I was thinking hard to find a failing case.
•  » » » You lost one letter A somewhere. Need 5 letters A, but only have 4 in the answer.
•  » » » 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).
•  » » i got WA from 1 4 AB BC CD AA
•  » » » I did toposort, still WA :(
•  » » » » We cannot perform toposort because the graph might contain cycles.
•  » » » » » then the answer won't be possible if graph had cycles, bcz then there would be no possible way to arrange them continuously
•  » » » » » » What if all the input strings are "A". Then even though it cannot be sorted topologically, but the answer is still possible.
•  » » » » » » » 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 →   codeI upsolved it later. I didn't apply toposort directly, I preprocessed it a bit. This got accepted.
•  » » » » 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 →   ya i got my mistake , i wasn't checking for multiple components 6 RTTYYUUUII KLZZZXXCCV QQQWWWWEER OOPPAAASDD VBBBNNNMMM DFGGGGHHJJ -> QQQWWWWEERRTTYYUUUII + OOPPAAASDDDFGGGGHHJJ + KLZZZXXCCVVBBBNNNMMM 
 » 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
•  » » 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.
 » 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
 » 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.
 » a few seconds late( •  » » BTW, how to solve without guessing. I got this formula: Spoiler$\frac{C_{k-1}}{C_{m-1}} \binom{m-2}{2k-2} 2^{m-2k}$
•  » » » What is this sorcery?
•  » » » This is wonderfully simple; are you able to explain how you arrived at this formula? Thanks.
•  » » » » 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.
•  » » » » » Thanks! That's great deduction / pattern spotting regardless. A decidedly non-trivial formula.
•  » » » » » » 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...
•  » » » 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 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$.) 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.
 » 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)
 » Could someone explain the solution for the subtask 2 with $k > 1$ of the second problem. Thank you.
•  » » 2 months ago, # ^ | ← Rev. 2 →   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$.
•  » » » So, for K>=2, the answer is never IMPOSSIBLE?
•  » » » » Never.
•  » » » » » The answer can be impossible when $s_2+s^2 \equiv{1}\pmod{2}$
•  » » » » » » 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 →   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.
•  » » » 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.
 » For problem Letter Blocks, a relatively simple strategy works:- consider the strings s with s==s[n-1] and concatenate them with any other string t with t==s or t[n-1]==s- consider the remaining strings s and concatenate them with any other remaining string t with t[n-1]==s- concatenate all the remaining strings to obtain the answer- check if the answer is good or notThis is white2302's solution.
 » 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.
 » 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.