The round was written by IH19980412. A draft of the editorial can be found here.

Thanks for the nice problemset!

I liked Div1 Hard that inclusion-exclusion principle works elegantly. Using De Bruijn Sequence, we can improve the solution to $$$O(2^N + HW)$$$, which is faster than naive $$$O(2^N \times N + HW)$$$.

Alternative solution for Hard: go through the table from top to bottom and maintain dp with state being a vector of degrees of all special cells. It works in $$$nm4^k$$$, but we can optimise it: if we are now in row $$$i$$$, we only need to know about cells in rows $$$i-1, i, i + 1$$$. It still works slow if there are a lot of special cells in three adjacent rows, but in that case there will not be a lot of special cells in any three adjacent columns, so let's just transpose the table.

My solution for Div1 Hard: Consider the neighbors of the undetermined cells. Intuitively it appears that there can't be many undetermined cells with more than one special neighbors (can't provide the maximum number, but the worst test case I came up with had 25 such cells). Thus, we can iterate over all of the combinations for choosing a state for those cells, and calculate the number of ways with respect to the other undetermined cells in $$$O(2^K*S)$$$, where $$$K$$$ is the number of undetermined cells with more than one special neighbors, and $$$S$$$ is the number of special cells. The complexity may be worse than the intended solution, but it avoids using the inclusion-exclusion principle.

Hi Everyone, I am certainly missing something very obvious for problem NewBanknote. My idea is, add the new currency to given denomination and sort them. For any given value, I try all the currencies recursively and take minimum out of it. My solution is failing for some values with off by one which I believe tailored for this problem. I am not looking for solution, but a hint that what is wrong with my thinking. A small test case would be great.

    int recurVal(map<int, int> &mp, vector<int> &curr, int val)
    {
      if (mp.find(val) != mp.end()) return mp[val];
      if (val ==  0) return 0;
      
      vector<int> ret;
      for(int i = 0; i < curr.size(); i++)
      {
          if (curr[i] > val) continue;
          div_t divresult = div(val, curr[i]);
          ret.push_back(divresult.quot + recurVal(mp, curr, divresult.rem));
      }   
      
      mp[val] = *min_element(ret.begin(), ret.end());
      return mp[val];
    } 
    
    
 
    vector<int> fewestPieces(int newBanknote, vector<int> amountsToPay) {
        vector<int> curr{1, 2, 5, 10, 20, 50, 100, 200,  500, 1000, 2000, 5000, 
                         10000, 20000, 50000};
        curr.push_back(newBanknote);
        sort(curr.begin(), curr.end());
        int n = curr.size();
        map<int, int> mp;
        mp.insert(make_pair(0, 0));
        for (int i = 0 ; i < n; i++)
          mp.insert(make_pair(curr[i], 1));

        //for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++)
          //cout << it->first << " " <<it->second <<endl;

        vector<int> ret;
        for(int i = 0; i < amountsToPay.size(); i++)
        {
          ret.push_back(recurVal(mp, curr, amountsToPay[i]));
        }

        return ret;
    }

For a while already, I've wondered about the problem which appeared as Div1 Medium in this round:

We are given a sequence. Can it be split into two equal subsequences?

In the round, the size was only up to 40, which allowed for multiple exponential solutions. The question is, is it solvable in polynomial time? It certainly is when we know the subsequence to search for. So far,

• I don't see a polynomial solution,
• I don't see a reduction of some classic hard problem to this one, and
• I can't find any sources online which discuss the problem.

The problem statement is so short that one would think it had been studied decades ago, with some definite result. I'll be grateful if someone sheds some light on the matter.