Meta Hacker Cup Round 2

hopefully server works perfectly!

In Round 1 for Problem B1 there the T was ~ 960 . In my output.txt file it printed only upto 330 lines. I had already ran the command to make the stack size unlimited in Mac terminal before compiling the code and executing the .exe file. What should I do to make sure that this does not happen tomorrow, like the stack size issue is what worries me the most.

I really hope to qualify to the third round

I really hope that the input/output example will be visible tomorrow. Unlike the past round, I don't want to blindly guess how to output the solution.

btw is it rated?

Again a request to link the starting time to the Event Time Announcer tool instead of the countdown. It's extremely inconvenient to figure out the starting time using the countdown.

Any chance we could get the scoring distribution, or at least the number of problems, before the contest starts? As a personal preference I always like having problem scores in advance in order to make a plan for the contest, but more importantly knowing the number of problems is helpful to me in setting up my file system ahead of the competition.

damnnnnn, i fu*ked up on problem a2, didn't notice constraint of it and thought it was similar to a1 and when my timer was running out and i didn't get output, i was like: come back again next year. Till then bye bye.

On a Quest to become more Pro, Why don't you print something interesting on the t-shirt.

what should i do, if my website freezed and was unable to submit due to that?, i have submitted a clarification, lets see

Did anyone else get missing test cases for input file for A2? I got just around 50% of the test cases.

What happened to tourist?

Why didn't you make a system with tests and checkers?

Good round, huge improvement over the last one.

I got WA on everything except D and qualed bruh

Feedback on the round:

A: Fine as the easy problem.

B: Not my favorite problem. The observation that any answer that exists must be less than 2N is nice enough, but from there the problem feels like a couple of disjointed exercises tacked on together in a contrived way. Neither the step of checking whether the inequality constraints are respected using a sliding window-style approach nor the standard string exercise to check if A is the reverse of B felt especially interesting, and in the end I was left wondering what the point of doing all that was.

C: Nice problem; thinking through a way to handle the DP that was provably O(n log^2 n) was pretty interesting, and after all that the implementation isn't bad at all (though apparently, my solution is different from what was intended). It wasn't obvious to me that we had to have some friend starting at each leaf (and no friends starting elsewhere) until I read the formal version of the statement, which clarified that we are partitioning a tree into edge-disjoint paths; I think the flavor text could have been made clearer/more consistent with the formal statement of the problem.

I made an error in my implementation that degraded the complexity to O(n^2), and thus ended up spending much of my submission window frantically trying to find the bug (and eventually succeeding). I found this process very satisfying, and situations like this are one of the reasons why I hope Hacker Cup doesn't change its format.

(Sidenote: I do think MHC could do a better job communicating the intricacies of the format to new contestants. One example might be providing instructions on the contest website to increase the stack size limit for some commonly used operating systems and offering a year-round practice contest involving a single easy problem, perhaps even with code provided by the organizers, that requires contestants to set a large enough stack size to get AC. Depending on how paternalistic the organizers want to be, ACing this example problem could be required in order to register.)

D: Fine problem. I liked the red herring of requiring K <= 20, which doesn't make the problem any easier but does make solutions independent of K a bit more suspect, encouraging contestants to prove that their solution actually works rather than going for proof by validation tests. The part after realizing that the requirement is just for the GCD of all chosen numbers to be a factor of D is a bit on the standard side, but I haven't seen this exact variant before (though I have seen "make sure the GCD of all chosen numbers is exactly K for some fixed K" many times). I didn't think this was nearly difficult enough to justify the 41-point allotment; I felt that it was on par with C, and I think 8/9/21/31/31 would have been a reasonable score distribution.

Overall, I enjoyed the round, but I felt like it was substantially easier than Round 1. That said, it does look like the round was hard enough to plausibly distinguish the top 500 from the rest of the participants, so it seems things turned out fairly well.

Me when I make round 3 by knowing morbius inversion but not DFS:

Thank you for the round!

Also, D < B < C imo.

I misread the third problem and was solving the wrong version for quite some time. I was not able to solve it, so I am interested in whether somebody knows how to do so.

