Offtopic: It's brunoja. You can check the authors at the website: http://maratona.ime.usp.br/vagas15.html

Hi ivanilos,

I've been trying to solve this problem... Can you give more hints?

I'm confused, because the combinations of the vectors (people's numbers) can't be arbitrary linear combinations, right? The coefficients must be either 1 or 0 (the person was choose, or not).

Could you explain from the point of view of linear algebra?

Thanks in advance!

Nice solution, in the contest i used an extra parameter and my solution was a little bit more complicated.

Hello everyone , I have founded other solution simpler. Imagine we have a partial tree , if I process in order from left to right about leafts I will never have count twice any tree so we just process one by one.

Let dp(n,k) be a tree which have k leafs and we want to add n nodes in those leafs, this will compute how many tree there will be with this conditions, so the answer will be dp(n-1,1) , as I said , if a process lefts in order I will never count twice some thing. In each configuration I try to add children en the first leaf of our current tree, also exist take nothing dp(n , k) -> dp( n, k — 1)

Final solution:

dp(n , k) = comb(n , children) * dp(n — children , k — 1 + children )

0 <= children <= min( (Is first node ? k : k — 1) , n)

Hello,

I think that should be dp(i -1, K — 1) instead of dp(i, K — 1). [The rightmost recursive call]

Very nice solution, thanks (:

Make a graph in which each vertex is (city, number of tolls is even or odd).

Then Dijkstra in this new graph can solve the problem.

Use an extra parameter that says if you can buy/sell a stock.

It can be solved using DP. Each day you can either sell the stock (if you've already bought it before), buy it (if you haven't bought it already) or do nothing.

Dynamic Programming with states [left bound][right bound]. Try to build the palindrome from the borders. If both characters are equal, you can try to insert them in your current palindrome, otherwise, you have to 'discard' on of the characters. Remember that the problem asks you to minimize 2 parameters, used special positions and size, so you have to store a 'pair' as a state instead of a single digit. It is O(n^2)

Near the bottom of the page http://uhunt.felix-halim.net/id/0 there is a virtual contest generator. You can get all the problems from this subregional automatically by looking for it under the "Past Contests" list.

It wouldn't be bad if someone could just upload it to gyms, though.

Idk what you need to do to upload it to the gyms, but in case someone wants to do it, the official in/out can be found here. (It's the "Entradas e Saídas" link next to each problem).

marcoskwkm? Help?

https://en.wikipedia.org/wiki/Polyomino

I pre-computed and stored the just the "free" polyminos (<5K for 10). This became fast enough for scanning through all the polyminos at each position on the grid. However, this seem to require a bit masking trick to work fast enough, and my code is a bit slow right now. Basically there are 8 orientations with rotation+flip. We have 5 bits (<30), so that fits in a long long. So we want to do single scan for all the orientations at the same time though grid, and do a min across each starting position of max of heights of cells.

Just create a bit mask for each row of up to each 30 heights of grid, and create bit mask of each polymino. Then binary search to see if each one can be placed at a certain height. On average only <2.5 binary search passes are needed for 30 height values. Here is the code:

      bool found = false; // does polymino pattern exist.
      const auto& polym = polymask[n][pp];
      int dx = dimen[n][pp][0];
      int dy = dimen[n][pp][1];
      //cout << "here " << dx <<  " " << dy << endl;
      int minhh = gminh;
      int maxhh = gmaxh;
      REP(i, R-dx) {
        REP(j, C-dy) {
          minhh = gminh;
          maxhh = gmaxh;
          bool found = false;
          // Check if possible.
          while(minhh+1 < maxhh) {
            bool ok = true;
            int hh = (minhh+maxhh) / 2;
            REP(k, dx+1) if(polym[k] & (rows[hh][i+k]>>j)) {
              ok=false;
              break;
            }
            found = found | ok; // at some point was ok.
            if(ok) maxhh = hh;
            else minhh = hh;
          }
          if(found) break;
        }
        if(found) break;
      }
      if(found && h > maxhh) cnt += (h-maxhh);

Read the statement more carefully.

D is purely simulation. The statement is clear about the rules, specifically on this bit "it's always possible to find a row or a column where there's only one variable which its value is unknown". Therefore you should just find that variable, calculate it's value, and repeat this process.

It can be solved with dynamic programming. The states can be represented by [current index][do I have have the stock ?], in transitions you can choose to buy the stock in the current day (in case you don't own it yet) or sell it (in case you own it).

The DP is something like this:

dp(int day, bool stock) {
  /* Base case when there aren't any stocks left */
  if (day>=N) return 0;

  if (stock) res = P[day] + dp(day+1, false); /* Meaning that if you have a stock you can sell it for P[day]; and it's dp(day+1, FALSE) cause you don't have a stock anymore, because you just sold it */
  else res = -(C+P[day]) + dp(day+1, true); /* If you don't have a stock, you can buy it for C+P[day]; also dp(day+1, TRUE) because you just bought a stock */
  
  /* And you also need to take into account when you don't do anything for this day, cause that could be better */
  res = max(res, dp(day+1, stock));

  return res;
}

But (at least on uva) if you do it with recursion+memoization you'll get an Runtime Error because of stack overflow, so you gotta do it bottom-up. The following for loop uses the same idea, but without the recursion:

for (int i=N; i>=0; --i)
    for (int j=0; j<=1; ++j)
      if (i==N) dp[i][j] = 0;
      else {
         dp[i][j] = (j ? P[i]+dp[i+1][0] : -(C+P[i])+dp[i+1][1]);
         dp[i][j] = max(dp[i][j], dp[i+1][j]);
      }