If using a double linked list to implement 1922D, we can get a solution of O(n) time.

In problem E we could also construct an increasing sequence 1, 2, 3, ..., N. We could easily see that it has S = 2^N increasing subsequences (including the empty one).

If S*2 equals X, we just need to add N+1 at the end, else we need to add some values to get X-S more increasing subsequences.

Notice that if we add a value 1 <= v <= N to the end of the sequence, we would get 2^(v-1) more increasing subsequences, so we just need to check each bit from MSB to LSB.

Submission: 242459743

For problem B, I got accepted in the contest, but then I woke up this morning and got Time Limit Exceeded on Test case 6? I'm so confused why did this happen. I was supposed to hit expert.

Problem F can also be solved in $$$O((n^3 \cdot x)/64))$$$ using bitsets: link

Note that since $$$x$$$ is at most $$$100$$$, we can simply use 128 bit integers instead of bitsets for an even better constant factor.

I'm very confused by the editorial for E, so I feel like sharing my own (AC) approach:

First, observe that a strictly increasing array with $$$k$$$ elements will have $$$2^k$$$ increasing subsequences (including the empty subsequence), the elements to be removed can be any subset of all the elements. So for input $$$n$$$, we can find the largest power of 2 which is $$$\leq n$$$, e.g., for integer $$$p$$$ such that $$$2^p \leq n \lt 2^{p + 1}$$$, we can form an increasing array of $$$p$$$ elements to create $$$2^p$$$ subsequences (including the empty subsequence).

But what about the remaining $$$n - 2^p$$$ subsequences? Let's say the largest power of 2 you can fit in the remaining value is $$$2^q$$$, i.e., $$$2^q \leq n - 2^p \lt 2^{q + 1}$$$. Initially, I considered creating a separate subarray of $$$q$$$ elements, but having to do this with every power in the worst-case (e.g., if $$$n = 2^{59} - 1$$$) would exceed the 200-length limit (and we also have to avoid double-counting the empty subsequences).

Instead, however, we can generate $$$2^q$$$ new increasing subsequences by adding only one element to the end of the array: an element which is greater than the first $$$q$$$ elements of the original sequence (of $$$p$$$ elements) but smaller than the rest. The new subsequences generated involve the new element with any subset of the first $$$q$$$ elements, resulting in $$$2^q$$$ new subsequences (there are no empty subsequences here, since the new element is always included in these new subsequences).

This leads to the following algorithm: for the highest power $$$p$$$ of 2 that fits (i.e., leftmost 1 bit), prepare $$$p$$$ elements in strictly increasing order. This is the primary reference sequence. Then for the next power $$$q$$$ of 2 that fits, e.g., we simply add one extra element to the end whose value is between the $$$q$$$-th and the $$$(q + 1)$$$-th element of the primary reference sequence. Repeat for each power of $$$q$$$ that fits from the remnants of the previous step.

My submission: 242314370. The variable prm denotes $$$p$$$, the length of the primary sequence. I used multiples of 1000 for the primary sequence. Some of the code details overcomplicated this by considering when we might have multiple instances of the same $$$q$$$ value, but this is unnecessary with clear-headed hindsight, since we're basically just going through all the 1-bits in the binary representation from left to right. The __builtin_clz(n) function (count leading 0s) would likely have improved this, to quickly find the leftmost 1-bit each time.

My submission to E 242474581. I got long long overflow when I had (1ll<<i) for calculating power of 2s (Specifically at i=59). However, it did not overflow when I calculated poweroftwos by arithmetic (as in submission, the dp array).

Any suggestions why there was an overflow for (1<<i) case? 242470568

We can think of Problem-B in another way, we can assume that the three sides chosen by us are $$$(2^x, 2^{x+d_1}, 2^{x+d_1 + d_2})$$$ where $$$d_1, d_2 \geq 0$$$.

As mentioned in editorial in order to make a degenerate triangle we want $$$2^x + 2^{x + d_1} \gt 2^{x +d_1 + d_2}$$$ (Sum of two minimum is greater than maximum).