I read it as if when a person reaches an already visited page, they stop, but they nevertheless still read this page. So the paths are edge-disjoint, not vertex-disjoint. As far as I understand, in this version, the fact that a topic is mutually-learnable is equivalent to the fact that for any pair of leaves, this topic appears on the path between them (plus on any path from a leaf to the root). I don't know how to solve it in time faster than something like $$$O(nm/w)$$$. Does anybody have any ideas?

Hi,

I'm 501st in the contest, but I had two submissions sent in via the clarification system since I was unable to download the inputs. Can those submissions be considered somehow? My username is socho.

Thanks!

Upd: Thanks a lot, the submissions were added in!

omg. almost failed Hacker Cup again this year because of StackOverflow in A2(2 times failed in previous years). i changed my laptop and visual studio and old methods did not work( but submitted B 10 minutes before contest end and got AC)

Was C solved with something like dp for the sets of topics with small to large optimization?

Can B be solved with just a difference array? For each index find the spans where it is going to fit in the right place + an extra option to be placed in the middle when $$$N$$$ is odd (options to fit are ranging from $$$0$$$ to $$$2 \cdot N - 1$$$ operations). I got stuck with a bug and couldn't implement it properly, unlucky.

UPD.: I just realized that in case of an odd $$$N$$$ to account for extra cases when a pair of elements gets placed in the middle I was increasing by one the elements of the difference array, and not just a separate array, rip.

UPD2.: And it passed the tests, although I really didn't enforce the third condition, only for the halves to be greater/less than each other and the count of all elements to be an even number.

I had a different solution to C. For each string, we iterate over the nodes that contain it in reverse order of depths. Realising the leaf we choose to extend the path down from this node to doesn't matter, we simply check that there is at most one such leaf, and indicate to future nodes that a leaf in the current node's subtree has been satisfied. We do this with a segment/fenwick tree.

Am I the only one who didn't understand the statement of problem B. What does it mean that after each second A1 will move to end of B ?

Problems feedback:

A. First looked too scary for A but ended up being a nice little problem.

