Brazilian Sub Regionals 2015/16 Discussion

9 years ago, # |

← Rev. 5 →

+24

G — Curious Guardians

For any unrooted tree we can pick a root arbitrarily, so let's say 1 is our root. Let dp(N, K) be how many trees we can construct with N nodes other than the root and with the root having at most K children. Then the final answer we want is dp(N-1, K).

1 will have at most K subtrees as children. Let's pick the first one of them. Say it has i nodes in it. We can choose nodes to be in this subtree in $\text{[math]}$ ways, then we can pick the root of this subtree in i ways, and fill the rest of the tree in dp(i - 1, K - 1) ways. The other subtrees that are children of 1 can be picked in dp(n - i, k - 1) ways.

Maybe you realized this is actually overcounting some trees -- for example it considers 2-1-3 and 3-1-2 as distinct. If we have a problem because we are considering orders as distinct, let's force one order! Let's reorder the child subtrees of 1 so that, if you identify each subtree by its smallest node, they come in lexicographical order. This order is easy to achieve by forcing the smallest node available to go the first child subtree, which eliminates the double-counting.

Final solution:

$\text{[math]}$

→ Reply

Zailton

9 years ago, # ^ |

← Rev. 3 →

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

→ Reply

ecapia

9 years ago, # ^ |

← Rev. 4 →

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)

→ Reply

9 years ago, # ^ |

+12

The problem is equivalent to counting Prufer sequences where each of symbol appears (k-1) or less times, as the number of appearances in the Prufer code is degree — 1. So it's just counting the number of strings of length over symbols 1,2,..,n where each symbol appears k-1 or less times.

This then becomes a fairly standard string counting inclusion/exclusion principle problem, ie, Sum C(n,i)C(n-2,ik)(ik)!/(k!)^i n^(n-2-ik)(-1)^i.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Hah, I had this feeling that this problem had to have a cleaner solution, but I couldn't find it. Thanks a bunch for the pointer to Prufer sequences! :)

Edit: on trying to understand the inclusion-exclusion, are you not double-counting something? As in, the elements of the bigger than K groups and the rest are being permuted? I might need some more time to make sure but learning about these sequences was cool nonetheless.

→ Reply

9 years ago, # ^ |

← Rev. 3 →

Hi,

You are right, the formula is not quite correct, however with counting Prufer sequences, this problems simply reduces to the problem of ways of permutating n-2 elements picked from the multiset of {k*a1, k*a2,..., k*an}, where a1,..,an are the n labels. This can be solved with O(n^3) DP just like the tree problem.

A direct way of computing this though is using the simple generating function:

[ Sum over j (1<=j<=k) of (t^j / j!) ] ^ n

Let M be the coefficient of t^(n-2), then the answer is M*(n-2)! Since any time the coefficient goes over t^(n-2) in the computation, we can just drop it, we keep only O(n) terms each polynomial multiply, so the complexity of O(n log n) with FFT multiplies.

→ Reply

9 years ago, # ^ |

O(n log^2 n), in fact, because you need to do several multiplications. But while I haven't coded this (would be hard to do FFT with the modulo they used), this looks really likely to be correct.

→ Reply

9 years ago, # ^ |

I coded the FFT multiply solution, it got accepted: http://pastie.org/private/gumax8sj8m0dmwcssywvla

Why is FFT so slow u.u

→ Reply

Roberio

9 years ago, # ^ |

Constraints are small, so $\text{[math]}$ , where dp(n, m) is the number of sequences considering elements in [1, n], with length m and where elements repeat at most K - 1 times should do the job, and dp(n, n - 2) should give us the answer.

→ Reply

pimenta

9 years ago, # ^ |

This solution seems to be the simplest, but I can't understand the logic. Can you explain your math? Thanks in advance!

→ Reply

Roberio

9 years ago, # ^ |

This solution refers to baodog's observation (Prufer sequences) that all sequences of n - 2 elements in [1, n] (possibly repeated) form a bijection with the set of all spanning trees of complete graph K_n. Moreover, v appears k - 1 times in those sequences iff node v has degree k in correspondent tree.

