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

Looking Forward to this event!!

As a tester, I really recommend playing this round!
Tasty problems with amazing prizes!!

As one of the tester of this contest, I will definitely recommend everyone to play this contest and get ready to solve some really good problems. Good Luck Everyone! See you guys on Leaderboard :)

Great going PASC. Looking forward to play this contest!

is it rated?

Reminder: contest starts in ~1 hrs! (9 pm IST)
We have Global as well as India-level prizes, so be sure to participate!

How many problems

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

In the problem CDS05, should the answer be printed modulo some value?

Could a sample explanation be provided for CDS07? I don't think I understand the procedure described, and I'm not even sure what the answer to the sample is supposed to be as a fraction.

UPD: I think I'm following the sample input now, but an explanation would still be helpful to confirm that my interpretation of the problem is correct.

Thanks for the round--I thought the problems were quite nice! I do think the round could perhaps have done with a bit more preparation: in particular, the modulus in Count the Count wasn't initially specified, and a few of the problems had very weak and/or unexplained samples (which is relatively common on Codechef but can make it somewhat harder to understand the problems). In particular, I found the game theory problem a bit ambiguous because it was unclear from the problem statement whether we would select $$$Y_i$$$ for each string and then pick a random substring with that length to erase, or if we create a list containing all possible substrings to erase and pick one of those at random. Overall, though, I enjoyed the contest, and I'd definitely encourage the authors to keep writing problems.

Brief outlines of my solutions, in increasing order of problem difficulty (judging by solve counts):

Array Subarrays: A naive solution works here. Just split the array into $$$\frac{N}{K}$$$ subarrays of length $$$K$$$, reverse the ones in odd positions, and build the resulting array using the first subarray and the last element of all subsequent subarrays.

Count the Count: We can prove that the only way in which the resulting permutation can differ from the identity permutation is by swapping two adjacent elements. Therefore, in order to construct an array of N elements, we can either take a valid array of N-2 elements and add N and N-1, in that order, or we can take a valid array of N-1 and add N to the end. This means that if ans[i] is the answer to the problem when N = i, we have ans[N] = ans[N-1] + ans[N-2]. We can precompute these values (which are simply the Fibonacci sequence) for all possible values of N in O(maxN) time.

Soumya Wants to Buy a Tree: This is a relatively standard rerooting DP problem. We root the tree arbitrarily and first compute the answer for the subtree rooted at each vertex. Then, we traverse the tree again in order to compute answers for the whole tree. See my code for details. It's helpful here to observe that we can color the vertices black and white such that all edges connect a black vertex and a white vertex; then, the power of $$$-1$$$ in the cost function will be positive for exactly the set of vertices with the same color as the root.

GCD Operations: The answer must clearly be less than $$$A[i]$$$ for all $$$i$$$, so it is bounded by $$$10^6$$$. We check whether all GCDs from $$$1$$$ to $$$10^6$$$ are possible individually. The trick here is that we can compute the minimum number of operations necessary to achieve a given GCD $$$G$$$ in $$$O \left(\frac{\max A_i}{G} \right)$$$ after $$$O(\max A_i)$$$ precomputation using prefix sums (basically, for each multiple of $$$G$$$, we count the number of elements of $$$A$$$ for which this multiple of $$$G$$$ is the greatest multiple of $$$G$$$ less than $$$A_i$$$). Then, we can check if the total number of operations necessary is less than or equal to $$$K$$$, and update our answer if so.

Weird Divisibility: This problem has a fairly standard DP solution. Our state is the number of digits we've processed and the current sum, modulo $$$K$$$. Then, there are ten transitions from each state (ten possible values for the next digit). We can verify that $$$10NMK \leq 8 \cdot 10^7$$$, meaning that this approach should comfortably fit within the time limit.

Equation: The key observation is that if there is any valid solution $$$P$$$ for a fixed $$$Q$$$, then taking $$$P = 1$$$ must also work. This is because if $$$K P 2^Q \leq N < KP2^Q + K$$$, then we can replace $$$K$$$ with $$$KP$$$, at which point $$$KP 2^Q \leq N < KP2^Q + KP$$$ must hold. In other words, we only need to check that powers of two work. This allows us to implement a reasonably straightforward brute force solution, as finding the largest multiple of a power of two less than a given integer is relatively easy.

Special Event: First, if $$$A = B$$$, then the answer is yes if and only if $$$K = 0$$$. Similarly, if $$$K = 0$$$, the answer is yes if and only if $$$A = B$$$. Now, suppose $$$K > 1$$$. We claim the answer is always yes. If either value is not yet zero, then we make one of the values zero by, if $$$A > B$$$, setting $$$A = \lfloor \frac{B}{A} \rfloor.$$$ Then, assuming $$$A = 0$$$ and $$$B \neq 0$$$, we repeatedly set $$$B = A-B = -B$$$ until we've used $$$K-1$$$ moves, after which we set $$$A = B-A = B$$$ as our final move. Thus, the answer is always yes when $$$K > 1.$$$ It remains to deal with the $$$K = 1$$$ case, but here, we can simply check directly if any of the four moves work.

Is This a Game Theory Problem?: First, notice that we can compute hashes of all possible output strings corresponding to a given input string in $$$O(|H_i| \log |H_i|)$$$. Then, we process the input strings in order, maintaining, for each possible hash, the probability that all strings chosen so far have resulted in this particular hash. This probability can be updated using some relatively straightforward calculations; check my code for details.

Happy to answer questions about my solutions below! Obviously, these are very hasty/incomplete writeups, so if you're confused about my approach, checking my code may be helpful. I don't think my code for any of the problems got overly messy, so it hopefully shouldn't be too hard to follow.