B. For me personally looked like a problem with no ideas. Just apply some algorithms to do exactly what is written in the statement (we can just write ABA as one array and need to find a palindrome of length 2n in it which can be done using Manacher's algorithm, the inequalities are also easy to check).

C. From reading other comments and looking at other solutions I am not sure whether my solution is so common (UPD: It seems like it's actually the solution from the editorial). Though it is super easy. For a fixed topic for each leaf, we should look at the first vertex on the path to the root that contains this topic, and for all leaves, these chosen first vertices should be different. We can contract all the bamboos (paths of vertices with a single child), and after that the problem is obvious: if some topic appears in fewer vertices than the number of leaves there are, it can not be mutually-learned. Otherwise, we can just solve the problem in linear time for this topic (just go up for each vertex until you find a visited vertex or a vertex containing this topic) because in a tree where each vertex has at least two children, the number of vertices is at most twice the number of leaves, so the time complexity will be $$$O(M / n \cdot n) = O(M)$$$ where $$$M = \sum m_i$$$. I liked the problem.

D. Not a bad problem but a couple of standard observations and a classical algorithm do not seem worth 41 points.

I have a question for C's editorial. It states:

We can compress the tree by merging "lines", or sequences of nodes with only one child each. [...] With this compression, we guarantee that each tree node has at least 2 children. This means that the numbers of nodes at each level from the bottom to the root will be limited by L, L/2, L/4, ..., 1.

How would this tree be compressed?

There's an extremely simple solution to C which doesn't involve contracting edges or dp or clever optimizations, just a DFS:

1. For each node, count the number of leaves it has in the subtree.
2. Keep count of unpaired leaves for each topic, initially all leaves.
3. Do a DFS, recursively solve all the children first, then for each topic, count the number of unpaired leaves remaining in the subtree (by doing leaves in subtree — (before — after of unpaired leaves)). If the number of remaining leaves is > 1, this topic is impossible. Otherwise if it's 1, then pair it. If it's 0, then do nothing.

At the end a topic is possible if it has not been marked impossible and has 0 unpaired leaves. The complexity is O(n + sum(m)).

Can we get the certificate without rank in practice round(if we didn't participate/make submissions in that)?

This means that the numbers of nodes at each level from the bottom to the root will be limited by $$$L$$$, $$$\frac{L}{2}$$$, $$$\frac{L}{4}$$$, ..., $$$1$$$

Regarding C, does this claim work when the tree is skewed like this?

              1
             / \
            2   3
           / \
          4   5
         / \ 
        6   7
       / \
      8   9

Edit: Nevermind, I'm dumb. We should care about the relative levels and the number of nodes is still bounded by $$$O(L)$$$ anyway.

On macOS, apparently sudo ulimit -s unlimited doesn't change the stack size and doesn't print any errors. After my submission window for C had passed, I found out that these compiler flags worked: -Wl,-stack_size -Wl,20000000. Cost me round 3 qualification :(

Stack Overflow in A2. TT

I use codeblocks, how to increase stack size?

Maybe not standard solution for B and C, so just share some intuitions.

B: First it is trivial that $$$2N$$$ rounds form a cycle. Then my observation is that constraints 1 & 2 are strong enough so that only $$$O(1)$$$ is valid (without checking constraint 3). This is because we are constantly comparing the same pair of $$$(A[i], B[i])$$$ even if it is rotated to the tail of array. We can imagine a separation position where before it has $$$A[i]<B[i]$$$ and after it has $$$A[i]>B[i]$$$, only when this separation position coincides with $$$N/2$$$ can constraint 1 & 2 be satisfied. So $$$O(N)$$$ check for constraint 3 is acceptable, and constraint 1 & 2 can be checked via prefix sum or something similar.

C: An obvious observation is that "a set of paths where each node has only one son" is equivalent to "a single edge", because we will not split such path into smaller sub-paths. Then we can simply merge these paths by merging the topics alongside. After such modification, the tree becomes more compact, as every non-leaf nodes has at least 2 sons, then the number of non-leaf nodes is no larger than number of leaves.

Then we can justify that the number of occurrences of a valid topic should be larger than the number of leaves, because there is one disjoint-path that starts from each leaf. So there are at most $$$O(\sum_i M_i/ leaf)$$$ possibly valid topics, and we can run a simple DP to check if it is possible to assign disjoint-paths, which is $$$O(leaf \log leaf)$$$ (there is log term because I used std::set to check if topic is contained at each node).

Also I'm not an expert in Go (and I would like if someone could clarify this for me), but are moves placing a black stone in positions like this:

. W W
W W W
W W W

or

W W W
W . W
W W W

legal moves? I tried to skim through the rules of Go, but still haven't figured what moves are legal and not (in other words: is placing a black stone on the vacant spots in examples above a "suicide" move, or would it actually capture all of the stones in the real game of Go).

UPD.: I've seen one source mentioning "enforce the capture rule before the suicide rule", so I guess it does make sense in this case.

Can someone please please tell how to change the hard limit of my stack on M2 Mac, it is maxed out to 64MB. I thought ulimit -s unlimited does the trick but it doesn't raise the stack size to over 64MB. Caused me lot of sadness ｡°(°.◜ᯅ◝°)°｡ during the contest. The trick mentioned in nor's blog doesn't work on my arm based processor.

There is actually no reason to use mobious function for problem D. Let $$$f(x)$$$ be number of subsets with $$$GCD = x$$$, then we just compute $$$f$$$ using the following way:

for(int i = MAXV;i >= 1;--i){
    f[i] = Cnk(freq[i], k);
    for(int j = i * 2;j <= MAXV;j += i) f[i] -= f[j];
}

Answer is sum of $$$f(d)$$$ over all divisors of $$$D$$$.

the stack limit really got me today in A2. hopefully MHC will come back with better judge system next year.

I used enhanced Manacher algorithm for B:
I prepared input as follows: C array where Ci = Ai — Bi, then D array = C + (C reversed and negative) + C
Then ran algo on D array with enhanced condition: left_value < 0 && left_value == -right_value. If found palindrome length >= N, then we found center of this palindrome and we can calculate start index of palindrome(meaning answer = needed seconds to get logo). The only thing to care about is that center should be equal to 0 for odd N