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

We can do 1922B - Forming Triangles without binomial coefficient. 242267553 We can assume that the three sides chosen by us are (2^x,2^(x+d1),2^(x+d1+d2)) d1, d2 ≥ 0. Our triangle must meet these conditions 2^x + 2^(x+d1) > 2^(x+d1+d2). In the other way, sum of two minimum must be greater than maximum one.

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 < 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 < 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} > 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) < 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?

Wow, problem E is so creative, revolutionary and original — learned a lot about bitwise operation from that one!!!!! What inspired you to create such a ground-breaking, intuitive and simply perfect problem???.?!!!!!!

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

In problem E, it is written that : If we add a new maximum to the end of the array, the number of increasing subsequences in the new array equals 2x (since the new element forms increasing subsequences with any other elements).

I think this is not well explained. In fact, if we have x increasing sequences, there are x-1 non-empty sequences and 1 empty sequence. When we add a new maximum, there will be x new non-empty increasing sequences (x-1 from the previous sequences and 1 sequence composed only of the new element). if we count again the empty sequence, the total will be (x-1) + x + 1 = 2x.

I'm getting Memory Limit Exceeded in test 5 of Problem E, why is it so?

can anyone help me with the claim that when only the particular element is dead the suitable candidates would be its Neighbours ? in problem D

BledDest The editorial solution for D problem is a little bit wrong in the case where our i in cur is equal to 0 then the nxt and prev values give us the garbage value this is working because of the summation of the garbage values is always less than INT_MAX, but if we use long long vector to store the attack and defense value than the garbage value given will also be long long which will exceed the INT_MAX value so then it will give wrong answer. sorry for my bad English.

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?

I shouldn't be able to understand problem F solution, why am I? :-)

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

Hello everyone, I am having some trouble with problem F. I solved it with the help of the code from Dominater069.

From what I understood. He did and I copied something like:

1. Break dp2 subproblems and calculate (OK)
2. Break dp subproblems and calculate (OK)
3. dp[i][j][k] can be formed by 1 extra step after dp2[i][j][k]
4. dp2[i][j][x] can be formed by any k other than x and we need the minimum one

Now the part where the part 3 and part 4 just relies on each other I want a closure of why this is not in recursion or recurance. I tried solving it like Bellmanford where if the weights stop relaxing we stop the algorithm between step 3 and 4 and it will work but it doesn't even matter. I', interested in the doesn't matter part. Can someone prove it.

Thank you for reading my comment and special thanks if you can shed some light on it. Thanks everyone.

The second question was very nice problem!!

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

I use ideone.com for writing my code .I dont know how my code matches to others .Requesting you to not block my id

Is there an issue with codeforces's compiler ? I used unordered_map and ordered map in B and got different results whereas got same results with COdechef's ide