pabloskimg's blog

Fygon 2.0 (NEERC 2017-2018) — Need help understanding Russian tutorial
By pabloskimg, history, 4 years ago, In English

I was trying to solve problem Fygon 2.0 from ICPC 2017–2018, NEERC, Northern Subregional Contest, but I couldn't come up with a solution, so I decided to check out this tutorial. Unfortunately, the tutorial is in Russian and the explanation is quite short and is probably omitting a lot of details. Using google translate I managed to understand that we should build a DAG where nodes represent the variables in the nested for loops and the edges represent inequalities between variables, but I don't understand how you can compute $$$C$$$ and $$$k$$$ from that. Any help is appreciated. Thanks in advance.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Each edge in a DAG represents some inequality $$$v_i \le v_j$$$. When $$$n$$$ reaches infinity, we may assume that all values of for-loop variables are distinct (the number of lags when some variables are equal is insignificant).

Let's sort them in increasing order. If the order we get contradicts some of the inequalities, then the order is bad, otherwise, it is good. It is hard to prove without some complex calculus, but the trick is that when $$$n \to \infty$$$, we can estimate the ratio of the number of lags we get to the total possible number of lags (the number we would get when all ranges are from $$$1$$$ to $$$n$$$) as the ratio of the number of good orderings to the number of all $$$m!$$$ orderings.

Now we want to compute the number of good orderings — and it is the number of topological sortings of the graph we have built, so we can run a dynamic programming: $$$dp_{mask}$$$ is the number of valid orderings of some $$$mask$$$ of variables.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Update: the graph is not always a DAG, so sometimes you have to run SCC detection and compress each SCC into a single vertex.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. Is this a well-known theorem? Can I read the proof somewhere?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Unfortunately, I don't know it.

      If I had to prove the following:

      Spoiler

      I think I would start with something like "suppose we know that the values of our variables in sorted order are $$$a_1$$$, $$$a_2$$$, ..., $$$a_m$$$, but we don't know which variable corresponds to which value. There are $$$m!$$$ assignments in total, but the only valid ones are the assignments where each inequality is met — so, the number of valid ways to assign values is exactly the number of topological sortings. So, for the most sets of values, $$$\frac{T}{m!}$$$ ways are valid, where $$$T$$$ is the number of topological sortings".

      → Reply