After simplfying above inequality we get $$$2^{d_1} \cdot (2^{d_2} - 1) \lt 1$$$, which is only possible when $$$d_2 = 0$$$, thus for each $$$a_i$$$ we just want to find out the number of $$$a_i's$$$ after it. As for the first side length i.e., $$$2^{x}$$$ it doesn't matter what we choose so our final answer is just $$$\sum_{i = 0}^{N - 1} i \cdot \text{count of}\ a_i\ \text{in range i + 1 to n - 1}$$$. (Note 0-indexing)

Here is my submission.

why this code give wrong answer forn D question 242491110

Can anyone please explain how tester of E could have been written so that it checks the answer in polynomial time? I can't think of one.

I feel like my D should get hacked. Can someone try? submission

why is my code for problem D 242468805 getting a time limit exceeded signal ? shouldn't it be faster than this approach using sets?

For F, I feel like we don't need to precompute that much to eliminate cyclic dependencies. Instead, we consider two cases:

1. ifa[l]==k: we calculatedp1[l][r][k]fromdp1[l+1][r][k] first, then calculatedp2[l][r][kk]fromdp1[l][r][k], where k!=kk.
2. ifa[l]!=k: we calculatedp2[l][r][k]fromdp2[l+1][r][k] first, then calculatedp1[l][r][k]fromdp2[l][r][k].

vector<vector<vector<int>>> dp1(n, vector<vector<int>>(n, vector<int>(m, INF)));
vector<vector<vector<int>>> dp2(n, vector<vector<int>>(n, vector<int>(m, INF)));
for (int len = 1; len <= n; len++) {
  for (int l = 0; l + len - 1 < n; l++) {
    int r = l + len - 1;
    for (int k = 0; k < m; k++) {
      if (len == 1) {
        dp1[l][r][k] = (int) (a[r] != k);
        dp2[l][r][k] = (int) (a[r] == k);
        continue;
      }
      for (int i = l; i < r; i++) {
        dp2[l][r][k] = min(dp2[l][r][k], dp2[l][i][k] + dp2[i + 1][r][k]);
      }
      for (int i = l; i < r; i++) {
        dp1[l][r][k] = min(dp1[l][r][k], dp1[l][i][k] + dp1[i + 1][r][k]);
      }
      // here are the two cases.
      if (a[l] == k) {
        dp1[l][r][k] = min(dp1[l][r][k], dp1[l + 1][r][k]);
        for (int kk = 0; kk < m; kk++) {
          if (k != kk) {
            dp2[l][r][kk] = min(dp2[l][r][kk], dp1[l][r][k]);
          }
        }
      } else {
        dp2[l][r][k] = min(dp2[l][r][k], dp2[l + 1][r][k]);
        dp1[l][r][k] = min(dp1[l][r][k], dp2[l][r][k] + 1);
      }
    }
  }
}

In the solution to D, what does prev(it) return in case "it" is the iterator pointing to the first element in the set?

can someone explain problem D. I don't understand why the problem setter's claim is valid.

Hey, could someone explain how removeing cyclic dependencies in problem F works. Is there a general approche or can we only do this for this spezific problem. Thanks!

Can somebody explain why my solution is getting TLE'D on test 15 for problem D 242631259

How elegant is the solution is for E . I feel I am so dumb :)

It was already mentioned, sorry.

Why somebody solve F so quickly?

can enyone help me with this problem? I am tring to solve it using Hash in c++ but can't

https://mirror.codeforces.com/contest/271/submission/243292259

Surprised that the editorial lists an $$$O(n^4)$$$ for problem F, when it can be done in $$$O(n^3)$$$, also surprised that no one has mentioned it in the comments.

243829676

for D: why if the neighbors of $$$i$$$-th monster are alive we don't have to check the $$$i$$$-th in the next round? Isn't it possible that the neighbors to kill it in the next round? UPD: I thought the defense (d) is being decreased each round