Threading worked.

I was implementing a $$$O(2^N \times 26)$$$ solution. Using meet in the middle and breaking bit strings into two $$$64-bit$$$ numbers.

For a binary string with only '?'s and characters. One can compute the number of nodes required by splitting the string into $$$4$$$ $$$25$$$-bit numbers, having precomputed counts for all $$$25$$$-bit numbers and merging these by linear combinations.

Somewhere around, I realized that I wasn't sure whether this would pass. I was using an M3 Pro with $$$11$$$ cores, so I ran each testcase in a separate thread and it passed. Took 3 minutes. Meet in the middle was still required, however, for memory limits.

If you find the expected number of moves to reduce the minimum achieved weight by $$$1$$$, you can just multiply this value by the difference of the weights to find the answer. Memorylessness.

Let's find this value. You start at $$$0$$$, You move left or right on the number line with equal liklihood, except when you are at $$$L$$$, you only move towards the left.

Expected number of moves to reach $$$-1$$$ is needed, which can be found by solving a system of equations. This is the approach used by most contestants, I believe.

I would describe another approach. Let's say that you are well aware of the following fact:

If you are on the number line at $$$0$$$, moving left and right with equal liklihood, and want to stop moving after you reach either $$$-a$$$ or $$$b$$$, then the expected number of moves needed is $$$ab$$$. This can be proven by solving a similar system of equations. But, this fact is more well known (look into gambler's ruin).

In the problem, you seem to have only one choice when you are at $$$L$$$, that is to move left. Say you remove this restriction and allow yourself to go to $$$L+1$$$. Assuming that your world has been reflected. In this reflection, $$$-1$$$ will appear at $$$2L+1$$$.

Now, this has been reduced to the version of gambler's ruin bounded on both sides, with $$$a = 1$$$ and $$$b = 2L+1$$$. The expected number of moves is thus $$$2L+1$$$.

E was nice. Until the last 40 minutes, I thought that the first operation can be only applied to the entire string. That led to a much more complicated problem. :(

Firstly, notice that the condition basically says that each integer $$$i$$$ ($$$1 \leq i \leq n$$$) should lie in at most $$$k-1$$$ segments of the set. This is a necessary and sufficient condition.

I first consider this method of "building" permutations. Basically, in a permutation, for each element you can make an edge to the next element. And make an edge from the last element to zero, to denote the end of the permutation. We will try to build this graph representation of the permutation.

Now, think of the subgraph of such a graph if you only consider the nodes $$$[0, i]$$$. This will look like a directed graph with $$$m$$$ chains, with exactly one chain ending at zero. We will basically build the final graph, by adding nodes to the graph one by one, from $$$1$$$ to $$$n$$$. When we add node $$$i$$$, we only have to decide if it has any outgoing or incoming edges to lower numbered nodes. We can see that depending on our choice, the number of chains will increase by $$$1$$$, decrease by $$$1$$$, or remain same. Try to see how the number of ways to cause each of these changes only depends on the initial number of chains $$$m$$$. We must make sure that we never attach a outgoing edge to the node $$$0$$$, as it's supposed to denote the end. Notice that depending on our choice of how we add $$$i$$$ to the graph, and the previous number of chains $$$m$$$, we can exactly determine the number of segments of the final permutation, in which $$$i$$$ will lie. This will allow us to not consider choices in which this exceeds $$$k-1$$$.

As the number of chains $$$m$$$ in the subgraph $$$[0, i-1]$$$, is the only important data we need, I denote $$$\text{dp}[i][m]$$$ as the number of ways to proceed to build a good permutation, given we have already built the subgraph with nodes $$$[0, i-1]$$$, which has $$$m$$$ chains. Try to form the $$$O(1)$$$ transition. The final answer is simply $$$\text{dp}[1][1]$$$.

Code

Permutation Segments was nice, but I feel the "segment intersection is empty" part should have been well defined. I missed AC because I took the definition to mean "length of intersection is zero", whereas the intended definition was that the intersection of the closed intervals should be zero (calling them segments rather than closed intervals threw me off). The different definitions lead to slight changes in the solution (one line). And the only way to realize that the second definition was intended was to analyze the missing permutations of test case 3, which I couldn't do during contest.

Again, nice problem though.

Now, if you could please explain the problem statement for Q5.

Oh yes, somewhat painful, but can be done.

Kind of sad that $$$O(N (\log{N})^2)$$$ approaches passed in F.

I initially had an interesting $$$O(N^2 \log{N})$$$ solution where I run a re-rooting DP on each edge weight separately, to calculate contributions of that edge weight (a range sum data structure was used for this, thus the log factor). I sped this to $$$O(N \log{N})$$$ by using the DFS times for each node and simulating the DFSs for each edge weight by just looping along occurrences of each edge weight in the DFS order, using only $$$O(\text{occ}(x) \log{N})$$$ for each weight $$$x$$$, where $$$\text{occ}(x)$$$ is the number of occurrences of $$$x$$$.

Edit to add:

Since people seem confused, I will explain my solution in some more detail. Firstly the $$$O(N^2 \log{N})$$$ idea. First root the tree arbitrarily. Now, we find the contribution for each edge weight separately. I will describe how to calculate the contribution of edge with weight $$$x$$$.

Notation:

$$$\text{comp}(u, x)$$$ is the size of connected component of if only edges with weight not equal to $$$x$$$ are considered, $$$\text{sz}(u)$$$ is the size of subtree of $$$u$$$, $$$\text{par}(u)$$$ is the parent of node $$$u$$$, $$$\text{anc}(u)$$$ is the set of proper ancestors of $$$u$$$, $$$\text{sub}(u)$$$ is the set of nodes in subtree of $$$u$$$.

Define $$$\text{dp1}[u] = \text{comp}(u, x)$$$ if the parent edge of $$$u$$$ has weight $$$x$$$ and $$$0$$$ otherwise. Similarly, define $$$\text{dp2}[u] = \text{comp}(\text{par}(u), x)$$$ if the parent edge of $$$u$$$ has weight $$$x$$$ and $$$0$$$ otherwise.

How to compute $$$\text{dp1}[u]$$$? Some careful thought yields:

and

With these expressions, $$$\text{dp1}[u]$$$ can simply be computed with DFS and a range sum data structure (on the Euler tour of the tree). After computing all values of $$$\text{dp1}$$$, the $$$\text{dp2}$$$ values can be computed with DFS and a range sum data structure, noting that $$$dp2$$$ value of a node $$$u$$$ will be used when $$$u$$$ is an ancestor and $$$dp1$$$ otherwise. So, these values can be switched in the range sum data structure during DFS.

Contribution of weight $$$x$$$ is simply $$$\sum \text{dp1}[u] \cdot \text{dp2}[u]$$$.

How to make this $$$O(N \log{N})$$$? Well, since only particular $$$dp$$$ values are ever non-zero for a weight $$$x$$$, we can simulate the entire process by just looping over the positions of these nodes in the DFS order.

Code: 158206764

Great round! Especially enjoyed E and F.

I did same :D. I was shocked seeing so many AC's so I thought a bit more later, and realized there was no need of FFT/NTT.

H was pretty cool.

Did anyone come with something else?

Aha my bad, I assumed segment tree was supposed to pass. I just realized that it can be done in linear time.

Problem F was somewhat straightforward if you have already solved 446C - DZY Loves Fibonacci Numbers. Why such a tight TL tho?

My solution:

Let's first look at the solution worth $$$50$$$ points. Do the following $$$n$$$ times, to assign positions to numbers from $$$1$$$ to $$$n$$$: Find a zero in the array, which doesn't have any other zero among the $$$k$$$ places to its left. Assign the $$$i$$$th number to this position in the answer. Subtract the values at the $$$k$$$ places to its left by $$$1$$$ and set the value at this position to infinity. If at any point there are no zeroes in the array, then output $$$-1$$$. Otherwise, output the final answer array. Try to see why this works.

There are a few more observations needed to get $$$100$$$ points. Firstly, observe that if any value turns negative during the process, then there is clearly no answer as this value will never reach zero. So, zeroes, if they exist will have to be the minimum values in the array.

For a moment, ignore the fact that if there are multiple zeroes, then you have to give preference to the zero which doesn't have another zero in the $$$k$$$ values to its left. We will tackle that later. Say you just want to find a zero. Then, you can just find the index of minimum value in the array and check if that is a zero. Updating the preceding $$$k$$$ values can simply be thought of as one or two range updates.

This problem can be solved by using a min segment tree with lazy updates. Just build the segment tree over pairs $$$(\text{value}, \text{index})$$$ to retrieve the index of the minimum.

Now, to tackle the part about choosing a particular zero if there are multiple zeroes. This part needs a final observation, why do we have $$$n \leq 2k-1$$$? Say a index $$$i$$$ dominates index $$$j$$$ if $$$i$$$ is among the $$$k$$$ indices to the left of index $$$j$$$. The condition $$$n \leq 2k-1$$$ means that for any two indices $$$i$$$ and $$$j$$$, either $$$i$$$ dominates $$$j$$$ or $$$j$$$ dominates $$$i$$$ (or both). Also, note that among multiple zeroes, we always have to choose the zero which is not dominated by any index.

This can be achieved simply by tweaking the comparator of the pairs $$$(value, index)$$$. If the values are same, then compare the index which dominates the other index as lesser (if both dominate each other, then it doesn't matter). This comparator has the property that whenever a solution exists, the index returned by the segment tree would surely be a valid index.

PS: Pretty problem.

My solution had used most of these ideas.

I solved it by fixing the middle element of the last 3 remaining elements, then counting the ways to remove the left part and right part separately (later multiply by a single binomial coefficient to account for permutations among the left and right operations).

Counting the left and right parts themselves needed some DP and segment tree ideas.

Unfortunately, there were some issues in my implementation during contest, which I fixed later. Really liked the problem though.

I had a different $$$O(Q \sqrt{N})$$$ solution for The Antique Store. I noticed the need for point update and range sum data structure along with Mo's algorithm. But since Mo's can have $$$O(Q \sqrt{N})$$$ updates, a data structure supporting update in $$$O(\log{N})$$$ won't be enough.

This suggests a need for a data structure which has faster updates but slightly slower queries. So, I used square root decomposition (on the array, not Mo's) for point update and range sum as updates are $$$O(1)$$$ and queries are $$$O(\sqrt{N})$$$. Since there are only $$$O(Q)$$$ queries, overall complexity is $$$O(Q \sqrt{N})$$$.

Code

Aha right, you can use each record and all elements till the next record, in that order, to form a cycle.

I found it interesting that the first four problems all had simplistic solutions, although participants could get lost trying complicated ideas.

Boring trip was somewhat standard as you say, it has lesser submissions than I would expect.

Beautiful Permutation: I took the longest for this one, was thinking about two variable generating functions, etc. for long time. I saw that quite a few participants had solved this very quickly so looked for something simpler.

Later realized that answer could be derived from number of permutations in $$$n$$$ having $$$k$$$ records, and multiplying by $$$2^k$$$. This coupled with the fact that the probability of the $$$i$$$th number being a record in a permutation is $$$1/i$$$ independently of the other probabilities led to Stirling numbers of the first kind. I think this probabilistic reasoning would be much simpler than derivation from two variable generating functions.

Overall I enjoyed the contest.

Maybe this problem?

Not exactly the same, the USACO problem has a greedy solution, but the DP solution works for both problems.

Maybe they don't have hard enough problems to serve all Div 1 contestants (like IGMs and LGMs) but good enough for lower rated Div 1 contestants, which they expect in the official round.

Prerequisites for this blog?

Well some proofs for D1 did help in solving D2. For example my proof (and solution for D2) described here.

Edit: I am talking about D2

I also had the $$$(\log{n})^2$$$ idea initially (small to large merging with some multiset-like data structure). I optimized it by using the following simple idea to construct edges:

If any forest becomes connected, we are done. Otherwise, both forests have at least $$$2$$$ components. Consider any two nodes $$$x$$$, $$$y$$$ in distinct components of the first forest and any two nodes $$$p$$$, $$$q$$$ in distinct components of the second forest.

If $$$x$$$ and $$$y$$$ are in distinct components of the second forest, then add edge between $$$x$$$ and $$$y$$$. Otherwise, at least one among $$$u$$$ and $$$v$$$ will be in a different component than $$$x$$$ and $$$y$$$ in the second forest, say $$$u$$$. Now, at least one among $$$x$$$ and $$$y$$$ will be in different component than $$$u$$$ in the first forest, say $$$x$$$. So merge $$$u$$$ and $$$x$$$.

This construction in fact acts as a proof for the solution!

Particular values of $$$a_i$$$

Nice problems!

Here's an extended version of $$$C$$$ which is cool:

You won't be given the array $$$a_i$$$ itself, instead you will be given $$$n$$$ and you can interact and ask for particular values of $$$a_i$$$. Ask at most $$$20$$$ queries and output the answer as required in the original problem. Assume $$$n \lt 10^5$$$.

Okay here is a solution as some people are asking:

Okay, as the editorial solution is entirely different, I will describe my solution here (which I liked better).

Code: 125400662

Nope. It's wrong. It's just hard to make an opponent to counter all such solutions I guess.

I just loved $$$E$$$. Nice puzzle. Here's a small hint for those interested:

You can see that consecutive red squares are in the same connected component, so there can be at most $$$4$$$ distinct connected components in a row.

This gives you a bound of $$$5^8 = 390625$$$, which is enough to work with (for storage).

Actual bound is much lower. Number of such connectivity states which are valid are called crossing-free partitions and are related to catalan numbers.

My Code

I did it with DP on a broken state. Maintain the connected components of the last row when processing the next row.

For everyone wondering why a good subarray cannot have length greater than $$$4$$$ in $$$C$$$. There is a theorem Erdos Szekeres which basically states that any sequence with length greater than $$$xy$$$ must have either a non-increasing subsequence of length $$$x+1$$$ or a non-decreasing subsequence of length $$$y+1$$$ or both.

Put $$$x = y = 2$$$ for this problem.

Hint for proving this theorem:

We can assign Grundy values to each game. Let's denote $$$g(x, y)$$$ as the Grundy value corresponding to the game where all intervals lying entirely in $$$[x, y)$$$ are considered. We find:

Alice wins if $$$g(1, 100) \gt 0$$$ otherwise Bob wins.

Code

Apparently many people solved $$$E$$$ with some casework. You can do also like: (which I think is intended solution).

Wow. Now it passed in ~2 seconds. Interesting!

Sad that simple $$$O(NK \log(N))$$$ with long long and recursive lazy segment tree TLEed on E. Had to make some submissions and ACed with unsigned in the end. Did no tester face this issue or was it intentional to prevent other slower solutions for passing?

Yes. I proved that work done will be same regardless of how you move the particle from $$$(1, 1)$$$ to $$$(n, m)$$$. The problem just asks to consider specific ways to displace the particle, using only the vectors $$$(1, 0)$$$ and $$$(0, 1)$$$.

You can also prove it like this:

Consider the conservative field $$$\vec{E}=y\hat{i} + x\hat{j}$$$. Observe that the value required is just the work function. As potential function is $$$U = xy$$$, work done will always be $$$nm - 1$$$.

Really liked $$$E$$$. I wonder if everyone solved it the way I did.

SOLDIERS was nice. I don't know if the intended solution involved randomization but here's mine:

For each index $$$i$$$, define set $$$S_{i}$$$ which is defined as:

Now, for $$$i$$$, if $$$S_i = \varnothing$$$, set $$$a_i = 1$$$ if $$$p=0$$$ or $$$a_i=N$$$ if $$$p=1$$$.

For all other $$$i$$$, gather all $$$i$$$ with identical $$$S_i$$$ and permute them optimally. For checking this, represent each set as a hash (xor of all $$$f_j$$$ where $$$j \in S_i$$$ and $$$f_j$$$ is randomly generated). To compute this fast, use some data structure like lazy segment tree or difference array.

C2 was really beautiful.

Here's a bonus problem for A: What if the numbers have to be pairwise distinct? Take $$$n \lt 1000$$$ and the numbers you output must be less than $$$5000$$$.

Those were day 1 results.

shashwatchan $$$175$$$

RestingRajarshi $$$160$$$

Well he was, but I made sure they are alright ;)

As a tester... Damn there's so many of us!

No, I just happened to stumble upon it.

Even B and D many solved without proving.

My solution for E was exactly like the one described by Mohammad_Yasser in the editorial. I also thought about why the third case $$$p_{a} | p_{b} = p_{b} | p_{c}$$$ doesn't appear often. Here's what I found.

Say number of unset bits in $$$p_b$$$ is $$$y$$$. Observe that $$$p_{a} | p_{b} = p_{b} | p_{c}$$$ implies that any bit unset in $$$p_b$$$ is set in $$$p_c$$$ if and only if it is set in $$$p_a$$$. Thus, assuming $$$p_a$$$ and $$$p_c$$$ are chosen uniformly at random (they aren't really random, but I will talk about that later), the probability that $$$p_{a} | p_{b} = p_{b} | p_{c}$$$ is $$$\frac{1}{2^{y}}$$$.

Now, with this observation, we have to find the expected number of times we need an extra query given we repeat the operation $$$q$$$ times. We can have the following dp for this:

Let $$$\text{dp}(q, y)$$$ denote the expected number of times we need an extra query given we repeat the operation $$$q$$$ times, and initially $$$p_b$$$ has $$$y$$$ unset bits. We arrive at the following recursion:

Now, you could either compute this dp for $$$q = 2048$$$ or just observe that as most numbers will have around half their bits set, this expected number is very less.

Also, as our algorithm basically tries to reduce $$$p_a$$$, the expected number of unset bits increases in general and thus the expected number of extra queries may actually be lesser.

No idea

Nice contest. I enjoyed solving all :p

Oh you are right. I might have written my brute force wrong then. My bad.

Edit: Oh no, my code is correct. 6+2+1+1 is wrong because if n = 4 you can't use 6.

The irony is that the one question answered by the FAQ has been answered wrongly.

I see many people aren't satisfied with the pattern finding solutions of Div2D/Div1B and Div2E/Div1C. Here are some ideas:

Div2D/Div1B:

Let's give each vertex $$$u$$$ a value $$$f(u)$$$, having the property that weight of edge $$$u-v$$$ is equal to $$$f(u) \oplus f(v) $$$. Observe that fixing the values of $$$f$$$ for all vertices gives unique values of edge weights and for each way of fixing edge weights, we have some corresponding values of $$$f$$$ (Infact fixing all edge weights and $$$f(u)$$$ for a single vertex produces a unique graph).

This trick of converting edge weights to vertex weights and vice versa is quite useful in lot of tree problems.

Now, observe that $$$\text{xor}$$$ along all edges of any path from $$$u$$$ to $$$v$$$ is equal to $$$f(u) \oplus f(v)$$$. Thus, if we want $$$\text{xor}$$$ along path between any $$$2$$$ leaves to be $$$0$$$, then values of $$$f$$$ for all leaves must be same, let's set them equal to $$$0$$$. Now, we can give any value for all non-leaf vertices, so long as no $$$2$$$ adjacent vertices have the same value (as edge weight cannot be zero).

Now, it's not that hard to see that if we assign, say the value $$$2^i$$$ to the $$$i$$$th non-leaf vertex, then all edges between non-leaf vertices will be distinct. So, this way we can calculate answer for the max case. For the min case, we "color" the non-leaf vertex with $$$2$$$ colors. If only one of these colors is ever adjacent to a leaf, we can let the other color be equal to the color of the leaf vertex, thus, all edges will be of the same weight. Otherwise, all $$$3$$$ colors come in contact with each other, so we have to use $$$3$$$ different edge weights for each pair of colors.

Edit: Deleted Div2E/Div1C explanation because it eas wrong.

Wow! Now, my proof looks stupid :(

Today's $$$E$$$ was a bit tricky to prove.

Firstly, let's represent any number $$$x$$$ by a sequence $$$x_i$$$ where

where $$$p_i$$$ are all the $$$n$$$ primes from $$$1$$$ to $$$n$$$.

Now, observe that the weight of the edge from $$$x$$$ to $$$y$$$ will be

where $$$x = y \cdot p_k$$$. (Why ?)

Now, if we want to go from $$$u$$$ to $$$v$$$ in the graph, in each step we can either add $$$1$$$ to some $$$u_i$$$ or subtract $$$1$$$ from some $$$u_i$$$. As we want to find the shortest path, we will reduce $$$u_i$$$ by $$$1$$$ only if $$$u_i \gt v_i$$$ and add $$$1$$$ only if $$$u_i \lt v_i$$$. Also, its optimal to reduce all $$$u_i$$$ which are greater than $$$v_i$$$ before increasing any $$$u_i$$$ which are less than $$$v_i$$$. Both these statements can be proven.

Now, consider all $$$i$$$ having $$$u_i \gt v_i$$$. In what order would you reduce these? I claim that the order in which you reduce these doesn't matter.

Thus, the number of shortest paths is the number of ways to reduce all $$$u_i \gt v_i$$$ to $$$v_i$$$ multiplied by number of ways to increase all $$$u_i \lt v_i$$$ to $$$v_i$$$.

I am sure many of you must have noticed this but for those who didn't:

The name ESAb ATAd is Data Base after reversing the letters and taking "complement". (If we take complement to mean switching cases).

This is similar to how a similar problem last year was named "Dat Bae" which is "Data Base" missing two lettets a and s. And that problem was about losing bits in data!

I had the same construction for cases 1-3. I couldn't figure out 4. Also, another thing to note is you can't represent all numbers in $$$[n+3, n^2-3]$$$ by picking three numbers that appear $$$x$$$, $$$1$$$ and $$$n-x-1$$$ times.

For eg. there is no such representation for $$$n = 4, k = 10$$$.

Good news is all these numbers can be represented by picking $$$2$$$ numbers, one appearing $$$2$$$ times and other appearing $$$n-2$$$ times. So, you can use the square obtained from case 4 here.

I think your code is automatically doing this, so it should be fine.

Hint: Consider any $$$2$$$ leaves of the tree $$$u$$$ and $$$v$$$. Say $$$lca(u, v) = w$$$. Observe that $$$w \in $$${$$$u, v$$$} if and only if $$$w$$$ is the root.

No. You can find LDS in $$$O(n \log{k})$$$ where $$$k$$$ is the size of the alphabet using binary search/fenwick tree/segment tree. Even a simple $$$O(nk)$$$ algorithm will work for this problem. Search online for LIS solutions.

Solution for $$$E2$$$:

Firstly observe that the question asks to use minimum number of colors such that subsequence formed by each color is sorted.

Consider the longest decreasing subsequence (LDS) of the given array. Observe that no two elements of this sequence can be given the same color, hence number of colors must be greater than or equal to the length of the LDS.

Now, to find a coloring with number of colors equal to length of LDS, let $$$lds(i)$$$ denote the length of longest decreasing subsequence which ends at $$$i$$$ and includes the $$$i$$$th element. Observe that if $$$a_i \gt a_j$$$ with $$$i \lt j$$$, then $$$lds(j) \gt lds(i)$$$. Importantly, $$$lds(j) \neq lds(i)$$$. Thus, you can just assign the $$$i$$$th element the color $$$lds(i)$$$.

I can't think of one :(

The question is: Why should the greedy work?

Hmm. I had done this DP on (edge, direction) thing already once so it struck me quickly. Anyway, neat trick.

Yeah let dp[u][v] denote the maximum answer given edges from $$$0$$$ to $$$x-1$$$ lie on the path between $$$u$$$ and $$$v$$$ where $$$x$$$ is the length of path $$$(u, v)$$$.

Yeah I did with 2D DP. I let dp[u][v] denote the maximum answer given edges from $$$0$$$ to $$$x-1$$$ lie on the path between $$$u$$$ and $$$v$$$ where $$$x$$$ is the length of path $$$(u, v)$$$.

I really liked today's Div1C/Div2E. Here's a hint:

Observe that

Edit: Since, this was obvious for lot of people, hint 2:

Let dp[u][v] denote the maximum answer given edges from $0$ to $$$x-1$$$ lie on the path between $$$u$$$ and $$$v$$$ where $$$x$$$ is the length of path $$$(u, v)$$$. How can you transition?

I had a overkill solution for $$$D$$$ which led to a good data structures problem. While, others have provided much more elegant solutions, this reduced version is a good problem on its own and worth sharing.

Here's the problem:

You are given two sequences $$$a_i$$$ and $$$b_i$$$ of length $$$2N$$$ each. Each number from $$$1$$$ to $$$N$$$ appears exactly twice in both the sequences. You have to solve $$$Q$$$ queries of the following kind:

Given $$$l$$$, $$$r$$$, $$$x$$$ and $$$y$$$, find the set of distinct elements in $$$(l, r)$$$ in $$$a$$$ is exactly equal to the set of distinct elements in $$$(x, y)$$$ in $$$b$$$. That is, any number $$$u$$$ has an appearance in segment $$$(l, r)$$$ in $$$a$$$ if and only if it has an appearance in segment $$$(x, y)$$$ in $$$b$$$. Try to solve this online in $$$O((N+Q)\log(N))$$$.

Think of how you can reduce today's $$$D$$$ into this problem.

My code for today's D: 68189310

Umm, no. That is not sufficient. I am not sure how this passed, I have hacked your solution :). Poor test data?

Here's a counter case:

4
1 5 1 5
2 8 7 10
7 10 2 8
9 20 9 20

Here's a cool reduction I made for $$$E$$$:

Claim: Find the sum of number of points in all possible triangles in the given set. Divide this by $$$2$$$ and multiply by $$$n-4$$$, that's the answer.

Proof: For any castle of $$$4$$$ points and a point $$$P$$$ which lies inside it, consider all the $$$4$$$ triangles made by taking the castle points $$$3$$$ at a time. Out of these $$$4$$$ triangles, $$$P$$$ will lie in exactly $$$2$$$ of them. Conversely, consider any triangle and any point $$$P$$$ lying inside it. If you add any of the other $$$n-4$$$ points to make the triangle into a quadrilateral, you will get a valid castle of the triangle points and this new point which will protect $$$P$$$.

Thus, we have proven a two-one bijection between these two quantities.

Now, if you could find the sum of number of points lying inside each triangle in $$$O(n^2)$$$, you have solved the problem!

Thsnk you, guys!

I don't feel good about it either. I just chose a random adjective starting from 'A' to add next to my name. Guess I gotta wait till next year now. :(

$$$C$$$ answer for challenge is $$$1$$$ ($$$0$$$ if sequence is already good ofc). Observe that multiplying the xor by $$$2$$$ is just shifting its binary representation to the left by $$$1$$$ bit.

As $$$2 \cdot \text{xor} = \text{sum}$$$, the last bit of the sum must be $$$0$$$. Now, calculate the value of last bit of the sum by adding all the given numbers. If it is $$$1$$$, put $$$1$$$ as the last bit of the new number otherwise put $$$0$$$. Now, find xor of all these last bits of numbers including the number you just added. This must be the value of the second bit from the end of the sum. Keep repeating this process. Each time you fix the $$$i$$$ th bit of the new number, you xor all the $$$i$$$ th bits to get the $$$i+1$$$ th bit of the sum and hence you can fix the next bit.

Prove that this process cannot go on forever.

Complexity: $$$O(n\log{n})$$$

What editorial? Its not a solution. I am just posting a cool fact I thought I should share. And I have clarified on top that I posted this on the wrong thread. :)

$$$F$$$ was cool. Here's a fun fact: You can prove that number of trees in $$$n$$$ vertices is $$$n^{n-2}$$$ if you have a working algorithm for $$$F$$$!

Your algorithm is deterministic, so it generates exactly one output for each input. Also, as each output corresponds to a unique ordering of edge importance, each output will correspond to exactly one input. But number of different inputs with $$$n$$$ vertices $$$= n^{n-1}$$$ and number of different outputs $$$= nT(n)$$$ where $$$T(n)$$$ is number of undirected simple graphs in $$$n$$$ vertices which are trees. (We are multiplying by $$$n$$$ because same graph with different roots are considered distinct in the output.) Thus, as inputs and outputs have a bijection, $$$n^{n-1} = nT(n)$$$. Thus, $$$T(n) = n^{n-2}$$$!

This is kinda similar to other proofs of Caylee's formula like Prufer Codes and proof of Caylee's formula by double counting.

Edit: This was meant to be a comment for the Div 3 Contest.

$$$F$$$ was cool. Here's a fun fact: You can prove that number of trees in $$$n$$$ vertices is $$$n^{n-2}$$$ if you have a working algorithm for $$$F$$$!

Your algorithm is deterministic, so it generates exactly one output for each input. Also, as each output corresponds to a unique ordering of edge importance, each output will correspond to exactly one input. But number of different inputs with $$$n$$$ vertices $$$= n^{n-1}$$$ and number of different outputs $$$= nT(n)$$$ where $$$T(n)$$$ is number of undirected simple graphs in $$$n$$$ vertices which are trees. (We are multiplying by $$$n$$$ because same graph with different roots are considered distinct in the output.) Thus, as inputs and outputs have a bijection, $$$n^{n-1} = nT(n)$$$. Thus, $$$T(n) = n^{n-2}$$$!

This is kinda similar to other proofs of Caylee's formula like Prufer Codes and proof of Caylee's formula by double counting.

While we are on the topic of polynomials, you might as well try my polynomial problem:

Anay and Polynomial

It's a nice problem with an elegant solution of $$$40$$$ lines!

Edit: Why the downvotes?

I implemented the simulation by C++ upper_bound but I am missing some cases.

Edit: I just realized that I had just forgotten to replace a $$$x$$$ by $$$y$$$ after copy-paste. Got AC now. :(

Cool, thanks.

Greedy solution for $$$D$$$:

Keep going in the direction you are facing until you have to change it. When you can't move anymore, see if you covered all squares, if you did, answer is yes otherwise answer is no.

Try to prove this.

Implementation: 62820909

Edit: Why the downvotes?

Your first tree is not a BST. $$$4$$$ cannot be in the left subtree of $$$3$$$.

Wow! I can't believe I won a T-shirt. How and when do we receive it?

Here's my solution for E with proof:

Perfectly balanced tree must have the condition that every level, except possibly the last, must be completely filled.

What's the condition for striped BSTs? Let's find the condition for each child to match condition of its parent. So, if it's a left child, it should have key parity different than the parent and if it's a right child, it should have key parity different than the parent. Now, observe that for a left child $$$u$$$,

This tells us that every node which is a left child of its parent must have even number of nodes in its right subtree. Similary for every right child $$$u$$$,

This tells us that every node which is a right child of its parent must have odd number of children in its left subtree. With these two observations, we can find number of possible subtrees of height $$$h$$$ like this,

For height $$$1$$$, there is only one tree, one node with no children. For height $$$2$$$, there is only one tree, one node with one child on its left and no child on its right.

For each height $$$h$$$, let's store all the possible trees as a pair $$$(a,b)$$$ where $$$a$$$ is the number of nodes in the left subtree of the root and $$$b$$$ is the number of children in the right subtree of the root. Now, we observe the following simple pattern:

For height $$$1$$$ possible trees: $$$(0,0)$$$, possible sizes: $$$1$$$

For height $$$2$$$: $$$(1,0)$$$, possible sizes: $$$2$$$

For height $$$3$$$: $$$(1, 2)$$$, $$$(2,2)$$$, possible sizes: $$$4$$$, $$$5$$$

For height $$$4$$$: $$$(4, 4)$$$, $$$(5,4)$$$, possible sizes: $$$9$$$, $$$10$$$

For height $$$5$$$: $$$(9,10)$$$, $$$(10,10)$$$, possible sizes: $$$20$$$, $$$21$$$

Can you spot the pattern and prove it? For every height $$$\geq 3$$$, there are exactly two trees possible.

Proof: If for height $$$i$$$ we have possible trees $$$(a,x)$$$ and $$$(b,x)$$$ where $$$x$$$ is even, $$$a$$$ is even and $$$b$$$ is odd, then for height $$$i+1$$$, we can have the right child only as $$$(b,x)$$$ as only then then number of nodes in its left subtree will be even. But the left child can have any of the two values as both satisfy the condition of right subtree having even size. Thus, the new trees are $$$(a+x+1,b+x+1)$$$ and $$$(b+x+1,b+x+1)$$$, which can then be replaced with new $$$A$$$, $$$B$$$ and $$$X$$$ having $$$A = b + x + 1$$$, $$$B = a + x + 1$$$ and $$$X = b + x + 1$$$. Thus, we can say that the pattern holds by induction.

Base case has $$$i = 3$$$, which is satisfied as $$$a = 2$$$, $$$b=1$$$ and $$$x=2$$$.

So, find all possible trees till height $$$\log(\text{max value of n})$$$ and output $$$1$$$ if $$$n$$$ is one of those values and output $$$0$$$ if it isn't.

AC Code: 62737057

I completed the code at the last moment but couldn't submit in time.

Here's my solution in short:

Perfectly balanced tree must have the condition that every level, except possible the last, must be completely filled.

What's the condition for striped BSTs? Let's find the condition for each child to match condition of its parent. So, if it's a left child, it should have key parity different than the parent and if it's a right child, it should have key parity different than the parent. Now, observe that for a left child $$$u$$$,

This tells us that every node which is a left child of its parent must have even number of nodes in its right subtree. Similary for every right child $$$u$$$,

This tells us that every node which is a right child of its parent must have odd number of children in its left subtree. With these two observations, we can find number of possible subtrees of height $$$h$$$ like this,

For height $$$1$$$, there is only one tree, one node with no children. For height $$$2$$$, there is only one tree, one node with one child on its left and no child on its right.

For each height $$$h$$$, let's store all the possible trees as a pair $$$(a,b)$$$ where $$$a$$$ is the number of nodes in the left subtree of the root and $$$b$$$ is the number of children in the right subtree of the root. Now, we observe the following simple pattern:

For height $$$1$$$ possible trees: $$$(0,0)$$$, possible sizes: $$$1$$$

For height $$$2$$$: $$$(1,0)$$$, possible sizes: $$$2$$$

For height $$$3$$$: $$$(1, 2)$$$, $$$(2,2)$$$, possible sizes: $$$4$$$, $$$5$$$

For height $$$4$$$: $$$(4, 4)$$$, $$$(5,4)$$$, possible sizes: $$$9$$$, $$$10$$$

For height $$$5$$$: $$$(9,10)$$$, $$$(10,10)$$$, possible sizes: $$$20$$$, $$$21$$$

Can you spot the pattern and prove it? For every height $$$\geq 3$$$, there are exactly two trees possible.

Proof: If for height $$$i$$$ we have possible trees $$$(a,x)$$$ and $$$(b,x)$$$ where $$$x$$$ is even, $$$a$$$ is even and $$$b$$$ is odd, then for height $$$i+1$$$, we can have the right child only as $$$(b,x)$$$ as only then then number of nodes in its left subtree will be even. But the left child can have any of the two values as both satisfy the condition of right subtree having even size. Thus, the new trees are $$$(a+x+1,b+x+1)$$$ and $$$(b+x+1,b+x+1)$$$, which can then be replaced with new $$$A$$$, $$$B$$$ and $$$X$$$ having $$$A = b + x + 1$$$, $$$B = a + x + 1$$$ and $$$X = b + x + 1$$$. Thus, we can say that the pattern holds by induction.

Base case has $$$i = 3$$$, which is satisfied as $$$a = 2$$$, $$$b=1$$$ and $$$x=2$$$.

So, find all possible trees till height $$$\log(\text{max value of n})$$$ and output $$$1$$$ if $$$n$$$ is one of those values and output $$$0$$$ if it isn't.

AC Code: 62737057

Here's my solution with proof:

Btw, this was my first time setting a problem, so I hope you enjoyed it.

I thought those cases would give "NO" output due to some reason. I was wrong. Thanks.

My solution for A:

Consider all buildings already built and that you are removing them one by one. Let V be number of vertices which are in contact with atleast one building, let E be number of edges which are in contact with atleast one building, now if the graph of building is connected, then Euler's formula for connected planar graphs must hold (here number of faces F = number of buildings + 1). So, you can only erase a building if erasing it will maintain the equality (the graph will remain connected), call such a building available. A building is on the boundary if it is contact with one empty space. Now, maintain a set of all buildings on the boundary which are available, and erase the one with maximum id. Update the set after erasing each building. (Each update will change the status of atmost 8 buildings so this can be done fast).

I tried changing the codes, it still gives the same message.

I am not able to submit my codes. I am getting an error message saying "You have already submitted the exact code before" even when I haven't made a single submission.

Here's my solution:

The key idea I used was to think of the queries as sending $$$N$$$ $$$F$$$-bit numbers rather than $$$F$$$ $$$N$$$-bit strings. So, for example if you sent the following $$$3$$$ queries:

$$$1010$$$

$$$0100$$$

$$$1101$$$

Think of it like you are sending $$$4$$$ numbers, $$$5$$$, $$$6$$$, $$$1$$$, $$$4$$$ in that order. Here each number is represented by a vertical column, where the $$$i$$$th row determines the bit in the number $$$i$$$th from the right. So, first row corresponds to $$$2^{0}$$$, second row corresponds to $$$2^{1}$$$ and so on. Read the judge's response in the same way.

This makes the solution for $$$F = 10$$$ quite simple, as now you can send $$$N$$$ $$$F$$$-bit numbers, you just make each worker output its ID, that is, output $$$0$$$, $$$1$$$, $$$\ldots$$$, $$$1023$$$ in that order. Now, the judge will return some $$$N-B$$$ among these numbers and you just output the $$$B$$$ missing numbers as the answer.

Now, notice you haven't used $$$2$$$ details yet: 1. The numbers returned are returned in the order they were given. 2. $$$B$$$ cannot be more than $$$15$$$.

This allows us to let each worker output its ID modulo $$$16$$$ rather than the exact ID. So, your output looks like:

$$$0$$$, $$$1$$$, $$$\ldots$$$, $$$15$$$, $$$0$$$, $$$1$$$, $$$\ldots$$$

And the judge will return these numbers in the same order with atmost $$$15$$$ numbers missing. Now, notice each group of $$$0$$$, $$$1$$$, $$$\ldots$$$, $$$15$$$ contains $$$16$$$ numbers, so no group can go completely missing. So, in the returned numbers, if a number is less than or equal to the number before it, that means a we are in the next group. In this way, we can uniquely determine the ID's of the workers returned and thus output the ID's of the remaining workers. As, we output only $$$4$$$-bit numbers, we can solve this with $$$F = 4$$$.

Implementation

Yeay! My first Div 1!

This is beautiful.

This assumes separate edges are in separate triangles which need not be the case.

I don't think this proof is correct. This assumes all edges are part of separate triangles. But if there is a triangle with vertices $$$i$$$, $$$i+1$$$ and $$$i+2$$$, then two consecutive edges are accounted for in the same triangle.

Can someone check if my solution for E is correct? It's not maximum matching.

First, I find max mex for the given situation without considering updates. Here's how I do that: I go from $$$0$$$ to as far as I can go by randomly picking a club which has a member of the required potential. When I choose the $$$i$$$'th club for potential $$$j$$$, I make a directed edge from all other clubs who have a member with potential $$$j$$$ to $$$i$$$. Now, if I get stuck at some potential k, I will bfs from the unused clubs to find a club which has a member with potential $$$k$$$. Now, if the path to this club is like $$$p_{x}$$$ -> $$$p_{a_{1}}$$$ -> ... -> $$$p_{y}$$$, where $$$p_{x}$$$ is the unused club and $$$p_{y}$$$ has a member with potential $$$k$$$, I can replace $$$p_{a_{1}}$$$ with $$$p_{x}$$$, and $$$p_{a_{2}}$$$ with $$$p_{a_{1}}$$$ and so on. After this I update the edges of the graph as required. By the end, I will find the max mex for the given situation.

Now, for updates: First notice that the max mex can only decrease or remain same. Now, I maintain the reverse of the graph I mentioned above, if a member from club $$$i$$$ is chosen for potential $$$j$$$, then I make a edge from club $$$i$$$ to every other club which also has a member with potential $$$j$$$. Now, for each member which leaves, we see if we were using this member in our chosen max mex, if not, we do nothing. If yes, then we bfs from this club to either find a club which is unused right now (in which case max mex remains same) or we find a used club from which we have taken a member with the highest potential (in this case max mex becomes this new potential). In both cases we update the entire graph again as required.

Can someone check if my solution for E is correct? It's not maximum matching.

First, I find max mex for the given situation without considering updates. Here's how I do that: I go from $$$0$$$ to as far as I can go by randomly picking a club which has a member of the required potential. When I choose the $$$i$$$'th club for potential $$$j$$$, I make a directed edge from all other clubs who have a member with potential $$$j$$$ to $$$i$$$. Now, if I get stuck at some potential k, I will bfs from the unused clubs to find a club which has a member with potential $$$k$$$. Now, if the path to this club is like $$$p_{x}$$$ -> $$$p_{a_{1}}$$$ -> ... -> $$$p_{y}$$$, where $$$p_{x}$$$ is the unused club and $$$p_{y}$$$ has a member with potential $$$k$$$, I can replace $$$p_{a_{1}}$$$ with $$$p_{x}$$$, and $$$p_{a_{2}}$$$ with $$$p_{a_{1}}$$$ and so on. After this I update the edges of the graph as required. By the end, I will find the max mex for the given situation.

Now, for updates: First notice that the max mex can only decrease or remain same. Now, I maintain the reverse of the graph I mentioned above, if a member from club $$$i$$$ is chosen for potential $$$j$$$, then I make a edge from club $$$i$$$ to every other club which also has a member with potential $$$j$$$. Now, for each member which leaves, we see if we were using this member in our chosen max mex, if not, we do nothing. If yes, then we bfs from this club to either find a club which is unused right now (in which case max mex remains same) or we find a used club from which we have taken a member with the highest potential (in this case max mex becomes this new potential). In both cases we update the entire graph again as required.

Here's a nice solution for E:

Let the length of the string be n. You want to store an array change[n] storing where the ith character goes after the entire transformation.

The trick is to write all indices in base 26. Each index can be written in 3 digits in base 26 as n < 26^3. Use one query for each digit. You can encode the ith digit as,

encode(index) = (i/(26^(i-1)))%26 + 'a'

and decode as,

decode(character) = (character — 'a')*(26^(i-1))

Code: 50128214

thanks for fast editorial!

Search for rearrangement inequality. It's simple to prove, intuitive and quite useful.

Basically, it states that if ai and bi are permutations of 2 sequences of real numbers, then the sum ai*bi will be minimized when ai and bi are oppositely sorted and will be maximized when they are similarly sorted.

Intuitively, if you want to purchase some items from a store, such that you want ai objects having price pi, then to minimize the total cost, you want to buy the costliest item as less times as possible and so on. So, if prices pi are increasing, then ai must be decreasing.

I believe there is a slight correction in the proof of C. bi and ci form a corresponding grouping only if the following condition holds:

bi = cj if and only if bj = ci.

The proof still holds because each grouping can be mapped to a bi, ci and the optimal bi, ci can be mapped to a grouping.