Depends on how you're calculating Y. You need to be careful about the case when the king is already on (1,1).

Like milk lol.

Is that not the intended solution? If so, is there any other solution?

For C, I have a stack solution that should hopefully work in O(N).

Solution — https://mirror.codeforces.com/contest/1556/submission/127374965

The idea is that you keep track of open bracket sequences and completed ones in a stack and update accordingly. It works in O(N) because each value either adds a new entry in the stack or deletes a few.

But if the code will not be re-run, how will you know it's wrong?

Yeah, I can barely make it to the 5th or 6th problem with enough time in a 2hr contest.

I used to like Topcoder SRMs for this reason because one can actually get to the harder/nicer problems in time since there are only 3 problems. But i guess I'm digressing here, I'll give it a try when i find time to upsolve. Thanks.

Sure it is, but so are puzzles. None of these problems involved programming or designing a data structure or an algorithm I'd say.

I'm not saying these problems are bad, but it's nice to have a variety in contest problems. There is so much possible with graph/tree, DP, DataStructures, geometry, string algos. So it's a little disheartening to see the first 4 problems just being ad-hoc.

Every other problem is casework lol. Nothing to learn from the first 4 problems.

vovuh Sorry for the ping! But since you prepared this problem, I was wondering if you had some ideas on this? I would suppose you gave this version some thought and then added the constraint to make the problem easier. Would appreciate your input. Thanks.

Back to back segtree problems for the past 3 rounds.

Can anyone explain the thought process of reducing problem F from 2^(2n+2) to 2^(n+2) if one is following the basic inclusion-exclusion process?

Yeah, like why use the word "die" in the statement. I missed the part where they are resurrected and all friendships restored. Wasted an hour trying to see what is wrong. Could've been much clearer with a better wording.

If k = 2, you can pick any 2 nodes so answer is nC2. For k>2 —

Let's say we can pick k nodes such that each node has a distance D with the other. Since all of these nodes are equidistant from each other, and the number of nodes is >=3, this has to be a star formation with one "unselected" node at the centre, and all the selected k nodes are equidistant from this centre (distance of D/2 to be precise, D can never be odd). Let's call the centre X. Let's root the tree at X.

Also note that, any 2 selected nodes will have LCA equal to centre (meaning any path from one selected node to the other must go through centre, otherwise their distance will become shorter). What this means is that from the subtree of each child of X, only one node can be selected. If the number of children X has is <K , we can't select K nodes as the question states. If it has more children (C is the number of children X has) -

Do dfs from each child of X and for a height h, let's say there are n1, n2, n3 ... nC nodes at height h in each child-subtree respectively. Since from each child-subtree, we can only select 1 node. The task becomes selecting K nodes (one from each child) given the above information. This can be done with dp.

DP[a][b] means the number of ways we can select b such nodes (at max one from each child-subtree) from the first a children.

DP[a][b] = DP[a-1][b] + na * DP[a-1][b-1]
// Don't select a node from ath child + Select any 1 among the na nodes from the ath child.

ans += DP[C][K]

Looping over the root node X and height H and then solving the dp for each such combination yields the final result. You can look at my code, but my implementation is a bit messy with some extra code.

tourist Any updates on the editorial for the problems F,G,H?

Thanks. Unfortunately thought of at the last minute so no AC. But i'm glad you liked the solution.

For any prime p at appears in a[i] (ie, a[i]%p = 0) ,if p appears in a[i+1] too, then continousLen[p]++. Else contiuousLen[p] = 1.

This way you don't have to look at all the primes, but only those that are appearing in the number a[i]. We also update the maxLen over such primes only. Consider this similar to lazy updates.

So this should effectively pass in the the TL. This would be O(N * |max number of primes in one number|) Does this make sense?

I think I might be the only one with a non-binary search and non-segtree approach for F. Could not get AC so I'm not even sure if it's the right approach.

1. Divide a[i]/ gcd(a[0],a[1],...a[n-1]);
2. Concat array A with A to make A[1..N],A[1..n] of length 2n.
3. Now we know that the final gcd will be 1. All we need to find now is for a particular prime P, what is the longest continuous segment in the array where all numbers are divisible by P.
4. Final answer is, over all the primes, what is the length of maximum continuous segment as defined above.
5. Start from the index 2n-1 and move left to index 0. We can store the maxContinuous length of each prime in a separate array and update it (+1 if divisible, 0 if not) as we move left.

I couldn't get AC in time, but does the approach sound correct?

Was the TL for E2 really tight? My O(N) soln kept giving TLE on case 12.

https://mirror.codeforces.com/contest/1537/submission/119909827

Thankyou so much for taking out the time to look into this and getting back to regarding the issue. I definitely learnt something new today. I understand why this happened now. Have a nice day :)

https://mirror.codeforces.com/contest/1534/submission/119394653

Can somebody try this out on their machine. I submitted this in contest and it gave WA on pretest-1 and i tried it on my machine multiple times and it worked well. I'm really frustrated as I don't understand how the same code in 2 machines can give different output (my strategy isn't random, the program will always query the same nodes for a particular tree everytime it runs).

https://mirror.codeforces.com/contest/1534/submission/119394653 — This same case passes in my machine in 2 queries, i tried multiple other cases too. But CF says here it took more than 2 queries. Did i miss something here?

Thanks! I hope so too. I aim to reach Div1 sometime in the next few months. Let's see how it goes.

Sorry I'm getting back to CF after many years and now I see there is also a Div3. Will this round also be rated for Div3 folks?

It's still wrong even if both accounts are yours, you are essentially bypassing all the WA penalties. How do you expect CF to know which account belongs to which human on earth. If 2 accounts use the same solution, they should be penalised.

You can check my solution, but the idea is that you can sort the array and process it in order of increasing a[i]. Now you need to solve how many pairs are such that a[i] + a[j] <= X. If you start from the smallest a[i], all the numbers <= X — a[i] will be valid pairs. As you move to the next i, a[i] will increase, and the numbers <= X — a[i] will only decrease so you can use a pointer.

You can also use a 2 pointer approach.

Wow, this was such a fun read. Thanks for putting in the effort with the diagrams and thought-process.