So we can count number of valid sequences using the given DP. If we have sequences of m elements using only elements labeled in range [1, n], we can add 0 ≤ x < K elements labeled n + 1 to it so we will have a new sequence of m + x elements using elements labeled in range [1, n + 1].

We should be able to add these new x elements between any of the elements of the former sequence. It's equivalent to the problem of interpolating two strings without changing their original orders. There are $\text{[math]}$ ways to do that. From that you can derivate dp(n, m) transitions easily.

→ Reply

pin3da

9 years ago, # ^ |

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 (:

→ Reply

9 years ago, # ^ |

You're right, of course. Fixed.

→ Reply

jeferson

9 years ago, # |

Hi,

I'd like a hint to the problem A — Even Obsession.

→ Reply

9 years ago, # ^ |

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.

→ Reply

angelg

9 years ago, # |

Can someone give me a hint for Problem B — Stock Market ?

→ Reply

danft

9 years ago, # ^ |

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

→ Reply

9 years ago, # ^ |

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.

→ Reply

pelado

9 years ago, # |

Can someone give a hit about problem K: Palindrome?

→ Reply

aajjbb

9 years ago, # ^ |

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)

→ Reply

Temirulan

9 years ago, # |

← Rev. 2 →

+17

Does uva online judge support virtual contest? Or maybe someone can upload it to gyms?

→ Reply

tiagob.reis

9 years ago, # ^ |

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.

→ Reply

9 years ago, # ^ |

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).

→ Reply

9 years ago, # ^ |

I believe you should also have a working solution, at least to measure time constraints. Which I'm not able to do since I haven't gotten my Ominobox to stop giving TLEs u.u

→ Reply

victorsenam

9 years ago, # |

← Rev. 2 →

+12

Hey guys. Any tips on solving the I — Ominobox?

I guess the trouble is to discover quickly the minimum height for each n-omino.

→ Reply

victorsenam

9 years ago, # ^ |

marcoskwkm? Help?

→ Reply

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

9 years ago, # ^ |

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.

→ Reply

9 years ago, # ^ |

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);

→ Reply

victorsenam

9 years ago, # ^ |

Thanks a lot :) I was trying to do something similar but i tought the Binary search wasn't good enough for the time and the bitmasks got quite confusing. Your explanation was clarifying. Thanks.

→ Reply

9 years ago, # ^ |

← Rev. 4 →

I simply used a 1 to indicate "blocked" at that height and above, i.e.

    FOR(hh, gminh, gmaxh) REP(i,R) REP(j,C) {
      if(grid[i][j]>=hh) rows[hh][i]|=(1<<j);
    }

Once I did this, the problem became really trivial. BTW, additional optimizations I haven't had time to try and is not needed is:

1) Both vertical and horizontal bitmasks, check if polymino width > height,
if width is greater use horizontal, otherwise vertical.
2) Bound the min height/max height using a precomputed min max values for the subrectangle with same bounding box as each polymino (30^ 4 to compute).
3) In binary search skip values of heights which does not actually exists in the grid.

→ Reply

Temirulan

9 years ago, # |

How to solve D? Is it gauss?

→ Reply

9 years ago, # ^ |

Read the statement more carefully.

→ Reply

caioaao

9 years ago, # ^ |

but gauss would do as well, wouldn't it? It only has L + C equations and the problem says it's always possible to find a solution, so the number of variables is ≤ L + C ≤ 200, which is feasible with gauss elimination

→ Reply

9 years ago, # ^ |

Yes, it would. But in a time-limited contest, you don't want to miss the much easier solution because you didn't read one line, right?

→ Reply

caioaao

9 years ago, # ^ |

Depends on the contestant. Some people might find easier to copy a gaussian elimination (or, in this case, just the back substitution step) implementation than writing/debugging the simulation solution for this problem.

→ Reply

9 years ago, # ^ |

← Rev. 3 →

But some should really avoid that, specially if the gaussian elimination implementation they have is a pretty buggy one made by their coach.

→ Reply

crbonilha

9 years ago, # ^ |

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.

→ Reply

zayle

9 years ago, # |

alv-r, please give me your solution for Stock Marcket. Or a hint.

→ Reply

aajjbb

9 years ago, # ^ |

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).

→ Reply